№1 алгоритъм. Същност. Свойства на алгоритмите



Дата23.12.2017
Размер287.62 Kb.
#37417


АЛГОРИТМИ-Дипломен проект
І .УВОД

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

Алгоритмите са главен обект за изучаване в компютърната информатика.

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

Терминът алгоритъм произлиза от името на Абу Джафар Мохамед ибн Муса ал Хорезми- арабски математик, който около 820 г. от н.е. написва научен трактат за това как да се представят числата в 10-ична бройна система и как да се смята с тези представяния . Съчинението на Ал Хорезми е преведено на латински език в Средновековна Европа в началото на 12 век, но разпространението на „изкуството да се смята ” и ерата на ръчното и механичното смятане започва едва в 16 век. По-късно съдържанието на понятието се разширява- като алгоритми започват да се разглеждат и известни по това време изчислителни процедури.

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




ІІ. ИЗЛОЖЕНИЕ
ТЕМА № 1 АЛГОРИТЪМ.СЪЩНОСТ. СВОЙСТВА НА АЛГОРИТМИТЕ.


Цели:

1.Да се въведе понятието алгоритъм.

2.Да се разгледат характерните свойства на алгоритъма и основните видове алгоритъм.

3.Да се придобият знания и умения за решаване на задачи от определен тип- чрез използване на алгоритъм.

4.Да се осъществи връзка между знанията по матемематика и тези по програмиране.
Вид на урока: за нови знания

Ход на урока:
Римският принцип „разделяй и владей” е добре известен от историята. Той се прилага успешно когато искаме да изпълним, или да обясним някое сложно действие, например как да приготвим някое ястие. Затова понятието алгоритъм интуитивно се свързва с понятия като множество от правила, разпоредба, предписание, план, рецепта и др.
1.Алгоритъм.Същност.
Точното описание на действията, който трябва да се извършат, за да се постигне определен резултат се нарича алгоритъм. Действието, което изпълнителят може да извърши самостоятелно без допълнителни пояснения, се нарича елементарно действие. Извършването на едно елементарно действие от изпълнителя се нарича стъпка.

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

Редица човешки дейности са алгоритмични по своята природа. В течение на своя живот човек научава и прилага много правила за поведение и действие в различни ситуации.

При съставяне на алгоритъм е необходимо:



  • да се представи сложното действие чрез последователност от по-прости действия достъпни за изпълнителя;

  • да се използват елементарни за изпълнителя действия;

  • да се опише ясно и точно последователността в която трябва да се изпълняват елементарните действия;

Отношение към даден алгоритъм имат три категории лица: съставител, изпълнител и потребител на алгоритъма. Потребителя задава изпълнението на алгоритъма и ползва крайния резултат. Разбира се, някой от трите лица може да са един и същи човек. Най- трудоемка е работата на изпълнителя, но тя се състой от прости действия който позволяват за изпълнител да се използва и подходящ автомат. Наборът от допустими елементарни действия, се определя от възможностите на изпълнителя. Като синоним на елементарно действие се използва заповед, команда или просто операция.

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

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

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

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

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

Алгоритъмът е математически обект, а програмата зависи от машината и езика за програмиране. Учениците познават много и различни алгоритми. Необходимо е те да видят, как алгоритъма може да се превърне в програма и тя да се реализира.

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



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

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

Свойството крайност е свързано с изискването алгоритъмът да е описание на процес, който е локализиран в пространството и краен във времето. При условие че, описанието е адекватно на моделирания процес от това свойство следва, че всяко изпълнение на алгоритъма има начало и край във времето. Нарушаване на това изискване при описанието на алгоритми води например до проблем, известен сред специалистите по компютърна информатика като „зацикляне”.

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

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

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

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

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

Свойството масовост отразява възможността при изпълнението на алгоритъма за всеки начален елемент да се получава търсеният резултат. Иначе казано, алгоритъма може да се прилага не само при решаване на една конкретна задача, а на цял клас от еднотипни задачи. Такъв е например алгоритъма на Евклид за определяне на НОД на две числа.

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

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

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

