Головна Головна -> Підручники -> Підручник Вивчаємо FrontPage скачати онлайн-> 6. Поняття алгоритму

6. Поняття алгоритму



Поняття алгоритму

Інтуїтивно алгоритм визначається як “послідовність чітких недвозначних інструкцій, які зрозумілі виконавцеві і які призводять до певного результату за скінченний час”. Точне визначення алгоритму дати неможливо, але можна сформулювати ряд інтуїтивних вимог до алгоритмів. Вважається, що послідовність інструкцій є алгоритмом, якщо вона задовольняє таким вимогам:

·                      дискретність: алгоритм являє собою послідовність кроків, на кожному з яких виконується та чи інша інструкція; кожна наступна інструкція виконується після того, як завершиться виконання попередньої;

·                      елементарність кроків: кожна інструкція є елементарною для виконавця і не вимагає від нього ніякої винахідливості;

·                      локальність кроків: процес виконання інструкції не вимагає повернення до попередніх інструкцій або звертання до наступних;

·                      детермінованість: після завершення чергового кроку завжди відомо, що робити на наступному кроці;

·                      результативність: повинно бути визначено, що слід вважати результатом роботи алгоритму;

·                      скінченність: результат повинен досягатися за скінченну кількість кроків;

·                      масовість: алгоритм повинен бути призначений для вирішення не однієї конкретної задачі, а цілого класу однотипних задач.

Будемо називати деяку функцію y = f(x1,…,xn) ефективно обчислюваною, або просто обчислюваною, якщо існує будь-яка механічна процедура, яка дозволяє знайти значення y, якщо відомі значення x1,…,xn. Якщо функція визначена не для всіх значень x1,…,xn, вона називається частково обчислюваною.
Отже, будь-який алгоритм, і, відповідно, будь-яку програму ми розглядаємо як реалізацію деякого інформаційного перетворення, тобто як реалізацію частково обчислюваної функції, аргументами якої є вхідні дані алгоритму, а значенням – результат роботи алгоритму.
Слова “алгоритм” і “механічна процедура” ми розглядаємо як синоніми. Ми кажемо, що будь-яка механічна процедура реалізує певний алгоритм, і навпаки – якщо послідовність інструкцій є алгоритмом, то повинен існувати якийсь механізм, здатний виконати цю послідовність інструкцій.

Поняття обчислювальної складності

Основними мірами обчислювальною складності алгоритмів є:

·                      часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму;

·                      ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму.Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних. Надалі обмежимося тільки аналізом часової складності.

Складність алгоритму описується функцією f(n), де n – розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції.
Визначення.
Кажуть, що f(n) = O (g(n)), якщо існує така константа с > 0, що для будь-якого n виконується нерівність: |f(n)| Ј с |g(n)|.Оскільки і розмір вхідних даних, і кількість операцій є величинами невід’ємними (а фактично – додатніми), модулі можна опустити.

Виділяють такі основні класи алгоритмів:

·                      логарифмічні: f(n) = O (log2n);

·                      лінійні: f(n) = O (n);

·                      поліноміальні: f(n) = O (nm); тут m – натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним;

·                      експоненційні: f(n) = O (an); a – натуральне число, більше від одиниці.

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

Приклад.
Часто зустрічається задача пошуку в масиві, яка неформально формулюється таким чином: в заданій послідовності чисел знайти елемент з певним значенням.
В загальному випадку застосовується алгоритм послідовного пошуку, який полягає в послідовному перегляді всіх елементів і порівнянні їх з потрібним значенням. Легко бачити, що цей алгоритм має лінійну часову складність.
Але, якщо заздалегідь відомо, що послідовність упорядкована за зростанням або за спаданням, можна застосувати інший алгоритм – алгоритм половинного ділення. Послідовність ділиться на дві рівні частини. Оскільки послідовність упорядкована, можна визначити, в якій частині знаходиться потрібний елемент. Після цього процедура повторюється: потрібна частина знову ділиться навпіл і т.п. Цей алгоритм є логарифмічним.

Будемо називати часовою складністю задачі часову складність найбільш ефективного алгоритму для її вирішення.

Експоненційні алгоритми та перебір

Експоненційні алгоритми часто пов’язані з перебором різних варіантів розв’язку.

Наведемо типовий приклад.
Розглянемо задачу про виконуваність булевого виразу, яка формулюється так: для будь-якого булевого виразу від n змінних знайти хоча б один набір значень змінних x1… xn, при якому цей вираз приймає значення 1.
Типова схема розв’язку цієї задачі може мати такий вигляд: спочатку надаємо одне з двох можливих значень (0 або 1) першій змінній x1, потім другій і т.д. Коли будуть розставлені значення всіх змінних, ми можемо визначити значення булевого виразу. Якщо він дорівнює 1, задача вирішена. Якщо ні – потрібно повернутися назад і змінити значення деяких змінних.
Можна інтерпретувати цю задачу як задачу пошуку на певному дереві перебору. Кожна вершина цього дерева відповідає певному набору встановлених значень x1 …, xk . Ми можемо встановити змінну xk+1 в 0 або 1, тобто маємо вибір з двох дій. Тоді кожній з цих дій відповідає одна з двох дуг, які йдуть від цієї вершини. Вершина x1 …, xk має двох синів x1 …, xk 0 і x1 …, xk 1.
При n=3 дерево можливостей матиме вигляд, показаний на мал. (вершини помічені наборами значень змінних, а дуги – рішеннями, які приймаються на черговому кроці). Вершини, що відповідають рішенням задачі для виразу (x1 x2) є x3, зафарбовані.

