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