Курс лекций по УД ОП.08 "Теория алгоритмов" специальности 09.02.03 "Программирование в компьютерных системах"

Лекция 1. 1

АЛГОРИТМ И ЕГО СВОЙСТВА.. 1

1       ОПРЕДЕЛЕНИЕ АЛГОРИТМА. ПРАВИЛА ИСПОЛНЕНИЯ АЛГОРИТМА. 1

5       ЛИНЕЙНЫЙ АЛГОРИТМ... 4

УСЛОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ.. 6

6       ВЕТВЛЕНИЕ. УСЛОВИЯ. 6

7        ВЫБОР. 10

ЦИКЛИЧЕСКИЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ.. 11

8       ЦИКЛ. ВИДЫ ЦИКЛОВ. 11

9       ЦИКЛ С ПРЕДУСЛОВИЕМ (ПОКА). 11

10          ЦИКЛ С ПОСТУСЛОВИЕМ (ДО). 11

11          ЦИКЛ С ПАРАМЕТРОМ (ПРЕДОПРЕДЕЛЕННЫЙ) 12

Лекция 1               

АЛГОРИТМ И ЕГО СВОЙСТВА

1        ОПРЕДЕЛЕНИЕ АЛГОРИТМА. ПРАВИЛА ИСПОЛНЕНИЯ АЛГОРИТМА

            Понятие алгоритма является в информатике одним из фундаментальных. Термин алгоритм был позаимствован из математики. Происходит термин алгоритм от латинского Algorithmi – написания имени выдающегося математика средневекового Востока Мухамеда аль-Хорезми (787-850).

            В настоящее время понятие алгоритм используется в различных науках и имеет различные определения. Даже в информатике этот термин имеет целый ряд определений, эти определения дают описание алгоритма с различной степенью детализации и акцентом на те его стороны, которое будут востребованы в том или ином направлении. 

            Например:

1)      Алгоритм – это последовательность команд для управления каким - либо исполнителем. (школьный курс информатики)

2)      Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные, называемые также входом алгоритма или его аргументом, и выдающая результат вычислений на выход. (Томас Кормен. Алгоритмы: построение и анализ)

3)      Алгоритм – это процедура выполнения определенной задачи. Алгоритм является основополагающей идеей любой компьютерной программы. (Стивен Скиена. Алгоритмы: руководство по разработке)

Мы будем придерживаться следующего определения:

Алгоритм - это определенным образом организованная последовательность действий, за конечное число шагов приводящая к решению задачи.

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

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

1. Действия в алгоритме выполняются в порядке их записи
2. Нельзя менять местами никакие два действия алгоритма

3.      Нельзя не закончив одного действия переходить к следующему

2        СВОЙСТВА АЛГОРИТМОВ

Определенность – каждое действие имеет единственно возможный вариант исполнения.

Дискретность – состоит из отдельных, завершенных, локализованных действий. В записи дискретность – каждое действие с новой строчки.

Целенаправленность – каждое действие направлено на достижение общей цели – решить поставленную задачу.

Конечность – состоит из конечного числа действий и не зацикливается.

Массовость – подходит для решения класса задач.

3        СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ

Для записи алгоритмов используются специальные языки:

1. Естественный язык (словесная запись)
2. Формулы
3. Псевдокод
4. Структурограммы
5. Синтаксические диаграммы
6. Графический (язык блок-схем)

1.      Естественный язык:
если условие то действие1 иначе действие2

2. Структурограмма:
   
3. Синтаксическая диаграмма:
   
4. Графический язык:
   

4        АЛГОРИТМИЧЕСКИЙ ЯЗЫК БЛОК-СХЕМ

Составление алгоритмов графическим способом изначально подчинялось двум ГОСТам:

1. ГОСТ 19.002-80, соответствующего международному стандарту ИСО 2636-73,  регламентирующему правила составления блок-схем.
2. ГОСТ 19.003-80, соответствующего международному стандарту ИСО 1028-73, регламентирующему использование графических примитивов.

В настоящее время стандарт един  и регламентирует все части составления  и записи алгоритмов на языке блок – схем, это ГОСТ 19.701-90 ЕСПД. «Схемы алгоритмов, программ, данных и систем».