Пример: Алгоритъм за построяване на правоъгълен триъгълник по дадени катет и хипотенуза.

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



Задачи:

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






Алгоритъм за:

Свойства:

1.







2.







3.







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

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

4. Опишете алгоритъм за провеждане на телефонен разговор в три варианта

- по монетен автомат, по домашен телефон, с използване на фонокарта.

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

6. Съставете описание на алгоритъм за определяне площта на правоъгълно парче земя.

7. Какво според вас означава всяко от следващите свойства на компютърните алгоритми? Попълнете самостоятелно!






Свойство

Означава

1.

Формалност




2.

Крайност




3.

Дискретност




4.

Определеност




5.

Масовост




6.

Изпълнимост




7.

Ефективност




8.

Резултативност




8. Съставете таблица за умножение на всички числа от 1 до19, като попълването и извършите наум.



ТЕМА № 2 ПАРАМЕТРИ НА АЛГОРИТМИТЕ. ВИДОВЕ АЛГОРИТМИ.

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

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

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

Изпълнението на даден алгоритъм е локализирано в пространството, ограничено във времето и дискретно по характер. Следователно съществени моменти при изпълнението на алгоритмите са посочването на началния момент и определянето на края.

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

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

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

И така, параметрите, характеризиращи всеки алгоритъм са:



  • Множество на възможните начални ( входни) данни;

  • Множество на възможните резултати ( изходни данни);

  • Множество на междинните резултати;

  • Правило за започване ( начало);

  • Правила за непосредствена обработка (за получаване на междинните резултати);

  • Правило за край ( условие за приключване на изпълнението на алгоритъма);

  • Правило за посочване на крайния резултат;


2. Видове алгоритми.
Описанието на всеки алгоритъм се състои от отделни стъпки . Те задават изпълнението на елементарни действия или определят, коя е следващата команда която трябва да се изпълни..

В зависимост от типа на съставящите ги команди алгоритмите се делят на три основни вида:



- последователни – съставени са от команди, който се изпълняват една след друга, последователно по реда на записването им;

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

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

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

Според съдържанието си алгоритмите се делят на:

- числови – участват числови величини, стандартни и потребителски функции, знаци за аритметични операции, повтарящи и затварящи скоби;

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

- логически – участват логически отношения между аритметични и текстови изрази;

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



- словесно;

- графично – чрез блок –схеми;

- описание на проектански език;

- описание на език за програмиране;

В тази тема учениците се запознават с понятието алгоритъм и неговото словестно описание. За затвърдяване на новите знания на учениците се поставя задача да направят словестно описание на алгоритъма на Евклид за намиране на НОД.

Вход: Числа a и b. Изход: НОД на a и b.

Стъпка 1. Въведете и запомнете числата a и b.

Стъпка 2. Ако a е различно от b, изпълнете стъпка 3, в противен случай- стъпка 5.

Стъпка 3. Ако a> b, то изчислете a- b и го запомнете като a, в противен случай изчислете b- a и го запомнете като b.

Стъпка 4. Изпълнете стъпка 2.

Стъпка 5. Съобщете стойността на a като резултат.

Стъпка 6. Прекратете работа.
Алгоритъма на Евклид притежава всички основни свойства на алгоритмите- дискретност, яснота, изпълнимост и т.н. Алгоритъма е масов, защото може да бъде изпълнен за всяка двойка естествени числа a и b; краен- защото винаги води до намиране на НОД на a и b след краен брой стъпки.

Демонстрация на действието на Алгоритъма на Евклид се прави на черната дъска като се задават две конкретни стойности.

Домашна работа:

Например: a = 12, b = 8


Задачи: 1. Кой са параметрите на компютърните алгоритми?.

2. Какви видове алгоритми познавате? Дайте примери за всеки от тях.

3. Съставете алгоритъм за намиране на НОД на три естествени числа.

4. Запишете седемте параметъра за алгоритъма на Евклид в таблица.

