Введение в теоретическую информатику

Теоретическая информатика — раздел математики, связанный с логикой, алгоритмами, сложностью. 

Введение в теоретическую информатику
Бесплатно
86 уроков86 уроков
Сертификат гос. образцаСертификат гос. образца
РусскийРусский
Stepik

Описание:

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

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

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

  1. Отгадывание числа: верхние и нижние оценки
  2. Отгадывание с ошибками
  3. Поиск максимума
  4. Сортировка: примеры
  5. Сортировка: верхние и нижние оценки для n
  6. Ещё несколько задач