Название	Символ (рисунок)	Выполняемая функция (пояснение)
1. Блок процесс		Выполняет вычислительное действие или группу действий
2. Логический блок		Выбор направления выполнения алгоритма в зависимости от условия
3. Блок ввода/вывода		Ввод или вывод данных вне зависимости от физического носителя
		Вывод данных на печатающее устройство
4. Начало/конец (вход/выход)		Начало или конец программы, вход или выход в подпрограмму
5. Предопределенный процесс		Вычисления по стандартной или пользовательской подпрограмме
6. Блок модификации		Выполнение действий, изменяющих пункты алгоритма
7. Соединитель		Указание связи между прерванными линиями в пределах одной страницы
8. Межстраничный соединитель		Указание связи между частями схемы, расположенной на разных страницах

Правила построения блок-схем:

-        Все блоки в схеме вычерчиваются на основе прямоугольника с соотношением сторон 2:3.

-        Блоки в схеме располагаются в одном направлении либо сверху вниз, либо слева направо. Это направление называется основным.

-        Блоки в схеме соединяются линиями потока информации – отрезками.

-        В направлениях противоположных основным линии потока, в местах входа в схему, дополняются стрелочными указателями.

-        Каждый блок имеет не более одной входящей и не более одной исходящей линий потока информации. Исключением являются логические блоки.

-        Все повороты линий потока информации выполняются под прямым углом.

-        Между параллельными линиями потока информации должно быть расстояние не менее 3 мм. А между линией и параллельной ей стороной блока – не менее 5 мм.

5        ЛИНЕЙНЫЙ АЛГОРИТМ

Линейным называется алгоритм действия в котором выполняются строго одно за другим без повторов или возвратов к ранее выполненному.

Основными действиями линейных алгоритмов являются присваивания и ввод-вывод данных.

Рассмотрим пример решения задачи с использованием линейного алгоритма.

Составьте алгоритм вычисления значения функции y(x) )=x²-7x+6, при заданном значении х=0,23

                        Правильность составленного алгоритма нужно проверять тестированием. Для линейного алгоритма достаточно одного теста. Записывать тесты можно любым способом, например в таблицу.

Вводимое значение аргумента х	Ожидаемое значение функции Y(x)
1	0

Рассмотрим еще один пример.

Запишите выражение, зависящее от координат точки, и принимающее значение ИСТИНА, если точка принадлежит заштрихованной области, и ЛОЖЬ, если не принадлежит. Задана область:

Определить попадает ли в эту область точка с координатами (1,87; 1,45), а также любая точка с координатами заданными пользователем.

Построение математической модели задачи.

Заданная на рисунке область является объединением двух областей: треугольной части и части круга. Составим уравнение каждой части.

1)                 треугольная область является пересечением трех полуплоскостей. Первая задается неравенством y>=0, вторая неравенством x<=0. Для составления неравенства определяющего третью полуплоскость составим уравнение прямой проходящей через две точки. Из рисунка видно, что прямая проходит через точки с координатами (-3; 0) и (0; 2). Подставим эти координаты в общее уравнение прямой:    получим равенство . Преобразовав его получим уравнение прямой в виде  2x-3y+6=0. Определим знак неравенства задающего полуплоскость. Для этого подставим координаты точки, заведомо лежащей в искомой полуплоскости в уравнение прямой, пусть это точка (0; 0). В левой части неравенства получим 2*0-3*0+6, а справа 0, т.е. 6>0. Следовательно третью полуплоскость задает неравенство: 2x-3y+6>=0. Т.к. треугольник образован пересечением трех полуплоскостей, то объединим их неравенства логической операцией «И». Получим запись:

(x<=0) И (y>=0) И (2x-3y+6>=0)

2)                 Вторая часть задается пересечением круга и двух полуплоскостей. Полуплоскости заданы неравенствами: x>=0 и y>=0. Для определения неравенства задающего круг воспользуемся уравнением окружности вида: (x-a)²+(y-b)²=r², где (a; b)- координаты центра окружности, а r-ее радиус. Подставив данные рисунка получим: x²+y²=4. Т.к. нас интересует только внутренняя часть круга, то зададим следующее неравенство: x²+y²<=4.  Т.к. вторая часть области являет пересечением полуплоскостей, то запишем их неравенства объединив логической конструкцией «И».

