Теоретическая информатика: вычислимость

Курс «Теоретическая информатика: вычислимость» на платформе Stepik расскажет вам об алгоритмах и их возможностях в программировании.

Вы узнаете о машинах Тьюринга, ассоциативных исчислениях, программах и некоторых функциях.

Вам подойдет этот курс, если вы:

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

Ключевые навыки, которые вы освоите на этом курсе:

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

Учебная программа:

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

По окончании обучения выдается сертификат от Computer Science Center.