Алгоритъм. Понятие, свойства, представяне и видове. Произход на понятието „алгоритъм“



Дата14.11.2017
Размер131.47 Kb.
Алгоритъм. Понятие, свойства, представяне и видове.

  1. Произход на понятието „алгоритъм“

Според някои автори думата „алгоритъм“ произлиза от името на персийския учен Ал Хорезми, който през през 825 г. е написал научен трактат за това как да се представят (записват) числата в Десетична бройна система и как се извършват аритметичните операции с тези представяния.

  1. Понятие за „алгоритъм“

Алгоритъм“ е интуитивно понятие. То е основно понятие в науката и не се дефинира (както точка, права и равнина в геометрията, пространство и време във физиката и др.), но за него може да се даде интуитивна представа. Понятието „алгоритъм“ е широкообхватно. Разглеждаме алгоритмите, предназначени за изпълнение от компютър. Алгоритъм, това е последователност от стъпки (инструкции, команди, указания, оператори) за действие, която при изпълнението си реализира зададена функционална зависимост между данните и резултатите (иначе казано след изпълнението на предписанието ще бъде решена съответната задача). Ако последователността не реализира зададената функционална зависимост, то тя не е алгоритъм на дадената задача.

Във всяка инструкция (стъпка от алгоритъма) се указват всички или някои от следните елементи:



  • Каква операция (операции) се извършват;

  • Какви са нейните аргументи и резултатите от изпълнението й;

  • Коя е следващата инструкция за изпълнение.

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

  1. Свойства на (компютърните) алгоритми

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

б) Крайност (финитност). Алгоритъмът и всяка негова стъпка се изпълняват за крайно време. Алгоритъмът съдържа краен брой стъпки и следователно се изпълнява за краен брой стъпки.

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

Често поради грешки в алгоритъма (или програмата) процесът се превръща в безкраен, например при циклите ако е сгрешено условието за излизане от цикъла.

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



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

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



г) Масовост. Това свойство отразява възможността при изпълнението на алгоритъма за всеки начален елемент (от допустимото множество входни данни) да се получава търсеният резултат. С други думи: алгоритъмът да може да се прилага не само при решаването на една конкретна задача, а на цял клас от еднотипни задачи.

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

Резултатността на алгоритъма се третира като насоченост на алгоритъма – след краен брой стъпки трябва да се получи или решението на поставената задача или отговор за неприложимостта на този алгоритъм към конкретно избраното множество от началните данни (което също е резултат). В общия случай е възможно изпълнението на определения от алгоритъма процес да не завършва (нарушена е крайността) или да прекъсва на някоя стъпка с резултат „няма решение”.



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

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

з) Изпълнимост. „Силно” изискване, което се поставя пред компютърните алгоритми да се състоят от „изпълними стъпки”.

Пример: Алгоритъм за намиране на 17-тото по ред просто число

Стъпка 1: Съставете списък на всички естествени числа във възходящ ред;

Стъпка 2: Съставете списък на простите числа (във възходящ ред), като в списъка, формиран в стъпка 1 зачертаете всички числа, които не са прости;

Стъпка 3: От получения на стъпка 2 списък изведете като резултат 17-тото поред число.

Очевидно е, че стъпки 1 и 2 са неизпълними (за кой да е човек или автомат), затова предложеният „алгоритъм” не решава задачата. Предписанието, задавано от всеки алгоритъм, е предназначено за конкретен изпълнител. Изискването за изпълнимост е условно от гледна точка на знанията и уменията на конкретния изпълнител.

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


  1. Представяне (запис) на алгоритмите

a) Словесно описание. По начина, по който се пишат готварски рецепти.

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

Последователна инструкция: begin K1; K2; …; Kn end

Условна инструкция: if <условие> then K1 else K2

Инструкция за цикъл с предусловие: while <условие> do K

Инструкция за цикъл със следусловие: repeat K1; K2; …; Kn until <условие>

