Алгоритмы_Технологии программирования_ООП (1)

				Кафедра
		ВнутреннийУГАТУ		информатики
					УГАТУ
		блок
				Этапы
				проектирования и
				анализа алгоритмов
	Внешний
		блок
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	81	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	82
	Кафедра			Кафедра
	информатики			информатики
		Этапы проектирования и анализа алгоритмов		Этапы проектирования и анализа алгоритмов
			УГАТУ		УГАТУ
	1)	Понимание задачи.
	2)	Выбор:		Необходимо доказать, что алгоритм за
	•	исполнителя;
				ограниченный промежуток времени
	• вида решения (точное или приближенное);
				выдает требуемый результат для любых
	•	структур данных;
				корректных значений входных данных
	•	методики проектирования алгоритма
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	83	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	84

Кафедра				Кафедра	Оценка эффективности алгоритма
информатики				информатики
Этапы проектирования и анализа алгоритмов
			УГАТУ			УГАТУ
				И временная, и пространственная эффективности
				оцениваются в виде функции от некоторого
				параметра n, связанного с размером входных
Оценка эффективности алгоритма:				данных.
	временная (скорости работы) и			Временная эффективность измеряется путем
	пространственная (количество			подсчета числа основных операций,
				выполняемых в алгоритме.
	дополнительной оперативной памяти).
				Пространственная эффективность оценивается
Важными характеристиками являются				в виде количества дополнительных единиц
	также простота и универсальность			памяти, требуемых для работы алгоритма.
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	85		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	86
Кафедра		Оценка эффективности алгоритма		Кафедра	Оценка эффективности алгоритма
информатики				информатики
			УГАТУ			УГАТУ
Эффективность отдельных алгоритмов может				Значения некоторых функций, играющих особую
различаться в очень широких пределах для				роль в процессе анализа алгоритмов
разных наборов входных данных одинакового
размера.
Поэтому эффективность таких алгоритмов
оценивают для наихудшего, наилучшего и
типичного набора входных данных.
Когда размер входных данных n стремится к					Функция
бесконечности вычисляют порядок роста
функции.					Размер входных данных
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	87		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	88

Кафедра		Оценка эффективности алгоритма		Кафедра		Оценка эффективности алгоритма
информатики				информатики
			УГАТУ				УГАТУ
				Показательная функция 2n и функция вычисления
Программы, реализующие алгоритмы с				факториала n! имеют настолько высокий
	логарифмической функцией роста log2n,			порядок роста, что его значение становится
	будут выполняться практически			астрономически большим уже при умеренных
				значениях n. Говорят, что обе функции имеют
	мгновенно для всех диапазонов входных
				экспоненциальный порядок роста.
	данных реального размера.
				С помощью алгоритмов, в которых количество
				выполняемых операций растет по
				экспоненциальному закону, можно решить лишь
				задачи очень малых размеров.
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	89			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	90
Кафедра				Кафедра		Запись алгоритма нахождения НОД
информатики				информатики
Запись алгоритма на языке программирования						на FreePascal
			УГАТУ				УГАТУ
Для того чтобы с помощью ЭВМ можно было				var		m, n, d : integer;
				Begin
	решить конкретную задачу, недостаточно
				m := StrToInt(Edit1.Text);
	составить алгоритм ее решения, необходимо
				n := StrToInt(Edit2.Text);
	записать данный алгоритм на одном из
				if (n <> 0) And (m <> 0) then
	языков программирования.
					Repeat
Языки программирования относятся к						if (m > n) then
	формальным языкам, с их помощью алгоритм					m := m mod n
	можно записать в форме, понятной					else
	исполнителю.					n := n mod m;
					Until (m = 0) Or (n = 0);
В нашем случае исполнителем алгоритма				if (m = 0) then d := n else d := m;
	является компьютер.			Edit3.Text := IntToStr (d);
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	91	End; Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.			92

	Кафедра			Кафедра	Запись алгоритма нахождения НОД на C#
	Запись алгоритма нахождения НОД на VB.Net
	информатики			информатики
		УГАТУ					УГАТУ
	Dim m, n, d As integer			int m, n, d;
	m = val(textBox1.Text)			m = int.Parse(textBox1.Text);
	n = val(textBox2.Text)			n = int.Parse(textBox2.Text);
	if (n <> 0) And (m <> 0) Then			if (n != 0 && m != 0)
	do			{
	if (m > n) then					do
	m = m mod n					{
	else					if (m > n) m = m % n;
	n = n mod m					else n = n % m;
	end if					} while (m != 0 && n != 0) ;
	loop until (m = 0) or n = 0)			}
	end if			if (m == 0) d = n;
	if (m = 0) then d = n else d = m			else		d = m;
	textBox3.Text = Str(d)	93		textBox3.Text = d.ToString();			94
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.					Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

