Глава 1. Основы информатики
§1.3. Алгоритмы. Свойства алгоритмов.
Схемы алгоритмов
Алгоритм — точное описание
последовательности действий, которые необходимо выполнить для решения задачи.
Практически, решение любой задачи можно представить в виде обработки сообщения типа «исходные данные» с целью получения сообщения типа «результат». Можно сказать, что алгоритм описывает процесс преобразования исходных данных в результат.
30.06.19 Доцент С.Т. Касюк |
2 |
Разработка алгоритма является важнейшим этапом решения любой задачи. Разработать алгоритм решения задачи означает разбить задачу на последовательно выполняемые шаги (этапы). При этом должно быть четко указано содержание каждого этапа и определена последовательность их выполнения. После разработки алгоритма его можно реализовать практически на любом языке программирования.
30.06.19 Доцент С.Т. Касюк |
3 |
Основные свойства алгоритмов:
1. Конечность. Понимается двояко: во-первых, алгоритм состоит из отдельных элементарных шагов, или действий, причем множество различных шагов, из которых составлен алгоритм, конечно. Во-вторых, алгоритм должен заканчиваться за конечное число шагов.
2. Элементарность (понятность). Каждый шаг алгоритма должен быть простым, чтобы устройство, выполняющее операции, могло выполнить его одним действием.
30.06.19 Доцент С.Т. Касюк |
4 |
3. Дискретность. Алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых и заранее определенных этапов; каждый из этих этапов выполняется некоторый конечный отрезок времени. Иными словами, алгоритм должен отображать дискретность процесса преобразования исходных данных в результат.
4. Определенность (детерминированность).
Каждое действие, указанное в алгоритме, должно быть четким, однозначным, не оставляющим место для произвола. Выполнение алгоритма должно иметь чисто механический характер и не должно требовать дополнительных указаний или сведений о решаемой задаче.
30.06.19 Доцент С.Т. Касюк |
5 |
5. Результативность. Результативность. Алгоритм имеет некоторое число входных величин — аргументов. Цель выполнения алгоритма состоит в получении конкретного результата. Алгоритм должен останавливаться после конечного числа шагов, зависящего от данных, с указанием того, что считать результатом. Если решение не может быть найдено, то должно быть указано, что в этом случае считать результатом.
6. Массовость. Алгоритм должен быть применим для решения целого класса задач, которые различаются лишь исходными данными.
30.06.19 Доцент С.Т. Касюк |
6 |
7. Эффективность. Одну и ту же задачу можно решить по-разному и соответственно за разное время и с различными затратами памяти. Желательно, чтобы алгоритм состоял из минимального числа шагов и при этом решение удовлетворяло бы условию точности и требовало минимальных затрат машинных ресурсов.
30.06.19 Доцент С.Т. Касюк |
7 |
Как представляется алгоритм? Сначала фиксируется в виде схемы, а затем переводится на алгоритмические языки, т. е. представляется в виде программы.
Полный перечень правил и условных обозначений для изображения схем алгоритмов приведен в ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем.
Схема — графическое представление определения, анализа или метода решения задачи, в котором используются символы для отображения операций, данных, потока, оборудования и т. д.
30.06.19 Доцент С.Т. Касюк |
8 |
Схема программы отображает последовательность операций в программе.
Схема программы состоит:
1)из символов процесса, указывающих фактические операции обработки данных;
2)из линейных символов со стрелками- указателями, указывающих поток данных;
3)из специальных символов, используемых для облегчения написания и чтения схем.
30.06.19 Доцент С.Т. Касюк |
9 |
Типовые действия, наиболее часто
встречающиеся в схемах программ
1.Вычисление, функция обработки данных любого вида (символ «процесс»)
2.Вызов функции (символ «предопределенный процесс»)
3.Начало или конец программы (символ «терминатор»)
30.06.19 Доцент С.Т. Касюк |
10 |