МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Вятский государственный университет» (фгбоу впо «ВятГу»)
Факультет автоматики и вычислительной техники
Кафедра электронных вычислительных машин
ОБЪЕДИНЕНИЕ СХЕМ АЛГОРИТМОВ
Отчет
Лабораторная работа №4 по дисциплине
«Математическая логика и теория алгоритмов»
Выполнил студент группы ИВТ-12 ____________/Куропаткин Р.А./
Проверил преподаватель ______________________/Чистяков Г. А./
Киров 2012
1 Постановка задачи
По заданным программам построить графические схемы алгоритмов(ГСА), по ГСА перейти к матричным схемам алгоритмов(МСА). Построить общую МСА. С помощью систем переходов минимизировать алгоритм, построить логическую схему алгоритма (ЛСА). Построить общую ГСА.
Заданные программа
Заданные программы представлены на рисунках 1-3.
from A0 to A10
from A10 to P7
from P7 to P5 (if true) or to A2 (if false)
from P5 to P3 (if true) or to P2 (if false)
from P2 to A2 (if true) or to A4 (if false)
from A2 to A6
from A6 to A4
from A4 to P4
from P4 to A8 (if true) or to A1 (if false)
from A1 to A8
from A8 to A3
from A3 to P3
from P3 to A9 (if true) or to A7 (if false)
from A9 to P6
from P6 to P1 (if true) or to P1 (if false)
from P1 to A5 (if true) or to P3 (if false)
from A5 to A7
from A7 to Ak
Рисунок 1
from A0 to A8 from A8 to P5 from P5 to A10 (if true) or to P6 (if false) from P6 to A9 (if true) or to P5 (if false) from A9 to P3 from P3 to P1 (if true) or to A1 (if false) from P1 to P2 (if true) or to A10 (if false) from P2 to A4 (if true) or to A3 (if false) from A4 to A6 from A6 to A10 from A10 to A3 from A3 to A2 from A2 to A7 from A7 to P7 from P7 to A1 (if true) or to P4 (if false) from A1 to P4 from P4 to A6 (if true) or to A5 (if false) from A5 to Ak
|
Рисунок 2
from A0 to A9
from A9 to P4
from P4 to A8 (if true) or to P5 (if false)
from P5 to A10 (if true) or to A4 (if false)
from A4 to A10
from A10 to P7
from P7 to P1 (if true) or to P4 (if false)
from P1 to A6 (if true) or to A1 (if false)
from A6 to A2
from A2 to A3
from A3 to P2
from P2 to P6 (if true) or to P3 (if false)
from P6 to A10 (if true) or to A8 (if false)
from A8 to A5
from A5 to P3
from P3 to A4 (if true) or to A7 (if false)
from A7 to A1
from A1 to Ak
Рисунок 3
Разработка графической схемы алгоритма
Графическая схема алгоритма для программ 1.1 представлены соответственно на рисунках 4-6.
Рисунок 4
Рисунок 5
Рисунок 6
Разработка матричных схем алгоритма
Матричная схема алгоритма на основании графической схемы алгоритма (рисунок 4) представлена в таблице 1.
Таблица 1
|
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
AK |
A0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
A1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
A2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
A3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-P3 |
0 |
P3 |
0 |
0 |
A4 |
0 |
-P4 |
0 |
0 |
0 |
0 |
0 |
0 |
P4 |
0 |
0 |
0 |
A5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
A6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
A7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
A8 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
A9 |
0 |
0 |
0 |
0 |
0 |
P6 \/ -P6 P1 P1 |
0 |
P6 \/ -P6 -P1 -P1 -P3 -P3 |
0 |
P6 \/ -P6 -P1 -P1 P3 P3 |
0 |
0 |
A10 |
0 |
0 |
-P7\/P7 -P5 P2 |
0 |
P7 -P5 -P2 |
0 |
0 |
P7 P5 -P3 |
0 |
P7 P5 P3 |
0 |
0 |
AK |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Матричная схема алгоритма на основании графической схемы алгоритма (рисунок 5) представлена в таблице 2.
Таблица 2
|
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
AK |
A0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
A1 |
0 |
0 |
0 |
0 |
0 |
-P4 |
P4 |
0 |
0 |
0 |
0 |
0 |
A2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
A3 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
A4 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
A5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
A6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
A7 |
0 |
P7 |
0 |
0 |
0 |
-P7 -P4 |
-P7 P4 |
0 |
0 |
0 |
0 |
0 |
A8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-P5 \/ -P5 P6 -P6 -P5 P6 |
P5 \/ -P5 -P6 P5
|
0 |
A9 |
0 |
-P3
|
0 |
P3 P1 -P2 |
P3 P1 P2 |
0 |
0 |
0 |
0 |
0 |
P3 -P1 |
0 |
A10 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
AK |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Матричная схема алгоритма на основании графической схемы алгоритма (рисунок 6) представлена в таблице 3.
Таблица 3
|
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
AK |
A0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
A1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
A2 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
A3 |
0 |
0 |
0 |
0 |
- P2 P3 |
0 |
0 |
- P2 - P3 |
P2 - P6 |
0 |
0 |
P2 P6 |
A4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
A5 |
0 |
0 |
0 |
0 |
P3 |
0 |
0 |
- P3 |
0 |
0 |
0 |
0 |
A6 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
A7 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
A8 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
A9 |
0 |
0 |
0 |
0 |
- P4 - P5 |
0 |
0 |
0 |
P4 |
0 |
- P4 P5 |
0 |
A10 |
0 |
P7 - P1 |
0 |
0 |
- P7 - P4 - P5 |
0 |
P7 P1 |
0 |
- P7 P4 |
0 |
- P7 - P4 P5
|
0 |
AK |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |