Основні поняття й ознаки теорії складності
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
?упним у ієрархії складності йде клас . Задачі класу можна розвязати в поліноміальному просторі. До класу входить клас , але ряд задач вважають більш складним ніж задачі . Звісно, це поки що не може бути доведено. Відомий клас т.з. -повних задач, що мають таку властивість: якщо будь-яка з них є -задачею, то і якщо будь-яка з них є - задачею, то .
І, нарешті, існує клас . Ці задачі розвязуються за експоненційний час. На теперішній час можна довести, що -повні задачі неможливо розвязати за детермінований поліноміальний час. Крім того доведено, що .
Дамо деякі визначення. Ми говоритимемо про алгоритми.
Алгоритм це чітко задана обчислювальна процедура, що приймає змінні вхідні дані і зупиняється з видачею вихідних даних.
Звичайно, термін „чітко задана обчислювальна процедура” є математично неточною. Вона може бути зроблена точною за допомогою формальних обчислювальних моделей, таких як машини Тьюрінга, машини випадкового доступу чи булеві схеми. Однак, чим мати справу з технічними складностями таких моделей, краще розглядати алгоритм як компютерну програму, записану на деякій конкретній мові програмування для конкретного компютера, яка приймає змінні вхідні дані і зупиняється з видачею вихідних даних.
Зазвичай цікавим є знаходження найефективнішого (тобто, найшвидшого) алгоритму для вирішення даної обчислювальної задачі. Час, який витрачає алгоритм до зупинки, залежить від ”розміру” конкретної задачі. Крім того, одиниця часу, що використовується, має бути точною, особливо при порівнянні ефективності двох алгоритмів.
Якщо ми маємо справу з алгоритмом, то вважають зафіксованими два алфавіти: вхідний А і вихідний В. Робота алгоритму полягає у тому, що він отримує на вхід слово вхідного алфавіту, і як результат виконання послідовності елементарних операцій, подає на вихід слово у вихідному алфавіті.
Залежно від типу алгоритму говорять, що алгоритм обчислює функцію, розрізнює множину чи мову, знаходить елемент з певними властивостями.
Час виконання алгоритму на конкретних вхідних даних визначається як кількість елементарних операцій чи „кроків”, що виконуються. Часто крок використовується для визначення бітової операції. Для деяких алгоритмів буде більш зручним використовувати крок для маркування чогось ще, наприклад, порівняння, машинної команди, машинного тактового циклу, модулярного множення тощо.
Якщо t (n) cnc для деякої константи с, то алгоритм вирішує задачу за поліноміальний (від довжини входу) час.
Такий алгоритм називають поліноміальним, а задачу такою, що вирішується поліноміально.
Поняття поліноміального часу є центральною концепцією теорії складності обчислень. У рамках цієї концепції вважається, що поліноміальні алгоритми відповідають швидким, ефективним на практиці алгоритмам, а такі, що вирішуються поліноміально, відповідають легким задачам.
Алгоритм, що на безкінечній послідовності входів робить більш ніж кроків, де n довжина входу, а с > 0 деяка константа, називається експоненційним.
Про такий алгоритм говорять, що він потребує експоненційного часу. Експоненційні алгоритми відповідають загальним поняттям про неефективні на практиці алгоритми.
Так, наприклад, реалізація ідеї несиметричного шифрування базується на понятті однобічної взаємно однозначної функції, такої, що при відомому порівняно просто обчислити , однак зворотню функцію обчислити (за прийнятний час) неможливо. Цю властивість називають практичною незворотністю. Зазвичай обчислення прямої функції має поліноміальну складність, а зворотної у кращому випадку експоненційну. У криптосистемі RSA достатньо просто знайти добуток двох простих чисел (поліноміальна складність), але задача розкладання великого числа на прості співмножники є дуже складною (як мінімум експоненційної складності). Сьогодні не існує жодної однобічної функції, для якої математично була б доведена її практична незворотність або експоненційна складність. Ті функції, що знайшли довгострокове застосування в криптографії, вважаються однобічними. При цьому можна лише стверджувати, що на сьогодні відомі алгоритми обчислення зворотної функції зі складністю, що практично може бути реалізована (в рамках заданих параметрів).
Часто буває складно отримати час виконання алгоритму. У таких випадках змушені погодитися на апроксимацію часу виконання, зазвичай можна отримати асимптотичний час виконання, тобто досліджується, як збільшується час виконання алгоритму з безмежним збільшенням розміру вхідних даних. Розглядаються тільки ті функції, що задані на додатних цілих числах і приймають дійсні значення.
Нехай f та g будуть двома такими функціями.
Запис f(n) O( g(n)) означає, що f асимптотично зростає не швидше, ніж g(n), з точністю до постійного кратного, у той час як f(n) (g(n)) означає, що f(n) зростає, принаймні, також асимптотично швидко, як зростає g(n), з точністю до постійного множника.
f(n) O(g(n)) означає, що функція f(n) стає несуттєвою відносно g(n) по мірі зростання n.
При цьому для будь-яких функцій f(n), g(n), h(n) і l(n) справедливі такі властивості і співвідношення:
f (n) O(g(n)), у випадку. якщо g(n) = (f (n)).
f(n) (g(n)), у випадку. якщо f (n) O(g(n)) і (f)n (g(n)).
Якщо