5.Баща и двамата му сина тръгнали на пътешествие, но неочаквано се отзовали пред пълноводна река. Намерили лодка, която вози не повече от 100 кг. Как да постъпят, за да преминат реката, ако бащата тежи 100 кг, а синовете му по 50?

а) Опишете съставеният от вас алгоритъм.

б) Определете вида на предложеният от вас алгоритъм.

ТЕМА №3 ПРЕДСТАВЯНЕ НА АЛГОРИТМИ ЧРЕЗ БЛОК-СХЕМИ.


Цели:
1. Да се затвърдят знанията за изграждане на алгоритъм.

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

3. Да се изградят умения за съставяне на кратки и ясни блок - схеми

4. Да се запознаят и да се научат да прилагат линейните алгоритми
Вид на урока: за нови знания
Ход на урока:
В предишния урок разгледахме няколко конкретни алгоритъма. За тяхното описание използвахме естествен език

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

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

1.Блок — схеми - Представляват графични средства за изразяване на алгоритми. Изграждат се от няколко вида геометрични фигури , наречени блокове. Формата на всеки блок определя неговото предназначение. Блоковете са свързани със стрелки, определящи реда на изпълнението им. Формата , названието и предназначението на най - често използваните блокове е:

- блок за начало на блок - схемата – посочва мястото, от което започва изпълнението. Във всяка блок-схема има точно един блок НАЧАЛО. Той има само една изходяща стрелка, но няма входящи стрелки.


- блок за вход или изход - конкретното му предназначение се определя от

В/Д : или И/Д . В блока за вход се изреждат величините , които са необходими за изпълнение на алгоритъма. Към блока водят една или повече входящи стрелки. От блока излиза само една стрелка.

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





- блок за обработка ( изчисления ) — изчисляват се изрази и стойността се присвоява на променлива. В него се записва действието. Към блока водят една или повече входящи стрелки. От него излиза само една стрелка.






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


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






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


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


- свързваща стрелка - осъществява връзка между блоковете и е прието да

хоризонтална или вертикална.




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

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

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

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

Задача: Да се състави блок- схема за изчисляване на лицето S на триъгълник по зададени дължина на основата и височина към нея h. Решение:

2. Линейни блок схеми.


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

В практиката: на програмирането такива задачи се срещат много рядко, но

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

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

Да се състави блок- схема за размяна стойностите на две променливи.

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

Домашна работа: Съставете алгоритъм за изчисляване корените на система от две линейни уравнения с две неизвестни.

ax+ by = c



dx+ey =f
a, b, d, e са коефициенти пред неизвестните; c и f са свободни членове на системата.
3.Разклонени и циклични алгоритми- блок- схеми.
Цели :

1. Да се развие алгоритмичното мислене и да се усвоят командите за условен преход.

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

3. Да се усвоят основните алгоритмични конструкции при решаването на задачите, в които се използват цикли.

4. Да се запознаят с основните конструкции на алгоритъма за цикъл с предусловие и следусловие.
Вид на урока: за нови знания

Ход на урока:

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



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





Верига 1



Верига 2






Пример: Да се състави блок - схема на алгоритъма за решаване на линейно

уравнение от вида aх + b = 0




След съставяне на блок - схемата се обръща внимание на учениците разликата и с линейните блок - схеми . Дават се указания за това кога е удачно да се използват този вид блок - схеми. В зависимост от стойностите които ще получат a и b се разглеждат различните ситуации. Условията поставени в геометричната фигура ромб се наричат условия за разклонение.

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

Със следващите задачи се затвърдяват структурните разновидности на алтернативата.

Задача: Да се състави блок — схема на алгоритъма за размяна на стойностите на две променливи - х и у. Размяната да се извършва, само ако е изпълнено условието : х > у.

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




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

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

2. Циклични алгоритми – блок- схеми.

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

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

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

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

Циклични блок- схеми:

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

Самият цикъл чрез блок- схема може да бъде описан по един от начините:


