Алгоритми

Алгоритми, интуитивни понятия

Решенията на задачи с помощта на компютърна система, може да се сведе до краен набор от елементарни дискретни действия (аритметични и логически), наречени интуитивно алгоритъм. Дискретният характер на алгоритъма се определя от стъпките, които водят до решението на поставената задача. Важно за алгоритъма е последователността на дискретните стъпки (действия) и условията, при които те се изпълняват.

С помощта на компютрите могат да се решават всякакви информационно-изчислителни задачи, но за целта стъпките, включени в алгоритъма за решаването им, трябва да бъдат еднозначни и да изключват възможността от различно тълкуване (логическа противоречивост или неопределеност) при изпълнение.

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

Класическото понятие за алгоритъм отразява само един доста ограничен клас от процеси, свързани с последователна обработка на информацията и при това без връзка с външния свят, т.е. автономни процеси. Изясняването на класическия интуитивен алгоритъм обаче има голямо методическо значение за разбирането на алгоритмизацията като процес за отразяване на системите с паралелна обработка на информацията, управление в реално време, входни въздействия от външни среди и др. Там за алгоритмите се използуват и други средства за описание - например, мрежи на Петри, модели от типа събитие-условие, паралелно програмиране и т.н

Описание на алгоритмите

Действията на човека по разкриване и привеждане в изпълнение на всички изисквания, насочени към решаване на конкретна задача с компютър, се наричат алгоритмизация.

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

• на естествен език (чрез словесно описание) и
• на изкуствено създаден език (чрез блокови схеми, псевдокод и др. изкуствени реализации).

Словесно описание

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

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

Изкуствени езици

Вторият начин за описание на алгоритми, намира по-широко приложение в практиката. По БДС описанието на алгоритъма се извършва с функционални блокове (Flowchart, Flowdiagram), които след подреждане по последователността на действията образуват т.нар. блокови схеми. Блоковите схеми на алгоритмите се четат по правилата за четене в естествените езици, а именно отгоре-надолу и отляво-надясно. Вътре в блоковете и вдясно до тях могат да се включват доизясняващи текстове, написани на естествен език (т.е. на български език). Този подход е много по-прецизен и не допуска двузначно тълкувание.

Почти винаги решенията на практически задачи налагат използуването на съвременни алгоритмични и програмни средства. При тях за описание на конкретните програмни оператори и информационни системи понякога се прилагат т.нар. метаезици (например метаезик на Бекус-Наур, синтактични и семантични диаграми и др.) Това са формални езици със синтаксис и семантика, различни от тези на алгоритмичните и програмните езици. Например, синтаксисът на метаезика чрез синтактични диаграми се изразява чрез блокове, които се "разчитат" при обхождане на диаграмата от входа до изхода й по всички допустими пътища, посочени със стрелки. Най-широко са разпространени синтактичните диаграми със следните блокове в тях: kryg, oval, kvadrat

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

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

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

ОПРЕДЕЛЕНОСТ

(детерминираност) - свойство, което гарантира еднозначно тълкуване от разработчика и изпълнителите на включените в алгоритъма елементарни действия. Всяка алгоритмична стъпка, включена в алгоритъма, трябва да бъде еднозначно определена във времето и пространството. Това свойство гарантира възможността за повтаряемост на алгоритмите при решаване на сродни задачи;

ДИСКРЕТНОСТ

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

РЕЗУЛТАТНОСТ

свойство, отразяващо необходимостта алгоритъмът да води винаги до крайно решаване на проблема в определен срок (най-често свързан с жизнения цикъл на компютъра). Когато условията на задачата или входните данни не водят до конкретен резултат в определения срок, алгоритъмът трябва да съдържа действие, чрез което да се сигнализира за това особено състояние;

МАСОВОСТ

свойство, което е следствие на изискването всеки разработен алгоритъм да има определена универсалност, т.е. да решава определен клас от задачи, да не зависи от конкретен набор входни данни и да не е свързан с конкретен компютър. Масовостта определя по-високата ефективност на алгоритъма;

ЦЕЛЕСЪОБРАЗНОСТ

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