Контрольные вопросы и задания

1. В чем состоит отличие общей задачи (массовой) от частной (индивидуальной) задачи?

2. В чем отличие класса NP-полных задач от класса NP-трудных задач? Может ли какая-либо задача принадлежать первому из этих классов и не принадлежать второму?

3. Является ли задача распознавания целого неотрицательного числа на простоту задачей полиномиальной сложности?

4. К какому классу сложности относится общая задача о рюкзаке? К какому классу относится задача о «супервозрастающем рюкзаке»?

5. Какова сложность задачи, если она может быть разделена на конечное число задач полиномиальной сложности, решаемых последовательно?

6. Какова сложность задачи, если она может быть разделена на последовательно решаемые задачи полиномиальной сложности, и количество этих задач выражается полиномом от сложности исходных данных?

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

8. Граф задан матрицей смежностей. К какому классу относится сложность задачи распознавания того, является ли этот граф двудольным?

9. Граф задан матрицей смежностей. К какому классу относится сложность задачи распознавания того, является ли этот граф самодополнительным?

10. К какому классу сложности относится задача распознавания принадлежности слов длины n автоматному языку с конечным алфавитом?

11. В чем состоит особенность параметрической сложности по отношению к традиционному определению сложности? Как это влияет на отнесение задачи к тому или иному классу сложности?

12. Как можно применить подходы к параметризованной оценке сложности для алгоритмов на графах? Какие характеристики (инварианты) исходного графа можно выбрать в качестве параметров функции сложности?

Задачи для самостоятельного решения

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

2. К какому классу относится задача линейного программирования (вспомните дисциплину «Методы оптимизации», постановку оптимизационной задачи и способы ее решения) – полиномиальной сложности или экспоненциальной сложности?

3. Дана строка длины n, составленная из символов конечного алфавита A = {a₁ , a₂ , …, a_k}. Задача состоит в том, чтобы определить, является ли эта последовательность циклической. Найдите верхнюю и нижнюю оценки сложности решения этой задачи. Как сложность зависит от количества k символов в алфавите?

4. Дана строка длины n, составленная из символов конечного алфавита, и m правил автоматной грамматики. Задача состоит в том, чтобы определить, относится ли эта строка к языку, порождаемому данной грамматикой. Найдите верхнюю и нижнюю оценки сложности этой задачи.

5. Оцените сложность задачи построения дополнения обыкновенного неориентированного графа G, содержащего p вершин, если исходный граф задан матрицей смежностей. Дополнением графа называется неориентированный граф, содержащий те же вершины, что и граф G, но содержащий только те ребра полного графа, которые отсутствуют в графе G.

6. Компонентой графа называется максимальный связный подграф. Если граф связен, то он является единственной компонентой. Несвязный граф состоит из нескольких компонент. Оцените сложность задачи вычисления количества компонент в произвольном графе с p вершинами.

7. Проведите анализ сложности задачи определения того, является ли граф с p вершинами планарным. Используйте теорему Понтрягина – Куратовского и те факты, что полный граф с пятью вершинами не планарен, и полный двудольный граф с тремя вершинами в каждой доле также не планарен.