Методические рекомендации по выполнению практических занятий по учебной дисциплине «Теория алгоритмов» по теме «NP-полные задачи»
учебно-методический материал по информатике и икт по теме

Министерство образования И науки АРХАНГЕЛЬСКОЙ ОБЛАСТИ

государственное бюджетное  образовательное учреждение
среднего профессионального образования

Архангельской области
«ВЕЛЬСКИЙ ЭКОНОМИЧЕСКИЙ ТЕХНИКУМ»

 (ГБОУ СПО АО «ВЭТ»)

Дмитроченко М.И.

Методические рекомендации

по выполнению практических занятий

по учебной дисциплине

«Теория алгоритмов»

по теме «NP-полные задачи»

Вельск 2013

Рецензенты: Федяевская К.В., преподаватель ГБОУ СПО АО «ВЭТ».

Рохина С.Н., старший методист ГАОУ СПО Архангельской области «Вельский сельскохозяйственный техникум»

Дмитроченко М.И.. Методические рекомендации по выполнению практических занятий по учебной дисциплине «Теория алгоритмов» по теме «NP-полные задачи»: учебное пособие. – Вельск: ГБОУ СПО «ВЭТ», 2013 г.

Данное учебное пособие предназначено для преподавателей, студентов и слушателей курсов, изучающих дисциплину «Теория алгоритмов».

Рассмотрено и одобрено на заседании предметной (цикловой) комиссии вычислительны дисциплин ГБОУ СПО АО «ВЭТ», протокол № _1_ от «_17_» мая 2013 года

© Дмитроченко М.И., 2013.

© государственное бюджетное образовательное учреждение среднего профессионального образования Архангельской области «Вельский экономический техникума»

Усл. пч. л. 1

СОДЕРЖАНИЕ

ОСНОВНАЯ ЧАСТЬ        

1. Примеры NP-полных задач        

1.1.        Задача о выполнимости схемы        

1.1.1. Теоретические сведения.        

1.1.2. Методические указания к выполнению практического занятия № 1        

1.1.3. Пример решения задачи к практическому занятию № 1        

1.2.        Задача о клике        

1.2.1. Теоретические сведения.        

1.2.2. Методические указания к выполнению практического занятия № 2        

1.2.3. Пример решения задачи к практическому занятию № 2        

1. Примеры NP-полных задач

1. Задача о выполнимости схемы

1.1.1. Теоретические сведения.

Рассмотрим схему из функциональных элементов «и», «или», «не» с n битовыми входами и одним выходом, состоящую не более, чем из O(пk) элементов – рис.1.

Рис 1. Абстрактная функциональная схема

Будем понимать под выполняющим набором значений из множества {0,1} на входе схемы, такой набор входов - значения х1, ..., хn, при котором на выходе схемы будет значение «1».

Формулировка задачи - существует ли для данной схемы выполняющий набор значений входа. Очевидно, что задача принадлежит классу NP - проверка предъявленного выполняющего набора не сложнее количества функциональных элементов, и следовательно не больше чем O(пk).

Это была одна из первых задач, для которой была доказана ее NP полнота, т.е. любая задача из класса NP полиномиально сводима к задаче о выполнимости схемы.

Решение этой задачи может быть получено перебором всех 2n возможных значений входа с последующей проверкой на соответствие условию выполняющего набора. В худшем случае придется проверить все возможные значения входа, что приводит к оценке F′(п) = O(пk * 2n). Для этой, как и для всех других NP-полных задач не известен полиномиальный алгоритм решения.

1.1.2. Методические указания к выполнению практического занятия № 1

По дисциплине: “Теория алгоритмов”

Тема работы: “Задача о выполнимости схемы”

Цель работы: нахождение и анализ всех основных компонентов схемы.

Форма выполнения: индивидуальная.

Форма контроля: зачет.

Задание:

1. Получение условия задачи.
2. Построение таблицы истинности.
3. Построение математических формул.
4. Проверка всех строк таблицы.
5. Построение функциональной схемы на элементах И, ИЛИ, НЕ.
6. Подсчет n и k.
7. Подсчет оценки Fф(n).
8. Построение комбинационной схемы (СДНФ).
9. Подсчет n, k, Fф, Fk.
10. Сравнение Fф и Fk и анализ результатов.
11. Вывод.
12. Оформление отчёта.

1.1.3. Пример решения задачи к практическому занятию № 1

1)

2)        1            2                3                 4                5

3)    3 = не 2

       4 = 1 и 3

       5 = 1 или 4

4) (0,0) =

    (0,1) =

    (1,0) =

    (1,1) =

5)

х1                                                        х1

х2                                                        х2

6) n = 2,        k = 3.

