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

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

Це не є визначенням, тому що вираз «єдиний», «кінцеве число кроків» позбавлені математичної точності.

Риси, характерні для інтуїтивного поняття алгоритму

1. Дискретність. Ця властивість полягає в наступному: в початковий момент задається вихідна система величин, а в кожен наступний момент система величин виходить з попередньої системи величин за певним законом (програмі).

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

3. Елементарність кроків. Закон отримання подальшої системи величин з попередньої повинен бути простим і локальним.

4. Ефективність (результативність). Кожен крок роботи алгоритму повинен закінчуватися результатом.

5. Масовість алгоритму. Початкова система величин може вибиратися з деякого нескінченного рахункового безлічі Х.

6. Конструктивність. Об'єкти з Х, над яким працює алгоритм, повинні бути конструктивними.

Конструктивний об'єкт - той, який може бути набраний весь цілком і представлений для розгляду.

Прикладами конструктивних об'єктів є булеві функції, формули алгебри логіки, натуральні та раціональні числа, матриці з натуральними або раціональними елементами, многочлени від невідомих з раціональними коефіцієнтами.

Неконструктивними об'єктами є, наприклад, будь-які дійсні числа, подання яких в десяткового запису a₀ a ₁ ... a _n ... ні для якого nіз натуральних чисел не може бути цілком представлено для розгляду. Числа і не є конструктивними об'єктами.

Зрозуміло, що поняття алгоритму, що описується властивостями 1-6, є нестрогим: у формулюванні цих властивостей зустрічаються слова, які не мають точного математичного визначення. Необхідно також зазначити, що, взагалі кажучи, не передбачається, що процес застосування алгоритму до вихідних даних обов'язково повинен закінчитися результатом через кінцеве число кроків. Процес може закінчитися безрезультатно або не закінчитися взагалі. В цьому випадку говорять, що алгоритм застосуємо до досліджуваних вихідними даними.

Приклади алгоритмів:

• Алгоритми арифметичних дій з числами в двійковій системі числення

• алгоритм знаходження НОД 2-х цілих чисел, 2-х многочленів від змінної х;

• алгоритм вилучення? n,? n? N;

• алгоритм диференціювання многочлена від змінної;

• алгоритм знаходження визначника квадратної матриці А над?;

Аж до 30-х років двадцятого століття поняття алгоритму залишалося інтуїтивно зрозумілим, що мав швидше методологічне, а не математичне значення. Так, до початку ХХ ст. багато яскравих прикладів дала алгебра і теорія чисел. Серед них згадаємо алгоритм Евкліда знаходження найбільшого загального дільника двох натуральних чисел або двох цілочисельних многочленів, алгоритм Гаусса рішення системи лінійних рівнянь над полем, алгоритм знаходження раціональних коренів многочленів одного змінного з раціональними коефіцієнтами, алгоритм Штурма визначення числа дійсних коренів многочлена з дійсними коефіцієнтами на деякому відрізку дійсних чисел, алгоритм розкладання многочлена одного змінного над кінцевим полем на Непріводімие множники. Зазначені алгоритмічні проблеми вирішені шляхом зазначення конкретних дозвільних процедур. Для отримання результатів такого типу досить інтуїтивного поняття алгоритму.

Але тоді ж були висунуті алгоритмічні проблеми, для яких не вдавалося побудувати алгоритм, та й саме існування таких алгоритмів було під сумнівом.

Приклади:

• 10-я проблема Гільберта про можливості розв'язання довільного диофантово рівняння;

• Проблема визначення общезначимости довільної формули логіки предикатів.

Зазначені проблеми були вирішені негативно, тобто доведено, що не існує алгоритму для їх вирішення (відповідно Ю. Матіясевіч (1970 р.) і А. Черч (1936г.)).

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

1. обчислення функції натурального аргументу (частково-рекурсивні функції);

2. роботу деякої абстрактної машини (машини Тьюринга, машина з необмеженими регістрами);

3. послідовні перетворення слів, записаних в довільному алфавіті (нормальні алгоритми Маркова).

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

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

Уточнення поняття алгоритму за його властивостями

Поняття «алгоритм» можна уточнити, вказавши перелік властивостей, які характерні для алгоритмів. До них відносяться:  1. Дискретність алгоритму означає, що алгоритм розділений на окремі кроки (дії), причому, виконання чергового кроку можливо тільки після завершення всіх операцій на попередньому кроці. При цьому набір проміжних даних кінцевий і він виходить за певними правилами з даних попереднього кроку.  2. Детермінованість алгоритму полягає в тому, що сукупність проміжних величин та будь-якому кроці однозначно визначається системою величин, що були на попередньому кроці.Дана властивість означає, що результат виконання алгоритму не залежить від того, хто (або що) його виконує (тобто від виконавця алгоритму), а визначається тільки вхідними даними і кроками (послідовністю дій) самого алгоритму.  3. Елементарність кроків: закон отримання подальшої системи величин з попередньої повинен бути простим і локальним. Який крок (дія) можна вважати елементарним, визначається особливостями виконавця алгоритму.  4. Спрямованість алгоритму: якщо спосіб отримання наступних величин з будь-яких вихідних не призводить до результату, то повинно бути вказано, що слід вважати результатом алгоритму.  5. Масовість алгоритму: початкова система величин може вибиратися з деякого безлічі.

Остання властивість означає, що один алгоритм, тобто одна і та ж послідовність дій, в загальному випадку, може застосовуватися для вирішення деякого класу (тобто багатьох) завдань.Для практики і, зокрема, рішення задачі на комп'ютері, це властивість істотно, оскільки, як правило, призначена для користувача цінність програми виявляється тим вище, чим більший коло однотипних завдань вона дозволяє вирішити. Однак для побудови алгоритмічної теорії це властивість не є істотним і обов'язковим. Поняття алгоритму, в якійсь мірі визначається перерахуванням властивостей 1 - 5, також не можна вважати суворим, оскільки у формулюваннях властивостей використані терміни «величина», «спосіб», «простий», «локальний» та інші, точний зміст яких не встановлено. Дане визначення буде називатися нестрогим (іноді його називають інтуїтивним) поняттям алгоритму. ^[4]

Алгоритмічна розв'язність

Матеріал з Вікіпедії - вільної енциклопедії

Поточна версія сторінки поки не перевірялася досвідченими учасниками і може значно відрізнятися від версії , перевіреної 7 липня 2011; перевірки вимагає 1 правка .

У математичній логіці та теорії алгоритмів під розв'язність увазі властивість формальної теорії володіти алгоритмом , визначальним по даній формулі , виведена вона з безлічі аксіомданої теорії чи ні. Теорія називається розв'язною, якщо такий алгоритм існує, і нерозв'язною, в іншому випадку. Питання про виводимості у формальній теорії є приватним, але разом з тим, найважливішим випадком більш загальної проблеми розв'язання .

Зміст   [убрать]  1 Історія питання і передумови 2 Загальні відомості 2.1 Приклади розв'язаних теорій 2.2 Приклади нерозв'язних теорій 3 Полуразрешімость і автоматичне доказ 4 Зв'язок розв'язності та повноти 5 Література 6 Див також