Stepik Введение в теоретическую информатику
О курсе
Подробнее
Слова «теоретическая информатика», а особенно их английский вариант (“theoretical computer science”), звучат странно — как «сухое плавание». Но в них есть смысл, причём не только для теоретиков: абстрактные конструкции и математические результаты, если они хорошо поняты, в нужный момент могут натолкнуть на решение вполне практической задачи.Мы попытались отобрать простые и одновременно важные понятия и результаты, которые могут вам пригодиться. Некоторые из них совсем практические (скажем, инварианты циклов, коды с исправлением ошибок или криптографические протоколы), другие скорее указывают границы возможностей (скажем, результаты об алгоритмической неразрешимости или NP-полноте). Разделы достаточно независимы, так что если что-то не понравилось или показалось непонятным, можно идти дальше.По большей части мы не используем сложной математики (а базовые результаты про целые числа мы напоминаем) и каких-то конкретных программистских навыков, но, конечно, некоторая математическая грамотность и программистский опыт не повредят.Наконец, заранее просим прощения, если курс покажется вам неудачным — рассказывать что-то, не видя реакции, всегда трудно, и это скорее первый блин, чем результат многолетней практики.
Требования
Что нужно для старта
- По большей части мы не используем сложной математики (а базовые результаты про целые числа мы напоминаем) и каких-то конкретных программистских навыков, но, конечно, некоторая математическая грамотность и программистский опыт не повредят.
Аудитория
Для кого этот курс
- студенты младших курсов
Содержание
18 занятийПрограмма курса
№ТемаЧто внутри
01Разрешающие деревья
- Отгадывание числа: верхние и нижние оценки
- Отгадывание с ошибками
- Поиск максимума
- Сортировка: примеры
- Сортировка: верхние и нижние оценки для n
- Ещё несколько задач
02Схемы из функциональных элементов
- Связки, функциональные элементы, ДНФ и КНФ, полнота
- Оценки сложности. Сумма, сравнение
- Оценки сложности произвольных функций
03Пропозициональная логика
- Формулы. Следование. Тавтологии. Выполнимость
- Следование и выводимость
- Исчисление резолюций и его полнота
- Поиск вывода или контрпримера
- Нижние оценки на поиск вывода
04Вычислимость
- Вычислимость, разрешимость, перечислимость
- Свойства перечислимых множеств, теорема Поста
- Графики, проекции
- Проблема остановки: перечислимое неразрешимое множество
- Вычислимые действительные числа
05Программы и универсальные функции
- Интерпретаторы, программы, универсальные функции
- Гёделевы универсальные функции
- Св-ва гёделевых универсальных ф-й. Теорема Райса–Успенского
- У любой функции бесконечно много программ
- Отступление: перечислимые неотделимые множества
- Теорема о неподвижной точке и её следствия
- Доказательства теоремы о неподвижной точке
- Самоприменимость, парадокс лжеца, теорема Гёделя
- λ-исчисление
06Машины Тьюринга
- Мотивировка и примеры
- Формальное определение
- Модификации и их последствия
- Оценки времени работы
- Тезис Чёрча–Тьюринга
07Ассоциативные исчисления
- Определение и примеры
- Неразрешимость проблемы эквивалентности
08Переборные задачи и их сложность
- Переборные задачи
- Полиномиальные задачи
- Неразрешимые задачи
- Примеры переборных задач
- Сравнение сложности: сведение
- Переборные задачи вокруг нас
- NP-полные задачи
- Задача 3-CNF NP-полна
- Задача о независимом множестве NP-полна
- Задача о 3-раскраске NP-полна
- Задачи поиска сводятся к задачам проверки
09Ускорение перебора
- Чего мы хотим
- Задача о раскраске графа
- Задачи 2-SAT и 3-SAT
10Конечные автоматы
- Примеры
- Формальное определение. Автоматные множества
- Недетерминизм и его устранение
- Теорема Клини
- Минимальный автомат
11Контекстно-свободные языки
- Правильные скобочные структуры
- Два типа скобок: алгоритм и грамматика
- Однозначный разбор выражений
- Контекстно-свободные грамматики и их использование
12Игры
- Игры, стратегии, кванторы
- Выигрышные и проигрышные позиции. Доказательство теоремы Цермело
13Коды
- Код с исправлением ошибок
- Верхние и нижние оценки для числа кодовых слов
- Код Хемминга
14Коммуникационная сложность
- Постановка задачи. Пример: проверка равенства.
- Пространство вариантов и комбинаторные прямоугольники
- Вероятностная проверка равенства
- Уменьшение вероятности ошибки
- Ещё о проверке равенства: многочлены и коды
- Математическое отступление: (1 - 1/n)^n < 1/2 (три способа)
15Ликбез по арифметике: числа, остатки, алгоритм Евклида
- Арифметика остатков
- Свойства операций, обратимые элементы
- Алгоритм Евклида
- Алгоритм Евклида: время работы
- Разложение на простые: существование и единственность
- Малая теорема Ферма. Теорема Эйлера
- Китайская теорема об остатках
- Проверка простоты по Миллеру и Рабину
16Криптография
- Секретный ключ: можно ли без него обойтись?
- Схема Диффи–Хеллмана
- Система RSA
17Интерактивные доказательства
- Требования к доказательствам: неинтерактивные соответствуют NP
- Интерактивные док-ва: интерактивное док-во для неизоморфизма
- Доказательства с нулевым разглашением
18Правила Хоара
- Инвариант цикла: примеры
- Быстрое возведение в степень
- Математики и программисты
01Разрешающие деревья
- Отгадывание числа: верхние и нижние оценки
- Отгадывание с ошибками
- Поиск максимума
- Сортировка: примеры
- Сортировка: верхние и нижние оценки для n
- Ещё несколько задач
02Схемы из функциональных элементов
- Связки, функциональные элементы, ДНФ и КНФ, полнота
- Оценки сложности. Сумма, сравнение
- Оценки сложности произвольных функций
03Пропозициональная логика
- Формулы. Следование. Тавтологии. Выполнимость
- Следование и выводимость
- Исчисление резолюций и его полнота
- Поиск вывода или контрпримера
- Нижние оценки на поиск вывода
04Вычислимость
- Вычислимость, разрешимость, перечислимость
- Свойства перечислимых множеств, теорема Поста
- Графики, проекции
- Проблема остановки: перечислимое неразрешимое множество
- Вычислимые действительные числа
05Программы и универсальные функции
- Интерпретаторы, программы, универсальные функции
- Гёделевы универсальные функции
- Св-ва гёделевых универсальных ф-й. Теорема Райса–Успенского
- У любой функции бесконечно много программ
- Отступление: перечислимые неотделимые множества
- Теорема о неподвижной точке и её следствия
- Доказательства теоремы о неподвижной точке
- Самоприменимость, парадокс лжеца, теорема Гёделя
- λ-исчисление
06Машины Тьюринга
- Мотивировка и примеры
- Формальное определение
- Модификации и их последствия
- Оценки времени работы
- Тезис Чёрча–Тьюринга
07Ассоциативные исчисления
- Определение и примеры
- Неразрешимость проблемы эквивалентности
08Переборные задачи и их сложность
- Переборные задачи
- Полиномиальные задачи
- Неразрешимые задачи
- Примеры переборных задач
- Сравнение сложности: сведение
- Переборные задачи вокруг нас
- NP-полные задачи
- Задача 3-CNF NP-полна
- Задача о независимом множестве NP-полна
- Задача о 3-раскраске NP-полна
- Задачи поиска сводятся к задачам проверки
09Ускорение перебора
- Чего мы хотим
- Задача о раскраске графа
- Задачи 2-SAT и 3-SAT
10Конечные автоматы
- Примеры
- Формальное определение. Автоматные множества
- Недетерминизм и его устранение
- Теорема Клини
- Минимальный автомат
11Контекстно-свободные языки
- Правильные скобочные структуры
- Два типа скобок: алгоритм и грамматика
- Однозначный разбор выражений
- Контекстно-свободные грамматики и их использование
12Игры
- Игры, стратегии, кванторы
- Выигрышные и проигрышные позиции. Доказательство теоремы Цермело
13Коды
- Код с исправлением ошибок
- Верхние и нижние оценки для числа кодовых слов
- Код Хемминга
14Коммуникационная сложность
- Постановка задачи. Пример: проверка равенства.
- Пространство вариантов и комбинаторные прямоугольники
- Вероятностная проверка равенства
- Уменьшение вероятности ошибки
- Ещё о проверке равенства: многочлены и коды
- Математическое отступление: (1 - 1/n)^n < 1/2 (три способа)
15Ликбез по арифметике: числа, остатки, алгоритм Евклида
- Арифметика остатков
- Свойства операций, обратимые элементы
- Алгоритм Евклида
- Алгоритм Евклида: время работы
- Разложение на простые: существование и единственность
- Малая теорема Ферма. Теорема Эйлера
- Китайская теорема об остатках
- Проверка простоты по Миллеру и Рабину
16Криптография
- Секретный ключ: можно ли без него обойтись?
- Схема Диффи–Хеллмана
- Система RSA
17Интерактивные доказательства
- Требования к доказательствам: неинтерактивные соответствуют NP
- Интерактивные док-ва: интерактивное док-во для неизоморфизма
- Доказательства с нулевым разглашением
18Правила Хоара
- Инвариант цикла: примеры
- Быстрое возведение в степень
- Математики и программисты
Документ после выпуска
Computer Science центр
Организатор
Автор курса
Мнения учеников
Отзывы о курсе
Оставьте отзыв
Расскажите о качестве обучения, поддержке и результате. Это поможет другим выбрать организацию осознанно.
Оставьте заявку
Консультант ответит на вопросы о курсе «Введение в теоретическую информатику» и поможет разобраться в деталях обучения.
Нажимая кнопку, вы даете согласие на обработку персональных данных
Информация обновлена 7 сентября 2026 г.
Продолжить выбор
Похожие курсы
Начать без затрат
