course language
course duration
for credit at your university
Эдсгеру Дейкстре приписывают высказывание: «наука о вычислимости изучает компьютеры не в большей мере, чем астрономия изучает телескопы». Смысл этой фразы в том, что конкретный компьютер или конкретный язык программирования – только инструмент познания общих закономерностей, справедливых для всех вычислений. Основы этой науки заложены Тьюрингом, Гёделем, Чёрчем, Клини, Постом и другими математиками в 1930-х годах, когда вычислительных машин в современном понимании ещё не было. При этом базовые предположения в полной мере выполняются для современных компьютеров и, наверняка, будут верны для всех будущих, в том числе квантовых.
Основное достижение теории вычислимости заключается в существование задач, которые в принципе нельзя решить компьютерной программой. Более того, подобные задачи возникают в алгебре, комбинаторике слов и других разделах математики, с теорией вычислимости напрямую не связанных.
Теория вычислимости тесно переплетается и с математической логикой, особенно с логикой доказательств. Ещё Лейбниц предполагал, что любое рассуждение можно в конечном счёте заменить вычислением. Знаменитая теорема Гёделя о неполноте арифметики в некотором смысле делает невозможным реализацию идеи Лейбница. Теория вычислимости высвечивает глубинные причины этого явления.
В курс также включены два раздела, более близкие к практике. Первый – это лямбда-исчисление, альтернативный способ формализации, что такое программа. Эта наука закладывает основы функционального программирования. Второй – это теория сложности вычислений. На практике неважно, даст ли программа ответ в принципе. Важно, даст ли она его за приемлемое время. В этой теории возникает одна из ключевых открытых проблем современности: равны ли классы P и NP.
Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 3600 рублей.
Каждую неделю вас ждут видеолекции и проверочные задания, которые нужно выполнять в срок.
В конце – итоговая проверочная работа. Студенты, которые набрали достаточное количество баллов, смогут получить сертификат.
Все необходимые понятия будут определяться по ходу курса, однако от слушателей предполагается достаточно свободное владение аппаратом дискретной математики и булевой логики. Желателен хотя бы небольшой опыт написания программ.
course language
course duration
for credit at your university
Кандидат физико-математических наук
Position: Преподаватель кафедры дискретной математики МФТИ
A participant certificate is usually issued upon reaching 60 % of the overall rating, subject to the delivery of works before a hard deadline. The honors certificate is usually issued upon reaching 90 % of the overall rating, subject to the delivery of the work before the soft deadline.