15. Разрешимые и неразрешимые проблемы, невычислимые функции. Примеры.

Число задач (функций) больше числа алгоритмов. Существуют задачи для которых нет алгоритмов их решения – алгоритмически неразрешимые.

1. Задача останова. Дано: МТ, входящие данные Х. Остановится ли МТ на входных данных Х.

2. Задача эквивалентности: МТ1, МТ2. Верно ли что МТ1~МТ2? Для любых МТ1=МТ2

3. Задача о решении диафантовых уравнений x^2+y^2=z^2pdy(x)+pdy(y)=pdy(z). Существует ли решение уравнения в целых числах?

Придумать для разрешимых.

17. Задача о максимальном паросочетании. Волновой алгоритм.

Паросочетание – подмножество попарно несмежных ребер.

Задача нахождения максимального подмножества таких ребер и называется задача о максимальном паросочетании. (Например, задача о трудоустройстве)

Полным паросочетанием называется паросочетание, в котором участвуют все вершины графа.

«алгоритм чередующихся цепей»

Пусть М – паросочетание в графе G, вершинаv– парная, если она инцидентна ребру, принадлежащемуM.

Путь, соединяющий две непарные вершины, в котором чередуются ребра, входящие и не входящие в М, называется чередующейся цепью относительно М.

1)

2) найти чередующуюся цепь Р отн. М

3) если цепь найдена, увеличить паросочетание М вдоль цепи Р и перейти к шагу 2. Иначе конец алгоритма.

Корректность алгоритма доказывается теоремой Бержа:

Паросочетание М является маквсимальным тогда и только тогда, когда в графе нет чередующихся цепей относительно М.

Для нахождения чередующейся цепи используется волновой алгоритм:

V₁,v₂– доли в графе

Пусть имеется паросочетание М; F₀,F₁,... – волны алгоритма (подмножества вершин)

1) в множество F₀включаем все непарные вершины изv₁

2) циклпоk=1,...

Еслиkнечетное,

товF_kвключаются

иначевF_kвключаются

конец если

есливF_kвходит непарная вершина,

то конец алгоритма, чередующаяся цепь найдена,

конец если

еслиF_k=, токонец алгоритма, чередующаяся цепь не найдена

конец цикла

Пример:

1-a- чередующаяся цепь

2-c

3-b

4-e

5-c-2-a-1-d - ОТВЕТ

5-e-4-b-3

18. Задача о минимальном вершинном покрытии. Теорема Кёнига.

Вершинное покрытие.

Пусть дан граф G из множества вершин V и ребер E, вершинным покрытием называется подмножество вершин V' графа, таких что каждое ребро инцидентно хотя бы одной вершине из V'.

Минимальное вершинное покрытие– это вершинное покрытие, количество вершин в котором не превосходит количество вершин в любом другом вершинном покрытии (минимально возможное число вершин)

Задача о вершинном покрытии:

В заданном графе найти минимальное вершинное покрытие. Задача принадлежит классу NP-полный в слабом смысле.

Теорема Кёнига.

В двудольном графе количество вершин в минимальном вершинном покрытии совпадает с количеством ребер в максимальном паросочетании.

19. Задача о нахождении минимального расстояния между всеми парами вершин. Алгоритм Флойда.

Дан ориентированный граф G.

Вес ребра – целое число.

Алгоритм Флойда

Ограничение на граф: в нем не должно быть циклов с отрицательным весом.

Алгоритм заключается в построении квадратных матриц

- матрица расстояний в исходном графе.

Для нахождения самих цепей, а не только их длин, будем строить последовательность матриц

- номер первой вершины в минимальной цепи междуiиjвершинами.

Если на каком-либо шаге в матрице С на главной диагонали появилось отрицательное число, значит в графе присутствует цикл с отрицательным весом.

Пример:

Ответ: цепь (1,4): 1→2→3→4.