7 Лекция Основни алгоритмични структури
Разглеждат се основните понятия на алгоритъма в програмите и алгоритмизирането на решаването на проблеми.
„Алгоритъм“ е основната фундаментална концепция на компютърните науки, аалгоритмизацията(програмирането) е основният раздел на курса по компютърни науки (ядрото на курса). Концепцията заалгоритъм, както и концепцията за информация, не могат да бъдат точно определени. Поради това съществуват различни дефиниции – от „наивно-интуитивни“ („алгоритъмъте план за решаване на задачата“) до „строго формализирани“ (нормалниалгоритмиМарков).
Като работна дефиниция наалгоритъмприемаме следната дефиниция.
Алгоритъмътотговаря на следните основнисвойства:
Крайност (дискретност) на командите и действията, изпълнявани върху тяхалгоритъм.
Изпълнимост в конкретна работна среда (в определен клас изпълнители).
Ефективността на отделните команди и целияалгоритъм.
Приложимост наалгоритъмакъм всички възможни входни данни на определен клас задачи.
Определеност (определеност) на командите и всичкиалгоритъмза всички входни данни.
Формализирано, конструктивно описание (представяне) наалгоритъмкоманди.
Минимална пълнота на командната системаалгоритъм.
Съгласуваност на всекиалгоритъмкоманди за всеки входен набор от данни.
Всекиалгоритъме фокусиран върху някакъв общ метод за решаване на клас проблеми и е формализиран запис на метод, процедура.
Алгоритъмът, написан на някакъв алгоритмичен, формален език, се състои отзаглавка на алгоритъма(описание на параметрите, спецификации на клас задача) итяло на алгоритъма(последователности от команди на изпълнителя, които преобразуват входните параметри в изходни).
За записване, изпълнение, обмен и съхраняване наалгоритмиима различни инструменти, езици, псевдокодове - блокови диаграми (структурни диаграми на алгоритми), структурограми (диаграми на Наси-Шнайдерман), P-схеми, училищен алгоритмичен език (SAL), различни езици за програмиране.
Като език за описание наалгоритминие допълнително използваме визуален графичен метод за описание с помощта на блок-схеми, тъй като е по-визуален.
Повече подробности за процеса на описване на алгоритми можете да намерите в указанията:
Lantratov O.I. Указания и задачи за практически упражнения по темата „Структурни схеми на алгоритми” / O.I. Лантратов, Е.Б. Ивушкин. - Мини: Издателство ДГАС, 1997г.
8 Лекция: Данни, техните видове, структури и обработка
Разгледани са основните понятия за данни за алгоритми, техните основни типове и структури, въпроси за тяхното използване при алгоритмизиране на задачи.
Всяка актуализация на информация се основава на някоиданни, всичкиданнимогат да бъдат актуализирани по някакъв начин.
Даннитеса някои съобщения, думи в определена азбука.
Пример.Дадено ечислото 123, което е дума в азбуката от десет естествени цифри; число 12,34 -дадено, което е дума от азбуката от десет естествени цифри и десетична запетая; текстът "математика и информатика - необходимите дисциплини", -подаденна азбучен ред от буквите на българския език и препинателните знаци, включително интервал.
Текущото (т.е. разглежданото в момента) състояние наданнитесе нарича текущатастойностданниили простостойност.
Предиразработване на алгоритъм (програма), е необходимо да се избере оптималната структураданниза изпълнение на задачата. Неуспешният избор наданнии техните описания може не само да усложни решавания проблем и да го направи неразбираем, но и да доведе до неправилни резултати. Структурата наданнитесъщо се влияе от избрания метод на решение.
Пример.Когато решавате система от линейни алгебрични уравнения, можете да използвате метода на Крамер (използвайки детерминанти) или метода на Гаус (използвайки последователни елиминации на неизвестни). Методът на Cramer ще изисква около 3 пъти повече операции за изпълнение от метода на Gauss и следователно никога не се използва в компютърни изчисления.
Типътданнихарактеризира обхвата настойностиданни.
Типоветеданнисе определят чрез просто изброяване настойностина типа, например, както припрости типове данни, или чрез комбиниране (структуриране) на някои предварително дефинирани типове -структурирани типове данни.
Пример.Нека зададемпрости типове данни"специалност","студент","университет"със следното изброяване:
специалност = (филолог, историк, математик, лекар);
студент = (Петров, Николаев, Семенов, Иванова, Петрова);
университет = (Московски държавен университет, Руски държавен университет, KBSU).
Стойностот тип"студент"може да бъдеПетров.
Пример.Нека опишемтип структурирани данни"student_specialty":
Стойностот тип"student_specialty"може да бъде двойка (историк, Семьонов).
За обозначаване на текущитестойностиданнисе използват константи - числови, текстови, логически.
Често (в зависимост от задачата) се разглеждатданни, които имат не само"линейна" (както по-горе), но и йерархична структура.
Пример.Структурата на "университет" може да се определи като йерархична структура, състояща се например от следните нива: "Ректорат", "Декани и подразделения", "Катедри", "Катедри", "Преподавателски състав и персонал".
Алгоритмичните езици иматстандартни типове, като цели числа, реални, символни, тестови и булеви типове. Те не са посочени в тези езици (не са дефинирани, те са описани изрично) и имат съответните описания с помощта на функционални думи.
Пример.В училищния алгоритмичен език (SHAL), например, integer, real, character, text (letter, string) и логически типовеdataсе описват с ключовите думи integer, thing, sim, lit, log. В Pascal, с подобни ключови думи integer, real, char, string, boolean.
Всеки типданнипозволява използването на определени операции върхустойностиот типа ("с тип").
Пример.За целочислен типданнинека наречем операциите "=" (присвояване), "+", "–", "*", "=" (сравнение за равенство), "≠", " ", "≤", "≥".. За реален типданни, също и операцията "/" (деление). За символен типданни– само ":=", "=", "≠", " ", "≤", "≥". Например, сравнявайки "а"