Раздел 13 / 14

Страница 1 / 10

13. Генерическая сложность

Режим постраничного просмотра

/

На первую страницу

На предыдущую главу

На следующую главу

На последнюю страницу

Озвучивание недоступно

/

Внимание! Для озвучивания и цитирования книги перейдите в режим постраничного просмотра.

Режим постраничного просмотра

Для продолжения работы требуется Регистрация

На предыдущую главу

На следующую главу

Скачать приложение

Теория вычислительной сложности

Оглавление

Предисловие

1. Сложность алгоритмов

2. Асимптотические оценки сложности алгоритмов

3. Основные сложностные классы алгоритмов

4. Алгоритмические задачи

5. Алгоритмы разрешения

6. Неразрешимые задачи

7. Трудноразрешимые задачи

8. Машины Тьюринга

9. Классы задач P и NP
10. NP-полные задачи

11. NP-полнота задачи выполнимости

12. Другие NP-полные задачи

13. Генерическая сложность -

13.1. Генерическая разрешимость

13.2. Генерическая разрешимость задачи останова ДМТ . 32 13.3. Перечислимость

13.4. Сильная генерическая неразрешимость задачи останова ДМТ

13.5. Существование абсолютно неразрешимых задач

13.6. Генерическая сложность дискретного логарифмирования

Литература