(x>=0) И (y>=0) И (x*x+y*y<=4)

3)                 Область заданная рисунком содержит в себе как первую так и вторую части, т.е. является их объединением, поэтому включим определенные нами неравенства в общую запись с помощью конструкции «ИЛИ»:

 (x<=0) И (y>=0) И (2x-3y+6>=0) ИЛИ (x>=0) И (y>=0) И (x*x+y*y<=4)

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

Построим таблицу тестирования.

Как расположена точка	Координата X	Координата Y	Ожидаемый результат
Попала в левую (треугольник) часть области	-1	1	ИСТИНА
Попала в правую (часть круга) часть области	1	1	ИСТИНА
Не попала в область на рисунке	2	2	ЛОЖЬ

Лекция 2               

УСЛОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

6        ВЕТВЛЕНИЕ. УСЛОВИЯ

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

Ветвление - управляющая структура, организующая выполнение лишь одного из двух указанных действий в зависимости от справедливости некоторого условия.

Условие - вопрос, имеющий два варианта ответа: да или нет.

Условие – предложение истинность которого возможно установить.
Запись ветвления выполняется в двух формах: полной и неполной.
Полная форма:

 

Неполная форма:

Сложное или составное условие – предложение составленное из простых условий и логических операций И, ИЛИ, НЕ и т.п.

Для определения истинности сложных условий используются специальные таблицы

А	НЕ (А)
И	Л
Л	И

А	В	(А) И (В)
И	И	И
Л	И	Л
И	Л	Л
Л	Л	Л

А	В	(А) ИЛИ (В)
И	И	И
Л	И	И
И	Л	И
Л	Л	Л

Пример: найти наименьшее из трех чисел.
1 вариант решения:

2 вариант решения:

Рассмотрим еще один пример.

Составьте алгоритм вычисления значения функции при любых значениях аргументов.

Построение математической модели задачи.

При x>5 значение функции y определяется по формуле . Вычисление арифметического квадратного корня возможно только в том случае, когда подкоренное значение не отрицательно. Найдем математическое решение неравенства x-80;x8.

Решая два неравенства в системе, определяем, что в случае, когда x>5 решение возможно только при  x8.

При x<-5 значение функции y определяется по формуле . Приведенная формула содержит дробь, в знаменателе которой содержится переменная, следовательно, вычисления возможны только в том случае, когда знаменатель дроби отличен от 0. Найдем математическое решение уравнения 7+x=0;x=-7.

Следовательно, получая значение x меньшее -5 необходимо проверить, не равно ли оно -7, т.к. в этом случае решения у задачи нет.

При -55 функция y вычисляется по формуле . Так же как и в предыдущем случае в вычислениях используется дробь, следовательно, ее знаменатель не должен быть равным нулю. Найдем математическое решение  уравнения x-3=0;x=3.

Следовательно, получая значение x на отрезке [-5;5] необходимо проверить, не равно ли оно 3, т.к. в этом случае решения у задачи нет.

Запись алгоритма решения на языке блок-схем

Построение таблицы тестирования

1 способ.

x	x>5						y
	Да		Нет
	x8		x<-5
	Да	Нет	Да		Нет
			x7		x3
			Да	Нет	Да	Нет

2 способ.

x	x>5		x8		x<-5		x-7		x3		y
	Д	Н	Д	Н	Д	Н	Д	Н	Д	Н

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

x	x>5		x8		x<-5		x-7		x3		y
	Д	Н	Д	Н	Д	Н	Д	Н	Д	Н
9	+		+								1
4	+			+							Нет реш
-6		+			+		+				6
-7		+			+			+			Нет реш
4		+				+			+		1
3		+				+				+	Нет реш

7         ВЫБОР

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

 

Лекция 3               

ЦИКЛИЧЕСКИЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

8         ЦИКЛ. ВИДЫ ЦИКЛОВ

Цикл – ситуация, в которой в зависимости от истинности некоторого условия выполняется повторное исполнение группы действий.

