Содержание курса
18
разделов
86
уроков
111
тестов
118
задач
27 ч.
обн. 4 года назад
1. Разрешающие деревья
6 уроков
35 705
8 327
168м
954
Открытый
1.1
Отгадывание числа: верхние и нижние оценки
↗
19 512
1 868
57м 0с
500
Открытый
1.2
Отгадывание с ошибками
↗
5 177
1 912
37м 44с
140
Открытый
1.3
Поиск максимума
↗
3 328
1 868
17м 16с
113
Открытый
1.4
Сортировка: примеры
↗
2 859
847
31м 39с
99
Открытый
1.5
Сортировка: верхние и нижние оценки для n
↗
2 468
1 286
18м 47с
68
Открытый
1.6
Ещё несколько задач
↗
2 361
546
9м 3с
34
2. Схемы из функциональных элементов
3 урока
6 149
1 344
121м
123
Открытый
2.1
Связки, функциональные элементы, ДНФ и КНФ, полнота
↗
2 574
940
32м 8с
65
Открытый
2.2
Оценки сложности. Сумма, сравнение
↗
1 971
224
37м 10с
30
Открытый
2.3
Оценки сложности произвольных функций
↗
1 604
180
52м 59с
28
3. Пропозициональная логика
5 уроков
5 788
1 286
135м
77
Открытый
3.1
Формулы. Следование. Тавтологии. Выполнимость
↗
1 712
181
50м 27с
22
Открытый
3.2
Следование и выводимость
↗
1 177
182
21м 22с
17
Открытый
3.3
Исчисление резолюций и его полнота
↗
1 114
163
28м 9с
15
Открытый
3.4
Поиск вывода или контрпримера
↗
929
176
16м 22с
11
Открытый
3.5
Нижние оценки на поиск вывода
↗
856
584
18м 24с
12
4. Вычислимость
5 уроков
5 204
897
113м
106
Открытый
4.1
Вычислимость, разрешимость, перечислимость
↗
1 374
189
19м 59с
31
Открытый
4.2
Свойства перечислимых множеств, теорема Поста
↗
1 065
157
23м 35с
19
Открытый
4.3
Графики, проекции
↗
968
198
16м 57с
20
Открытый
4.4
Проблема остановки: перечислимое неразрешимое множество
↗
931
191
37м 55с
22
Открытый
4.5
Вычислимые действительные числа
↗
866
162
18м 9с
14
5. Программы и универсальные функции
9 уроков
7 447
1 379
156м
66
Открытый
5.1
Интерпретаторы, программы, универсальные функции
↗
1 131
222
8м 48с
16
Открытый
5.2
Гёделевы универсальные функции
↗
906
151
25м 15с
3
Открытый
5.3
Св-ва гёделевых универсальных ф-й. Теорема Райса–Успенского
↗
780
129
25м 41с
10
Открытый
5.4
У любой функции бесконечно много программ
↗
713
126
12м 7с
8
Открытый
5.5
Отступление: перечислимые неотделимые множества
↗
683
148
17м 18с
7
Открытый
5.6
Теорема о неподвижной точке и её следствия
↗
963
142
20м 37с
1
Открытый
5.7
Доказательства теоремы о неподвижной точке
↗
662
130
23м 8с
5
Открытый
5.8
Самоприменимость, парадокс лжеца, теорема Гёделя
↗
709
183
14м 30с
6
Открытый
5.9
λ-исчисление
↗
900
148
12м 49с
10
6. Машины Тьюринга
5 уроков
5 320
1 923
72м
84
Открытый
6.1
Мотивировка и примеры
↗
1 849
712
22м 3с
44
Открытый
6.2
Формальное определение
↗
976
408
13м 32с
11
Открытый
6.3
Модификации и их последствия
↗
825
532
19м 49с
15
Открытый
6.4
Оценки времени работы
↗
807
124
14м 49с
9
Открытый
6.5
Тезис Чёрча–Тьюринга
↗
863
147
5м 54с
5
7. Ассоциативные исчисления
2 урока
1 470
259
37м
9
Открытый
7.1
Определение и примеры
↗
823
142
18м 0с
5
Открытый
7.2
Неразрешимость проблемы эквивалентности
↗
647
117
19м 59с
4
8. Переборные задачи и их сложность
11 уроков
7 800
2 277
146м
43
Открытый
8.1
Переборные задачи
↗
928
176
19м 16с
10
Открытый
8.2
Полиномиальные задачи
↗
775
161
11м 41с
6
Открытый
8.3
Неразрешимые задачи
↗
731
151
7м 49с
3
Открытый
8.4
Примеры переборных задач
↗
741
133
13м 23с
4
Открытый
8.5
Сравнение сложности: сведение
↗
722
106
24м 8с
9
Открытый
8.6
Переборные задачи вокруг нас
↗
637
134
7м 47с
5
Открытый
8.7
NP-полные задачи
↗
719
457
16м 34с
3
Открытый
8.8
Задача 3-CNF NP-полна
↗
663
123
14м 19с
3
Открытый
8.9
Задача о независимом множестве NP-полна
↗
661
130
15м 31с
1
Открытый
8.10
Задача о 3-раскраске NP-полна
↗
669
305
13м 14с
-1
Открытый
8.11
Задачи поиска сводятся к задачам проверки
↗
554
401
7м 10с
0
9. Ускорение перебора
3 урока
3 720
694
109м
23
Открытый
9.1
Чего мы хотим
↗
722
499
2м 28с
3
Открытый
9.2
Задача о раскраске графа
↗
1 546
107
42м 48с
12
Открытый
9.3
Задачи 2-SAT и 3-SAT
↗
1 452
88
65м 47с
8
10. Конечные автоматы
5 уроков
4 484
945
110м
61
Открытый
10.1
Примеры
↗
1 207
181
14м 51с
26
Открытый
10.2
Формальное определение. Автоматные множества
↗
847
140
25м 59с
14
Открытый
10.3
Недетерминизм и его устранение
↗
714
95
28м 36с
12
Открытый
10.4
Теорема Клини
↗
1 061
91
32м 4с
7
Открытый
10.5
Минимальный автомат
↗
655
438
11м 2с
2
11. Контекстно-свободные языки
4 урока
2 872
1 028
59м
28
Открытый
11.1
Правильные скобочные структуры
↗
784
431
17м 20с
12
Открытый
11.2
Два типа скобок: алгоритм и грамматика
↗
655
138
12м 42с
7
Открытый
11.3
Однозначный разбор выражений
↗
618
385
10м 46с
5
Открытый
11.4
Контекстно-свободные грамматики и их использование
↗
815
74
20м 54с
4
12. Игры
2 урока
1 606
218
33м
17
Открытый
12.1
Игры, стратегии, кванторы
↗
901
107
15м 15с
10
Открытый
12.2
Выигрышные и проигрышные позиции. Доказательство теоремы Цермело
↗
705
111
17м 20с
7
13. Коды
3 урока
2 081
346
39м
21
Открытый
13.1
Код с исправлением ошибок
↗
781
118
11м 19с
10
Открытый
13.2
Верхние и нижние оценки для числа кодовых слов
↗
599
118
14м 39с
6
Открытый
13.3
Код Хемминга
↗
701
110
14м 15с
5
14. Коммуникационная сложность
6 уроков
2 944
791
69м
17
Открытый
14.1
Постановка задачи. Пример: проверка равенства.
↗
601
98
17м 47с
3
Закрытый
14.2
Пространство вариантов и комбинаторные прямоугольники
↗
475
102
9м 57с
-1
Закрытый
14.3
Вероятностная проверка равенства
↗
468
96
17м 58с
3
Закрытый
14.4
Уменьшение вероятности ошибки
↗
465
91
6м 44с
4
Открытый
14.5
Ещё о проверке равенства: многочлены и коды
↗
480
62
15м 10с
5
Открытый
14.6
Математическое отступление: (1 - 1/n)^n < 1/2 (три способа)
↗
455
342
5м 0с
3
15. Ликбез по арифметике: числа, остатки, алгоритм Евклида
8 уроков
6 359
2 023
164м
40
Открытый
15.1
Арифметика остатков
↗
1 239
271
24м 59с
17
Открытый
15.2
Свойства операций, обратимые элементы
↗
782
432
24м 35с
2
Открытый
15.3
Алгоритм Евклида
↗
836
162
38м 41с
1
Открытый
15.4
Алгоритм Евклида: время работы
↗
720
176
19м 1с
4
Открытый
15.5
Разложение на простые: существование и единственность
↗
645
134
8м 11с
2
Открытый
15.6
Малая теорема Ферма. Теорема Эйлера
↗
761
345
16м 12с
5
Открытый
15.7
Китайская теорема об остатках
↗
775
132
18м 59с
6
Открытый
15.8
Проверка простоты по Миллеру и Рабину
↗
601
371
18м 52с
3
16. Криптография
3 урока
2 148
261
38м
18
Открытый
16.1
Секретный ключ: можно ли без него обойтись?
↗
816
82
10м 41с
6
Открытый
16.2
Схема Диффи–Хеллмана
↗
636
104
9м 54с
5
Открытый
16.3
Система RSA
↗
696
75
19м 10с
7
17. Интерактивные доказательства
3 урока
1 486
261
40м
6
Закрытый
17.1
Требования к доказательствам: неинтерактивные соответствуют NP
↗
543
96
7м 36с
3
Закрытый
17.2
Интерактивные док-ва: интерактивное док-во для неизоморфизма
↗
469
74
16м 26с
1
Закрытый
17.3
Доказательства с нулевым разглашением
↗
474
91
17м 40с
2
18. Правила Хоара
3 урока
3 387
301
45м
27
Открытый
18.1
Инвариант цикла: примеры
↗
1 577
110
14м 5с
10
Открытый
18.2
Быстрое возведение в степень
↗
719
103
13м 4с
9
Открытый
18.3
Математики и программисты
↗
1 091
88
18м 46с
8