Тук са използвани следните означения:



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

  • тяло – група от блокове, които ще се изпълняват многократно;

  • модификация – променя се стойността на поне една величина от цикъла (най- често това е управляващата променлива );

  • условие – този блок определя дали да се изпълни тялото на цикъла още веднъж или не;

Да разгледаме следната задача:

Да се напише блок- схема за изчисляване стойността на произведението

1,2,3,...,N.

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


Задача: Представете с блок- схема алгоритъма на Евклид за намирането на НОД на две числа a и b.

Ще използваме циклична блок- схема, която ще влючва едната от двете разновидности на цикъл.


Едната разновидновидност се нарича повторение с предусловие, а втората повторение със следусловие.
повторение с предусловие повторение със следусловие

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

Да построим сега блок- схема на алгоритъма на Евклид за намиране на НОД на две числа a и b.

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


3. Специализирани представяния.
Примери за специализирани представяния са псевдокодовете и алгоритмичните езици.

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

Пример:

Представяне на алгоритъма на Евклид с псевдокод:



ВЪВЕДИ А, В

ДОКАТО А е различно от В ПОВТАРЯЙ

АКО А > В ТО А := А – В ИНАЧЕ В := В – А;

ИЗВЕДИ А

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

2. Представете с блок- схема алгоритъма за определяне на НОД на три естествени числа.

3. Опишете с блок- схема или псевдокод задачата за определяне на относителната молекулна маса на просто химично вещество по даден брой атоми в една молекула и относителната атомна маса на съответния химичен елемент.

4. Да се състави блок- схема на алгоритъм за пресмятане на лице на триъгълник по Хероновата формула. Преди да се премине към пресмятането на лицето S да се провери дали страни с дължина a,b,c образуват триъгълник.

5. Да се състави блок- схема на алгоритъм за изчисляване стойността на израза :

Z = 1+1/2+1/3+…+1/n

6. Да се състави блок- схема за пресмятане на x, n>0 цяло число.

7. Дадена е редица от числа а1, а2,...,аn

а ) Да се състави блок- схема за намиране сумата от стойностите на елементите на редицата.

б ) Да се състави блок- схема за намиране стойността на първия максимален елемент и неговия индекс.

в ) Да се състави блок- схема за сортирането и във възходящ ред.

ТЕМА № 4 АЛГОРИТМИ И ПРОГРАМИ.
След като бъде създаден алгоритъм за решаването на даден тип задачи, неговото изпълнение може да бъде възложено на изпълнител, които стриктно да следва и изпълнява съответните инструкции. При това съвсем не е необходимо изпълнителят да разбира принципите, на които се основава даден алгоритъм. От тук произлиза принципната възможност интелектът и знанията, изисквани за решаването на проблеми, да се кодират в съответни програми, а изпълнението да се предоставя на автомати. Следователно, за да може с помощта на компютър да се реши каквато и да е задача и да се получи съответния резултат, предварително е необходимо:1. човешкият интелект да намери правилен алгоритъм; 2. да го опише в подходяща форма и 3. да възложи изпълнението му на компютър.

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

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

Езикът за програмиране е език, предназначен за записване и разпространяване на компютърните алгоритми.

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

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

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

Първите езици за програмиране от високо ниво са създадени в началото на втората половина на XX век: Фортран- за числени пресмятания, Кобол- за икономически приложения, Лисп- за обработка на списъци и др. Днес широко се използват универсални езици за програмиране като Паскал, С++, Java и др., и специализирани езици за програмиране като SQL –за работа с бази данни, Пролог- за логически задачи и др.

Само по себе си, обаче, използването на алгоритмични езици не решава въпроса за „разбирането” на записаните чрез тях алгоритми от компютрите. Някои трябва да „преведе” алгоритъма, записан на конкретния алгоритмичен език, на съответния машинен език. Решението на този проблем се оказва просто: самия компютър може да поеме ролята на преводач. За целта е достатъчно за този компютър да бъде създаден алгоритъм за превод. Програмата преводач се нарича транслатор. Транслаторът анализира текста на първоначалната програма, разпознава езиковите конструкции, съобщава забелязаните грешки, а ако не открие грешки- преобразува зададената програма в програма на машинен език. Същевременно транслаторът определя местата (адресите ) в оперативната памет за разполагане на данните (входни, междинни и окончателни резултати ), които са необходими при изпълнението на преобразуваната програма.

