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

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

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

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

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

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

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

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

1 урок
Закрытый
1.1 Предисловие ↗
9 429
1 807
1м 7с
44

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

6 уроков
Закрытый
2.1 Отгадывание числа: верхние и нижние оценки ↗
3 216
362
53м 28с
76
Закрытый
2.2 Отгадывание с ошибками ↗
1 328
487
36м 39с
34
Закрытый
2.3 Поиск максимума ↗
995
499
17м 38с
26
Закрытый
2.4 Сортировка: примеры ↗
844
145
43м 34с
21
Закрытый
2.5 Сортировка: верхние и нижние оценки для n ↗
742
389
17м 1с
16
Закрытый
2.6 Ещё несколько задач ↗
725
51
10м 37с
10

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

3 урока
Закрытый
3.1 Связки, функциональные элементы, ДНФ и КНФ, полнота ↗
734
246
31м 36с
18
Закрытый
3.2 Оценки сложности. Сумма, сравнение ↗
639
66
36м 31с
13
Закрытый
3.3 Оценки сложности произвольных функций ↗
530
64
51м 57с
10

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

7 уроков
Закрытый
4.1 Формулы. Следование. Тавтологии. Выполнимость ↗
521
62
44м 45с
7
Закрытый
4.2 Следование и выводимость ↗
347
59
21м 58с
6
Закрытый
4.3 Исчисление резолюций и его полнота ↗
320
161
37м 15с
7
Закрытый
4.4 Доказательства полноты исчисления резолюций ↗
295
41
52м 28с
8
Закрытый
4.5 Поиск вывода или контрпримера ↗
267
33
56м 50с
4
Закрытый
4.6 Ещё о принципе Дирихле (приглашённый лектор --- Всеволод Опарин) ↗
292
99
27м 4с
5
Закрытый
4.7 Логика линейного программирования ↗
312
40
71м 7с
5

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

11 уроков
Закрытый
5.1 Переборные задачи ↗
393
60
21м 42с
6
Закрытый
5.2 Полиномиальные задачи ↗
341
59
11м 45с
6
Закрытый
5.3 Неразрешимые задачи ↗
302
41
7м 50с
4
Закрытый
5.4 Примеры переборных задач ↗
287
23
14м 43с
5
Открытый
5.5 Сравнение сложности: сведение ↗
310
22
36м 43с
7
Закрытый
5.6 Переборные задачи вокруг нас ↗
256
53
7м 48с
6
Закрытый
5.7 NP-полные задачи ↗
285
142
16м 35с
2
Закрытый
5.8 Задача 3-CNF NP-полна ↗
268
55
14м 23с
4
Закрытый
5.9 Задача о независимом множестве NP-полна ↗
226
42
15м 4с
4
Закрытый
5.10 Задача о 3-раскраске NP-полна ↗
247
74
15м 4с
5
Закрытый
5.11 Задачи поиска сводятся к задачам проверки ↗
206
120
7м 12с
4

6. Класс PSPACE

4 урока
Закрытый
6.1 Определение класса ↗
318
40
21м 48с
4
Закрытый
6.2 Игры, стратегии, кванторы ↗
268
32
16м 54с
4
Закрытый
6.3 Выигрышные и проигрышные позиции. Доказательство теоремы Цермело ↗
243
40
17м 18с
2
Закрытый
6.4 PSPACE и игры ↗
253
42
56м 32с
6

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

3 урока
Закрытый
7.1 Чего мы хотим ↗
267
161
2м 28с
4
Закрытый
7.2 Задача о раскраске графа ↗
297
16
44м 9с
2
Закрытый
7.3 Задачи 2-SAT и 3-SAT ↗
292
13
68м 52с
4