Презентация по темата за структурата на алгоритмите. Основни алгоритъмни структури

Алгоритъм и алгоритмични структури

Мосина А.Ю.

Алгоритъм е строго определена последователност от действия при решаване на даден проблем.

Алгоритъмът включва няколко стъпки.

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

„Алгоритъмът е ред от действия.“

Изпълнител е обект, който изпълнява определен набор от действия.

Изпълнителят може да бъде човек, робот, животно или компютър.

Командна система на изпълнителя (СКИ) е набор от команди, които изпълнителят може да изпълни.

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

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

Упражнение: Посочете изпълнителите на следните видове работа:

Почистване на боклука в двора

Обучение на деца в училище

Каране на кола

Отговорът е на дъската

Готвейки храна

Отпечатване на документ на принтер

Крайник– всяко отделно действие и алгоритъмът като цяло трябва да могат да бъдат изпълнени

Ефективност– получаване на резултати в краен брой стъпки

Дискретност(прекъснатост, отделност) – разделяне на алгоритъма на стъпки

Детерминизъм(сигурност, точност) – всяко действие трябва да бъде строго и недвусмислено дефинирано

Масов характер– използване на алгоритъм за решаване на подобни задачи

Свойства на АЛГОРИТЪМА

Класификация на алгоритмите по форма на представяне :

Глаголен

Табличен

Графика (блокови диаграми)

Софтуер

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

Основни конвенции в блокови диаграми

Символ

Предназначение на блока

Начало или край на алгоритъма

Въвеждане или извеждане на данни.

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

Процес.

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

Проверка на състоянието.

Логическите условия са записани вътре в блока. Има два изхода Да (+) и Не (-).

Посока.

Класификация на алгоритмите по структура:

Линеен (следващ)

Разклонен (клон, избор, алтернатива)

Цикъл (повтаряне)

Помощни

Комбиниран

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

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

(Пример: алгоритъм за събиране на портфолио).

Основна структура на линейния алгоритъм:

Отборна серия 1

Отборна серия 2

Екип N серия

Задача

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

Решение:

Етап 1: Формулиране на проблема.

Изходни данни: A, B, C – страни на произволен триъгълник

Изход: P – периметър на триъгълника.

Етап 2: Математически модел.

P=A+B+C

Етап 3: Съставяне на алгоритъм

Започнете

Въведете

Заключение

Край

№ 1 И използване на блок-схема на алгоритъма , изчислете стойността на функцията Y при X=2,

Започнете

вход: X

Z=8*X

• РЕШЕНИЕ:

• X=2
• Z = 8 * 2 = 16
• Z = √16 = 4
• Z = 4 – 1 = 3
• Y = 3 * 2 = 6
• Y = 6/3 = 2

Z = Z - 1

Y=3*X

Y=Y/Z

изход: Y

• Алгоритмите могат да опишат процесите на трансформация на голямо разнообразие от обекти. Самата дума „алгоритъм“ идва от „algorithmi“ - латинското изписване на името на изключителния математик от 9-ти век ал-Хорезми, който формулира правилата за извършване на аритметични операции.
• Алгоритъм- набор от команди, които описват реда на действията на изпълнителя за постигане на резултат от решаване на проблем в краен брой действия.

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

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

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

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

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

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

6. Ефективност- завършване на алгоритъма с определени резултати.

Начини за писане на алгоритми:

1. Словесен метод на запис

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

Пример

Като пример за словесен начин за писане на алгоритъм, помислете за алгоритъм за намиране на площта на правоъгълник

където S е площта на правоъгълника; a, b – дължините на страните му.

Очевидно a, b трябва да бъдат посочени предварително, в противен случай проблемът не може да бъде решен.

Начини за писане на алгоритми

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

• Началото на алгоритъма.
• Задайте числената стойност на страна a.
• Задайте числената стойност на страна b.
• Изчислете площта S на правоъгълника по формулата S=a*b.
• Изведете резултата от изчисленията.
• Край на алгоритъма.

Начини за писане на алгоритми

2. Графичен метод

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

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

Начини за писане на алгоритми

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

Име

Изчислителен блок (изчислителен блок)

Изчислителни действия или последователност от действия

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

Блок за вход/изход на данни

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

Общо обозначение за въвеждане (извеждане) на данни (независимо от физическия носител)

Начало (край)

Начало или край на алгоритъм, влизане или излизане в подпрограма

Начини за писане на алгоритми

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

Име

Потребителски процес (подпрограма)

