Зюзьков В.М. Лекции по теории алгоритмов ОНЛАЙН


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



Читать онлайн
скачать бесплатно


Теги:
Зюзьков теория алгоритмов, конспект лекций по теории алгоритмов

Коментарі до Зюзьков В.М. Лекции по теории алгоритмов ОНЛАЙН