March 16th, 2017

ёжик

Программа Гильберта, NP ≠ P, Рефлексия


Оглавление


0. Аннотация

1. Задачи из классов NP и P, NP+ и P+ – 4 страницы

             п. 1, пп. 2-3, пп. 4-5.

2. Программа Гильберта и теория алгоритмов – 3,5 страницы

             п. 1, п. 2.

3. Сложность вопроса о NP ≠ P – 1,5 страницы

4. Предварительное замечание о программе Гильберта для теории алгоритмов – 1,5 страницы

5. Диагонализация.

             5.1. Лемма о диагонализации – 3 страницы

                             Начало, Окончание.

             5.2. Теорема о построении алгоритма, применяемого к себе – 2,5 страницы

6. Задачи Кука и авторизуемые задачи из класса NP – 8 страниц

             п. 1, пп. 2.1-2.3, пп. 2.4-3, пп. 4-5.

7. NP ≠ P – 8,5 страниц

             пп. 1-3, пп. 4-5, пп. 6.1-6.3, пп. 6.4-7.

8. Приложения

             8.1. Первая теорема Гёделя о неполноте – 3 страницы

                             Начало, Окончание.

             8.2. Вторая теорема Гёделя о неполноте – 2,5 страницы

                             Начало, Окончание.

          8.3. Рефлексия. То, что все хотели знать о дилемме заключённого, но боялись спросить –                                             3,5 страницы

Скачать целиком в формате pdf с портала ЕДРИД: https://edrid.ru/rid/217.015.93d1.html (ссылка на скачивание будет внизу страницы)


Аннотация

( Collapse )