Изчисляване с помощта на стандартна програма или подпрограма

Модификационен блок

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

Конектор

Указване на връзката с прекъснати линии между информационните потоци

Начини за писане на алгоритми

Пример

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

Начини за писане на алгоритми

3. Псевдокодове

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

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

Начини за писане на алгоритми

Пример

• Започнете. Отидете на точка 2.
• Въвеждане на числата a и b. Отидете на точка 3.
• Изчислете S=a*b. Отидете на точка 4.
• Заключение S. Преминете към точка 5.
• Край.

Начини за писане на алгоритми

4. Софтуерен метод

Записване на алгоритъма на избрания език за програмиране.

Пример

Writeln('');

Writeln('S=', S);

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

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

Това е алгоритъм, в който има само следната структура.

Следване- Това е подредбата на действия едно след друго.

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

2. Алгоритъм за разклоняване (ако... тогава... иначе...)

Това е алгоритъм, който има разклонена структура.

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

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

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

Това е алгоритъм, който има структура на цикъл.

Цикъл- Това е многократното повторение на всяко действие.

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

4. Комбиниран алгоритъм

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

Ширина на блока px

Копирайте този код и го поставете на уебсайта си

Надписи на слайдове:

Алгоритми и структури от данни Литература:

• Д. Кнут. Изкуството на компютърното програмиране. Т. 1-3, М.: Мир, 1978, 1995 и др.
• Н. Вирт. Алгоритми и структури от данни. М.: Мир, 1989.

Концепция за тип данни

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

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

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

• Компютърни даннитова са отделни съобщения, които се представят във форма, използваема от компютър, компютърно разбираемо. За компютърен процесор всякакви данни са неструктуриранпоследователност от битове (понякога се използва терминът потокбитове).

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

• Непосредствени значенияТова непроменливпрограмни обекти, които представляват себе си: числа (25, 1.34E-20), символи ('A', '!'), низове ('Въведете матрични елементи');
• Константиса имена, присвоени на определени стойности (const pi=3.1415926).
• Променливитова са обекти, които могат да приемат стойност, да я запазват без промяна и да я променят, когато се извършват определени действия (var k:integer, x:real, a:array).
• Стойности на изрази и функции. Изразите и функциите са правила за изчисляване на стойности, записани по определен начин: k*x+ sqrt(x).

• Данните в програмите включват:

• Типът данни е най-важната характеристика, която определя:

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

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

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

• Основни принципи на понятието тип данни
• на програмни езици:

• Разновидности на типове данни и структури

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

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

• Значение скаларен(прост, атомен)представен тип гладка единкомпонент (пример: време, температура).

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

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

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

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

• Статични типове (структури от данни)

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

• Целочислени точни стойности. Примери: 73, -98, 5, 19674.
• Машинно представяне: формат с фиксирана точка. Диапазонът от стойности се определя от дължината на полето. Операции: +, -, *, div, mod,=,<, и т.д.

• Тип цяло число

• Нецелочислени приближения. Примери: 0.195, -91.84, 5.0
• Машинно представяне: формат с плаваща запетая. Обхватът и точността на стойностите се определят от дължината на полето. Операции: +, -, *, /, =,<, и т.д.

• Тип истински

• Единични текстови знаци. Примери: „a“, „!“, „5“.
• Машинно представяне: ASCII формат. Наборът от стойности се определя от кодовата таблица и възможностите на клавиатурата. Операции: +, =,<, и т.д.

• Тип въглен

• Две булеви стойности false и true. Освен това, невярно
• Машинно представяне ─ нула и еднобитова стойност: false е кодирана 0, true ─ 1. Операции: , , , =,< и т.д.

• Тип булево

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

• Има дискретни и непрекъснати скаларни типове. Множество значения отделентип краен или изброим. Множество значения непрекъснатоповече от изброим тип. Дискретните стандартни типове включват цяло число, символ и логически. Непрекъснатите стандартни типове включват реални.

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

• Обикновено се наричат ​​структури, подобни на вектори и матрици в компютърните науки масиви. Всички елементи на масива трябва да бъдат едно и същоТип.

• Масив или нормален тип

• За достъп (позоваване на) на отделен елемент от масива се използва индекс или няколко индекса (w; w; A). Индексите могат да бъдат изрази, чиито стойности могат да варират произволно в предварително зададени граници. Следователно те казват, че елементите на масива имат директен достъп.