7) Fф(n) =  O (nk  2n) = 23  22 = 8  4 = 32.

     Fф(n) = F (1) + F (2) = 13  21 + 23  22 = 1  2 + 8  4 = 34.

8) СДНФ =

9) n = 2,       k = 4.

    Fk = 0 (nk  2n) = 24  22 = 64

    Fk = F (1) + F (2) = 14  21 + 24  22 = 66.

10) Fф < Fk

11) Вывод по цели.

12) Проверка оформления отчета.

2. Задача о клике

1.2.1. Теоретические сведения.

Пусть дан граф G = G(V,E), где V— множество из n вершин, а Е – множество ребер. Будем понимать под кликой максимальный по количеству вершин полный подграф в графе в G.

Задача состоит в определении клики в заданном графе G.

Поскольку в полном графе на т вершинах имеется т(т-1)/2 ребер, то проверка, является ли данный граф полным, имеет сложность О(т2). Очевидно, что если мы рассматриваем подграф с т вершинами в графе G с вершинами (т < п), то всего существует Спт различных подграфов. Если в задаче о клике количество вершин клики фиксировано, то перебирающий алгоритм имеет полиномиальную сложность:

F(m, п) = O(т2  * Спт) = O(т2  * пт).

Однако в общем случае придется проверять все подграфы с количеством вершин т = (2, п) на их полноту и определить максимальное значения т для которого в данном графе G существует полный подграф, что приводит к оценке в худшем случае:

F′(n) = O(k2 * Cnk) =>O(п2* 2п)

Введем определение подграфов.

а) остовный подграф Gp – граф G(V,Ep), для которого Ep  E.

б) порожденный подграф Gs – граф Gs, содержащий некоторые вершины Vs  V и дуги (ребра), которые их связывают.

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

г) полный граф – граф, в котором m вершин и m (m–1)/2 ребер. Полный подграф формируется на основании полного графа.

Граф, вершины которого представляют сотрудников некоторого учреждения, а дуги – линии связи между сотрудниками. Тогда граф, представляющий только наиболее важные каналы связи данного учреждения, является остовным подграфом; граф, который подробно представляет линии связи только какой-то части этого учреждения (например, отделения), является порожденным подграфом, а граф, который представляет только важные линии связи в пределах отделения, является подграфом.

1.2.2. Методические указания к выполнению практического занятия № 2

По дисциплине: “Теория алгоритмов”

Тема работы: “Задача о клике”

Цель работы: определение клика в заданном графе G.

Форма выполнения: индивидуальная.

Форма контроля: зачет.

Задание:

1. Получение вариантов задания.
2. 1 вариант – 7 вершин;        2 вариант – 8 вершин;        3 вариант – 9 вершин.
3. Зарисовать полный граф с заданными вершинами, рассчитать количество ребер.
4. Построить для исходного графа по 5 видов:

– остовного;

– порожденного;

– подграфа.

5. Рассчитать для полного графа с m вершинами и соответствующим количеством ребер сложность O (m2).
6. Найти полиноминальную сложность  для фиксированного количества вершин клики по варианту.
7. Рассчитать оценку F (n).
8. Вывод.
9. Оформление отчёта.
10. Сдача отчёта преподавателю.

1.2.3. Пример решения задачи к практическому занятию № 2

Рассмотрим примеры построения полных графов.

1) m = 4, следовательно: 4 (4–1)/2 = 6 ребер.

х1                х2

х4                х3

2) m = 5, следовательно: 5 (5–1)/2 = 10 ребер.

     х3

х2                        х4

х1                        х5

2) m = 6, следовательно: 6 (6–1)/2 = 15 ребер.

     х3

х2                        х4

х1                        х5

    х6

Построим все подграфы для примеров.

1)                                – остовный                                – порожденный

                                – подграф

2)                                – остовный                                – порожденный

– подграф

3)            

                        – остовный                                – порожденный

                                – подграф

Подсчитаем сложность О(т2) для рассматриваемых графов на полноту

1) О(4) = 16

    О(5) = 25

    О(6) = 36

2) Если мы рассматриваем подграф с т вершинами в графе G (т <n), то существует Спт различных подграфов, например:

m = 2; n = 4; Спт = O( пт) = 42.

m = 6; n = 8; Спт = O( пт) = 86.

Если в задаче о клике количество вершин клики фиксировано, то перебирающий алгоритм имеет полиномиальную сложность:

F(m, п) = O(т2  * Спт) = O(т2  * пт).

Например: m = 2                O(22  * 42) = 4  * 16 = 64.

         m = 3                O(32  * 43) = 9  * 64 = 576.

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

Например:

F′(n) =O(п2* 2п) = 62 * 26 = 36 * 64 = 2304 вершин.