Тема_Алгоритмы

	Кафедра	ЛЕКЦИИ ПО ИНФОРМАТИКЕ		Кафедра		Тема
	информатики		УГАТУ	информатики			УГАТУ
		Для студентов факультета АТС
		групп МХ, ММ, СМ, ФМ, АТП, ТМ, ВТ
	Составители:					Алгоритмы
	доценты Кафедры Информатика
	Ахметсафина Римма Закиевна
	Карчевская Маргарита Петровна
	Рамбургер Ольга Леонардовна
		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	1
	Кафедра	Понятие алгоритма		Кафедра	Понятие алгоритма
	информатики			информатики
			УГАТУ				УГАТУ
	Понятие алгоритма является одним из			Алгоритм – конечный набор точных и понятных
				исполнителю предписаний, позволяющих
	основных понятий современной			решать конкретную задачу из определенного
	информатики.			класса однотипных задач.
	Термин алгоритм произошел от латинской			Исполнителем может быть человек, группа людей, робот,
	формы написания имени выдающегося			станок, компьютер, язык программирования и т.д.
	математика IX века Аль Хорезми (algorithmi),			Исполнитель имеет в наличии только некоторую совокупность
				команд (систему команд исполнителя – СКИ), которую может
	который сформулировал правила
				использовать при выполнении алгоритма для получения
	выполнения четырех арифметических			необходимого результата.
	действий в десятичной системе счисления.			Исполнитель действует формально, отвлеченно от содержания
				поставленной задачи, не вникая в смысл того, что он делает,
				только строго выполняет некоторые правила, инструкции,
				команды
		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	3		Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	4

Кафедра	Понятие алгоритма		Кафедра		Понятие алгоритма
информатики			информатики
	УГАТУ					УГАТУ
Наличие алгоритма формализует процесс решения			Понятие алгоритма связано с понятием исходных данных и
задачи, исключает рассуждение исполнителя.				искомого результата, поскольку назначением любого алгоритма
				является преобразование исходных данных в искомый
Использование алгоритма дает возможность				результат. При этом исходные данные выбираются из
решать задачу формально, механически				некоторой области, которая называется областью допустимых
				значений исходных данных.
исполняя команды алгоритма в указанной			Преобразование исходных данных в искомый результат
последовательности.				выполняется на основе знаний о предметной области. Знания,
				как правило, имеют вид различных естественных законов
Целесообразность предусматриваемых				(физических, химических, биологических, экономических и т.д.),
				либо абстрактных законов (математические формулы, правила
алгоритмом действий обеспечивается точным
				или теоремы).
анализом со стороны того, кто составляет этот			На основе знаний при составлении алгоритма формируются
алгоритм.				цепочки действий, приводящих к искомому результату.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	5			Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	6
Кафедра	СВОЙСТВА АЛГОРИТМА		Кафедра		СВОЙСТВА АЛГОРИТМА
информатики			информатики
	УГАТУ					УГАТУ
Дискретность. Путь решения задачи определен в виде			Подводя итог выше сказанному, можно дать следующее
последовательности шагов – четко разделенных друг от друга
			понятие алгоритма.
предписаний. Только выполнив одно предписание, можно
приступить к выполнению следующего.			Алгоритм – это последовательность однозначных
Понятность. Алгоритм создается в расчете на определенного
			понятных исполнителю предписаний, исполнение
исполнителя, необходимо, чтобы он мог понять и выполнить
каждый шаг предписания.			которых позволяет за конечное число шагов
Детерминированность. Процесс применения правил к исходным			получить искомый результат, определяемый
данным (путь решения задачи) определен однозначно.			исходными данными для однотипных задач
Результативность. На каждом шаге процесса применения правил
			некоторого класса.
известно, что считать результатом этого шага, а сам процесс
должен закончиться за конечное число шагов.
Массовость. Означает, что алгоритм применим к целому классу			Примечание. Это понятие алгоритма применимо для практических
однотипных задач, а при решении конкретной задачи из класса
			задач, имеющих решение.
исходные данные могут меняться в определенных пределах.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	7			Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	8

Кафедра	Понятие алгоритма		Кафедра	СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ
информатики			информатики
	УГАТУ			УГАТУ
Когда задача или класс задач могут и не иметь решения требуется			Алгоритм можно записать с помощью
строго формализованное понятие алгоритма, чтобы иметь			естественного языка, с помощью псевдокода,
возможность доказать отсутствие решения.
			графически с помощью блок-схемы.
