Xreferat.com » Рефераты по коммуникации и связи » Основні поняття й ознаки теорії складності

Основні поняття й ознаки теорії складності

конкретного комп’ютера, яка приймає змінні вхідні дані і зупиняється з видачею вихідних даних.

Зазвичай цікавим є знаходження найефективнішого (тобто, найшвидшого) алгоритму для вирішення даної обчислювальної задачі. Час, який витрачає алгоритм до зупинки, залежить від ”розміру” конкретної задачі. Крім того, одиниця часу, що використовується, має бути точною, особливо при порівнянні ефективності двох алгоритмів.

Якщо ми маємо справу з алгоритмом, то вважають зафіксованими два алфавіти: вхідний – А і вихідний – В. Робота алгоритму полягає у тому, що він отримує на вхід слово вхідного алфавіту, і як результат виконання послідовності елементарних операцій, подає на вихід слово у вихідному алфавіті.

Залежно від типу алгоритму говорять, що алгоритм обчислює функцію, розрізнює множину чи мову, знаходить елемент з певними властивостями.

Час виконання алгоритму на конкретних вхідних даних визначається як кількість елементарних операцій чи „кроків”, що виконуються. Часто крок використовується для визначення бітової операції. Для деяких алгоритмів буде більш зручним використовувати крок для маркування чогось ще, наприклад, порівняння, машинної команди, машинного тактового циклу, модулярного множення тощо.

Якщо 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)).

Якщо f (n) = O(h(n)) і (g)n = O(h(n)), то ( f + g)(n) = O(h(n)).

Якщо f (n) = O( h(n)) і g(n) = O(l(n)), то ( f - g)( n) = O(h(n)l(n)).

Рефлексивність f(n) = O(f(n)).

Транзитивність. Якщо f(n) = O(g(n)) і g(n) = O(h(n)), то f(n) = O(h(n)).


Складність алгоритмів вимірюють кількістю арифметичних операцій (додавань, віднімань, множень і ділень із залишком), необхідних для виконання всіх дій. Однак це визначення не бере до уваги величини чисел, що беруть участь в обчисленнях. Тому, часто беруть до уваги ще й величину чисел, зводячи обчислення до бітових операцій, тобто оцінюючи кількість необхідних операцій із цифрами 0 і 1, у двійковому записі чисел. Це залежить від задачі, що розглядаються.

Даний підхід зручний з таких міркувань. По-перше, у комп’ютерах дані подаються і обробляються у двійковому вигляді, а інші подання в основному використовують під час введення даних і під час виведення результатів. По-друге, перевід числа Основні поняття й ознаки теорії складності від однієї основи системи обчислень до іншої виконується швидко і потребує виконання Основні поняття й ознаки теорії складності арифметичних операцій (ділення з залишком, множення або додаваня чисел), де Основні поняття й ознаки теорії складності – довжина запису числа Основні поняття й ознаки теорії складності (основу логарифмам не вказуємо, оскільки воно не впливає на вид оцінки складності). Перехід до іншої основи є рідкісною операцією, затратами на її виконання можна знехтувати. Нарешті, бітова оцінка непогано відображує реальну складність операцій, оскільки, як правило, оцінки складності для інших основ систем обчислень призводять лише до змін у константному множнику функції оцінки складності. При оцінці складності обчислювальних задач, звичайно, застосовують методи редукції і піднесення до інших задач з відомими оцінками складності.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: