1. Визначення алгоритму
Слово алгоритм містить у своєму складі перетворене географічна назва Хорезм. Термін В«алгоритмВ» зобов'язаний своїм походженням великому вченому середньовічного Сходу - Муххамад ібн Муса ал-Хорезмі (Магомет, син Мойсея, з Хорезма). Він жив приблизно з 783 по 850 роки, і в 1983 році відзначалося 1200-річчя з дня його народження в місті Ургенчі - обласному центрі сучасної Хорезмськой області Узбекистану. У латинських перекладах з арабської арифметичного трактату ал-Хорезмі його ім'я транскрибовано як algorismi. Звідки і пішла слово В«алгоритмВ» - спочатку для позначення алгоритмів цифрових обчислень десяткової позиційної арифметики, а потім для позначення процесів, в яких шукані величини розв'язуваних завдань знаходяться послідовно з вихідних даних за певними правилами та інструкціями.
У всіх сферах своєї діяльності, і особливо в сфері обробки інформації, людина стикається з різними способами або методиками вирішення завдань. Вони визначають порядок виконання дій для отримання бажаного результату - можна трактувати це як початкове або інтуїтивне визначення алгоритму. Деякі додаткові вимоги призводять до неформального визначенню алгоритму.
Алгоритм - це заданий на деякій мові кінцеве припис, що задає кінцеву послідовність здійсненних елементарних операцій для вирішення завдання, загальне для класу можливих вихідних даних. Нехай D - область (безліч) вихідних даних завдання, а R - безліч можливих результатів, тоді ми можемо говорити, що алгоритм здійснює відображення D в†’ R. Оскільки таке відображення може бути не повним, то вводяться такі поняття: алгоритм називається частковим алгоритмом, якщо ми отримуємо результат тільки для деяких, і повним алгоритмом, якщо алгоритм отримує правильний результат для всіх.
Незважаючи на всі зусилля дослідників, відсутнє одне вичерпно суворе визначення поняття В«АлгоритмВ». Тому в теорії алгоритмів були введені різні формальні визначення алгоритму. При цьому дивним науковим результатом є доказ еквівалентності цих формальних визначень у розумінні їх рівнопотужності.
Варіанти словесного визначення алгоритму належать російським вченим О.М. Колмогорову і А.А. Маркову. p> Алгоритм за Колмогорова - це всяка система обчислень, виконуваних за суворо визначеними правилами, яка після якого-небудь числа кроків завідомо призводить до вирішення поставленого завдання.
Алгоритм за Маркову - це точне розпорядження, що визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.
Слід зазначити, що різні визначення алгоритму, в явній або неявній формі, постулюють наступний ряд вимог:
- алгоритм повинен містити кінцеве кількість елементарно здійсненних приписів, тобто задовольняти вимогу кінцівки запису;
- алгоритм повинен виконувати кінцеве кількість кроків при вирішенні завдання, тобто задовольняти вимогу кінцівки дій;
- алгоритм повинен бути єдиним для всіх допустимих вихідних даних, тобто задовольняти вимогу універсальності;
- алгоритм повинен призводити до правильного по відношенню до поставленого завдання рішенням, тобто задовольняти вимогу правильності.
Аж до 30-х років минулого століття поняття алгоритму залишалося інтуїтивно зрозумілим і мало швидше методологічне, а не математичне значення. До початку ХХ століття багато яскравих прикладів дала алгебра і теорія чисел. Серед них можна згадати алгоритм Евкліда знаходження найбільшого загального дільника двох натуральних чисел або двох цілочисельних многочленів, алгоритм Гауса рішення системи лінійних рівнянь над полем, алгоритм знаходження раціональних коренів многочленів одного змінного з раціональними коефіцієнтами. До них також можна віднести алгоритм Штурма визначення числа дійсних коренів многочлена з дійсними коефіцієнтами на деякому відрізку дійсних чисел, алгоритм розкладання многочлена одного змінного над кінцевим полем на Непріводімие множники. Зазначені алгоритмічні проблеми вирішені шляхом зазначення конкретних дозвільних процедур. Очевидно, що для отримання результатів такого типу досить поняття алгоритму в інтуїтивної інтерпретації, тобто в судження не алгорітмізірованних, а заснованих на особливій проникливості, що дозволяє вгадувати правду. Досить докладно про це пише Р. Пенроуз у своїх роботах В«Новий розум короляВ» і В«Тіні розумуВ». p> Однак на початку ХХ століття були сформульовані алгоритмічні проблеми, позитивне вирішення яких уявлялося малоймовірним. Вирішення таких проблем зажадало залучення нових логічних засобів. Адже одна справа довести існування дозволяючого алгоритму - це можна зробити, використовуючи інтуїтивне поняття алгоритму. Інше справа - довести відсутність алгоритму - для цього потрібно знати точно, що таке алгоритм.
Початковою точкою відліку сучасної теорії алгоритмів можна вважати роботу німецького математика Курта Геделя (1931 рік - теорема про неповноту символічних логік),...
