Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

Подождите немного. Документ загружается.

311

Тема: vertex-covering

Задача № 2.1.5 на странице 83

Найдите приближенный алгоритм с точностью

для на-

хождения максимального подмножества дуг, не образующих

цикл, в ориентированном подграфе.

Задача № 2.1.6 на странице 83

Найдите приближенный алгоритм с точностью

для на-

хождения максимального (по включению) паросочетания мак-

симального объема.

Задача № 2.1.7 на странице 83

Найдите приближенный алгоритм с точностью

для на-

хождения максимального (по включению) паросочетания ми-

нимального объема.

Задача № 2.1.8 на странице 83

Студент предложил для задачи 2.1.2 «Vertex Covering» при-

ближенный алгоритм с точностью

: найти в графе дерево (ме-

тодом поиска в ширину), выкинуть из него листья, а оставше-

еся объявить вершинным покрытием. Прав ли он? Докажите

или опровергните.

Задача № 2.1.9 на странице 83

Студент предложил для задачи 2.1.2 «Vertex Covering» при-

ближенный алгоритм с точностью

: найти в графе дерево (ме-

тодом поиска в глубину), выкинуть из него листья, а оставше-

312 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

еся объявить вершинным покрытием. Прав ли он? Докажите

или опровергните.

Тема: greedy-knapsack

Задача № 2.1.10 на странице 85

Докажите, что для любого числа k можно представить

входной набор данных, для которых алгоритм 18 выберет на-

бор, который в k раз хуже оптимального.

Тема: dynamic-programming-knapsack

Задача № 2.2.1 на странице 97

Рассмотрим некоторую модификацию задачи 23 «Сумма

размеров», разрешим даже отрицательные размеры. Формально:

• Даны целые числа a

, ∀i ∈ [1 . . . n] − n

≤ a

≤ n

и число B.

• Найти ответ на «Существует ли решение в 0–1 перемен-

ных (x

, . . . , x

) уравнения

i=1

= B?».

Существует ли полиномиальный алгоритм для этой задачи?

Задача № 2.2.2 на странице 99

313

Постройте алгоритм динамического программирования для

задачи 13 «Knapsack», основанный на отборе наиболее «лег-

ких» частичных решений. Какова будет его временная слож-

ность?

Задача № 2.2.3 на странице 101

Придумайте входные наборы для алгоритма 24 «Рюкзак-

ДинПрог», на которых он будет работать экспоненциальное

время.

Задача № 2.2.4 на странице 101

Придумайте входные наборы для алгоритма из упражне-

ния 2.2.2, на которых он будет работать экспоненциальное вре-

мя.

Задача № 2.2.5 на странице 103

Придумайте входные наборы для алгоритма 25 «Рюкзак

Немхаузера–Ульмана», на которых он будет работать экспо-

ненциальное время.

Задача № 2.2.6 на странице 103

Некоторая торговая сеть решила ускорить обслуживание

на кассах, по возможности исключив возню кассиров с копей-

ками. К сожалению, просто «прощать» покупателям «копееч-

ную» часть суммы покупки нельзя — для контролирующих ор-

ганов необходимо, чтобы зарегистрированные на кассе суммы

полностью совпадали с полученными деньгами.

К кассе покупатель подходит с корзиной товаров, каждая

строка корзины — тип товара, его цена и количество. На каж-

дый товар, можно давать скидку, но такую, чтобы его цена не

стала ниже его цены в рублях (т. е. если товар стоит 12 рублей

314 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

и 34 копейки, нельзя сбросить цену ниже 12 рублей).

Задача — найти алгоритм, который уменьшит цены всех

товаров (при вышеуказанном ограничении), чтобы сумма всей

корзины стала целым числом рублей с одной стороны, а с дру-

гой, чтобы потери для торговой сети были минимальными.

Очевидно, что существует тривиальное допустимое реше-

ние — округлить цены всех товаров, но требуется найти именно

решение с минимальными потерями.

Алгоритм должен работать быстро, за линейное от количе-

ства товаров время — это должен быть мгновенный расчет на

кассе.

Задача № 2.2.7 на странице 104

DVS

технология позволяет снижать напряжение на про-

цессоре, и добиваться экономии электроэнергии за счет увели-

чения времени выполнения задачи.

Пусть процессор поддерживает два уровня напряжения —

< U

. Есть набор из n задач, каждая из которых имеет

энергоемкость и время выполнения для обоих режимов — т. е.

∀i, энергоемкости c

и c

и длительности t

и t

Нужно выполнить все задачи на одном процессоре за время

не более T , при этом добиться минимального энергопотребле-

ния.

Тема: complexity-average-defs

Задача № 3.1.1 на странице 114

Приведите пример функции T

(времени работы неко-

Dynamic Voltage Scaling

315

торого алгоритма A) и распределения исходных данных

(I), для которых T

является полиномиальной в среднем

= O(n

)), а T

— нет.

Тема: average-packing

Задача № 3.2.1 на странице 117

Укажите, как надо организовать вычисление, чтобы про-

верка на допустимость нового решения имела сложность O(m).

Задача № 3.2.2 на странице 117

Какие входные данные для алгоритма 28 «Упаковка-

ДинПрог» заставят его работать экспоненциально долго? А

