ливих результатів, тоді ми можемо говорити, що алгоритм здійснює відображення D? R. Оскільки таке відображення може бути не повним, то вводяться такі поняття:
Алгоритм називається частковим алгоритмом, якщо ми отримуємо результат тільки для деяких d є D і повним алгоритмом, якщо алгоритм отримує правильний результат для всіх d є D.
У теорії алгоритмів були введені різні формальні визначення алгоритму і дивним науковим результатом є доказ еквівалентності цих формальних визначень у розумінні їх рівнопотужності. Варіанти словесного визначення алгоритму належать російським вченим О.М. Колмогорову і А.А. Маркову (9, стор 24):
Визначення 1. (Колмогоров): Алгоритм - це всяка система обчислень, виконуваних за суворо визначеними правилами, яка після якого-небудь числа кроків завідомо призводить до вирішення поставленого завдання. p align="justify"> Визначення 2 (Марков): Алгоритм - це точне розпорядження, що визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.
Різні визначення алгоритму, в явній або неявній формі, постулюють наступний ряд вимог (см.5, стор 62-63):
- алгоритм повинен містити кінцеве кількість елементарно здійсненних приписів, тобто задовольняти вимогу кінцівки запису;
- алгоритм повинен виконувати кінцеве кількість кроків при вирішенні завдання, тобто задовольняти вимогу кінцівки дій;
- алгоритм повинен бути єдиним для всіх допустимих вихідних даних, тобто задовольняти вимогу універсальності;
- алгоритм повинен призводити до правильного по відношенню до поставленого завдання рішенням, тобто задовольняти вимогу правильності.
Інші формальні визначення поняття алгоритму пов'язані з введенням спеціальних математичних конструкцій (машина Посту, машина Тьюринга, рекурсивно-обчислюваної функції Черча) і постулированием тези про еквівалентність такого формалізму і поняття В«алгоритмВ» (9, стор 25 -27).
Будемо розглядати надалі, дотримуючись визначень Посту, застосовні до загальної проблеми, правильні і фінітні алгоритми, тобто алгоритми, що дають 1-рішення загальної проблеми. В якості формальної системи будемо розглядати абстрактну машину, що включає процесор з фон-неймановскую архітектурою, що підтримує адресну пам'ять і набір В«елементарнихВ» операцій співвіднесених з мовою високого рівня. З метою подальшого аналізу приймемо такі припущення:
- кожна команда виконується не більше ніж за фіксований час;
- вихідні дані алгоритму представляються машинними словами по b бітів кожне.
Конкретна проблема задається N словами пам'яті, таким чином, на вході алгоритму - N b