Цикл - управляющая структура, организующая многократное выполнение указанного действия.

 Зацикливание - бесконечное повторение выполняемых действий.

9        ЦИКЛ С ПРЕДУСЛОВИЕМ (ПОКА)

Выполнение цикла "пока" начинается с проверки условия, поэтому такую разновидность циклов называют циклы с предусловием. Переход к выполнению действия осуществляется только в том случае, если условие выполняется, в противном случае происходит выход из цикла. Можно сказать, что условие цикла "пока" - это условие входа в цикл. В частном случае может оказаться, что действие не выполнялось ни разу. Условие цикла необходимо подобрать так, чтобы действия, выполняемые в цикла, привели к нарушению его истинности, иначе произойдет зацикливание.

10    ЦИКЛ С ПОСТУСЛОВИЕМ (ДО)

Исполнение цикла начинается с выполнения действия. Таким образом, тело цикла будет реализовано хотя бы один раз. После этого происходит проверка условия. Поэтому цикл "до" называют циклом с постусловием. Если условие не выполняется, то происходит возврат к выполнению действий. Если условие истинно, то осуществляется выход из цикла. Таким образом, условие цикла "до" - это условие выхода. Для предотвращения зацикливания необходимо предусмотреть действия, приводящие к истинности условия.

11    ЦИКЛ С ПАРАМЕТРОМ (ПРЕДОПРЕДЕЛЕННЫЙ)

Цикл с параметром, или цикл со счетчиком, или арифметический цикл - это цикл с заранее известным числом повторов.

В блоке модификации указывается закон изменения переменной I параметра цикла.
i_o - начальное значение параметра
h - шаг
i_n - последнее значение параметра.

При создании циклов с параметром необходимо помнить правила:

1. Параметр цикла, его начальное и конечное значения и шаг должны быть одного типа.
2. Запрещено изменять в теле цикла значения начальное, текущее и конечное для параметра.
3. Запрещено входить в цикл, минуя блок модификации.
4. Если начальное значение больше конечного, то шаг - число отрицательное.
5. После выхода из цикла значение переменной параметра неопределенно и не может использоваться в дальнейших вычислениях.

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

1.5. Использование циклов с параметром для обработки массивов.

Массив - упорядоченная структура, предназначенная для хранения однотипных данных.
Упорядочение элементов в массиве происходит по их индексам.
Индекс - порядковый номер элемента.
Массив задается именем (заглавные латинские буквы), типом данных, размерностью и размером.
Размер - максимально возможное количество элементов в массиве. В один момент времени можно обратиться только к одному элементу массива. Для этого указывается имя массива и в скобках индекс элемента.

Размерность – количество индексов у каждого элемента.
В зависимости от размерности массивы делятся на одномерные (линейные) и двумерные.
Прообразом в математике для одномерного массива является вектор. Для двумерного - матрица.
Пример: вычислить n!

Пример: вычислить aⁿ


Пример: ввести элементы массива:
а)одномерного, размерности 10

б)двумерного, 5x5

Структура программных продуктов

В большей степени программные продукты не являются монолитом и имеют конструкцию (архитектуру) построения - состав и взаимосвязь программных модулей.

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

Таким образом, программный продукт обладает внутренней организацией, или же внутренней структурой, образованной взаимосвязанными программными модулями. Это справедливо для сложных и многофункциональных программных продуктов, которые часто называются программными системами.

Структуризация программ выполняется в первую очередь для удобства разработки, программирования, отладки и внесения изменений в программный продукт

Структурное ``разбиение'' программ на отдельные составляющие служит основой и для выбора инструментальных средств их создания, хотя имеет место и обратное влияние - выбор инструментальных средств разработчика программного обеспечения определяет типы программных модулей. При создании программных продуктов выделяются многократно используемые модули, проводится их типизация и унификация, за счет чего сокращаются сроки и трудозатраты на разработку программного продукта в целом.

Некоторые программные продукты используют модули из готовых библиотек стандартных подпрограмм, процедур, функций, объектов, методов обработки данных.

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

Рис 1.4. Структура программного продукта

Среди множества модулей различают:

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

