Индивидуальная работа по теме:

Индивидуальная работа по теме:

«Графы и конечные автоматы»

Вариант 1.

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

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

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

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

S

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

Вариант 2.

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

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

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

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

S

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

Вариант 3.

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

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

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

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

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

Вариант 4.

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

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

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

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

S0 S1 S2 S3 S4	S1 S4 S3 S4 S4	S2 S2 S0 S0 S4

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

Вариант 5.

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

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

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

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

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

Вариант 6.

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

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

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

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

s1 s2 s3 s4 s5 s6	s5 s6 s4 s3 s3 s4	s4 s3 s1 s2 s6 s5

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

Вариант 7.

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

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

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

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

S

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

Вариант 8.

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

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

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

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

S

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

Вариант 9.

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

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

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

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

s1 s2 s3 s4 s5	s5 s2 s4 s3 s3	s4 s3 s1 s2 s5

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

Вариант 10.

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

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

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

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

М

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

Дата добавления: 2015-10-21