Индивидуалка. Графы и автоматы
.docИндивидуальная работа по теме:
«Графы и конечные автоматы»
Вариант 1.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||
S |
||||
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. Составить программу для машины Тьюринта, вычисляющую значения функции .
Вариант 2.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||
S |
||||
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. Составить программу для машины Тьюринта, вычисляющую значения функции .
Вариант 3.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||||
|
||||||
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. Составить программу для машины Тьюринта, вычисляющую значения функции .
Вариант 4.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||
|
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. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||||
|
||||||
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. Составить программу для машины Тьюринта, вычисляющую значения функции .
Вариант 6.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||
1 2 3 4 5 6 |
s5 s6 s4 s3 s3 s4 |
s4 s3 s1 s2 s6 s5 |
1 1 1 1 0 0 |
0 0 1 1 1 1 |
5. Составить программу для машины Тьюринта, вычисляющую значения функции .
Вариант 7.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||
S |
||||
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. Составить программу для машины Тьюринта, вычисляющую значения функции .
Вариант 8.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||
S |
||||
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. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .
2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.
3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).
4. Найти минимальную форму автомата и граф переходов минимальной формы:
|
||||
1 2 3 4 5
|
s5 s2 s4 s3 s3
|
s4 s3 s1 s2 s5
|
1 1 1 1 0
|
0 0 1 1 1
|
5. Составить программу для машины Тьюринта, вычисляющую значения функции .
Вариант 10.
1. Дан граф с указанными длинами ребер. Найти в графе путь кратчайшей длины, соединяющий вершину с вершиной .