Вопрос 29. Эффективности вычислений:

Z={z} – массовая задача

Исходные данные представленные в виде слов Р в конечном алфавите, зависящих от z.

Размерность - длина слов Р, кодирующего исходные данные задачи z.

Пример Вектор значений булевой функции.

Массовая задача решается эффективно (просто), если существует полином Q(x), такой что время решения каждой задачи z Ć Z не превосходит Q(e(z))

Эффективное вычисление – вычисление с полиномнальной сложностью.

Переборная задача 2^e(z)

Метод сводимости:

Массовая задача Z={z} полиномиально сводится к массовой задачи Z`={z`}, если существует словарная функция F, которая по произвольной задаче z Ć Z строит задачу F(z)=z`Ć Z`, что задача z имеет положительные ответ тогда когда z` имеет положительный ответ и время вычисления F(z) ограничено значением Q(e(z)), где Q(x) – некоторый полином, зависящий от массовых задач Z и Z`, но не от некоторых задач z и z`.

Пример. Задача о МДНФ сводится к задаче покрытия единиц множествами, образование К – мерной карты (карты корно).

Определение переборной задачи

Массовая задача Z называется переборной, если она может быть сформулирована в след. виде: по заданному значению z Ć Z выяснить, существует ли y, размерность которого e(y) не превосходит полинома e(z) и такой, что выполнено свойство R(z,y), поверяемое на машине Тьренга за время, ограниченное полиномом от e(z)+e(y). Перебор объектов y до тех пор, пока не выполнится R(z,y)

Число переборов растет по экспоненте.

1. z четно? z/y=2 Если y найден z=2y

2. Кодовый замок y – ключ.

3. f,g –булевы функции f=g

y=(q₁…….q_n) f(q₁…….q_n)=g(q₁…….q_n)

Переборная задача Z называется универсальной или полной, если любая ПЗ полиномиально к ней сводится.

1. Задача выполнимой булевой функции

2. Задача о полном подграфе

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

Множество вершин таких, что каждое ребро графа инцедентно к некоторой вершине из этого множества.

4. Задача о существовании гамельтонова цикла в гафе.

5. Задача о раскраске графа.

6. Задача о изоморфном подграфе (для заданных графов G и G` установить существует ли в G` подграф, изоморфный графу G).

Вопрос 30.Понятие переборной задачи. Универсальные переборные задачи. Примеры.

Массовая задача Z называется переборной, если она может быть сформулированная следующим образом: по заданному zZ выяснить, сущ. ли такой y, размерность которого l(y) не превосходит Q(l(z)) полинома от l(z) и такой, что выполнено свойство R(z,y), проверяемое на подходящей МТ за время, не превосходящее полинома Q(l(z)+l(y)).

Решается перебором объектов y до тех пор, пока не выполнится R(z,y)

Число переборов растет экспоненциально от y.

Переборная задача Z⁰ называется универсальной, если любая переборная задача полиноминально к ней сводится.

Примеры.

1) Задача о выполнимости булевой ф-ии

2) Задача о полном подграфе (по заданному подграфу G выяснить, имеется ли в G полный К-вершинный подграф)

3) Задача о вершинном покрытии (по заданному графу G и числу K, узнать, имеется ли вершинной покрытие G мощности K)

4) Задача о существовании гамильтонова цикла в графе

5) Задача раскраски графа K цветами

6) Задача об изоморфном подграфе (для заданных графов G и G’ установить, существует ли в G’ подграф, изоморфный графу G)