Понятие алгоритма, свойства алгоритмов

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

ПРОГРАММА = АЛГОРИТМ + СТРУКТУРА ДАННЫХ

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

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

Понятие алгоритма является основным при составлении любого вида программ для ЭВМ. Программа для ЭВМ - алгоритм, оформленный специальным образом, конечная последовательность предписаний, определяющих процесс переработки входных данных в выходные. Согласно ГОСТу 19.781-74 под алгоритмом понимается “точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату”.

Слово алгоритм происходит от латинской формы написания имени выдающегося узбекского математика IX века Аль -Хорезми. Он впервые сформулировал правила выполнения арифметических действий с использованием арабских цифр.

Для примера рассмотрим алгоритм, изложенный Эвклидом для процесса нахождения наибольшего общего делителя (НОД) двух чисел. Даны два целых положительных числа m и n. Требуется найти их НОД.

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

1) нахождение остатка. Разделим m на n и остаток обозначим r

0 < r < n,

2) проверка остатка на равенство 0. Если r = 0, то вычисление заканчивается, n - искомое число,

3) замена m на n, n на r. Повторить с 1-ого этапа.

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

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

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

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

г. Свойство дискретности. Предопределенный алгоритмом вычислительный процесс можно расчленить на отдельные этапы, элементарные операции.

2. Способы описания алгоритмов

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

словесный (записи на естественном языке),

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

графический (изображение схем и графических символов),

программный (тексты на языках программирования).

1. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных и задается в произвольном изложении на естественном языке. Примером является описание задачи определения НОД двух чисел.

Способ прост для автора алгоритма, но для “исполнителей” часто неприемлем, т. к. не имеет строгой формализации, допускает неоднозначность толкования отдельных предписаний, многословен. Поэтому он не получил широкого распространения.

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

3. Наиболее распространенным и используемым способом описания алгоритмов является язык графических символов. Для изображения структур алгоритмов в нем используется совокупность блочных символов (блоков), соединяемых линиями передачи управления. Такое изображение называется методом блок-схем. Метод блок-схем можно применять на любом уровне абстракции. Поскольку алгоритмы воспринимаются в первую очередь визуально, их следует изображать таким образом, чтобы их структура выглядела четко и выразительно. Краткость, выразительность и планомерность при проектировании позволяют создать схемы алгоритмов высокого качества, т.е. блок-схема алгоритма - это графическое представление хода решения задачи.

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

Вид геометрических символов и правила выполнения схем стандартизированы. Перечень символов, их наименования, отображаемые функции, формы и размеры, а также правила выполнения схем содержатся в ГОСТах (ГОСТ 19.002-80,19.003-80), входящих в состав Единой системы программной документации (ЕСПД), принятой Госстандартом СССР в 1978 году. Рассмотрим символы, которые будут нами использоваться, в таблице 1.

Таблица 1

СИМВОЛ	НАЗВАНИЕ	ОТОБРАЖАЕМАЯ ФУНКЦИЯ
	Пуск - останов	Начало, конец, останов, вход и выход в подпрограммах
a   b	Процесс	Вычислительное действие или последовательность действий
	Решение	Проверка условия
а	Модификация	Начало цикла
a   0.15a	Предопределенный процесс	Вычисления по подпрограмме, стандартной подпрограмме
а	Документ	Вывод, печать результатов на бумаге
a   025.a	Ввод – вывод	Ввод данных в ЭВМ и вывод результатов обработки
0.5a	Межстраничный соединитель	Разрыв линий потока на одном листе
№ л. № с. 0.6а   0.5а	Межстраничный соединитель	Разрыв линий потока при переходе на другие листы

Окончание таблицы 1

	Ручной ввод	Ввод с клавиатуры
	Магнитный диск	Ввод (вывод) на (с) магнитного диска
	Магнитная лента	Ввод (вывод) на (с) магнитной ленты
	Комментарий	Запись пояснений
	Линия потока

Размер а должен выбираться из ряда 10, 15, 20 мм. Допускается увеличивать размер а на число, кратное 5. Размер b = 1,5а или 2а. При выполнении блок- схем алгоритмов необходимо придерживаться следующих основных правил.

1. Начало алгоритма отмечается символом “Пуск-останов”, из которого выходит одна линия и внутри которого записывается слово «начало», конец алгоритма этим же символом, на который может замыкаться одна или более линий, и не имеющего ни одной выходной линии, внутри записывается «конец».

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

Например: А = Х + 4; i = i + 1, < A > - - > B.

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

4. Блок “Решение” используется для обозначения переходов управления по условию. В каждом блоке решения должны быть указаны: вопрос, решение, условие или сравнение, которые он определяет. С помощью одного символа возможно 2, 3 и более направлений ветвления. Выходные стрелки должны быть помечены ответами так, чтобы были учтены все возможные ответы.

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

6. В пределах одной схемы допускается не более 2-х типоразмеров символов.

Пример: Блок-схема вычисления значения у = а^N.

Рис.1

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

да нет

Q1 B Q5

да

B1

Q2 Q3 Q4

нет

Q6

а) б) в)

Рис.2.

ЭТАП 3

Продолжительность 2 часа

Учебные вопросы:

1. Графические схемы линейных вычислительных процессов.

2. Графические схемы разветвляющихся вычислительных процессов.

Распределение времени:

ВВОДНАЯ ЧАСТЬ (характеристика занятия) 5 мин.

ПРАКТИЧЕСКАЯ РАБОТА 80 мин.

– графические схемы линейных вычислительных процессов 30 мин.

– графические схемы разветвляющихся вычислительных

процессов 50 мин.

ПОДВЕДЕНИЕ ИТОГОВ (анализ степени реализации

поставленных целей занятия, выставление оценок) 5 мин.

Рекомендации:

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

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

Практическая работа:

Поиск по сайту: