МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Вятский государственный университет» (фгбоу впо «ВятГу»)

Факультет автоматики и вычислительной техники

Кафедра электронных вычислительных машин

ОБЪЕДИНЕНИЕ СХЕМ АЛГОРИТМОВ

Отчет

Лабораторная работа №4 по дисциплине

«Математическая логика и теория алгоритмов»

Выполнил студент группы ИВТ-12 ____________/Куропаткин Р.А./

Проверил преподаватель ______________________/Чистяков Г. А./

Киров 2012

1 Постановка задачи

По заданным программам построить графические схемы алгоритмов(ГСА), по ГСА перейти к матричным схемам алгоритмов(МСА). Построить общую МСА. С помощью систем переходов минимизировать алгоритм, построить логическую схему алгоритма (ЛСА). Построить общую ГСА.

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

2. Разработка графической схемы алгоритма

Графическая схема алгоритма для программ 1.1 представлены соответственно на рисунках 4-6.

Рисунок 4

Рисунок 5

Рисунок 6

3. Разработка матричных схем алгоритма

Матричная схема алгоритма на основании графической схемы алгоритма (рисунок 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