9. Сравнение способов записи алгоритмов: Логическая схема и Структурная схема. Достоинства и недостатки

1)Логическая схема алгоритма

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

Для записи алгоритмов используют основные типы операторов:

- арифметические операторы (обозначаются начальными заглавными буквами латинского алфавита),

- операторы проверки логических условий (малые буквы латинского алфавита),

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

- операторы переноса,

- операторы формирования. Логическая схема алгоритма Пример: Аор₁↑₁А₁↓₁р₂↑₂А₂А₃↓₂А₄Ак

Ао , Ак – операторы начала и конца, А₁… А₄ – операторы, р₁ , р₂ – логические условия.

Если р₁ = 1, то произойдет переход на оператор А₁, если = 0, то произойдет переход на оператор р₂

2) Структурная схема алгоритма

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

Блоки соединяются стрелками, показывающими связи между ними.

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

Достоинства:

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

2. Обеспечивается наглядное чтение и понимание алгоритмов.

3. Уменьшается число ошибок при программировании.

Структурная схема алгоритма. Примеры записи вершин графа

10.Описание графов с помощью матриц

1. Матрица смежности

Е сли задан граф G(X, U), то ему можно поставить в соответствие квадратную матрицу (матрицу смежности) размерностью n x n, где n – мощность множества вершин графа (m – кратность смежных ребер):

1. Матрица смежности. Пример

2. Матрица весовых соотношений

с троятся аналогично матрицам смежности, но значения их элементов определяются весом ребра графа (T_ij – вес связи):

3 . Матрица длин

Это квадратная матрица (L_ij – длина ребра):

4. Матрица инцидентности

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

П ример

5. Матрица смежности ребер

Э та матрица, элементы которой образуются по правилу

П ример

11. Формальное описание коммутационных схем

Э лементы схемы Граф Матрица

Любую схему можно представить как некоторое подмножество элементов X_L:

с оединенных между собой цепями из множества Е:

П редставляя гиперграф H (X, E) матрицей инцидентности B получаем удобную форму представления схемы в памяти ЭВМ.

Электрическую схему задают также в виде матрицы цепей:

К аждый элемент схемы имеет некоторое множество соединительных выводов, которые называются множеством контактов C.

Т огда любую схему можно задать в виде графа:

F – определяет принадлежность контактов из множества С элементам Х;

W - задаются вхождением контакта из множества С в цепи Е.

Граф вида G задается обычно в виде трехмерной матрицы А, которую можно представить в виде двух матриц А1, А2.

Ф ормальное описание коммутационных схем Пример 1/1

Матрица инцидентности: Матрица цепей: