Розділ 6 Ефективність алгоритмів

Характеристики алгоритмів.

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

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

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

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

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

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

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

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

Будемо називати деяку функцію y = f(x₁,…,x_n) ефективно обчислюваною, або просто обчислюваною, якщо існує будь-яка механічна процедура, яка дозволяє знайти значення y, якщо відомі значення x₁,…,x_n. Якщо функція визначена не для всіх значень x₁,…,x_n, вона називається частково обчислюваною.

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Приклади.	\|	Ємна та часова складність. Поліноміальна зв’язність.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.