Кафедра	Кафедра
Инструментарий технологии программирования	Инструментарий технологии программирования
информатики	информатики
УГАТУ	УГАТУ

Трансляторы

Компиляторы

Интерпретаторы

создается

исполняемый файл

исполняемый

не создается,

файл, текст

текст программы

программы больше

Машинный код

нужен

не нужен

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

95

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

96

Кафедра			Кафедра
информатики			информатики
Инструментарий технологии программирования			Инструментарий технологии программирования
		УГАТУ				УГАТУ
Компиляторы			Интерпретаторы
• Исходный код просматривается полностью			• Очередной оператор исходного кода
• Проводится его синтаксический анализ				просматривается.
• Переводится в исполняемый машинный код			•	Проводится синтаксический анализ
			• Переводится в машинный код
			•	Исполняется
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	97			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	98
Кафедра	Языки программирования		Кафедра		Языки программирования
информатики			информатики
		УГАТУ				УГАТУ
Языки программирования – искусственные языки.			Нарушение формы записи программы приводит к
От естественных они отличаются ограниченным			синтаксической ошибке.
числом «слов» и очень строгими правилами			Правильно написанное, но не отвечающее
записи команд (операторов).			алгоритму использование команд языка, приводит
Синтаксис языка образует совокупность подобных			к семантическим ошибкам (логическим, ошибкам
требований программирования,			времени выполнения).
Семантика языка – смысл каждой команды и			Процесс поиска ошибок в программе называется
других конструкций языка.			тестированием, процесс устранения ошибок –
			отладкой.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	99			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	100

Кафедра	Языки программирования		Кафедра	Языки программирования
информатики			информатики
		УГАТУ				УГАТУ
Разные типы процессоров имеют разные			В данном случае «низкий уровень» не
наборы команд.			значит «плохой». Имеется в виду, что
Языки программирования ориентированные			операторы языка близки к машинному
на конкретный тип процессора, т.е.			коду и ориентированы на конкретные
являются машинно-зависимыми,			команды процессора.
относятся к языкам программирования			Языками низкого уровня являются все
низкого уровня.			языки ассемблеров.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	101		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		102
Кафедра	Языки программирования		Кафедра	Языки программирования
информатики			информатики
		УГАТУ				УГАТУ
Языки программирования, не учитывающие			Назначение языка		Название языка
особенности конкретных компьютерных
архитектур, относятся к языкам
программирования высокого уровня.
Программы написанные на таких языках на
уровне исходных текстов легко
переносятся на другие платформы, для
которых создан транслятор этого языка.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	103		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		104

Кафедра	Контрольные вопросы		Кафедра		Контрольные вопросы
информатики			информатики
		УГАТУ				УГАТУ
1. Что такое алгоритм?			10. Перечислите и приведите примеры записи базовых
2. Перечислите свойства алгоритма.				структур алгоритмов.
3. Что такое область допустимых значений входных данных			11. Как работает и как графически обозначается по ГОСТ
алгоритма?				базовая структура Ветвление (приведите примеры).
4. Чем следует руководствоваться при создании алгоритма?			12. Как работает и как графически обозначается по ГОСТ
				базовая структура Цикл с параметром (приведите
5. Приведите примеры объектов алгоритма.
				примеры).
6. Каким образом можно записать алгоритм.
			13. Как работает и как графически обозначается по ГОСТ
7. Перечислите этапы проектирования и анализа
				базовая структура Цикл с условием (приведите
алгоритмов.
				примеры).
8. Назовите оценки эффективности алгоритма.			14. Как работают и как графически обозначаются по ГОСТ
9. Когда необходимо оценивать эффективность алгоритма				Вложенные циклические структуры (приведите
для наихудшего, наилучшего и типичного набора входных
				примеры).