Машинната програма, получена в резултат на транслацията, се нарича изпълнима програма.

За да изпълни компютърът програма на език за програмиране се преминава през два етепа- транслиране и изпълнение.




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

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

Разпространен е и друг подход: последователно превеждане на части от програмата- напр. отделни оператори (етап 1 ) и незабавното им изпълнение (етап 2 ). Транслаторите, които действат по този начин, се наричат интерпретатори. При тях последователно се превключва от етап 1 към етап 2 и обратно. Едно предимство на интерпретаторите пред компилаторите е, че са много по- малки по обем (вследствие на по- простия алгоритъм за превод ).

ІІІ.ЗАКЛЮЧЕНИЕ

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

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

При разглеждането на темите учителят има за цел, учениците да придобият следните знания и умения:

1. Да се запознаят с понятието алгоритъм и неговите основни свойства.

2. Да се запознаят с основните характеристики на алгоритмите.

3. Да се запознаят с видовете алгоритми.

4. Да се придобият умения да съставят различни блок- схеми в зависимост от вида на алгоритъма.

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

6. Да се запознават с понятието цикъл, видове цикли и основните логически конструкции за реализиране на цикли.

7. Да се подготвят за съставянето на програми след запознаването им с конкретен език за програмиране.



ТЕСТ
ЗА ПРОВЕРКА НА ЗНАНИЯТА И УМЕНИЯТА ПРИДОБИТИ ОТ УЧЕНИЦИТЕ СЛЕД ИЗУЧАВАНЕ НА ТЕМАТА АЛГОРИТМИ:



  1. Алгоритъм е:

А ) действия, чрез които се решава конкретна задача;

Б ) система от указания, определящи елементарни действия. Изпълнението на тези действия осигурява решаването на коя да е задача от определено множество;

В ) система от указания, определящи действия, чрез изпълнението на които се осигурява решаването на конкретна задача;

2. Кои свойства притежават всички алгоритми?

А ) определеност, масовост, резултатност;

Б ) определеност, масовост, резултатност, цикличност;

В ) определеност, резултатност;

3. В някои алгоритми броят на указанията е равен на броя на действията, които се извършват по време на изпълнението на алгоритъма. Как се наричат тези алгоритми?

А ) циклични;

Б ) разклонени;

В ) линейни;

4. Тялото на цикъла се изпълнява поне веднъж, ако е:

А ) цикъл с прдусловие;

Б ) цикъл със следусловие;

В ) и в двата случая;

5. Възможно ли е в дадена блок- схема да липсва блок за анализ?

А ) да, ако описва линеен алгоритъм;

Б ) да, ако описва цикличен алгоритъм;

В ) не, блокът за анализ присъства във всяка блок- схема;

6. Какво означава записът x +1: = x ?

А ) x получава стойност, равна на досегашната му стойност плюс единица;

Б ) x е равно на нула;

В ) записът е неправилен;

7. Дадена е редицата от числа а1, а2,...,аn. Съставете блок- схема за намиране броя на елементите с положителна стойност.





Каталог: files -> files
files -> Р е п у б л и к а б ъ л г а р и я
files -> Дебелината на армираната изравнителна циментова замазка /позиция 3/ е 4 см
files -> „Европейско законодателство и практики в помощ на добри управленски решения, която се състоя на 24 септември 2009 г в София
files -> В сила oт 16. 03. 2011 Разяснение на нап здравни Вноски при Неплатен Отпуск ззо
files -> В сила oт 23. 05. 2008 Указание нои прилагане на ксо и нпос ксо
files -> 1. По пътя към паметник „1300 години България
files -> Георги Димитров – Kreston BulMar
files -> В сила oт 13. 05. 2005 Писмо мтсп обезщетение Неизползван Отпуск кт


Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

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