Алгоритми
от Българският сайт за математика
Думата алгоритъм произхожда от името на арабския математик Мохамед ибн Муса Алъхверизми или съкратено Ал-Хорезми, живял през IX век и формулирал правилата за извършване на аритметичните действия с естествени числа, записани в десетична бройна система. По-точно, думата алгоритъм е произлязла от записа на името на този математик на латински - Algorismus.
Както е известно, математиката отразява различни страни на обективната реалност, в това число и на човешката дейност. Алгоритмичният аспект на тази дейност става предмет на активното математическо изследване преди около 50 години. Той се изразява във факта, че много неща от човешката практика могат да се извършат посредством стриктно изпълнение на последователност от точни указания, без да е необходимо изпълнителят да проявява творчество.
Понятието алгоритъм може да се въведе интуитивно (чрез описателно определение (или формално) чрез строги дефиниции). Ние ще приложим първия подход, т.е. за понятието алгоритъм ще дадем следното описателно определение:
Система от указания, която определя последователност от елементарни действия, изпълнението на които осигурява решаването на коя да е задача от определено множество задачи или води до постигане на опредлен резултат, се нарича алгоритъм.
В даденото определение се използва понятието "елементарно действие". Под това понятие ще разбираме онова действие, което изпълнителят може да извърши правилно, без да се нуждае от допълнителни обяснения и помощ. Това означава, че то трябва да е добре познато на изпълнителя и че той може да го извърши механично, т.е. без влагане на творчество и съобразителност. Тогава алгоритъмът, съгласно даденото определение, може да се рзглежда и като разлагане на дадено действие на последователност от по-прости "елементарни действия".
Голяма част от човешките знания се отнасят до определяне последователността от действия, които трябва да се извършват, за да се получи желан резултат. Но изпълнението на тези действия предполага специална подготовка на изпълнителя. Подобни знания в практиката се наричат с различни имена - инструкции, предписания, рецепти, технологии и др. Чрез тях се обобщава човешкият опит и той може да се разпространява сред хората и да се предава на следващите поколения. Трябва да се има в предвид обаче, че въпреки наличието на сходни черти, никое от тези понятия не е идентично с понятието алгоритъм.
Елементарните действия, които се използват в алгоритмите, трябва да са достатъчно прости и да са широко известни, за да могат да се изпълняват от различни изпълнители без специална подготовка, а така също и от автоматични устройства. Също така те трябва да са малко на брой, но да дават възможност да се съставят алгоритми за решаване на разнообразни задачи.
Пак съгласно даденото определение, алгоритъмът е система от указания. Тъй като всяко негово изпълнение води до решаването на определена задача, то броят на тези указания трябва да бъде краен. Освен това, тъй като тези указания определят някаква последователност от елементарни действия, те могат да се номерират, т.е. ще има едно указание, което е първо, ще има указание, което е след него и т.н., ще има указание, което е последно. Указанието, което се изпълнява след определено указание, се нарича негов наследник.
Указанията, които влизат в един алгоритъм, са няколко вида. Основни са така наречените безусловни указания. Това са тези, които определят точно едно елементарно действие и имат един наследник. Указания, които имат повече от един наследник (обикновено два), се наричат условни. Към кой наследник трябва да се тръгне зависи от това дали указанието с тези наследници е изпълнено или не. Освен посочените видове има указания за прекратяване или започване на работата по алгоритъма. Тези от първия вид нямат наследник, а тези от втория - не са наследник на никое указание.
Характерни особености, които могат или трябва да имат алгоритмите, са следните:
а) Определеност - отразява точността и общоразбираемостта на алгоритмите. Наличието й означава, че повторното изпълнение на алгоритъма със същите начални данни, от кой да е изпълнител, води до същите резултати.
б) Масовост - изразява факта, че алгоритъмът служи за решаване на цял клас еднотипни задачи.
в) Резултатност - гарантира, че изпълнението на алгоритъма при произволни допустими начални данни води до определен резултат. Това означава, че броят на указанията, които влизат в него, трябва да е краен и времето за тяхното изпълнение също трябва да е крайно.
г) Дискретност - означава, че всеки алгоритъм се състои от краен брой елементарни действия, които се изпълняват едно след друго, на стъпки, т.е. всяко елементарно действие има свой логически наследник.
д) Разклонимост - последователността, в която се изпълняват елементарните действия, може да зависи от началните данни или от получени междинни резултати. Това означава, че съдържащите се в указанията условия могат да предизвикват при различни начални данни различни последователности от елементарни действия.
е) Цикличност - отразява възможността за организиране с условни указания многократното изпълнение на групи от елементарни действия в един и същ ред, преди да премине към изпълнение на следващо елементарно действие.
За изразяване на алгоритмите обикновено се използват 3 начина.
1. Чрез естествен (книжовен) език. При този начин отделните указания се записват на книжовен език, като за съкратено записване, наред с математическите символи, се използват и следните два: ":=" и "->". Първият от тях се нарича "знак за присвояване (даване) стойност на променлива", а вторият се използва вместо израза: "изпълнете указание". Например, записът b := b-a, -> 1 означава "на променливата b присвоете стойност b-a, изпълнете указание 1".
Изразяването на алгоритми с естествен книжовен език има два съществени недостатъка:
а) Някои текстове на книжовен език могат да предизвикат различни тълкувания.
б) Естественият език е неразбираем за изпълнител машина. Избягването на този недостатък е сложно и скъпо.
2. Чрез алгоритмичен език. Алгоритмичните езици са създадени специално за описване на алогритми. Те се характеризират със строги граматически правила, недопускащи никакви изключения. В тях не съществуват конструкции, които могат да се тълкуват двусмислено. Има създадени алгоритмични езици с различно предназначение и различни възможности. Най-разпространени са езиците Фортран, Кобол, Алгол и ПЛ/1.
3. Чрез блок-схема. Всяка блок-схема се състои от блокове и връзки между тях. Блоковете представляват геометрични фигури (най-често правоъгълници и ромбове), в които са записани съответните указания, като се използват посочените по-горе символи и думи на естествения език. Връзките между блоковете се изразяват чрез стрелки.
Всяка блок-схема съдържа един начален блок, който посочва откъде започва изпълнението на алгоритъма, и един краен блок (или няколко), който показва, че алгоритъмът завършва. Началните и крайни блокове имат овална форма. Блоковете, които съответстват на безусловни указания, имат правоъгълна форма, тези, които съответстват на условни указания - ромбовидна форма.
Като пример за изразяване на алгоритъм по трите начина ще дадем алгоритъма на Евклид за намиране на най-голям общ делител на числата a и b.
a) Чрез естествен език.
1. Ако a > b, -> 4; иначе -> 2.
2. Ако a = b, -> 5; иначе -> 3.
3. b := b-a, -> 1.
4. a := a-b, -> 1.
5. Съобщете последната стойност на a - това е търсеният най-голям общ делител на a и b, -> 6.
6. Прекратете работата.
Например, ако a = 10 и b = 15, то определянето на най-големия общ делител на a и b чрез прилагане на дадения алгоритъм е следното:
10 > 15 - не;
10 = 15 - не;
b := 15 - 10 = 5;
10 > 5 - да;
a := 10 - 5 = 5;
5 > 5 - не;
5 = 5 - да.
Най-големият общ делите на 10 и 15 е 5.
б) Чрез езика Фортран.
1. IF(A-B) 4, 6, 2
2. A = A-B
3. GOTO 1
4. B = B-A
5. GOTO 1
6. WRITE (7) A
7. FORMAT (15)
STOP
Отделните указания при езика Фортран се наричат оператори. Оператор 1 означава, че в зависимост от това дали A-B = 0, трябва да се изпълни оператор 4, 6 или 2; оператор 2 означава, че на A трябва да се присвои стойност A-B; оператор 3 означава "премини на оператор 1"; оператор 6 означава, че трябва да се отпечата (нашише) стойността на A в съответствие с посочения в оператор 7 формат, т.е. че A трябва да се отпечата като цяло число, заемащо най-много 5 позиции.
в) Чрез блок-схема.
