1.
Същност на понятието алгоритъм
Решаването на задачи често пъти се свежда до формулиране на последователност от указания, с които се описват някакви действия. Такъв подход се нарича алгоритмичен, а системата от указания, с изпълнението на които се цели получаването на определен резултат – алгоритъм.
Понятието алгоритъм е основно за информатиката. То произлиза от името на арабския математик Абу Джафар Мохамед ибн Муса ал-Хорезми (780 г.– 847 г.) от град Хорезм, днес Хива в Узбекистан, който описал извършването на аритметични операции с арабски числа. Математическото му съчинение “За индийското смятане” е посветено на числата в десетична бройна система и извършването на аритметични операции. Затова в средните векове с понятието “алгоритъм” са обозначавали десетичната бройна система и правилата за извършване на операциите в нея.
Съчинението на Ал-Хорезми е преведено на латински език в средновековна Европа в началото на XII век, но разпространението на “изкуството да се смята” и ерата на ръчното и механизираното смятане започва едва през XVI век. По-късно съдържанието на понятието се разширява – като алгоритми започват да се разглеждат и известни по това време изчислителни процедури (вкл. и открити от математиката в по-стари времена).
С не по-малка популярност обаче се ползва древногръцкият математик Евклид, който в своята книга “Елементи” описва алгоритъм за намиране на най-големия общ делител на две числа.
Понятието алгоритъм добива съвременния си смисъл в работите на Рудолф (1525 г.) и Лайбниц (1684 г.): “систематичен изчислителен процес, който с краен брой стъпки решава определена задача”.
Алгоритми се използват от дълбока древност, за да се научат хората да изпълняват определени действия чрез по-прости (например да извършват аритметични действия с многоцифрени числа, да търсят път в лабиринт, да пресмятат лица на фигури, да подреждат списъци в азбучен ред). Когато се създадоха компютрите, които безпогрешно и бързо изпълняват прости действия, алгоритмите започнаха да се прилагат много широко, включително за много сложни действия като например управление на ракети.
Редица човешки дейности са алгоритмични по своята природа. В течение на своя живот човек научава и прилага много правила за поведение и действие в различни ситуации. Нещо повече – една голяма част от своето време човек изразходва, за да създава и научава или да прилага такива правила (пресмята в магазина, говори по телефона и т.н.)
Ще цитираме определенията за алгоритъм, които дават някои тълковни речници.
Речник на българския език, изд. БАН, том I, 1977: Система от правила, които определят последователност от изчислителни операции, прилагането на които води до решението на дадена задача. Алгоритъм на Евклид.
Larousse de la langue Francaise, Lexis, 1979: Съвкупност от правила или предписания за получаване с краен брой операции на определен резултат.
Webster’s New Colegiate Dictionary, 1980: Процедура за решаване на математически проблеми (например намиране на най-голям общ делител) с краен брой стъпки, която често съдържа повтарящи се операции.
Понятието алгоритъм е близко по смисъл до начин, метод, рецепта, способ, програма, предписание, инструкция. Разбира се, тези сродни понятия не са идентични. Всяко от тях има своя специфичност.
Ще разгледаме някои примери, наподобяващи алгоритми. Примерите са взаимствани от различни литературни източници.
Характерно за разгледаните примери е, че в тях се описва какво трябва да правим, за да получим определен резултат, за да извършим някое действие – хващане на лъв, правене на баница и т. н. Желаният резулта се достига след последователно изпълнение на по-прости действия. Предполага се, че изпълнителят не знае как да достигне крайния резултат, но може да върши определените действия, които водят до него.
В разгледаните примери тези действия не винаги са точно определени. Говори се например за “2-3 яйца”, за “1-2 супени лъжици вода” и т.н. Следователно резултатът ще зависи от избора, който ще направи изпълнителят. Понякога указанията са недостатъчни и неясни. Някои от примерите съдъжат излишна информация, която не е необходима за достигане на крайния резултат
Алгоритъмът е система от указания, които определят последователност от елементарни действия, изпълнението на които осигурява решаването на коя да е задача от определен тип. Системата от указания се изразява чрез някакъв език – естествен, чрез блок-схема или друг изкуствен език.
Примери за алгоритми в точния смисъл на думата:
Алгоритъм на Евклид за намиране на най-големия общ делител на две естествени числа.
Предполага се, че дадените числа са първоначални стойности на променливите a и b.
1. Ако a>b, изпълнете т. 4, в противен случай изпълнете т. 2.
2. Ако а=b, изпълнете т. 5, в противен случай изпълнете т. 3.
3. Пресметнете разликата b-a и за в бъдеще считайте, че b има стойността на тази разлика. Изпълнете т. 1.
4. Пресметнете разликата a-b и за в бъдеще считайте, че a има стойността на тази разлика. Изпълнете т. 1.
5. Съобщете последната стойност на а – това е търсеният най-голям общ делител на а и b. Изпълнете т. 6.
6. Прекратете изпълненето на алгоритъма.
В таблицата са използувани две съкращения.
Стрелката “→”означава “преминава се към изпълнение на т”.
Знакът „ := " се нарича знак за присвояване на стойност.
Така изразът х:=5 означава, че х получава стойност 5, докато x=5 означава, твърдението, че х има стойност 5.
Това твърдение има две вярностни стойности — „истина" и „неистина". х:=х+1 означава, че новата стойност, която се присвоява на х, е с единица, по-голяма от предишната. С други думи, стойността на х се увеличава с 1.
Така определеното понятие е разгледано достатъчно подробно, ясно и задълбочено и формира добра интуитивна представа за алгоритъма. На интуитивното понятие алгоритъм математиката поставя в съответствие и формално определение, което е значително по-точно.
Съществуват няколко формални теории, свързани с понятието алгоритъм. Те определят това понятие с методите на математиката, т.е. определението се основава или на други понятия, имащи математически определения, или на първични понятия, които се приемат без определение.
Една от теориите се базира на рекурсивните функции.
Друга, създадена от английския математик А. Тюринг, се основава на въображаемо устройтво, известно като “машина на Тюринг”.
Трета теория е създадена от Марков, който въвежда понятие “нормален алгоритъм”. Доказано е, че в теоретично отношение всички те са еквивалентни.
Тук ще разгледаме една от формалните теории, създадена от американския математик Е. Пост.
Чрез формалната система на Пост се уточнява понятието алгоритъм. Но това уточнение не обхваща всички алгоритми, а само едно тясно подмножество и то не е предназначено да удовлетворява практическите нужди.
Формалното определение на понятието алгоритъм е дал А. М. Тюринг, чрез така наречената универсална машина на Тюринг, А. А. Марков, Джон фон Нойман и др.
Може да се докаже, че дадените от тях определения са еквивалентни, т.е., че по същество представят едно и също понятие.
2. Свойства на алгоритмите
Най-важен елемент на всяка компютърна програма е нейният алгоритъм. От описания алгоритъм на Евклид могат да се забележат някои особености, които са характерни за всички алгоритми.
Входни данни
В описанието на всеки алгоритъм се използват величини. Едни от тях са константи, а други – променливи. Преди да се използват, променливите величини трябва да получат стойности, наречени начални стойности. Някои от променливите получават началните си стойности в рамките на описанието на самия алгоритъм. Други променливи получават своите начални стойности като входни данни, т.е. по време на изпълнението на алгоритъма. Така тези променливи играят ролята на параметри на алгоритъма. В алгоритъма на Евклид те са естествените числа, които променливите М и N получават като стойности. Има случаи, при които множеството от входните данни на някои алгоритми е празното множество.
Изходни резултати
С изпълнението на всеки алгоритъм се цели получаване на определен резултат. Най-често този резултат е крайна стойност на някои от използваните в алгоритъма величини. Естествено тези крайни стойности зависят от началните стойности, т.е. от входните данни. Изходният резултат в алгоритъма на Евклид е крайнта стойност на променливата а (или b).
Понятието алгоритъм има няколко основни характеристики, на които ще се спрем по-подробно.
1. Нека е зададено множество от обекти и съвкупност от операции с тези обекти. Обикновено това са математически обекти и операции с тях. Например за естествените числа това са аритметичните операции и сравняването; за съждителните формули – конюнкцията, дизюнкцията и отрицанието и т.н. Когато става дума за нематематически обекти, често срещан подход е подходящото им заместване с математически, т.е. създаване на математически модел, затова тук ще се ограничим само с обекти от математиката.
2. След като е зададено множество от обекти и операции с тях, интерес представляват задачите за тези обекти, които могат да бъдат решавани само с помощта на избраните операции. В общия случай тези задачи изглеждат така: „Дадени са някои обекти от избраното множество. Само с прилагане на избраните операции намерете обекти от множеството, имащи зададени свойства и зависещи по някакъв начин от зададените обекти.” В едно от определенията се посочва една такава задача за естествени числа - намиране на най-голям общ делител (НОД) на две естествени числа. Това е задачата: „Дадени са две естествени числа А и В, различни от 0. Намерете най-голямото естествено число С, което дели без остатък както А, така и В. Допустими са аритметичните операции и сравняването на естествени числа.” Такива задачи ще наричаме масови задачи. Задаваните обекти се наричат входни данни (или просто вход), а получаваните обекти - изходен резултат (или просто изход). Входните данни на масовата задача „намиране на НОД” са произволни две естествени, различни от 0 числа, а изходният резултат е естествено число с предписаните свойства. Ако фиксираме входните данни, получаваме конкретна задача. Например: „Дадени са числата 12 и 30. Намерете НОД.”
3. Алгоритъмът е процедура за решаване на дадена масова задача, т.е. за произволна конкретна задача той намира съответния изход. Алгоритъмът трябва да е съставен така, че безусловно да определя последователност от операции, която при изпълнение над входните данни на произволна конкретна задача дава очаквания резултат.
Процедурата трябва да е детерминирана - който и да я изпълни над едни и същи входни данни, тя трябва да дава един и същ резултат. Споменатият в едно от определенията алгоритъм на Евклид е точно такава процедура за намиране НОД на две естествени числа.
4. Важна характеристика на процедурите, които наричаме алгоритми, е, че те дават решение в краен брой стъпки, т.е. с прилагане краен брой пъти на допустими операции. Нещо повече, в общия случай този брой може да бъде намерен предварително или поне да бъде оценен достатъчно точно, като се знаят входните данни. Този брой определя сложността на алгоритъма. Не е изключено за една масова задача да бъдат построени няколко алгоритъма, които се различават по сложността си. Добре би било да можем да избираме в такива случаи най-добрия алгоритъм.
5. Не случайно в една от дефинициите е подчертано, че в процедурата, наречена алгоритъм, е възможно някои последователности от операции да бъдат повтаряни многократно.Такива повторения се наричат цикли.
Често създаването на алгоритъм се състои в определяне на подходяща последователност от операции, която да бъде повторена в цикъл многократно (над променящи се данни). Може да се каже, че организирането на цикли е същностна черта на процеса на създаване на алгоритми.
Да обобщим:
Алгоритмите притежават следните важни свойства.
1. Определеност – описанието на алгоритъма е ясно и не съдържа двусмислици. То определя еднозначно действията, които трябва да се извършат. При определени данни (стойности на външните величини) алгоритъмът довежда до един и същ резултат, независимо от това кой е изпълнителят. Определеността позволява алгоритмите да бъдат изпълнявани от широк кръг изпълнители. Всяко едно от указанията в алгоритмите трябва да бъде записано по начин, недопускащ двусмислие. Това е причината, поради която естествените езици не са подходящи за описание на алгоритми.
2. Масовост – приложимост на алгоритъма за различни данни. Така например алгоритъмът на Евклид позволява да се намери най-големият общ делител на кои да са две естествени числа, докато при готварската рецепта, както изобщо и при всяка технология, началните продукти са фиксирани по вид и количествата им трябва да се намират в определени пропорции.
Ефективността от прилагането на алгоритмите се дължи на тяхната масовост. Благодарение на нея един алгоритъм може да се прилага многократно в различни случаи.
Масовостта не означава, че даден алгоритъм може да се прилага при какви да е данни. Всеки алгоритъм може да се прилага за определен клас данни, които ще наричаме допустими за алгоритъма.
3. Резултатност – завършване работата на алгоритъма за крайно време. Това свойство на алгоритмите позволява те практически да бъдат прилагани. Крайното време за изпълнение на алгоритъма е следствие от предположението, че всеки алгоритъм се състои от краен брой стъпки и че всяка стъпка (всяко елементарно действие) се изпълнява за крайно време.
И все пак трябва да си даваме сметка, че крайният брой действия, необходими за изпълнение на даден алгоритъм, не означава непременно, че алгоритъмът е практически изпълним. Така например съществува алгоритъм (изискващ краен брой действия), чрез който може де се установи дали играещият на шах с белите фигури може да спечели дори в случая, когато противникът му винаги избира най-добрите отговори. Този алгоритъм изисква проследяването на повече от 10200 варианта.
Всеки алгоритъм трябва да бъде определен по такъв начин, че независимо от конкретните начални данни изходните резултати да могат да се получават след краен брой изпълнения на указанията (стъпки), съставящи алгоритъма. Лесно може да се докаже, че определянето на най-големия общ делител на две естествени числа е краен изчислителен метод, т.е. алгоритъм. Не всеки изчислителен метод е краен.
4. Ефективност
За ефективността на всеки алгоритъм се поставя изискването указанията и операциите да бъдат достатъчно прости, т.е. елементарни за конкретния изпълнител, така че да са изпълними за крайно време. За такива указания се казва, че са ефективни.
Делението на две естествени числа е пример за ефективно указание. Делението обаче на две произволни реални числа, представени като безкрайни десетични дроби, не е ефективна операция.
И така, най-общо всеки алгоритъм определя изчислителна процедура, която може да се опише с четворката (D, I, R, f), където
D – множество от допустимите стойности на използваните величини;
I – множество от входните данни, ;
R – множество от крайните резултати f – правило за преобразуване на входните данни в изходни резултати.
Броят на елементите, получени чрез правилото f, може да е краен или безкраен. В този смисъл съответната изчислителна процедура може да е крайна или безкрайна. Само крайните изчислителни процедури са алгоритми.
Тъй като за много математически задачи може да се посочи повече от едно решение, така и за много задачи, които се свеждат до съставяне на алгоритми, като решение може да се намери повече от един алгоритъм. Следователно естествено е да се постави въпросът за сравняване на алгоритми.
Изборът на един измежду няколко алгоритъма, решаващи една и съща задача, ще зависи от техните качествени показатели. Като един от най-важните качествени показатели на алгоритмите се приема времето, необходимо за тяхното изпълнение.
5. Цикличност – възможност за описване на алгоритми така, че групи от указания да се изпълняват многократно при евентуално изменение на някои участващи в указанията величини. Цикличността позволява чрез малък брой указания да бъдат описани алгоритми, изпълнението на които при някои начални данни изисква значителен брой стъпки.
Без използването на цикли някои задачи стават алгоритмично неразрешими. Такава е например задачата да се намери сумата a1+a2+…+an, ако броят на числата n не е известен при написването на алгоритъма, а ще бъде зададен непосредствено преди изпълнението му.
Да обобщим казаното за понятието алгоритъм:
Нека е зададено множество от обекти и крайна съвкупност от допустими операции с тези обекти, като всяка операция дава точно определен резултат от същото множество.
Алгоритъмът е процедура за решаване на масова задача над зададените обекти, която детерминирано, в краен брой стъпки, започвайки от конкретни входни данни и прилагайки допустимите операции довежда до искания резултат.
Примери за алгоритмични процедури:
По зададено крайно множество да се намери естественото число, което му съответства в Р-ична бройна система;
Да се намери сумата (разликата, произведението) на две естествени числа в Р-ична бройна система;
Да се сравнят по големина две естествени числа в Р-ична бройна система;
Да се преобразува зададено число от една бройна система в друга;
3. Роля на алгоритмите
Ролата на алгоритмите както в ежедневния живот, така и в науката и техниката е твърде голяма. Ние знаем, че техниците, инженерите, конструкторите, архитектите, лекарите, счетоводителите и много други специалисти използват специални справочници, които в значителната си част представляват сборници от алгоритми. По тези причини алгоритмите се явяват ръководство за действие при решаването на проблеми и следователно средство, позволяващо да се икономисва умствен труд.
Алгоритмите са подходяща и удобна форма за излагане на научни резултати – съществуват редица списания, в които във вид на алгоритми се печатат съобщения за различни новооткрити методи главно в областта на математиката.
Поради това, че съвременните компютри могат да изпълняват алгоритми, то всяка дейност, свързана с автоматизация на информационните дейности, предполага предварително да се създават подходящи алгоритми, т.е. те са необходимо звено на автоматизацията.
Голямото значение на алгоритмите обуславя интереса към тях. Специалистите от всеки отрасъл на науката и техниката търсят алгоритми за решаване на различни задачи както за непосредствено приложение в практиката, така и за развитието на науката.