Графы и автоматы

Индивидуальная работа по теме:
«Графы и конечные автоматы»

Вариант 1.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

1
2
3
4
5
6
2
3
4
4
5
6
2
3
4
4
6
5
1
1
1
0
1
1
0
0
0
1
1
1


5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.
Вариант 2.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415
4. Найти минимальную форму автомата и граф переходов минимальной формы:

13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

1
2
3
4
5
6
7
8
9
9
2
7
2
2
3
6
9
4
1
2
5
2
2
9
8
9
6
1
1
0
1
1
1
1
1
0
1
0
1
0
0
0
0
0
0

5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.
Вариант 3.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

1
2
3
4
5
6
7
8
9
2
1
2
3
6
8
6
4
7
2
4
2
2
4
9
2
4
9
5
4
5
2
3
6
8
7
7
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
0
0
1

5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.
Вариант 4.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


0
1
0
1

S0
S1
S2
S3
S4
S1
S4
S3
S4
S4
S2
S2
S0
S0
S4
1
0
1
0
0
0
0
0
0
0


5. Дана последовательность из нулей и единиц. Написать программу машины, которая меняет местами нули и единицы (т.е. вместо нуля должна стоять единица, вместо единицы – нуль).

Вариант 5.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

1
2
3
4
5
6
7
8
9
4
4
6
1
2
8
6
5
7
4
4
5
5
4
9
4
5
9
3
3
2
5
4
6
8
7
7
1
1
1
0
0
0
1
1
0
0
0
0
1
1
1
0
0
1
0
0
0
1
1
1
0
0
1


5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.
·
Вариант 6.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

(1
(2
(3
(4
(5
(6
(5
(6
(4
(3
(3
(4
(4
(3
(1
(2
(6
(5
1
1
1
1
0
0
0
0
1
1
1
1


5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.


Вариант 7.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.

13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

1
2
3
4
5
6
7
8
9
9
2
7
2
2
3
6
9
4
1
2
5
2
2
9
8
9
6
1
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
1
0

5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.
Вариант 8.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:



13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

1
2
3
4
5
6
2
3
4
4
5
6
2
3
4
4
6
5
1
0
1
0
1
1
0
0
0
1
1
1


5. На ленте машины Тьюринга написана конечная последовательность из нуля и следующих за ним единиц. Написать программу машины, которая переставляет нуль на последнее место.


Вариант 9.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

13 EMBED Equation.3 1415

4. Найти минимальную форму автомата и граф переходов минимальной формы:



13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

(1
(2
(3
(4
(5

(5
(2
(4
(3
(3

(4
(3
(1
(2
(5

1
1
1
1
0

0
0
1
1
1



5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.

Вариант 10.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину 13 EMBED Equation.3 1415 с вершиной 13 EMBED Equation.3 1415.
13 EMBED Word.Picture.8 1415
2. Дан граф транспортной сети, 13 EMBED Equation.3 1415 – вход, 13 EMBED Equation.3 1415 – выход, 13 EMBED Equation.3 1415 – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
13 EMBED Word.Picture.8 1415
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
13 EMBED Equation.3 1415
4. Найти минимальную форму автомата и граф переходов минимальной формы:
М
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415


13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

1
2
3
4
5
6
7
8
2
6
2
8
2
2
6
8
5
2
2
3
5
6
6
7
5
5
7
1
5
5
3
5
1
0
0
1
1
0
0
1
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1


















5. Составить программу для машины Тьюринта, вычисляющую значения функции 13 EMBED Equation.3 1415.


S



S



S



S



Root EntryEquation NativeEquation Native15Times New RomanАндрей КочевскийАндрей Кочевский

Приложенные файлы

  • doc 1777528
    Размер файла: 661 kB Загрузок: 0

Добавить комментарий