наверх
  • 14 недель

    длительность курса

  • 3 зачётных единицы

    для зачета в своем вузе

Эдсгеру Дейкстре приписывают высказывание: «наука о вычислимости изучает компьютеры не в большей мере, чем астрономия изучает телескопы». Смысл этой фразы в том, что конкретный компьютер или конкретный язык программирования – только инструмент познания общих закономерностей, справедливых для всех вычислений. Основы этой науки заложены Тьюрингом, Гёделем, Чёрчем, Клини, Постом и другими математиками в 1930-х годах, когда вычислительных машин в современном понимании ещё не было. При этом базовые предположения в полной мере выполняются для современных компьютеров и, наверняка, будут верны для всех будущих, в том числе квантовых.

О курсе

Основное достижение теории вычислимости заключается в существование задач, которые в принципе нельзя решить компьютерной программой. Более того, подобные задачи возникают в алгебре, комбинаторике слов и других разделах математики, с теорией вычислимости напрямую не связанных.

Теория вычислимости тесно переплетается и с математической логикой, особенно с логикой доказательств. Ещё Лейбниц предполагал, что любое рассуждение можно в конечном счёте заменить вычислением. Знаменитая теорема Гёделя о неполноте арифметики в некотором смысле делает невозможным реализацию идеи Лейбница. Теория вычислимости высвечивает глубинные причины этого явления.

В курс также включены два раздела, более близкие к практике. Первый – это лямбда-исчисление, альтернативный способ формализации, что такое программа. Эта наука закладывает основы функционального программирования. Второй – это теория сложности вычислений. На практике неважно, даст ли программа ответ в принципе. Важно, даст ли она его за приемлемое время. В этой теории возникает одна из ключевых открытых проблем современности: равны ли классы P и NP.

Формат

Каждую неделю вас ждут видеолекции и проверочные задания, которые нужно выполнять в срок.

В конце – итоговая проверочная работа. Студенты, которые набрали достаточное количество баллов, смогут получить сертификат.

  • Н.К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов, часть 1, Начала теории множеств. – М.: МЦНМО, 2012.
  • Н.К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов, часть 2, Языки и исчисления. – М.: МЦНМО, 2012.
  • Н.К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов, часть 3, Вычислимые функции. – М.: МЦНМО, 2012.
  • Х.Барендрегт, Ламбда-исчисление, его синтаксис и семантика. – М.: Мир, 1985
  • С.А. Абрамов, Лекции по сложности алгоритмов. – М.: МЦНМО, 2009

Требования

Все необходимые понятия будут определяться по ходу курса, однако от слушателей предполагается достаточно свободное владение аппаратом дискретной математики и булевой логики. Желателен хотя бы небольшой опыт написания программ.

Программа курса

  1. Множества и их мощности. Счётные и несчётные множества. Диагональный метод Кантора.
  2. Абстрактное понятие алгоритма. Машины Тьюринга. Счётность множества всех алгоритмов.
  3. Вычислимые функции. Разрешимые и перечислимые множества. Существование невычислимых функций и неразрешимых множеств из соображений мощности.
  4. Неразрешимость проблем самоприменимости и остановки. Теорема Успенского-Райса.
  5. Понятие m-сводимости. Построение неперечислимого множества, дополнение к которому также неперечислимо.
  6. Алгоритмически неразрешимые задачи в комбинаторике и алгебре.
  7. Теорема Клини о неподвижной точке. Существование в любом языке программирования программы, печатающей собственный текст.
  8. Понятие формальной системы доказательств. Аксиомы формальной арифметики.
  9. Теорема Гёделя о неполноте. Существование принципиально непознаваемой программы.
  10. Лямбда-исчисление: синтаксис, приведение к нормальной форме, нумералы Чёрча, реализация простейших функций.
  11. Лямбда-исчисление: комбинатор неподвижной точки и рекурсивное программирование.
  12. Основы теории сложности вычислений: измерение времени работы программы. Классы P и NP. Проблема перебора (равны ли классы P и NP). NP-полные задачи.

Результаты обучения

  • знать фундаментальные результаты теории вычислимых функций: существование функций, невычислимых на компьютере, примеры алгоритмически неразрешимых задач, существование программы, печатающей свой текст, существование истинных, но недоказуемых утверждений, существование программы, про которую ничего нельзя доказать;
  • уметь аргументировать неразрешимость алгоритмической проблемы, строить комбинаторы, реализующие различные функции в лямбда-исчислении;
  • владеть основными приёмами доказательства неразрешимости математических проблем.

Направления подготовки

05.00.00 Науки о земле
07.00.00 Архитектура
08.00.00 Техника и технологии строительства
09.00.00 Информатика и вычислительная техника
10.00.00 Информационная безопасность
11.00.00 Электроника, радиотехника и системы связи
12.00.00 Фотоника, приборостроение, оптические и биотехнические системы и технологии
13.00.00 Электро- и теплоэнергетика
14.00.00 Ядерная энергетика и технологии
15.00.00 Машиностроение
16.00.00 Физико-технические науки и технологии
17.00.00 Оружие и системы вооружения
18.00.00 Химические технологии
19.00.00 Промышленная экология и биотехнологии
20.00.00 Техносферная безопасность и природообустройство
21.00.00 Прикладная геология, горное дело, нефтегазовое дело и геодезия
22.00.00 Технологии материалов
23.00.00 Техника и технологии наземного транспорта
24.00.00 Авиационная и ракетно-космическая техника
25.00.00 Аэронавигация и эксплуатация авиационной и ракетно-космической техники
26.00.00 Техника и технологии кораблестроения и водного транспорта
27.00.00 Управление в технических системах
28.00.00 Нанотехнологии и наноматериалы
29.00.00 Технологии легкой промышленности

Мусатов Даниил Владимирович

Кандидат физико-математических наук
Должность: Преподаватель кафедры дискретной математики МФТИ

Похожие курсы