Определение такого понятия алгоритма стала одной из центральных
математических проблем.
Известно несколько подходов к формализации понятия «алгоритм»:			Описание алгоритма Евклида для нахождения наибольшего
- теория конечных и бесконечных автоматов (машины Поста и			общего делителя (НОД) двух целых неодинаковых
Тьюринга);			положительных чисел m и n:

-теория вычислимых (рекурсивных) функций;

-λ-исчисление Черча.

Все эти подходы исторически возникли независимо друг от друга, а в последствие оказались эквивалентными.

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

Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.

9

Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.

10

Кафедра

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

Графический способ записи алгоритмов

Кафедра

информатики

информатики

УГАТУ

УГАТУ

Обозначение некоторых блоков в соответствии с

На естественном языке

На языке псевдокода

На языке блок-схем

ГОСТ 19.701-90 СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ

нач цел m,n,x,y,f

ДАННЫХ И СИСТЕМ

Шаг 1: Задать числа m и n.

ввод m,n

Шаг 2: Если m больше n, то

нц

сделать m равным остатку от

если (m>n)

деления m на n, иначе

то m:=mod (m,n)

сделать n равным остатку от

иначе n:=mod(n,m)

деления n на m.

Шаг 3: Если m и n не равны

все

нулю, то перейти к шагу 2.

кц до (m=0) or (n=0)

Шаг 4: Если m равно нулю, то

если (m=0)

НОД равен n, иначе НОД

то d:=n

равен m.

иначе d:=m

все

вывод d

кон

Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2,

2009 г.

11

Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.

12

Кафедра			Кафедра
информатики			информатики
Графический способ записи алгоритмов			Графический способ записи алгоритмов
		УГАТУ		УГАТУ
			Блоки соединяются линиями потока информации. Внутри блоков записываются
			выполняемые действия. Линии со стрелками определяют направление
			вычислений.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	13	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	14
Кафедра Основные правила применения символов и			Кафедра
информатики	выполнения схем согласно ГОСТ		информатикиБазовые алгоритмические структуры
		УГАТУ		УГАТУ
• символы в схеме должны быть расположены равномерно;			Практически любой сложный алгоритм
• следует избегать большого числа длинных линий и пересечений;
			представляет собой комбинацию трех типов
• не допускается изменения углов в начертании символов;
			базовых алгоритмических структур: линейного,
• если объем текста, помещаемого внутри символа, превышает его
размеры, то следует использовать символ комментария;			разветвляющегося и циклического.
• в схемах может использоваться идентификатор символов,
располагаемый слева над символом, который определяет символ			Линейные алгоритмические структуры (следование)
для использования в справочных целях;
			состоят из последовательности операций, выполняющихся
• потоки данных или управления показываются линиями, и если
			только один раз в порядке их следования
поток имеет направление, отличное от стандартного (направление
потока слева направо и сверху вниз считается стандартным), то
стрелки должны указывать это направление;
• входящие линии могут объединяться в одну исходящую линию, при
этом место их объединения должно быть смещено;
• линии в схемах должны подходить к символу либо слева, либо
сверху, а исходить либо справа, либо снизу и направлены к центру
символа.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	15	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	16

Кафедра				Кафедра
информатикиБазовые алгоритмические структуры			УГАТУ	информатикиБазовые алгоритмические структуры			УГАТУ
				Разветвляющиеся алгоритмические
				структуры (ветвление)
				обеспечивают выбор между
В блок-схемах для записи				двумя альтернативами.
				Выполняется проверка