данных?
Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		105		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		106
Кафедра			Кафедра
информатики			информатики
	Тема		Этапы развития технологии программирования
		УГАТУ				УГАТУ
			Технологией программирования
	Технология программирования		называют совокупность методов и
			средств, используемых в процессе
•	Основные этапы развития		разработки программного обеспечения.
	технологии программирования;		Основные этапы развития технологии
•	Краткая характеристика этапов		программирования:
			I. «Стихийное» программирование (от появления
			первых вычислительных машин до середины 60-х
			годов XX в).
			II. Структурное программирование (60-70-е годы XX в)
				Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		108

Кафедра				Кафедра		«Стихийное» программирование
информатики				информатики
Этапы развития технологии программирования
			УГАТУ				УГАТУ
Основные этапы развития технологии				Структура первых
программирования:					программ это:
III. Объектно-ориентированное					программа на
					машинном языке и
	программирование (с середины 80-х до
					обрабатываемые ею
	конца 90-х годов ХХ века).
					данных.
IV. Компонентный подход к				Появление Ассемблеров позволило вместо
	программированию (с середины 90-х				двоичных или 16-ричных кодов использовать
	годов XX до нашего времени).				символические имена данных и мнемоники
V. Net-технология					кодов операций. В результате программы стали
					более «читаемыми».
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	109			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	110
Кафедра		«Стихийное» программирование		Кафедра		«Стихийное» программирование
информатики				информатики
			УГАТУ				УГАТУ
Создание языков программирования высокого				После появления подпрограмм
уровня, таких, как FORTRAN и ALGOL,					структура программы
существенно упростило программирование, это					изменилась:
позволило увеличить сложность программ.				•	основная программа;
				•	область глобальных
					данных;
				•	набор подпрограмм (в
					основном
					библиотечных),
					выполняющих
					обработку всех данных
					или их части.
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	111			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	112

Кафедра	«Стихийное» программирование		Кафедра		«Стихийное» программирование
информатики			информатики
		УГАТУ				УГАТУ
Использование подхода			Чтобы сократить количество искажений части
			глобальных данных, в подпрограммах стали
«снизу-вверх»
			размещать локальные данные.
(восходящее
проектирование):
вначале проектировали
и реализовывали
сравнительно простые
подпрограммы, из
которых затем
пытались построить
сложную программу.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	113			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	114
Кафедра	«Стихийное» программирование		Кафедра		«Стихийное» программирование
информатики			информатики
		УГАТУ				УГАТУ
			Этап стихийного программирования
				характеризуется:
			•	Проектированием «снизу-вверх»
				(восходящее);
			•	Появлением подпрограмм;
			•	Делением данных на глобальные и локальные;
			•	Появлением языков ассемблеров;
Интерфейсы подпрограмм получались сложными, и			•	Появлением языков программирования
при сборке программного продукта выявлялось				высокого уровня (FORTRAN, ALGOL).
большое количество ошибок согласования.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	115			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	116

Кафедра	Структурное программирование		Кафедра		Структурное программирование
информатики			информатики
		УГАТУ				УГАТУ
В основе лежит принцип декомпозиции			•	представление задачи в виде иерархии
(разбиение на части) сложных программ и				подзадач простейшей структуры;
реализация этих частей в виде отдельных			•	реализация подзадач в виде отдельных
небольших подпрограмм.				небольших подпрограмм.
Проектирование осуществляется «сверху вниз»			Эти принципы были заложена в основу
(нисходящее проектирование):				процедурных языков программирования
• реализация общей идеи, которая обеспечивает				(Фортран, Алгол, Кобол, PL/I, Basic, Pascal, Си).
проработку интерфейсов подпрограмм;
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	117			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	118
Кафедра	Структурное программирование		Кафедра		Структурное программирование
информатики			информатики
		УГАТУ				УГАТУ
Дальнейший рост сложности и размеров			Стремление разграничить доступ к глобальным
разрабатываемого программного обеспечения				данным программы, привело к возникновению
потребовал развития структурирования				технологии модульного программирования,
данных, в языках появляется возможность				которое предполагает выделение групп
определения пользовательских типов				подпрограмм, использующих одни и те же
данных.				глобальные данные, в отдельно компилируемые
				модули (библиотеки подпрограмм), например,
				модуль графических ресурсов, модуль
				подпрограмм вывода на принтер и т.п.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	119			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	120