Курс на Stepik
Обложка курса «Теоретическая информатика: сложность вычислений» на Stepik
Бесплатно

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

Открыть на
STEPIK.ORG

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

Показатель Текущие показатели Рост
Значение 🏆 Рейтинг 3 дн 7 дн 30 дн
Количество учеников на курсе «Теоретическая информатика: сложность вычислений»Учеников на курсе 9 787
Сертификаты, выданные на курсе «Теоретическая информатика: сложность вычислений»Сертификатов выдано 207
Отзывы о курсе «Теоретическая информатика: сложность вычислений»Отзывов получено 9
Рейтинг курса «Теоретическая информатика: сложность вычислений»Рейтинг курса 4.333
Уроки в курсе «Теоретическая информатика: сложность вычислений»Количество уроков 35
Тесты в курсе «Теоретическая информатика: сложность вычислений»Количество квизов 64
Задачи с кодом в курсе «Теоретическая информатика: сложность вычислений»Количество задач с кодом 52
Время прохождения курса «Теоретическая информатика: сложность вычислений»Время прохождения курса —
Обновления курса «Теоретическая информатика: сложность вычислений»Обновления курса — —
Дата публикации курса «Теоретическая информатика: сложность вычислений»Дата публикации курса — ———
Последнее обновление курса «Теоретическая информатика: сложность вычислений»Последнее обновление — ———

Содержание курса

Разделы в курсе «Теоретическая информатика: сложность вычислений» 7 разделов Уроки в курсе «Теоретическая информатика: сложность вычислений» 35 уроков Тесты в курсе «Теоретическая информатика: сложность вычислений» 64 теста Задачи в курсе «Теоретическая информатика: сложность вычислений» 52 задачи Время прохождения курса «Теоретическая информатика: сложность вычислений» 19 ч. Последнее обновление курса «Теоретическая информатика: сложность вычислений» обн. 1 год назад

О чём этот курс?

1 урок
1. Предисловие ↗

Разрешающие деревья

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

Схемы из функциональных элементов

3 урока
1. Связки, функциональные элементы, ДНФ и КНФ, полнота ↗
2. Оценки сложности. Сумма, сравнение ↗
3. Оценки сложности произвольных функций ↗

Пропозициональная логика

7 уроков
1. Формулы. Следование. Тавтологии. Выполнимость ↗
2. Следование и выводимость ↗
3. Исчисление резолюций и его полнота ↗
4. Доказательства полноты исчисления резолюций ↗
5. Поиск вывода или контрпримера ↗
6. Ещё о принципе Дирихле (приглашённый лектор --- Всеволод Опарин) ↗
7. Логика линейного программирования ↗

Переборные задачи и их сложность

11 уроков
1. Переборные задачи ↗
2. Полиномиальные задачи ↗
3. Неразрешимые задачи ↗
4. Примеры переборных задач ↗
5. Сравнение сложности: сведение ↗
6. Переборные задачи вокруг нас ↗
7. NP-полные задачи ↗
8. Задача 3-CNF NP-полна ↗
9. Задача о независимом множестве NP-полна ↗
10. Задача о 3-раскраске NP-полна ↗
11. Задачи поиска сводятся к задачам проверки ↗

Класс PSPACE

4 урока
1. Определение класса ↗
2. Игры, стратегии, кванторы ↗
3. Выигрышные и проигрышные позиции. Доказательство теоремы Цермело ↗
4. PSPACE и игры ↗

Ускорение перебора

3 урока
1. Чего мы хотим ↗
2. Задача о раскраске графа ↗
3. Задачи 2-SAT и 3-SAT ↗