Лекция №2 алгоритмично-програмни конструкции видове алгоритми

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

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

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

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

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

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

Блок. Блокът е обособена последователност от декларации и оператори.

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

Активирането на блок се осъществява по два начина:

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

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

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

Предимствата на модулното структуриране на алгоритми и програми (Програмните езици MODULA, SIMULA и др..) са поне три:

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

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

Втората част е скрита и има физически характер. В нея се реализират действията на пакета, които най-често не засягат останалата част на програмата.
Обект. Обектът е набор от процедури и данни с динамична структура и организация (програмни езици С, С⁺⁺ и др.).

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

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

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

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

за самостоятелна работа

1. 
   Характеризирайте с конкретни примери основните етапи на алгоритмизацията.
   
2. 
   Опитайте се да решите приведената комплексна задача по няколко начина и с използването на различни програмно-алгоритмични конструкции.
   Задача: Да се разработи и документира алгоритъм, гарантиращ поддържането на температурата в едно помещение в границите на 18-25 градуса по Целзий.
   - При условие, че температурата спадне под работния интервал, то да се включва нагревател.
   - Ако температурата се покачи над работния интервал, то да се включи вентилатор за охлаждане.
   - При температура под 13 и над 30 градуса – да се задейства звуков и светлинен сигнал за опасност с конкретни съобщения за причината,.
   - Измерването и регулирането да става на всеки 5 минути, а при невъзможност да се реализира някоя от функциите – да се задейства звуков и светлинен сигнал за опасност с конкретни съобщения за причината.