Зюзьков В.М. Лекции по теории алгоритмов (мехмат)
Содержание
1. Алгоритмы и вычислимые функции_1
1.1. Понятие алгоритма и неформальная вычислимость_1
1.2. Частично-рекурсивные функции_3
1.3. Машины Тьюринга_6
1.4. Тезис Чёрча_8
1.5. Теорема о рекурсии_9
1.6. Куины_12
1.7. Некоторые алгоритмически неразрешимые проблемы_13
2. Элементарная арифметика и неполнота_14
2.1. Элементарная арифметика_14
2.2. Арифметические функции и отношения_16
2.3. Гёделева нумерация_17
2.4. Лемма о рефлексии _19
2.5. Теорема Гёделя о неполноте_20
2.6. Нестандартное расширение EA_23
Супернатуральные числа_23
Варианты теории чисел и банкиры_24
Варианты теории чисел и метаматематики_25
2.7. Теорема Гудстейна_25
Наследственное представление_25
Последовательность Гудстейна_26
Теорема Гудстейна_26
2.8. Об аксиоматизации_28
3. Сложность вычислений_29
3.1. Асимптотические обозначения_29
3.2. Алгоритмы и их сложность_31
3.3. Сложность задач_33
4. NP-полнота_35
4.1. Задачи разрешения и задачи оптимизации_36
4.2. Формальные языки_37
4.3. Проверка принадлежности языку и класс NP_38
4.4. NP-полнота и сводимость_40
Литература_42
