Алгоритми

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ДИСКРЕТНОСТ

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

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

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

МАСОВОСТ

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

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

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

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

Разработката на алгоритми за решаване на практически задачи преминава през следните основни етапи:

1. Определяне на стратегията на алгоритъма, т.нар. “идеен проект”.
2. Формиране и описание на основните относително самостоятелни части, които могат да се обособят в задачата и алгоритъма за решението й.
3. Определяне на връзките между обектите и процесите в модулите.
4. Разработване на пълен блоков алгоритъм за решаване на задачата с отчитане на необходимите входни данни и очакваните изходни резултати.
5. Тестова проверка и доказателство на верността на алгоритъма с характеристични набори от работоспособни данни.

По структурата си алгоритмите могат да се класифицират на:

Линеен алгоритъм

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

Разклонен алгоритъм

Последователност от действия зависи от проверката на някакво условие в зависимост от което изчислителният процес протича по един или друг начин. Например: Алгоритъма за решаване на квадратно уравнение.

Цикличен алгоритъм

Многократно извършване на едни и същи операции в определен последователност, като при това се изменя част от данните. Задават се началните стойности на параметрите, управляващ цикъл. Цикълът се записва само един път в описанието на алгоритъм. За периодичното му изпълнение трябва да се осигури смяна на стойностите на управляващите параметри. За да бъде изчислителния процес, трябва да се осигури завършване на цикъл чрез проверка за край. Например: Програмите за продажба на билети в транспорта, отчитащи различните маршрути и естествено – различна стойност на билета и брой пътници.

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

Същност на структурирането на алгоритми

Структурирането на алгоритмите има за задача да осигури при програмирането възможност за йерархична програма от обособени части (модули) без сложни връзки между тях.

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

От друга страна формирането на структурни части в алгоритъма за решаване на определена задача е едно от условията за доказателство на верността на решението. Понастоящем широко приложение имат следните структурни части:

Блок

Блокът е обособена последователност от декларации и оператори. Най-добрата илюстрация на блокове са подпрограмите на FORTRAN и процедурите в PASCAL. Принципната разлика между двете реализации е в статичното разпределение на паметта при първия език и динамичното - при втория. Програмните езици допускат влагане на блокове един в друг. В такива случаи блокът на най-високото ниво (съдържащ всички останали блокове) се нарича глобален, а останалите са локални. Блоковата алгоритмизация се предшества от декомпозиция на задачата. Активирането на блок се осъществява по два начина:

• • в естествен ред - активирането се реализира от програмата в момента, когато изпълнението достигне началото на блока;
  • принудително – активирането се реализира от специален оператор, включен в програмата.

Дезактивирането също се реализира по два начина:

• • в естествен ред - когато изпълнението достигне края на блока и срещне затварящ оператор;
  • с насочващ оператор - когато управлението се предава на посочения оператор от програмата.

В блоковите структури декларирането на променливите важи само в рамките на блока, т.е. от активирането до дезактивирането му.

Модул

Модулът е логически завършена част от програма, решаваща определен проблем, и позволяваща многократно използване. Модулът прилича на блока по организация, но се отличава от него по т.нар. “скриване на операциите за изпълнение” и осигуряване само на интерфейсна връзка (по вход - изход) с потребителя на програмата. Предимствата на модулното структуриране на алгоритми и програми са поне три:

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

Пакет

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

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

Втората част е скрита и има физически характер. В нея се реализират действията на пакета, които най-често не засягат останалата част на програмата.

Обект

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

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

Променливите от тип обект могат да бъдат предавани в програмата като параметри и връщани като функции.

Клас

Структурата клас е развитие на структурата обект по посока на скриване на данните, множественото наследяване и управление на видимостта.

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

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

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