линейной алгоритмической				некоторого условия, а затем
структуры используется				выбирается один из путей
блок «Процесс».				продолжения алгоритма.
				Подобная структура называется
				также «ЕСЛИ – ТО – ИНАЧЕ»,
				или «развилка». Каждый из путей
				(ТО или ИНАЧЕ) ведет к общей
				точке слияния, так что
				выполнение программы
				продолжается независимо от
				того, какой путь был выбран.
Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2,	2009 г.	17	Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2,	2009 г.	18
Кафедра				Кафедра
информатикиБазовые алгоритмические структуры			УГАТУ	информатикиБазовые алгоритмические структуры			УГАТУ
Для графического способа записи
разветвляющих алгоритмов
используется блок «Принятие
решения», внутри которого
записывается логическое				Пример. Найти квадрат
выражение .				наибольшего из трех
Может оказаться, что для одного из				заданных чисел: a, b, c.
результатов проверки ничего
предпринимать не надо. В этом
случае можно применять только
один обрабатывающий блок. Такие
структуры называют «Неполное
ветвление» или «ЕСЛИ – ТО»,
Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2,	2009 г.	19	Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2,	2009 г.	20

	Кафедра					Кафедра
	информатикиБазовые алгоритмические структуры				УГАТУ	информатикиБазовые алгоритмические структуры			УГАТУ
	Пример. Даны действительные числа x, y – координаты точки.					Циклические алгоритмические структуры обеспечивают
						многократное выполнение одной и той же последовательности
	Определить принадлежит ли точка (x, y) области,
						действий для различных значений, входящих в них
	заштрихованной на рисунке.
						переменных.
						Основной блок цикла, тело цикла, производит требуемые
						вычисления. Остальные блоки организуют циклический
	R1	R2				процесс: устанавливают начальные и новые значения данных,
						проверяют условия окончания или продолжения циклического
						процесса.
						Циклический алгоритм позволяет компактно описать большое
						число одинаковых вычислений над разными данными для
						получения необходимого результата.
						Различают два типа структур цикла:
						- цикл с параметром или с повторением;
						- цикл с условием.
	Информатика		ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	21	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	22
	Кафедра					Кафедра
	информатикиБазовые алгоритмические структуры				УГАТУ	информатикиБазовые алгоритмические структуры			УГАТУ
	Циклы с параметром используют тогда, когда						Выполняется базовая циклическая структура типа
	количество повторов тела цикла заранее известно.
							«Цикл с параметром» следующим образом:
	Для графического способа записи таких алгоритмов используется						1. Параметру цикла k присваивается начальное
	блок «Модификация», внутри которого записывается как						значение a и сравнивается с конечным значением b.
	изменяется параметр цикла .						Если начальное значение параметра цикла
							превышает (при положительном шаге цикла) конечное
			блок организующий циклический процесс				значение, то тело цикла ни разу не выполнится;
							2. Выполняется тело цикла;
			тело цикла			3. Текущее значение параметра цикла k увеличивается (или уменьшается)
						на значение шага h. Результат операции k+h присваивается параметру
						цикла k, старое значение при этом теряется;
			k –параметр цикла, a – начальное значение			4. Проверяется условие окончания цикла: текущее значение параметра
			параметра цикла,			сравнивается с конечным значением b. Если значение параметра цикла
			b – конечное значение параметра цикла,			становится больше конечного (при положительном шаге h), то
			h – шаг изменения параметра цикла.			происходит выход из цикла, иначе происходит переход к пункту 2.
	Информатика		ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	23	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	24

Кафедра	Базовые алгоритмические структуры		Кафедра		Базовые алгоритмические структуры
информатики			информатики
		УГАТУ				УГАТУ
			Циклы с условием используются тогда, когда
Пример. Вычислить значения				число повторений цикла заранее неизвестно,
функции y = f(x) некоторой				но задано условие окончания цикла.
переменной х, изменяющейся
от начального значения х0 до
конечного хk с постоянным			Для графического способа записи таких алгоритмов
шагом h (протабулировать				используется блок «Границы цикла».
функцию на заданном
промежутке [х0 , хk] с шагом h).
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	25			Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	26
Кафедра	Базовые алгоритмические структуры		Кафедра
информатики		УГАТУ	информатикиБазовые алгоритмические структуры			УГАТУ
Если условие окончания цикла проверяется перед выполнением			Если проверка условия происходит после выполнения тела цикла –
тела цикла, то такие циклические структуры называют циклами с
			циклами с постусловием («Выполнять до тех пор пока не»)
предусловием («Выполнять пока»)
					Начало цикла
	Блок организующий циклический процесс
	Тело цикла				Тело цикла
	Значение логического выражения в условии вычисляется				Блок организующий циклический процесс
	перед каждым выполнением тела цикла.				Вначале выполняется тело цикла, затем проверяется
	Если оно истинно, то выполняется тело цикла и снова				условие выхода из цикла.
	вычисляется выражение условия.				Если значение логического выражения ложно, тело
	Если результат имеет ложное значение, происходит				цикла выполняется еще раз, если истинно –
	выход из цикла.				происходит выход из цикла.
	Конец цикла		Таким образом, цикл продолжает свою работу, до тех пор пока значение
