Приведите несколько примеров np-полных задач.
Задача 3- выполнимость,
Задача о вершинном покрытии.
Задача о гамильтоновом цикле. Дан граф G = (V, E). Существует ли цикл, ровно один раз проходящий через каждую вершину?
Задача о самом длинном пути. Дан граф G = (V, E), заданы номера двух вершин A и B, а также число K. Существует ли путь из A в B с длиной не менее K?
Задача о разбиении. Даны n предметов с весами pi. Можно ли разбить множество предметов на два непересекающихся подмножества с одинаковым весом?
Почему задача о рюкзаке, являясь np-полной, имеет эффективные алгоритмы решения?
из-за длины описания задачи B=O(2^|z|)
Дело в том, что существенное замедление работы алгоритма будет ощущаться только при очень больших значениях B. Заметим, что увеличение длины описания задачи на каких-то 20 битов позволяет задать в 1000000 раз большее значение B! Псевдополиномиальный алгоритм.
Что такое псевдополиномиальный алгоритм?
экспон. характер при больших знач параметров Tmax(z)=O(P (|z|, M(z) ) ), где Р-полином
/.известен алгоритм, проявляющий экспоненциальный характер только при очень больших значениях параметров, встречается не так уж редко. Подобные алгоритмы, как и решаемые ими задачи, носят название псевдополиномиальных. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости Tмакс(z) = O(P(|z|, M(z))), где P – некоторый полином от двух переменных.
Что такое ориентированный и неориентированный граф?
Если порядок вершин графа важен, то граф ориентированный. Если не важен – то граф неориентированный
Что такое сильно связный граф? К каким графам применимо это понятие – ориентированным или неориентированным?
Связные графы (есть путь из любой вершины в любую); сильно связные орграфы (есть ориентированный путь из любой в любую).
Что такое дерево? Сколько ребер имеет дерево?
Дерево (связный граф без циклов).
Это означает, что между любой парой вершин этого графа существует как минимум один путь.
M = N – 1, где м – кол-во вершин
Что такое ациклический ориентированный граф и чем он отличается от дерева?
Граф, в котором нет ориентированных циклов. Связный ациклический граф называется деревом.
Граф, в отличие от дерева, может состоять из нескольких компонент связности (м.б. менее, чем n-1 ребро)
Сколько ребер имеет полный граф?
Для полного графа (без петель):
ориентированного: M = N * (N – 1);
неориентированного: M = N * (N – 1) / 2;
Что такое матрица смежности графа? Сколько в ней строк и сколько столбцов?
Матрицей смежности для n узлов называется квадратная матрица порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен с узлом i (есть путь < i,j >), и 0 -в противном случае
Чем отличается матрица смежности ориентированного графа от неориентированного?
Для неориентированного графа матрица всегда симметрична, для ориентированного – не обязательно симметричная матрица.
Что такое матрица инцидентности графа? Сколько в ней строк и сколько столбцов?
Матрица инцидентности: используется для орграфов. Если дуга направлена из х в у, то х=1, у=-1, напротив остальных вершин ставим ноль.
размерность nxm, где n – число вершин, m – число ребер (-1 – куда, 1- откуда)
В каких случаях удобнее использовать списки смежности вместо матрицы смежности?
Удобно использовать при малом количестве ребер, если нужно часто просматривать ребра, инцидентные вершине, если граф меняется.
В случаях, когда в ходе решения задачи менялся граф (добавлялись или удалялись рёбра).
Чем отличается поиск по графу в глубину от обхода дерева?
При обходе дерева вершина просматривается ровно 1 раз, при обходе графа в глубину алгоритм может зациклиться. Проверка на зацикливание.
В каком случае при поиске в глубину будет выполнен обход всех вершин графа?
Если нет удовлетворяющего нас решения
Как можно проверить связность графа?
Проверить между любой ли парой существует как минимум один путь.
В чем заключается алгоритм проверки ацикличности ориентированного графа?
Он заключается в проходе в глубину графа и поиска на наличие обратного ребра.
Что такое топологическая сортировка? К каким графам она применима?
Размещение вершин ациклического орграфа так, чтобы все дуги легли в одном направлении, ориентация вершин в одну сторону (планирование работ, связанных с к-л этапами)
Размещение вершин графа так, чтобы все дуги шли в одном направлении(от предыдущего к последующему).
В чем заключается алгоритм топологической сортировки?
Выбирается какой-либо элемент, которому не предшествует никакой другой. Этот элемент помещается в начало списка и исключается из рассмотрения множества. Оставшееся множество частично упорядоченное, применяем тот же алгоритм до тех пор пока оно не станет пустым.
Для чего может быть полезна топологическая сортировка?
Эту задачу можно решить за линейное время одним проходом.
При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера.
Что такое критический путь в графе? В чем важность этого понятия?
Критический путь графа — путь максимальной длины в ориентированном ациклическом графе.
Его длина является минимальной из всех возможных высот у ярусно-параллельной формы данного ациклического графа.
При распараллеливании алгоритма очень важно это понятие.
Что такое поиск по графу в ширину и чем он отличается от поиска в глубину?
В глубину: Просмотр начинается с некоторой вершины v. Выбирается вершина u, смежная с v, и процесс повторяется с ней.Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не просмотренных ранее, то возвращаемся в предыдущий шаг. Если попадаем в первый шаг, то просмотр завершен. (реализация – рекурсивная процедура).
В ширину: Hеобходимо рассмотреть все вершины, смежные с текущей. Выбор следующей "текущей" - выбирается та, что была раньше "рассмотрена". (реализация – явная очередь)
придя в нек. верш. переб все смежн. с ним, затем потомков
Что такое остовное дерево? В чем практический смысл этого понятия?
Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом.
Какую задачу решает алгоритм Прима и в чем идея этого алгоритма?
Алгоритм Прима находит остовный лес минимального веса в данном связном графе.
Основная идея: начав с произвольной вершины, на каждом шаге добавлять в дерево ту вершину, которая смежна с любой из вершин, ранее включенных в дерево, по самому короткому ребру.
Прима. сотр. ребра, берем с наим. длиной, следим чтоб не было циклов
Какую задачу решает алгоритм Крускала и в чем идея этого алгоритма?
Основная идея: заранее отсортировав ребра по длине, выбирать самые короткие их них, следя только, чтобы не построить цикл. Когда число ребер будет N-1, они волей-неволей образуют остовное дерево.
Этот алгоритм предназначен для пстроения остовного дерева.
Оценка T(n,m)=O(mlogm).
В каких случаях алгоритм Крускала предпочтительнее, чем алгоритм Прима?
Сложность Прима О(n2), то есть не зависит от количества ребер, а Крускала О(m*logm), используем Прима, где много ребер, а Крускала, где мало рёбер.
Какую задачу решает алгоритм Флойда и в чем идея этого алгоритма?
Решает задачу поиска кратчайших путей в графе. Алгоритм Флойда строит матрицу длин кратчайших путей.
Вначале происходит инициализация матрицы кратчайших расстояний, она совпадает с матрицей смежности. После этого мы пытаемся улучшить кратчайшие расстояния между парой вершин, добавляя в качестве промежуточной величины вершину с номером k.
Идет сортировка по множеству вершин, через которые будем искать путь.