Введение в теоретическую информатику
Теоретическая информатика — раздел математики, связанный с логикой, алгоритмами, сложностью.
Описание:
Слова «теоретическая информатика», а особенно их английский вариант (“theoretical computer science”), звучат странно — как «сухое плавание». Но в них есть смысл, причём не только для теоретиков: абстрактные конструкции и математические результаты, если они хорошо поняты, в нужный момент могут натолкнуть на решение вполне практической задачи.
Мы попытались отобрать простые и одновременно важные понятия и результаты, которые могут вам пригодиться. Некоторые из них совсем практические (скажем, инварианты циклов, коды с исправлением ошибок или криптографические протоколы), другие скорее указывают границы возможностей (скажем, результаты об алгоритмической неразрешимости или NP-полноте). Разделы достаточно независимы, так что если что-то не понравилось или показалось непонятным, можно идти дальше.
Программа курса:
- Отгадывание числа: верхние и нижние оценки
- Отгадывание с ошибками
- Поиск максимума
- Сортировка: примеры
- Сортировка: верхние и нижние оценки для n
- Ещё несколько задач