Таким образом, цикл продолжает свою работу, пока значение логического				логического выражения остается ложным.
выражения остается истинным.			Тело цикла с постусловием всегда выполняется хотя бы один раз.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	27			Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	28

Кафедра			Кафедра	Базовые алгоритмические структуры
информатикиБазовые алгоритмические структуры		УГАТУ	информатики						УГАТУ
Чтобы циклы с условием успешно			Пример. Алгоритм Евклида
			для нахождения наибольшего
завершились необходимо, чтобы в теле
			общего делителя (НОД) двух
цикла был хотя бы один оператор,			целых неодинаковых
изменяющий значения, входящих в			положительных чисел m и n.
логическое выражение переменных.
Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	29		Информатика	ФАП - 2, ФАТС – 2, 3		курс 1,	семестр 2, 2009 г.	30
Кафедра	Вложенные циклы		Кафедра		Вложенные циклы
информатики			информатики
		УГАТУ							УГАТУ
Если телом цикла является также циклическая			Пример. Вычислить
структура, то такие циклы называют				произведение
вложенными. Тип циклов при этом может				n	m	i
				∏ ∏
быть любым.
				i=1	j =1 1 + j 2
При построении вложенных циклических				Внутренний
структур всегда следует соблюдать правило:
				блок
все блоки внутреннего цикла должны
полностью лежать в теле внешнего цикла.			Внешний
				блок
Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	31		Информатика	ФАП - 2, ФАТС – 2, 3		курс 1,	семестр 2, 2009 г.	32

	Кафедра		Массивы		Кафедра	Массивы
	информатики				информатики
				УГАТУ				УГАТУ
	Многие задачи связаны с обработкой больших объемов				Массив – это конечная упорядоченная по индексу совокупность
	информации, представляющей совокупность данных,				однотипных данных, имеющая одно имя.
					Работа с массивом сводится к действиям над его элементами.
	объединенных единым математическим содержанием
	или связанных между собой по смыслу.				Индексы определяют положение элемента в массиве.
	Такие данные удобно представлять в виде линейных или				Массив характеризуется – именем, размерностью и размером.
	прямоугольных таблиц.
					Число индексов определяет размерность массива.
	В линейной таблице (список) каждому ее элементу
					Количество элементов в массиве определяет его размер.
	соответствует порядковый номер.
	Для элемента прямоугольной таблицы должны быть
	указаны два номера: номер по вертикали (номер строки)				Размерность массива – одномерный. Размер массива равен 5
	и номер по горизонтали (номер столбца).					Размерность массива –
	В алгоритмах для представления таких данных
						двумерный
	используются массивы.					Размер массива равен 12
	Информатика		ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	33	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2,	2009 г.	34
	Кафедра		Массивы		Кафедра	Массивы
	информатики				информатики
				УГАТУ				УГАТУ
	Элемент одномерного массива обозначается переменной с					Индексы одномерного массива
	одним индексом.
	Элемент двумерного массива обозначается переменной с
	двумя индексами. Первый индекс обозначает номер строки,
	а второй – номер столбца.
	Таким образом, для обращения к конкретному элементу
	массива необходимо указать имя массива и значения
	индексов:	ai ; bi, j
						Значения одномерного массива
	Информатика		ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	35	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2,	2009 г.	36

Кафедра	Массивы		Кафедра	Массивы
информатики			информатики
		УГАТУ			УГАТУ
	Индексы двумерного массива		Пример. В одномерном массиве чисел аi (i = 1, 2, …, N) найти
			сумму чисел с нечетными индексами (s1) и среднее
			арифметическое чисел с четными индексами (s2)
				Формирование одномерного массива
				Обработка одномерного массива
Значения двумерного массива
Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	37	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	38
Кафедра			Кафедра
информатики			информатики
Запись алгоритма на языке программирования			Запись алгоритма на языке программирования
		УГАТУ			УГАТУ
Для того чтобы с помощью ЭВМ можно было			Запись алгоритма Евклида для нахождения наибольшего общего
решить конкретную задачу, недостаточно			делителя (НОД) двух целых положительных неодинаковых чисел
составить алгоритм ее решения, необходимо			m и n на языках программирования
записать данный алгоритм на одном из			Microsoft Visual Basic	Pascal (Borland Delphi)
языков программирования.
Языки программирования относятся к
формальным языкам, с их помощью алгоритм
можно записать в форме, понятной
исполнителю.
В нашем случае исполнителем алгоритма
является компьютер.
Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	39	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	40