Редактирование: Список заданий по АиСД-year2015-сем2

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 63: Строка 63:
 
# Задан несильносвязный турнир. Турнир {{---}} ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $O(V^2)$.
 
# Задан несильносвязный турнир. Турнир {{---}} ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $O(V^2)$.
 
# Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.
 
# Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.
# Есть взвешенный граф, где веса ребер, исходящих из одной вершины, одинаковы. Докажите, как модифицировать алгоритм Дейкстры, чтобы для каждой вершины происходила ровно одна релаксация.
+
# Есть взвешенный граф, где веса ребер, исходящих из одной вершины, одинаковы. Докажите, что алгоритм Дейкстры, реализованный с помощью двоичной кучи, будет работать за $O(V\log{V} + E)$
 
# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за $O(VE)$.
 
# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за $O(VE)$.
 
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.
 
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.
Строка 74: Строка 74:
 
# Предложите алгоритм поиска всех ребер, которые лежат во всех MST за $O(E \log{V})$.
 
# Предложите алгоритм поиска всех ребер, которые лежат во всех MST за $O(E \log{V})$.
 
# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе с отрицательными ребрами, но без отрицательных циклов, за $O(VE)$.
 
# Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе с отрицательными ребрами, но без отрицательных циклов, за $O(VE)$.
# Вы запустили алгоритм Форда-Беллмана. Насколько большими и насколько маленькими бывают значения чисел в массиве расстояний, если у вас $V$ вершин, $E$ ребер и вес каждого ребра по модулю не превосходит $C$.
 
# Вы запустили алгоритм Флойда. Насколько большими и насколько маленькими бывают значения чисел в массиве расстояний, если у вас $V$ вершин, $E$ ребер и вес каждого ребра по модулю не превосходит $C$.
 
# Модифицированная задача о рюкзаке. У вас есть $n$ номиналов монеток. Каждая монета с целой ценностью не более $c$. Каждого из $n$ номиналов у вас имеется неограниченное число монеток. Ответьте на много запросов: можете ли вы набрать сумму $W$, каждый запрос за $O(1)$, с предпосчетом за $O(nc\log{c})$
 
# Задан неориентированный граф, все веса положительные целые числа не превосходящие $c$. Вам нужно узнать, существует ли путь из вершины $s$ в вершину $t$, с весом равным $W$ за $O(Ec \log{c})$.
 
 
</wikitex>
 
</wikitex>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: