Теория алгоритмов. Зюзысов В.М. - 4 стр.

UptoLike

Составители:

Рубрика:

5 Сложность вычислений__________________________________________________54

5.1 Асимптотические обозначения _____________________________________________54

Θ–обозначение ________________________________________________________________________ 54

O– и Ω-обозначения____________________________________________________________________ 55

Сравнение роста функций_______________________________________________________________ 56

5.2 Алгоритмы и их сложность ________________________________________________58

5.3 Сложность задач __________________________________________________________60

6 NP-полнота ____________________________________________________________64

6.1 Задачи разрешения и задачи оптимизации ___________________________________64

6.2 Формальные языки _______________________________________________________65

6.3 Проверка принадлежности языку и класс NP ________________________________67

6.4 NP-полнота и сводимость __________________________________________________68

Литература ________________________________________________________________71