Лого на 91. НЕГ „Проф. Константин Гълъбов“

Модул 2 · Урок 1

Алгоритми

Откъде идва думата „алгоритъм“ и какви са шестте му характеристики. Масова задача и екземпляр, детерминираност, крайност. Представяне с ограничен естествен език.

Откъде идва думата

Понятието алгоритъм е основно за информатиката. То произлиза от името на средноазиатския математик Мохамед ибн Муса ал Хорезми (от град Хорезм, днес Хива в Узбекистан), роден около 780 г. и починал през 847 г. Той е автор на съчинението „За индийското смятане“, посветено на представянето на числата в десетичната бройна система и извършването на аритметични операции с тях.

Затова през Средните векове с думите algorismus или algorithmus са обозначавали правилата за извършване на операции в десетичната бройна система. Постепенно смисълът се разширява до съвременното си разбиране.

Ключово

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

Шестте характеристики

От речниковите описания на алгоритмите можем да извлечем следните основни техни характеристики:

№ХарактеристикаКакво значи
1Обекти и операцииЗа създаване на алгоритъм е необходимо множество от обекти и операции с тях — например естествените числа с аритметичните операции и сравняването.
2Задача върху допустими обектиЗадаваните обекти се наричат вход, а получаваните — резултат или изход.
3ПроцедураПоследователност от операции, която при изпълнение над входните данни на произволен екземпляр дава очаквания резултат.
4ДетерминираностКойто и да я изпълни над едни и същи входни данни, трябва да получи един и същ резултат.
5Краен брой стъпкиБроят прилагания на допустима операция определя бързодействието на алгоритъма.
6ЦиклиНякои последователности от операции може да се повтарят многократно — характерна черта на много алгоритми.

Масова задача и екземпляр

Масова задача

Задача, при която множеството от различните възможни входни данни може да е много голямо или дори безкрайно. Например: „намерете НОД на две естествени числа“.

Екземпляр на задачата

Масовата задача с фиксирани входни данни. Например: „дадени са числата 12 и 30, намерете техния НОД“.

Бележка

Разликата има значение. Задачата „намерете НОД на 30 и 12“ би могла да се реши и по друг начин, неприложим за други две зададени стойности — например като просто си спомним отговора. За такъв „алгоритъм“ не става дума.

Представяне с ограничен естествен език

Естествените езици не могат да бъдат използвани за описване на алгоритми заради възможността от неясно двусмислено изразяване. Описан на естествен език алгоритъм може да се окаже недетерминиран.

Не е невъзможно обаче алгоритми да се представят чрез ограничен естествен език, който следва някои ограничения, свеждащи до минимум възможните нееднозначности.

Три опита за решаване на A·X + B = 0

Опит 1 — изглежда работещ, но не е алгоритъм:

1. Въведи A
2. Въведи B
3. Пресметни X = -B/A
4. Изведи X
5. Край

Ако A = 0, стъпка 3 няма да може да се изпълни заради невъзможността да се дели на 0. Процедурата не е добре дефинирана — не успява да завърши при някои стойности на входните данни, и значи не е алгоритъм.

Опит 2 — добавена е проверка дали A = 0:

1. Въведи A
2. Въведи B
3. Ако A==0 премини_към 6
4. X = -B/A
5. Изведи X и премини_към 7
6. Изведи "Няма решение"
7. Край

Сега процедурата няма да спре аварийно при A = 0, но има друг дефект: ако A = 0 и B = 0, тогава всяка стойност на x е решение, а процедурата ще изведе невярното съобщение „Няма решение“.

Опит 3 — с още една проверка процедурата най-сетне става алгоритъм:

1. Въведи A
2. Въведи B
3. Ако A==0 премини_към 6
4. X = -B/A
5. Изведи X и премини_към 8
6. Ако B==0 изведи "Всяко число е решение" и премини_към 8
7. Изведи "Няма решение"
8. Край

Внимание

Забележи == в стъпка 3. В ограничения естествен език, както и в C#, знакът за равенство е зает за присвояване (стъпка 4), а за сравняване се използва двойното равенство.

Графично представяне

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

  • Блок-схемният език е използван много в зората на програмирането. Графичен е и позволява разклоненията и зациклянията да се представят по-лесно.
  • UML (чете се Ю Ем Ел) съдържа в себе си както всички възможности на блок-схемния език, така и много други, важни за професионалното програмиране. Днес в професионалните среди се използва все по-активно.

Елементите на UML диаграмите вече ги знаеш от Модул 1: блокове за начало и край, обработващ блок, блок за проверка на условие и свързващи блокове. На тях е посветен следващият урок.

Задачи

Упражнения

Задача 1. Обясни изискването алгоритъмът да е процедура за решаване на масова задача.

Задача 2. Защо кулинарните рецепти не са алгоритми?

Въпроси и задачи

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

2. Дай пример на процедура, която удовлетворява всички изисквания за алгоритъм освен изискването за: а) детерминираност; б) крайност; в) масовост; г) наличие на вход.

Съвет

Подсказка за задача 2: „бъркай, докато стане на каша“ не е детерминирано (кой колко бърка?), „щипка сол“ не е измеримо, а „пържи до златисто“ няма ясен край. Точно затова рецептите не са алгоритми.

Какво трябва да запомниш

  • Масовата задача има безкрайно много възможни входове; екземплярът е тя с фиксирани данни.
  • Детерминираност: едни и същи входни данни → един и същ резултат, независимо кой изпълнява.
  • Крайност: алгоритъмът трябва да завършва за краен брой стъпки за всеки допустим вход.
  • Процедура, която се чупи дори при един допустим вход, не е алгоритъм.
  • Естественият език е двусмислен — затова алгоритмите се пишат на ограничен естествен език или се рисуват.