Инструкция за цикъл с предварително зададен брой итерации (цикъл с брояч):

for <начална стойност на брояча> to <крайна стойност на брояча> step <стъпка> do K.

Предимство на този начин е, че заема малко място върху хартия и е предназначен за четене от човек. Недостатък – при текст на естествен език може да се получи нееднозначност и поради това не може да се изпълнява от компютър.



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

Елементи на блок-схеми на алгоритми


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

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



Основни елементи на блок-схемите на алгоритмите

Наименование

Обозначение

Функция

Блокове

Начало и

Край
(Терминатори за начало и край)





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

Блок Действие /Обработка
Изпълнение на операции над данни



Изпълнение на една или няколко операции, обработка на данни от всякакъв вид (изменение стойностите на данните, формата на представяне, разположението). Вътре в правоъгълника се записват непосредствено самите операции, например, операция Присвояване: a = 10*b + c.

Логически блок (блок за условие)



Изобразява решение или функция от превключващ тип с един вход и два (или повече) алтернативни изхода, от които само един може да бъде избран след изчисляване на условията, определени в блока. Входът в елемента се обозначава с линия, влизаща обикновено в горния връх на блока. Ако изходите са два или три, то всеки изход се обозначава с линия, излизаща от съответния от останалите върхове (странични и отдолу). Ако изходите са повече от три, то те може да се показват с една линия, излизаща най-често от долния връх на блока, която линия след това се разклонява. Съответните резултати от изчисленията може да се записват до линиите, изобразяващи тези пътища. Примери в програмирането са условните оператори if (два изхода: true и false) и case (множество изходи).

Предопределен процес
Извикване на външна процедура



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

Данни
Операции по въвеждане и извеждане на данни




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

Съединител
Конектор





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

Коментар



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

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

Блокът “Решение се използва за обозначаване на преходи на управлението според условието. Във всеки блок “Решение трябва да се посочват въпроса/условието или сравнението, които той определя.

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


Пример: Сортиране с вмъкване


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

На всяка стъпка от алгоритъма се избира първият елемент от необработената част на масива и се вмъква в отсортираната така, че в нея да се запази искания ред на следване на елементите. Вмъкването може да се изпълнява както в края на масива, така и по средата. При вмъкване в средата трябва да се отместят всички елементи, разположени “в дясно” от позицията за вмъкване е един елемент надясно. В алгоритъма се използват два цикъла – в първия се избират елементи от необработената част, а във втория се осъществяват вмъкванията.



Фиг. 1 Блок-схема на алгоритъм за сортиране чрез вмъкване

В приведената блок-схема за организиране на цикъл се използва символът за разклоняване. В главния цикъл (i < n) се проверяват елементите от необработената част на масива. Ако всички елементи са обработени, то алгоритъмът завършва работата си, в противен случай се изпълнява търсене на позицията за вмъкване на i-тия елемент. Търсената позиция ще се съхрани в променливата j в резултат на изпълнението на вътрешния цикъл, осъществяващ отместване на елементите дотогава, докато не беде намерен елемент, стойността на който е по-малка от стойността на i-тия.

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



в) С език за програмиране. Записът на алгоритъм с език за програмиране се нарича програма и е предназначен за изпълнение от компютър. Този начин на записване не допуска еднозначност.

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

д) С теоретични алгоритмични системи - Машини на Тюринг, рекурсивни функции, система на Пост, нормални алгоритми на Марков и др. Тези системи съдържат минимален брой максимално прости инструкции. Служат за теоретични изследвания – доказва се дали дадена задача има алгоритъм за решаването й. Ако задачата има алгоритъм тя се нарича алгоритмично решима, ако няма – алгоритмично нерешима.

Използвана литература:



  1. Стойчев, Ст. Синтез и анализ на алгоритми. Изд.БПС,София, 2003.

  2. Тотков, Г., В. Шкуртов, Р. Донева. Основи на компютърната информатика. с/о Jusautor, София, 2001.


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница