EMBER_CLI_FASTBOOT_BODY

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

The course meets the formal recommendations of Stepik
Video Player is loading.
Current Time 0:00
/
Duration 0:00
Loaded: 0%
Progress: 0%
Stream Type LIVE
Remaining Time -0:00
 
1x
Play
To watch this video please visit https://stepik.org/lesson//step/

About the course

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

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

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

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

Instructors

  1. User picture
    Александр Шень
    ЦССМШ -- Вторая школа -- мехмат МГУ -- аспирантура кафедры логики (В.А.Успенский) -- ИППИ РАН, LIF Marseille, LIRMM Montpellier (CNRS)
    www.lirmm.fr/~ashen
Video Player is loading.
Current Time 0:00
/
Duration 0:00
Loaded: 0%
Progress: 0%
Stream Type LIVE
Remaining Time -0:00
 
1x
Play
To watch this video please visit https://stepik.org/lesson//step/

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

Expected time to complete:
12 hours
Language:
Русский
Certificate:
Computer Science центр
Certificate details
Certificate condition: 76 points
With distinction: 102 points

About the course

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

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

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

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

Target audience

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

This course is entirely free. All content is available now.