Формализиране на понятието алгоритъм
Глава III. Теория на алгоритъма
Понятието "алгоритъм" принадлежи към основните понятия на математиката и заема едно от централните места в изчислителната математика.
Още през 9 век арабският учен Мохамед бен-муса ал-Хорезми разработва система от правила за четири аритметични операции с числа в десетичната позиционна бройна система. Тези правила предписват строга последователност от действия върху първоначалните данни - числа, за да се получи желаният резултат - число. Тези правила са наречени „алгоритъм“ след арабското име al-Khwarizmi.
До 20-те години на миналия век концепцията за алгоритъм се намира в математическата литература само в контекста: за решаване на разглеждания проблем има алгоритъм, състоящ се от следната последователност от действия - направете това, след това и така нататък и ще получите желания резултат. С други думи, по това време те използват интуитивното определение на алгоритъма: алгоритъм Представлява ли общ, единен, точно установен начин за решаване на всеки проблем от даден масов проблем - безкраен брой подобни задачи.
По този начин алгоритъмът винаги е свързан с решаването на масов проблем. Задачите от този клас се различават помежду си по стойностите на техните параметри. Примери за алгоритми: извличане на квадратен корен, изчисление на производни, намиране на цикъла на Ойлер в графика на Ойлер и др. Дадената дефиниция на алгоритъма не е строга, тъй като съдържа думи, чието точно значение не е установено, например "метод". Въпреки това, дори и с тази дефиниция, могат да се разграничат някои характерни черти на алгоритъма:
1. Дискретност. Алгоритъмът се състои от отделни елементарни действия, изпълнявани на стъпки.
2. Детерминизъм. Между всички стойности, получени от алгоритъма, има силна причинно-следствена връзка. Всяка следваща стойност се получава от стойностите на предишните според определен, обикновено прост закон.
3. Масов характер. Началната система от стойности се избира от определен набор. Първоначалните условия могат да варират безкрайно.
4. Ефективност (конвергенция). Задължително е да се спре алгоритмичният процес след краен брой стъпки, като се посочи постигнатият структурен обект под формата на желания резултат.
В съвременната математика различни конструктивни обекти на математиката са се превърнали в изходни данни и резултати от работата на алгоритъма: числа и полиноми, матрици и графики, думи и текстове. Тези структурни обекти се формират според определени правила от елементарни обекти. Трансформацията на структурен обект, която се случва в една стъпка, е от локално естество, тоест не се трансформира целият обект, а само част от него: колона или ред от матрица, фрагмент от графика, част на дума или текст и др. Извиква се процесът на трансформиране на структурен обект, който включва дадена последователност от стъпки алгоритмичен процес.
Интуитивната концепция на алгоритъма работи, когато става въпрос за намерения алгоритъм за решаване на конкретен проблем. Ситуацията се променя значително, ако възникне алгоритмичен проблем, чието решение не е намерено и се изисква да се установи дали има решение. В този случай е необходимо да се докаже или съществуването на алгоритъма, или липсата му. Първото може да се направи, като всъщност се опише процесът, който решава проблема. В този случай интуитивното понятие за алгоритъм е достатъчно, за да се увери, че описаният процес е алгоритъм. Невъзможно е да се докаже несъществуването на алгоритъма по този начин. Това изисква точна формална дефиниция. Нямаше такова определение до средата на тридесетте години на ХХ век. Тогава, почти едновременно, редица математици предложиха няколко дефиниции на алгоритъма (с други думи, формализиране на понятието алгоритъм).