Алгоритми - същност, свойства и видове

1. Понятие

 

Алгоритъм представлява всяко точно и еднозначно описана крайна последователност от действия над определени входни данни, която винаги води до резултат, който е във функционална зависимост от стойностите на входните данни.

Ако така описаната последователност завършва не винаги, а само за определена област от стойности на входните данни, такъв алгоритъм се нарича частичен алгоритъм или процедура.

2. Свойства на алгоритмите

Свойства на алгоритмите - презентация

1. Дискретност – всеки алгоритъм трябва да се състои от отделни, разграничени по време една от друга стъпки, всяка от които се извършва за крайно време.
2. Детерминираност – Резултатът от действията върху данните и посочването на следващата стъпка трябва да бъдат еднозначно определени от действията, извършвани в текущия момент.
3. Масовост – процедурата трябва да дава резултат на за краен брой съчетания на входните данни, а за едно потенциално безкрайно множество от входни данни.
4. Резултатност – процедурата трябва винаги да дава резултат, ако входните данни принадлежат на допустимото подмножество.
5. Крайност – процедурата трябва да завършва с резултат за краен брой стъпки.

Пример: Алгоритъм на Евклид за намиране на най-големият общ делител на две цели положителни числа p и q.

Описание:

Входни данни: p и q, p>0 и q>0;

Резултат: да се намери най-големият общ делител на p и q;

Процедура:

стъпка1: r = остатъка от p/q;

стъпка2: Ако r = 0, се предполага, че делителя е равен на q и край. В противен случай p = q, q = r и се преминава към стъпка1.

3. Видове алгоритми

Според последователността на действията, които се изпълняват алгоритмите биват:

1.      Линейни – характеризират се с последователен ред на изпълнение на действията, който винаги е един и същ, независимо от набора данни, за които се прилага.

Пример: Да се определи обиколката на триъгълник със страни a, b и c.

Входни данни: a, b и c, a>0, b>0, c>0;

Резултат: P – обиколка;

Процедура:

стъпка1: задава се стойност за a;

стъпка2: задава се стойност за b;

стъпка3: задава се стойност за c;

стъпка4: P = a+b+c;

2. Разклонени – В практиката често присъстват ситуации, при които трябва да се вземе решение и да се изпълни едно или друго действие. За да се отразява по-точно действителността и да се описва се налага въвеждането на разклонени алгоритми. Разклонението дава възможност да се избере една от две възможности за продължаване на изчислителния процес.

Пример: Деление на две числа x и y.

Величини: x, y;

Резултат: z;

Действия:

стъпка1: задава се стойност за x;

стъпка2: задава се стойност за y;

стъпка3: Ако y = 0 делението е невъзможно. В противен случай z = x/y.

3. Циклични – Тези при които една стъпка или група от стъпки се изпълняват многократно.

Пример: Намиране на сумата на числата от 1 до 100.

Данни: Целите числа от 1 до 100 и br;

Резултат: S – сумата;

Действия:

стъпка1: S = 0;

стъпка2: br = 1;

стъпка3: S = S+br;

стъпка4: Ако стойността на брояча е по.малка или равна на 100, стойността на брояча се увеличава с еденица и се преминава към стъпка3. В противен случай - край;