в якій було показано, що деякі математичні проблеми не можуть бути вирішені алгоритмами з деякого класу. Спільність результату Геделя пов'язана з тим, чи збігається використаний ним клас алгоритмів з класом всіх (у інтуїтивному сенсі) алгоритмів. Ця робота дала поштовх до пошуку та аналізу різних формалізацій алгоритму.
Завдання точного визначення поняття алгоритму була вирішена в 30-х роках в роботах Д. Гільберта, А. Черча, С. Кліні, Е. Посту, А. Тьюринга у двох формах: на основі поняття рекурсивної функції і на основі опису алгоритмічного процесу. Рекурсивна функція - це функція, для якої існує алгоритм обчислення її значень за довільним значенням аргументу. Клас рекурсивних функцій був визначений строго як конкретний клас функцій в деякій формальній системі. Був сформульований тезу (званий В«теза ЧерчаВ»), який стверджує, що даний клас функцій збігається з безліччю функцій, для яких є алгоритм обчислення значень за значенням аргументів. Інший підхід полягав у тому, що алгоритмічний процес визначається як процес, здійсненний на конкретно влаштованої машині (званої В«машиною ТьюрингаВ»). Було сформульовано тезу (В«Теза ТьюрингаВ»), який стверджує, що будь-який алгоритм може бути реалізований на підходящої машині Тьюринга. Обидва даних підходу, а також інші підходи (А.А. Марков, Е. Пост) призвели до одного і того ж класу алгоритмічно обчислюваних функцій і підтвердили доцільність використання тези Черча або тези Тьюринга для вирішення алгоритмічних проблем. p> Оскільки поняття рекурсивної функції строго математичне, то за допомогою математичного підходу можна довести, що вирішальна деяку задачу функція не є рекурсивної, що еквівалентно відсутності для даної задачі дозволяючого алгоритму. Аналогічно, відсутність роздільної машини Тьюринга для деякої задачі рівносильне відсутності для неї дозволяючого алгоритму. Зазначені результати складають основу так званої дескриптивної теорії алгоритмів, основним змістом якої є класифікація завдань за ознакою алгоритмічної розв'язності, тобто отримання висловлювань типу В«Завдання алгоритмічно розв'язнаВ» або В«Завдання алгоритмічно нерозв'язнаВ». p> У даному напрямку отримано ряд фундаментальних результатів. Серед них - негативне рішення в 1952 П.С. Новіковим класичної проблеми тотожності для звичайно певних груп, сформульованої Деном в 1912 році. Алгоритмічна нерозв'язність знаменитої десятої проблеми Гільберта, сформульованої ним серед інших 23 проблем в 1900 році. Завдання про можливість розв'язання диофантова рівняння. Нехай задано диофантово рівняння з довільними невідомими і цілими раціональними числовими коефіцієнтами. Вказати спосіб, за допомогою якого можливо після кінцевого числа операцій встановити, вирішуване Чи це рівняння в цілих раціональних числах В»), була доведена в 1970 році Ю.В. Мятіясевічем. p> У техніку термін В«АлгоритмВ» прийшов разом з кібернетикою. Поняття алгоритму допомогло, наприклад, точно визначити, що означає ефективно задати послідовність керуючих сигналів. Застосування ЕОМ послужило стимулом до розвитку теорії алгоритмів і вивченню алгоритмічних моделей, до самостійного вивчення алгоритмів з метою їх порівняння по робочих характеристик (числу дій, витраті пам'яті), а також їх оптимізації. Виникло важливий напрям у теорії алгоритмів - складність алгоритмів і обчислень (Колмогоров). Почала складатися так звана метрична теорія алгоритмів, основним змістом якої є класифікація завдань за класами складності. Самі алгоритми стали об'єктом точного дослідження, як і ті об'єкти, для роботи з якими вони призначені. У цій області, природно, виділяються задачі одержання верхніх і завдання отримання нижніх оцінок складності алгоритмів, і методи вирішення цих завдань абсолютно різні. p> Для отримання верхніх оцінок досить інтуїтивного поняття алгоритму. Для цього будується неформальний алгоритм вирішення конкретного завдання, після чого він формалізується для реалізації на підходящої алгоритмічної моделі. Якщо показується, що складність (час або пам'ять) обчислення для цього алгоритму вбирається значення підходящої функції при всіх значеннях аргументу, то ця функція оголошується верхньої оцінкою складності рішення розглянутої задачі. В області отримання верхніх оцінок отримано багато яскравих результатів для конкретних завдань. Серед них розроблені швидкі алгоритми множення цілих чисел, багаточленів, матриць, рішення лінійних систем рівнянь, які вимагають значно менше ресурсів, ніж традиційні алгоритми. p> Встановити нижню оцінку - Значить довести, що ніякої алгоритм обчислення не має складності меншою, ніж задана межа. Для отримання результатів такого типу необхідна точна фіксація розглянутої алгоритмічної моделі, і такі результати отримані тільки в дуже жорстких обчислювальних моделях. У зв'язку з цим отримала розвиток проблематика отримання В«відноснихВ» нижніх оцінок, так звана теорія NP -повноти, пов'язана з важкою вирішувана переборних завдань.
<...
