Введение в информационные системы. Брюхомицкий Ю.А. - 105 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

105
Граф, в котором вершинам соответствуют шаги, а ребрам – переходы
между шагами, называется блок-схемой алгоритма. Его вершины могут быть
двух видов: вершины, из которых выходит одно ребро соответствуют операто-
рам; вершины, из которых выходят более одного ребра соответствуют операто-
рам перехода или предикатам. Кроме того, имеется единственный оператор на-
чала
и единственный оператор конца, из которого не выходит ни одного ребра.
Особенностью блок-схемы является то, что связи, которые она описывает, не
зависят от того, являются ли шаги элементарными или представляют собой са-
мостоятельные алгоритмы (блоки). Точки разветвления, могут быть не только
двоичными, но и многозначными, важно чтобы верным был ровно
один из воз-
можных ответов. Примеры таких условий:
а) x < 0, x = 0, x > 0;
б) x < 5, 5 ≤ х < 20, х = 20, х < 20.
С помощью блок-схем можно несколько алгоритмов, рассматриваемых
как блоки, связать в один большой алгоритм. В частности, если алгоритм А
1
вычисляющий функцию f
1
(x), соединен с алгоритмом А
2
, вычисляющим функ-
цию f
2
(x) и при этом исходными данными для А
2
служит результат А
1
, то полу-
ченная блок-схема (рис. 7.2) задает алгоритм, вычисляющий f
2
(f
1
(x)), т.е. компо-
зицию f
1
и f
2
. Такое соединение алгоритмов называется композицией алгорит-
мов.
На блок-схеме хорошо видна разница между описанием алгоритма и
процессом его реализации. Описание – это граф, а процесс реализации – это
путь в графе. Различные пути в одном и том же графе возникают при различных
данных, которые создают разные логические условия (предикаты
) в точках
ветвления. Отсутствие сходимости означает, что в процессе вычисления не по-
является условий, ведущих к концу, и процесс идет бесконечно (зацикливается).
Блок-схемы хорошо отражают детерминизм алгоритмов и связи по
управлению, но при всей их наглядности не могут рассматриваться как язык
алгоритмов, поскольку не учитывают множество других факторов: связей
по
информации; сведений о данных, о памяти, об используемых наборах шагов
(отсутствие циклов в блок-схеме не означает, что их нет внутри неэлементар-
ных блоков) и др.
Языки, используемые для записи алгоритмов. Средства, используемые
для записи информации и, в частности, алгоритмов, образуют язык. Язык харак-
теризуется своим алфавитом, синтаксисом и
семантикой. Алфавит – это множе-
ство символов, используемых в языке. Синтаксис языка состоит из системы
правил, определяющих порядок построения выражений из символов алфавита.
Начало Конец
А
1
А
2
Рис. 7.2. Композиция алгоритмов

Страницы