EMBER_CLI_FASTBOOT_BODY

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

Теоретическая информатика — раздел математики, связанный с логикой, алгоритмами, сложностью: там много несложных, но важных результатов, о некоторых мы попробуем рассказать. В этом курсе мы расскажем про общую теорию вычислимости (что в принципе могут делать алгоритмы --- если отвлечься от практических ограничений, а что не могут)

Certificate Stepik

About this course

Слова «теоретическая информатика», а особенно их английский вариант (“theoretical computer science”), звучат странно — как «сухое плавание». Но в них есть смысл, причём не только для теоретиков: абстрактные конструкции и математические результаты, если они хорошо поняты, в нужный момент могут натолкнуть на решение вполне практической задачи.

Мы попытались отобрать простые и одновременно важные понятия и результаты, которые могут вам пригодиться. Некоторые из них совсем практические (скажем, инварианты циклов, коды с исправлением ошибок или криптографические протоколы), другие скорее указывают границы возможностей (скажем, результаты об алгоритмической неразрешимости или NP-полноте). Разделы достаточно независимы, так что если что-то не понравилось или показалось непонятным, можно идти дальше.

По большей части мы не используем сложной математики (а базовые результаты про целые числа мы напоминаем) и каких-то конкретных программистских навыков, но, конечно, некоторая математическая грамотность и программистский опыт не повредят.

Наконец, заранее просим прощения, если курс покажется вам неудачным — рассказывать что-то, не видя реакции, всегда трудно, и это скорее первый блин, чем результат многолетней практики.

Who is this course for

студенты младших курсов

Meet the Instructors

User picture
Александр Шень
ЦССМШ -- Вторая школа -- мехмат МГУ -- аспирантура кафедры логики (В.А.Успенский) -- ИППИ РАН, LIF Marseille, LIRMM Montpellier (CNRS)
www.lirmm.fr/~ashen

Course content

Приглашение
  1. Теоретическая информатика и теория вычислимости
Вычислимость
Программы и универсальные функции
Машины Тьюринга
Конвей и FRACTRAN
Ассоциативные исчисления

Certificate

Computer Science центр

Share this course