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

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

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

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

Показатель Текущие показатели Рост
Значение 🏆 Рейтинг 3 дн 7 дн 30 дн
Количество учеников на курсе «Теоретическая информатика: сложность вычислений»Учеников на курсе 9 782
Сертификаты, выданные на курсе «Теоретическая информатика: сложность вычислений»Сертификатов выдано 206
Отзывы о курсе «Теоретическая информатика: сложность вычислений»Отзывов получено 8
Рейтинг курса «Теоретическая информатика: сложность вычислений»Рейтинг курса 4.250
Уроки в курсе «Теоретическая информатика: сложность вычислений»Количество уроков 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