В работе программного продукта активизируются необходимые программные модули. Управляющие модули задают последовательность вызова на выполнение очередною модуля. Информационная связь модулей обеспечивается за счет использования общей базы данных либо межмодульной передачи данных через переменные обмена.

Каждый модуль может оформляться как самостоятельно хранимый файл; для функционирования программного продукта необходимо наличие программных модулей в полном составе.

Модульное проектирование программных средств

Модульное проектирование является одним из первых подходов к разработке структуры ПС и в настоящее время является классическим подходом.

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

Модульная программа – это программа, в которой любую часть логической структуры можно изменить, не вызывая изменений в других ее частях.

Признаки модульности программ:

-          программа состоит из модулей

-          модули являются независимыми. Это значит, что модуль можно изменять или модифицировать без последствий в других модулях.

-          Условие «один вход – один вход». Каждый модуль имеет одну точку входа и одну точку выхода. В общем случае может быть более одного входа, но важно, чтобы точки входов были определены и другие модули не могли входить в данный модуль в произвольной точке.

Достоинства модульного проектирования:

-          Упрощение разработки ПС

-          Исключение чрезмерной детализации обработки данных

-          Упрощение сопровождения ПС

-          Облегчение чтения и понимания программы

-          Облегчение работы с данными, имеющими сложную структуру

Недостатки модульности:

-          Модульный подход требует большего времени работы центрального процессора (в среднем на 5-10 %) за счет времени обращения к модулям

-          Модульность программы приводит к увеличению ее объема (в среднем на 5-10%)

-          Модульность требует дополнительной работы программиста и определенных навыков проектирования ПС.

Классические методы структурного проектирования модульных ПС делятся на три основные группы:

1.      Методы нисходящего проектирования;

2.      Методы расширения ядра;

3.      Методы восходящего проектирования.

Методы нисходящего проектирования

Основное назначение нисходящего проектирования – служить средством разбиения большой задачи на меньшие подзадачи так, чтобы каждую подзадачу можно было рассматривать независимо.

Суть метода заключается в следующем.

На начальном шаге в соответствии с общими функциональными требованиями к программному средству разрабатывается его укрупненная структура, без детальной проработки его отдельных частей. Затем выделяются функциональные требования более низкого уровня и в соответствии с ними разрабатываются отдельные компоненты программного средства, не детализированные на предыдущем шаге. Эти действия являются рекурсивными, то есть каждый из компонентов детализируется до тех пор, пока его составные части не будут окончательно уточнены. В последнем случае принимается решение о прекращении дальнейшего проектирования.

На каждом шаге нисходящего проектирования делается оценка правильности вносимых уточнений в контексте правильности функционирования разрабатываемого программного средства в целом.

Компоненты нижнего уровня ПС называются программными модулями. Для модулей характерны достаточная простота и прозрачность, позволяющие выполнять их непосредственное программирование.

Таким образом, на каждом шаге разработки уточняется реализация фрагмента алгоритма, то есть решается более простая задача. Следует отметить, что метод нисходящего проектирования положен в основу стандартного процесса разработки, регламентированного стандартом СТБ ИСО/МЭК 12207-2003.

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

-          Пошаговое уточнение; данная стратегия разработана Э.Дейкстрой

-          Анализ сообщений; данная стратегия базируется на работах группы авторов (Йордана, Мейерса, Константайна).

Эти стратегии отличаются способами определения начальных спецификаций требований, методами разбиения задачи на части и правилами записи (нотациями), положенными в основу проектирования ПС.

Пошаговое уточнение

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

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

1.      Проектирование программного средства с помощью псевдокода и управляющих конструкций структурного программирования

2.      Использование комментариев для описания обработки данных

Преимущества метода пошагового уточнения:

-          Основное внимание при его использовании обращается на проектирование корректной структуры программы, а не на ее детализацию

-          Так как каждый последующий этап является уточнением предыдущего лишь с небольшими изменениями, то легко может быть выполнена проверка корректности процесса разработки на всех этапах.

Недостаток метода пошагового уточнения: на позднх этапах проектирования ПС может обнаружиться необходимость в структурных изменениях, требующих пересмотра более ранних решений.