какие — за O(n

Задача № 3.2.3 на странице 120

Чему будет равны x

, p

и P

при k = 0?

Задача № 3.2.4 на странице 120

Докажите, что E |X

| =

k=0





Тема: average-sat

316 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

Задача № 3.3.1 на странице 127

Какие входные данные для алгоритма 29 заставят его ра-

ботать экспоненциально долго?

Задача № 3.3.2 на странице 127

На каких входных данных этот алгоритм будет рабо-

тать O(m)?

Задача № 3.3.3 на странице 130

Докажите, что

E max

| ≤

k=1





P (k).

Тема: randomized-veriﬁcation

Задача № 4.1.1 на странице 148

Покажите, что для любых двух событий E

, E

P{E

} ≤ P{E

| E

} + P{E

Задача № 4.1.2 на странице 148

Имеется n × n матрица A, элементами которой являются

линейные функции f

(x) = a

x + b

Придумайте алгоритм Монте-Карло с односторонней ошиб-

кой для проверки этой матрицы на вырожденность (det A ≡ 0).

317

Тема: dnf-counting

Задача № 4.2.1 на странице 151

Почему y

независимые случайные величины?

Тема: randomized-rounding

Задача № 4.4.1 на странице 173

Докажите эквивалентность ЦЛП (4.1) и задачи 20 «MAX-

SAT».

Тема: max-cut-semideﬁnite

Задача № 4.4.2 на странице 180

Докажите, что для простого, невзвешенного графа в зада-

че 23 «MAX-CUT» можно применить простую стратегию, даю-

щую вероятностный 0.5-приближенный алгоритм: для каждой

вершины с вероятностью 1/2 отнести ее к множеству S и с

вероятностью 1/2 — к множеству T .

Задача № 4.4.3 на странице 180

318 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

Студент предлагает для задачи 23 «MAX-CUT» прибли-

женный алгоритм с точностью

: положить первую вершину

в одну часть, последнюю — в другую, затем по-очереди до-

бавлять оставшиеся вершины, к множеству, с которым у этой

вершины меньше ребер-связей.

Прав ли студент?

Тема: derandomization-maxsat

Задача № 5.1.1 на странице 191

Покажите, что можно организовать вычисление f

и f

та-

ким образом, что сложность алгоритма 35 «MAX-SAT дерандо-

мизация» (кроме решения линейной релаксации) будет O(mn).

Задача № 5.1.2 на странице 191

Честный попутчик в поезде предлагает вам сыграть в сле-

дующую игру, вариант классического «наперстка». т. е. есть

три наперстка, шарик, ваша задача обнаружить шарик — тогда

вы выигрываете, иначе — выигрывает сдающий.

Каждый раз на кон, вы и сдающий, ставите по 50 рублей.

Сдающий тасует три наперстка, и прячет под одним из них ша-

рик. Затем он предлагает вам выбрать наперсток. После того,

как вы выбрали наперсток (пусть это будет наперсток «A»),

вы можете открыть его, либо, заплатив еще 10 рублей, потре-

бовать от сдающего, открыть пустой наперсток из двух остав-

шихся (пусть открытый будет «B»), после чего выбрать один

из двух закрытых наперстков (т. е. «A» или «С»).

319

Заметим, что сдающий и предметы честные (никаких «ис-

чезающих» шариков и прочего мошенничества, наперсток для

шарика выбирается совершенно случайно).

Какая стратегия оптимальна?

1) Не играть. Выигрыш — 0.

2) Выбрать наперсток «A» и открыть его.

3) Выбрать наперсток «A», «купить» открытие пустого на-

перстка «B», но выбрать наперсток «A».

4) Выбрать наперсток «A», «купить» открытие пустого на-

перстка «B», и выбрать наперсток «С».

Дорога длинная, играть можно много раз, правильная

стратегия может привести к существенному обогащению,

неправильная — к разорению. . .

Обоснуйте. Подсчитайте матожидание выигрыша для каж-

дой из стратегий.

Тема: machines-turing

Задача № 6.1.1 на странице 201

Постройте машину Тьюринга, которая записывает входное

двоичное слово в обратном порядке.

320 Глава 8. Сборник упражнений (ИСПРАН-2008-весна)

Задача № 6.1.2 на странице 206

Постройте машину Тьюринга, которая складывает два чис-

ла, записанные в двоичной системе. Для определенности счи-

тайте, что записи чисел разделены специальным символом ал-

фавита «+».

Задача № 6.1.3 на странице 211

Покажите, что число сканированных машиной T ячеек

M = O(N).

Задача № 6.1.4 на странице 213

Докажите, что существуют невычислимые по Тьюрингу

функции y = f(x). Использовать мощностные соображения.

Задача № 6.1.5 на странице 215

Докажите, что также неразрешима версия задачи 26 «HALT» —

«остановка на пустом слове», т. е. для данной МТ T определить,

остановится ли она на пустом слове.

Задача № 6.1.6 на странице 215

Докажите, что неразрешима «Проблема недостижимого

кода» — нет алгоритма, который для заданной машины

Тьюринга T и ее состояния q

выясняет: попадет ли маши-

на в это состояние хотя бы для одного входного слова x ?

Задача № 6.1.7 на странице 215

Докажите, что не существует алгоритма, который выписы-

вает одну за другой все машины Тьюринга, которые не оста-