З малюнку видно, що вирішення задачі зводиться до перебору листів дерева з метою виявлення, які з них відповідають наборам, що перетворюють заданий булевий вираз на 1. Для виразу (x1 x2) є x3 такими наборами будуть 000, 010, 111.
Якщо n=3, дерево має 23= 8 листів. У загальному ж випадку кількість можливих варіантів дорівнює 2n. Цей вираз експоненційно залежить від n, і перебірний алгоритм має експоненційний характер.
Описана вище схема алгоритму вирішення цієї задача має фундаментальний характер. Вона носить назву бектрекінгу (інша назва – перебір з поверненням) і використовується для вирішення найрізноманітніших перебірних задач (задача про вісім ферзів, задача про розфарбування карти, автоматизація дедуктивних побудов тощо).
Слід звернути увагу на те, що не будь-який перебірний алгоритм є експоненційним. (Наприклад, алгоритм пошуку в масиві. Незважаючи на його перебірний характер, він є лінійним, а не експоненційним).
Зі зростанням розмірності будь-який поліноміальний алгоритм стає більш ефективним, ніж будь-який експоненційний. Для лінійного алгоритму зростання швидкодії комп’ютера в 10 разів дозволяє за той же час розв’язати задачу, розмір якої в 10 разів більший. Для експоненційного алгоритму з основою 2 цей же розмір можна збільшити лише на 3 одиниці.
Як правило, якщо для розв’язку якоїсь задачі придумано деякий поліноміальний алгоритм, часова оцінка цього алгоритму швидко поліпшується.

P- та NP- задачі

Визначення.
P-задачею називається задача, яка може бути розв’язана на детермінованій машині Тьюринга за поліноміальний час O (nm), де n – розмір задачі. Іншими словами, P-задача – це задача, для розв’язку якої існує поліноміальний алгоритм.
Під детермінованою машиною Тьюринга мається на увазі машина Тьюринга у вищенаведеному розумінні. “Детермінованість” означає, що в будь-який момент дія машини є чітко визначеною. На відміну від цього, недетермінована машина Тьюринга у будь-який момент часу може одночасно реалізовувати декілька можливих варіантів дій. Така машина є теоретичною абстракцією і не може бути реалізована на основі фон-нейманівських принципів. Вона могла б бути реалізована лише на багатопроцесорній машині за умови наявності необмеженої кількості процесорів.
Формально інструкцію недетермінованої машини Тьюринга можна записати у вигляді:
aiskSAI,
це означає, що, якщо машина перебуває у стані sk і читає символ ai, вона породжує певну кількість нових машин, кожна з яких записує деякий символ з S, переходить до деякого стану з A і зсувається вправо, вліво, або залишається на місці. Можна вважати, що всі породжені машини продовжують перебір варіантів.
Визначення.
NP-задачею називається задача, яка може бути розв’язана на детермінованій машині Тьюринга за поліноміальний час O (nm), де n – розмір задачі.
Якщо ж обмежитися детермінованими алгоритмами, то для вирішення будь-якої NP-задачі можна використовувати схему перебору з поверненням або подібні до неї перебірні схеми. Як зазначалося раніше, подібні алгоритми є експоненційними по своїй суті, і задачі, які вимагають застосування таких алгоритмів, відносяться до класу важко вирішуваних. Втім, це не виключає існування поліноміальних алгоритмів, і для ряду задач, які мають характер пошуку на дереві, такі алгоритми дійсно були знайдені.Позначимо через P клас P-задач, а через NP – клас NP-задач Ясно, що P – підмножина NP. Але питання про те, чи є це включення строгим, залишається відкритим.

NP-повні задачі

Кажуть, що задача A поліноміально зводиться до задачі B, якщо рішення задачі A може бути отримано з рішення задачі B за поліноміальний час.
Задача називається NP-складною, якщо до неї за поліноміальний час зводиться будь-яка NP – задача.
Якщо NP-складна задача є NP-задачею, така задача називається NP-повною. Поняття NP-повної задачі має велике значення. Якщо для будь-якої NP-повної задачі буде знайдений поліноміальний алгоритм, це означатиме, що поліноміальний алгоритм існує для будь-якої NP-задачі, і тоді виявиться, що P = NP. Але таких алгоритмів поки що знайдено не було, і шансів на їх знаходження залишається все менше і менше.
Дуже важливим є наступний результат, що був отриманий Куком: задача про виконуваність булевого виразу є NP-повною.








Популярні глави цього підручника:



Всі глави цього підручника:

Вивчаємо FrontPage