• Извикват се структури, подобни на редовете на таблицата записи. Компонентите на записите обикновено се извикват полета. Могат да бъдат различни полета (колони на таблица). различенвидове. За достъп до отделни полета на запис те са фиксирани и непроменими имена. Например: Ден на победата. Месец:= май. Полетата могат да бъдат избрани за обработка в произволен ред, така че се казва, че има достъп до компонентите на записа прав.

• Рекорден или комбиниран тип

• Ден на победата:

• Файл (последователност)

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

• Полетът на Гагарин:

• Няколко

• В много математически и информационни проблеми има нужда от пряко или косвено използване на основния математически обект комплекти. Типът данни, съответстващ на набор, по дефиниция е структуриран, тъй като в общия случай наборът може да се състои от повече от един елемент и в същото време трябва да се извършват операции с всички елементи на набора като едно цяло. Броят на елементите в комплекта не се определя предварително и с времето може да се промени. Всички елементи на комплекта трябва да са от един и същи тип. Достъпкъм отделни елементи от комплекта Не. Можете само да разберете дали даден елемент принадлежи към набор или не, да включите елемент в набора или да го изключите от набора. Предлагат се и стандартни операции върху множества: обединение, пресичане, изваждане и др.

• X1 X5 X4

• Динамични структури от данни

• Данни с динамична структура във времето промени себе си структура, а не само броя на елементите, като файлове или последователности. Основните динамични структури от данни са:

• предмет;
• линеен списък;
• дърво;
• графика.

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

• Линеен списък

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

• Много други видове динамични структури са организирани на базата на линеен списък. Това е по-специално: пръстени, опашки, палубиИ стекове.

• Пръстенова структура

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

• За линеен списък и пръстен е възможен достъп до всеки елемент от структурата. За да направите това, трябва последователно да преминете от един елемент към друг. В много ситуации от реалния свят такъв достъп отсъстващ. Можете да взаимодействате само с първия и последния елемент или само с един от тях. Опашки, палуби и стекове се използват за моделиране на такива обекти.

• Структура на опашката

• Краят на опашката е достъпен за включване, а началото е достъпно за изключване (селекция). Елементът, който е пристигнал в опашката по-рано и се обслужва първи. Казват, че опашката е структура с дисциплина на обслужване FIFO (Епърво азн, Епърво О ut) ─ „първи идва, първи си отива“.

• Структура на палубата

• Палубата разполага с двата края, както за включване, така и за вземане на проби. По този начин можем да кажем, че Dec ─ е двупосочна опашка.

• Структура на стека

• Стекът има само един край на структурата, наличен за взаимодействие: горната част на стека. Както включването на нов елемент в стека, така и изборът на последния включен преди това елемент преминава през върха на стека. Така първо се обработва артикулът, който е пристигнал последен. Казват, че стекът е структура с дисциплина на поддръжка LIFO (Ласт азн, Епърво О ut) ─ „дошъл последен, първи си тръгнал“.

• БЛАГОДАРЯ ЗА ВНИМАНИЕТО!

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

Първата основна структура е следната
се състои от верига от блокове без
разклонения.

Разклоняване

да
Не
състояние

Специален случай на разклоняване
състояние

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

Цикъл

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

Цикъл с постусловие

Цикл с предварително условие

Параметричен цикъл

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

i:= в
Тяло
цикъл
i:= i + di
Не
да
i > ik

i:=in
i>ik
Тяло
цикъл
i:=i+di

Проектиране на сложни алгоритми

Метод за проектиране на алгоритъм отгоре надолу

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

Пример

Дадено е уравнението ax2 + bx + c = 0 и функцията
f(x).
Ако едно уравнение има две реални числа
корени x1 и x2, изградете таблица със стойности
функция върху сегмента, състоящ се от n
точки.

Алгоритъм от най-високо ниво
Въведете a,b,c
Решение
уравнения
Не
х1, х2
намерени
да
Въведете n
Строителство
маси
Няма решение
СПРИ СЕ

Алгоритъм, който реализира подпроблема за решение
квадратно уравнение
d:=b2 – 4ac
Не
D>0
да
X1=(- b + √ d)/2/a
X2= (- b - √ d)/2/a

Алгоритъм за построяване на таблица със стойности
функции
h=(x2-x1)/(n-1)
x = x1
i=1
Изход x, f(x)
x=x+h
i = i +1
да
Не
i>n

По този начин решението на проблема
проблемът се състои от горен алгоритъм
ниво и две подзадачи.
Алгоритъм за свързване на подзадачи
Решение
уравнения
Строителство
таблици f(x)