<<
>>

Упражнения 1.

Формулировка задачи 3-раскраски предполагает ответ «да/нет», но задачу так- же можно переформулировать в виде оптимизационной задачи.

Допустим, имеется граф G = (V, E), каждый узел которого должен быть окрашен в один из трех цветов, даже если не удастся назначить разные цвета каждой паре смежных узлов.

Ребро (u, v) будет называться реализованным, если и и v назначены разные цвета.

Рассмотрим 3-раскраску, максимизирующую количество реализованных ребер, и обозначим это количество с*. Предложите алгоритм с полиномиальным вре- менем, который дает 3-раскраску, реализующую не менее ребер. При жела- нии алгоритм можно рандомизировать; в этом случае ожидаемое количество реализуемых ребер должно быть не менее £0*.

сторонниками демократов, так что 80 000 избирателей идут на выборы с на- мерением голосовать за D, а 20 000 избирателей собираются голосовать за R. Тем не менее правила голосования достаточно сложны, поэтому каждый избира- тель независимо от других с вероятностью 1 голосует за другого кандидата — ' 100 ' '

то есть за того, за которого он голосовать не собирался.

(Напомним, что в этих выборах участвуют всего два кандидата.)

Случайная переменная X равна количеству голосов за демократического кан- дидата D при проведении голосования с возможными ошибками. Определите ожидаемое значение X и объясните ход своих рассуждений при выводе этого значения.

3. В разделе 13.1 описан простой распределенный протокол для решения конкрет- ной задачи разрешения конфликтов. Здесь рассматривается другая ситуация с применением рандомизации для разрешении конфликтов, в которой осущест- вляется распределенное построение независимого множества.

Предположим, имеется система с n процессами. Между некоторыми парами процессов возникает конфликт (предполагается, что обоим процессам необхо- дим доступ к общему ресурсу).

Для заданного интервала времени требуется спланировать выполнение большого подмножества S процессов (остальные процессы при этом не работают), чтобы никакие два конфликтующих процесса не входили в запланированное множество S. Назовем такое множество S бес- конфликтным.

Ситуацию можно смоделировать графом G = (V, E), в котором узлы представ- ляют процессы, а ребра соединяют пары процессов, находящихся в конфликте. Легко убедиться в том, что множество процессов S является бесконфликтным в том, и только в том случае, если оно образует независимое множество в G. Это наводит на мысль, что найти бесконфликтное множество S максимального раз- мера для произвольного конфликта G будет сложно (так как обобщенная задача о независимом множестве сводится к этой задаче). Тем не менее мы попробуем найти эвристику для нахождения бесконфликтного множества достаточно большого размера. Также хотелось бы найти простой метод достижения этой цели без централизованного управления: каждый процесс должен обменяться информацией только с небольшим количеством других процессов и затем ре- шить, должен ли он принадлежать множеству S.

В контексте этого вопроса предположим, что у каждого узла в графе G ровно d соседей. (То есть каждый процесс участвует в конфликтах ровно с d другими процессами.)

(a) Рассмотрим следующий простой протокол.

Каждый процесс Р. независимо выбирает случайное значение х.; с вероят- ностью I переменной х. присваивается значение 1, и с вероятностью I х.

2 ' 2 ' присваивается значение 0. Затем процесс решает войти в множество S в том,

и только в том случае, если он выбирает значение 1, и каждый из процессов, с которыми он участвует в конфликте, выбирает значение 0.

Докажите, что множество S, полученное в результате выполнения этого про- токола, является бесконфликтным. Также приведите формулу для ожидае- мого размера S в отношении к n (количество процессов) и к d (количество конфликтов на один процесс).

(b) Выбор вероятности I в приведенном выше протоколе был достаточно

2

произвольным, и не так уж очевидно, что он должен обеспечить лучшую

эффективность системы.

В более общей спецификации протокола вероят- ность I заменяется параметром р в диапазоне от 0 до 1 так, как описано ниже.

2

Каждый процесс P. независимо выбирает случайное значение х; с вероятно- стью p переменной х присваивается значение 1, и с вероятностью 1 - p х присва- ивается значение 0. Затем процесс решает войти в множество S в том, и только в том случае, если он выбирает значение 1, и каждый из процессов, с которыми он участвует в конфликте, выбирает значение 0.

В контексте параметров графа G приведите значение p, максимизирующее ожидаемый размер полученного множества S. Предложите формулу для ожи- даемого размера S, когда p присваивается это оптимальное значение.

4. Многие одноранговые системы в Интернете строятся на базе оверлейных сетей. Вместо использования физической топологии Интернета и выполнения с ней необходимых вычислений такие системы используют протоколы, в которых узлы выбирают совокупности виртуальных «соседей» для определения высоко- уровневого графа, структура которого имеет минимальное отношение к струк- туре используемой физической сети. Затем такая оверлейная сеть используется для обмена данными и сервисами и может быть исключительно гибкой по сравнению с физической сетью, которую трудно изменить в реальном времени для адаптации к изменяющимся условиям.

Одноранговые сети обычно растут за счет новых участников, которые при- соединяются к существующей структуре. Процесс развития сети оказывает специфическое влияние на характеристики общей сети. За последнее время были исследованы простые абстрактные модели развития сетей, которые дают представление о поведении таких процессов в реальных сетях на качественном уровне.

Рассмотрим простой пример такой модели. Система начинается с одиночного узла v1, после чего узлы присоединяются к ней один за одним; при присоеди- нении узла выполняется протокол с формированием направленного канала связи с другим узлом, выбранным случайно и равномерно из узлов, уже присут- ствующих в системе.

Конкретнее, если система уже содержит узлы v1, v2, ..., vk1 и узел vk желает присоединиться, он случайным образом выбирает один из узлов v1, v2, ..., vk-1 и устанавливает связь с ним.

Предположим, процесс повторяется вплоть до формирования системы, со- стоящей из узлов v1, v2, ..., vn; описанная выше случайная процедура создает направленную сеть, в которой каждый узел, кроме v1, имеет ровно один выход- ной канал. С другой стороны, узел может иметь несколько входных каналов, а может не иметь ни одного. Входные каналы v. представляют все остальные узлы, которые получают доступ к системе через v.; таким образом, если v. имеет много входных каналов, нагрузка на него может оказаться достаточно высокой. Чтобы система была сбалансирована, нам хотелось бы, чтобы узлы имели примерно одинаковое количество входных каналов. Однако в опи- санной ситуации это маловероятно, так как узлы, присоединенные на более ранней стадии процесса, с большей вероятностью будут иметь больше входных каналов, чем узлы, присоединившиеся позднее. Попробуем дать численную оценку этому дисбалансу.

(a) Для заданного случайного процесса, описанного выше, каково ожи- даемое количество входных каналов к узлу v в такой сети? Приведите точную формулу для n и и попробуйте выразить эту величину асимпто- тически (выражением без громоздкого суммирования) с использованием записи еt>

(b) Часть (a) точно выражает смысл, в котором узлы, присоединяемые ранее, получают «несправедливую» долю соединений в сети. Другой способ чис- ленного выражения дисбаланса основан на том факте, что при выполнении этого случайного процесса можно ожидать, что многие узлы останутся без входных каналов.

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

5. Где-то в сельской местности n небольших городков решили подключиться к Интернету по оптоволоконному кабелю с высокой пропускной способно- стью.

Городки обозначаются T1, T2, ..., Tn и располагаются вдоль одной длин- ной долроги, так что город T удален на i километров от точки подключения (рис. 13.6).

Точка подключения

Рис. 13.6. Городки T Tn должны решить, как им разделить расходы на покупку кабеля

Кабель стоит довольно дорого — к долларов за километр, то есть общая стои- мость всего кабеля составляет кп долларов. Представители городков собираются вместе и обсуждают, как им следует разделить расходы на покупку кабеля. Наконец, один из городков на дальнем конце дороги вносит следующее пред- ложение.

Предложение A. Разделить затраты поровну между всеми городками, чтобы каждый платил к долларов.

В каком-то смысле предложение честное: все выглядит так, словно каждый городок платит за километр кабеля, который ведет непосредственно к нему. Но один из представителей городка, расположенного очень близко к точке под- ключения, резонно указывает, что от более длинного кабеля выигрывают в ос- новном дальние городки, а ближние вполне обошлись бы и коротким кабелем. Поэтому он выдвигает встречное предложение:

Предложение Б. Разделить стоимость так, чтобы вклад городка T был про- порционален i, то есть расстоянию до точки подключения.

Представитель другого городка, также очень близкого к точке подключения, указывает, что существует другой способ непропорционального деления, кото- рый тоже естествен. Он основан на концептуальном делении кабеля на n «ре- бер» равной длины e1, ..., en; первое ребро e1 ведет от точки подключения к T1, а i-е (i > 1) ведет от T._x к T.. Заметим, что хотя e1 используется всеми городками, en приносит пользу только последнему городку. Так появляется

Предложение В. Разделить стоимость для каждого ребра e.

по отдельности. Стоимость e. должна оплачиваться в равной мере городками T, T+1,..., T, так как они находятся «после» ei.

Итак, вариантов много; какой из них самый справедливый? За ответом на этот вопрос собрание обращается к работе Ллойда Шепли, одного из самых знаме- нитых экономистов-математиков XX века. Он предложил общий механизм раз- деления стоимости или прибылей между общими сторонами, который теперь называется распределением Шепли. Этот механизм может рассматриваться как определение «предельного вклада» каждой стороны в предположении, что сто- роны прибывают в случайном порядке.

В условиях нашей задачи произойдет следующее: возьмем упорядочение О го- родков и предположим, что городки «прибывают» в этом порядке. Предельная стоимость городка Ti в порядке О определяется следующим образом: если Ti является первым в порядке О, то T платит k — стоимость всего кабеля на всем отрезке от точки подключения до Ti. В противном случае алгоритм просматри- вает множество городков, предшествующих T. в порядке О; допустим, из этих городков T_ находится на наибольшем расстоянии от точки подключения. При прибытии T. предполагается, что кабель уже проложен до T, но не далее. Итак, если J > ί (Tj находится дальше T ), предельная стоимость T равна 0, так как кабель уже проходит мимо T на своем пути к TJ. С другой стороны, если J < , то предельная стоимость T равна k( -J): это стоимость продления кабеля от Tj к T. (Предположим, n = 3, и городки прибывают в порядке T1, T3, T2. Сначала T1 пла- тит k при прибытии. Затем прибывает T3, которому достаточно заплатить 2k для продления кабеля от T1. Наконец, при прибытии T2 платить вообще ничего не нужно, так как кабель уже проложен мимо этого городка до T3.)

Пусть X — случайная переменная, равная предельной стоимости городка T при случайном равномерном выборе порядка О из всех перестановок множества городков. По правилам распределения Шепли величина, которую городок Ti должен внести в общую стоимость кабеля, равна ожидаемому значению X.

Вопрос: какое из трех предложений (если оно есть) обеспечивает такое же распределение стоимостей, как механизм распределения Шепли? Приведите доказательство ответа.

6.Одна из (многих) сложных задач, связанных с расшифровкой генома, может быть сформулирована следующим абстрактным способом. Имеется множество из n маркеров {μ1, ..., μη} — позиций в хромосоме, требуется вывести линей- ное упорядочение этих маркеров. Вывод должен удовлетворять множеству к ограничений, каждое из которых задается триплетом (μ;, μ^, μλ) и требует, чтобы маркер μ^. находился между μ; и μk в общем упорядочении). (Обратите внимание: это ограничение не указывает, какой из маркеров μ; или μk должен находиться на первом месте в упорядочении, а лишь требует, чтобы маркер μ^. находился между ними).

Одновременное выполнение всех ограничений не всегда возможно, поэтому требуется получить упорядочение, выполняющее как можно больше из них. К сожалению, принятие решения о существовании упорядочения, выполняю- щего не менее к' из к ограничений, является ХР-сложной задачей (доказывать это не нужно).

Приведите константу а > 0 (не зависящую от n) и алгоритм, обладающий сле- дующим свойством: если возможно выполнить к* ограничений, то алгоритм выдает упорядочение маркеров, выполняющее не менее аk ограничений. Ал- горитм может быть рандомизированным; в таком случае он должен выдавать упорядочение, для которого ожидаемое количество выполненных ограничений не менее ак*

7. В разделе 13.4 был разработан аппроксимирующий алгоритм для задачи MAX 3-SAT с множителем 7/8, в котором предполагалось, что каждое условие содер- жит составляющие для трех разных переменных. В этой задаче рассматривается похожая задача MAX SAT: для заданного множества условий C1, ..., Ck по множе- ству переменных X = {x1, ..., xn} найти логическое присваивание, выполняющее как можно большее количество условий. Каждое условие содержит минимум один литерал, и все переменные в одном условии различны, но в остальном никакие допущения относительно длины условий не делаются: одни условия могут состоять из многих переменных, а другие содержат всего одну.

(a) Сначала рассмотрим рандомизированный аппроксимирующий алгоритм, который мы использовали для задачи MAX 3-SAT, с независимым присва- иванием каждой переменной истинного или ложного значения с вероятно- стью 1/2. Покажите, что ожидаемое количество условий, выполненных этим случайным присваиванием, не менее k/2, то есть в ожидании выполняется по меньшей мере половина условий. Приведите пример, показывающий, что существуют экземпляры задачи MAX SAT, в которых никакое присваивание не выполняет более половины условий.

(b) Если имеется условие, состоящее только из одного литерала (например, условие, включающее только x{ или только v- ), то оно может быть выполне- но только одним способом: нужно присвоить переменной соответствующее

значение. Если есть два условия, одно из которых состоит только из х., а дру- гое из его отрицания, возникает довольно очевидное противоречие. Предположим, в нашем экземпляре нет таких «прямых конфликтов», то есть не существует переменной х, для которой условие С = {х.} существует

одновременно с условием С1 = |xг J. Измените приведенную выше рандоми- зированную процедуру, чтобы улучшить коэффициент аппроксимации с 1/2 до минимум 0,6. Другими словами, измените алгоритм так, чтобы ожидаемое количество условий, выполняемых процессом, было не менее 0,6k.

(c) Предложите рандомизированный алгоритм с полиномиальным време- нем для обобщенной задачи MAX SAT, при котором ожидаемое количество условий, выполняемых алгоритмом, лежит в пределах множителя 0,6 от мак- симума. (Учтите, что по аналогии с (a) существуют экземпляры, в которых невозможно выполнить более к/2 условий; суть в том, что нам хотелось бы иметь эффективный алгоритм, способный в ожидании выполнить до 0,6 ча- сти условий от максимума, выполняемого при оптимальном присваивании.)

8. Имеется ненаправленный граф G = (V, E) с n узлами и m ребрами. Для подмно- жества X !Ξ Vзапись G[X] будет обозначать подграф, индуцированный по X, — то есть граф, множеством узлов которого является X, а множество ребер состоит из всех ребер G, оба конца которых принадлежат X.

Для заданного натурального числа к < n требуется найти множество из к узлов, индуцирующее из G «плотный» подграф. Или в более точной формулировке, предложите алгоритм с полиномиальным временем, который выдает для за- данного натурального числа к < n множество Л' !Ξ Г’из к узлов, обладающее тем

... ... , тk{к-]}

свойством, что индуцированный подграф сj|ЛJ содержит минимум --------------------------

, ^ ^ ч(rt-l)

ребер.

Приведите либо (a) детерминированный алгоритм, либо (b) рандомизирован- ный алгоритм с полиномиальным оиждаемым временем выполнения, который выводит только правильные ответы.

9. Допустим, вы разрабатываете стратегии для продажи товаров на популярном аукционном сайте. В отличие от других аукционных сайтов, на вашем исполь- зуется однопроходной аукцион, в котором каждая ставка либо немедленно (и без- возвратно) принимается, либо отклоняется. Ниже приведена более конкретная схема работы сайта.

• Продавец выставляет товар для продажи.

• Покупатели приходят последовательно.

• При появлении покупатель i делает ставку b. > 0.

• Продавец немедленно решает, принять эту ставку или нет. Если ставка при- нята, то товар продается, а будущие покупатели теряют возможность его купить. Если ставка отклонена, то покупатель i уходит, а ставка отменяется; только после этого продавец сможет увидеть заявки будущих покупателей.

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

Например, продавец всегда может принимать первую ставку. В результате ве- роятность того, что он примет высшую из n заявок, составит всего 1/n, так как высшая ставка должна оказаться первой из поданных.

Предложите стратегию, при которой продавец принимает высшую из n ставок с вероятностью не менее 1/4 независимо от значения n. (Для простоты считайте, что число n четно.) Докажите, что ваша стратегия обеспечивает эту вероятност- ную гарантию.

10. Рассмотрим очень простую систему проведения веб-аукциона, которая работает следующим образом. Имеются n агентов; агент i делает ставку b,, которая явля- ется положительным целым числом. Будем считать, что все ставки b отличны друг от друга. Агенты появляются в порядке, выбираемом случайным образом с равномерным распределением, каждый делает свою ставку b,, а система посто- янно поддерживает переменную b* равную наивысшей из сделанных на данный момент ставок. (Переменная b* инициализируется 0.)

Приведите оценку ожидаемого количества обновлений b* при выполнении этой процедуры как функцию параметров задачи.

Пример. Допустим, b1 = 20, b2 = 25 и b3 = 10, а агенты прибывают в порядке 1, 3, 2. Тогда b* обновляется для заявок агентов 1 и 2, но не для 3.

11. Алгоритмы распределения нагрузки для параллельных или распределенных систем стремятся равномерно распределить группу вычислительных заданий по нескольким машинам. Это делается для того, чтобы избежать пиковых на- грузок на отдельных машинах. Если централизованная координация возможна, то нагрузка может быть распределена почти идеально. Но что, если задания поступают из разных источников, которые не могут координироваться? Как было показано в разделе 13.10, задания можно распределять между машинами случайным образом, надеясь, что рандомизация поможет предотвратить несба- лансированность. Разумеется, такое решение в общем случае уступает идеаль- ному централизованному решению, но оно может быть вполне эффективным. Попробуем проанализировать некоторые вариации и расширения простой эвристики распределения нагрузки, описанной в разделе 13.10.

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

(a) Обозначим N(k) ожидаемое количество машин, не получивших ни одного задания, так что N(к)/к — ожидаемая часть бездействующих машин. Чему равен предел liп⅛^, jV(⅛}/к ? Приведите доказательство.

(b) Допустим, машины не могут ставить в очередь лишние задания, так что если случайное распределение назначает на машину M больше одного задания, то M выполняет первое из полученных заданий и отклоняет все остальные. Пусть R(k) — ожидаемое количество отклоненных заданий; со- ответственно R(к)/к — ожидаемая часть отклоненных заданий. Чему равен предел lim1⅞ R(к)/к ? Приведите доказательство.

(c) Предположим, машины имеют встроенный буфер чуть большего размера; каждая машина M выполняет первые два полученных задания и отклоняет все остальные. Обозначим R2(к) ожидаемое количество заданий, откло- ненных по этому правилу. Чему равен предел liint_v R,(к)fк ? Приведите доказательство.

12. Рассмотрим аналогию с алгоритмом Каргера для нахождения минимального разреза s-t. Ребра будут стягиваться в итеративном режиме с использованием рандомизированной процедуры. Пусть в заданной итерации s и t — (возможно) стянутые узлы, содержащие исходные узлы s и t соответственно. Чтобы гаран- тировать, что узлы s и t не будут сжаты, на каждой итерации удаляются все ребра, соединяющие s и t, а стягиваемое ребро выбирается случайным образом среди остальных ребер. Приведите пример, показывающий, что вероятность нахождения этим методом минимального разреза s-t может быть экспоненци- ально малой.

13. Рассмотрим классический эксперимент с шарами и корзинами. Как обычно, каждый шар независимо попадает в одну из двух корзин, при этом попадание в каждую из корзин равновероятно. Ожидаемое количество шаров в каждой корзине равно n. В этой задаче исследуется вопрос возможной величины их разности. Пусть X1 и X2 — количество шаров в первой и второй корзине соот- ветственно (X и Л', — случайные переменные). Докажите, что для любого ε > О

существует константа с > 0, для которой вероятность Рг[jf, — Xг > t'>/ii] < ε.

14. Ученые, разрабатывающие параллельные физические модели, обращаются к вам по поводу следующей задачи. Имеется множество P из к базовых про- цессов, требуется назначить каждый процесс на одну из двух машин M1 или M2. Затем они будут выполнять серию из n заданий Jp ..., J Каждое задание J представляется множеством ђ С Р из ровно 2n базовых процессов, которые должны выполняться (каждый на назначенной машине) во время обработки задания. Распределение базовых процессов по машинам называется идеально сбалансированным, если для каждого задания J. ровно n базовых процессов, свя- занных с J., были назначены на каждую из двух машин. Распределение базовых процессов между машинами будет называться почти сбалансированным, если

для каждого задания J не более -и базовых процессов, связанных с J, были ' j '

назначены на одну машину.

(a) Покажите, что для произвольно больших значений n существуют серии заданий J1, ..., Jn, для которых не существует идеально сбалансированного распределения.

(b) Предположим, n > 200. Предложите алгоритм, который получает произ- вольную серию заданий J1, ..., Jn, и строит почти сбалансированное распреде- ление базовых процессов между машинами. Ваш алгоритм может быть ран- домизированным; в этом случае ожидаемое время выполнения должно быть полиномиальным и алгоритм всегда должен выдавать правильный ответ.

15. Предположим, имеется очень большое множество S вещественных чисел, и вы хотите вычислить предполагаемую медиану этих чисел на основании выборки. Можно считать, что все числа в S различны. Пусть n = \S\; число х будет на- зываться ^-приближенной медианой S, если по крайней мере — t\п чисел в S

меньше х и по крайней мере --d∩ чисел в S больше

Рассмотрим алгоритм, который выбирает случайное подмножество S* С S с равномерным распределением, вычисляет медиану S' и возвращает ее как приближенную медиану S. Покажите, что существует абсолютная константа с, независимая от n, так что при применении алгоритма с выборкой S' размера с с вероятностью 0,99 возвращаемое число будет (0,05)-приближенной медиа- ной S. (Рассмотрите либо версию алгоритма, строящую S' посредством фор- мирования выборки с заменой, чтобы элемент S мог выбираться многократно, либо версию без замены.)

16. Рассмотрим следующий (частично определенный) метод безопасной передачи сообщения между отправителем и получателем. Сообщение будет представле- но в виде битовой строки. Пусть ∑ = {0* 1| и ∑ — множество всех строк из 0 и более битов (например, 0,00,1110001 Е ∑ ). «Пустая строка», не содержащая битов, будет обозначаться λ Е ∑ .

Отправитель и получатель совместно используют секретную функцию ∕: ∑* х∑ —> ∑ . Иначе говоря,/получает слово и бит и возвращает бит. По- лучая последовательность битов н £ ∑ , получатель выполняет следующий метод для ее расшифровки.

Пусть α = a1a2...an, где n - количество битов в а.

Целью является получение расшированного n-битного сообщения

β = Р⅜.Рn

Присвоить β1 = f (λ,α1)

Для i = 2,3,4......... n

Присвоить β. = f (β1β2...β._1,α.)

Конец цикла Вывести β

Происходящее можно рассматривать как своего рода «потоковый шифр с об- ратной связью». Недостаток такого решения заключается в том, что если любой

бит α. будет поврежден при передаче, он повредит вычисленное значение β. для всех j > i.

Рассмотрим следующую задачу: отправитель S хочет передать сообщение (про- стой текст) β каждому из к получателей R1, ..., Rk. С каждым получателем он обменивается секретной функцией f (i) (разной для разных получателей). Затем каждому получателю отправляется свое зашифрованное сообщение a(i), такое что a(i) расшифровывается в β при выполнении описанного выше алгоритма с функцией f (i).

К сожалению, каналы связи сильно зашумлены, и каждый из n битов в каждой из к передач подвергается независимому искажению (то есть принимает проти- воположное значение) с вероятностью 1/4. Таким образом, любой получатель с большой вероятностью не сможет расшифровать сообщение сам по себе. По- кажите, что если значение к достаточно велико как функция n, то к получателей смогут совместными усилиями восстановить текстовое сообщение: для этого они собираются вместе и, не раскрывая никакие из a(i) или f(i), в интерактив- ном режиме выполняют алгоритм, который строит правильное содержимое β с вероятностью не менее 9/10. (Насколько большим должно быть значение к в вашем алгоритме?)

17. Рассмотрим простую модель азартной игры при неблагоприятных шансах. В начале общий выигрыш равен 0. Проводится серия из n раундов; в каждом раунде выигрыш возрастает на 1 с вероятностью 1/3 и убывает на 1 с вероят- ностью 2/3.

Покажите, что для ожидаемого количества шагов, при котором выигрыш по- ложителен, можно определить верхнюю границу в виде абсолютной константы, не зависящей от значения n.

18. В этой задаче рассматривается рандомизированный алгоритм для задачи о вер- шинном покрытии.

Инициализировать S = 0

Пока S не является вершинным покрытием,

Выбрать ребро e, не покрываемое S

Выбрать один конец e случайным образом (с равной вероятностью).

Добавить выбранный узел в S.

Конец Пока

Нас интересует ожидаемая стоимость вершинного покрытия, выбираемого этим алгоритмом.

(a) Является ли этот алгоритм с-аппроксимирующим алгоритмом для задачи о вершинном покрытии с минимальным весом для некоторой константы с? Докажите свой ответ.

(b) Является ли этот алгоритм с-аппроксимирующим алгоритмом для за- дачи о вершинном покрытии с минимальной мощностью для некоторой константы с? Докажите свой ответ.

Подсказка: обозначим pe вероятность того, что ребро e выбирается как непо- крытое ребро в этом алгоритме. Сможете ли вы выразить ожидаемое значение решения через эти вероятности? Чтобы ограничить значение оптимального решения в контексте вероятностей р , попробуйте ограничить сумму вероят- ностей для ребер, инцидентных заданной вершине v, а именно ]Гj jр⅛.

г iпi i⅛m из V

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнения 1.:

  1. УПРАЖНЕНИЕ
  2. Приведем список всех упражнений и их номера:
  3. 5.4. Планирование упражнений
  4. Упражнение 2
  5. Упражнение 3
  6. Упражнение 4
  7. Упражнение 5
  8. Упражнение 6
  9. Упражнение 7
  10. Упражнение 8
  11. Упражнение 9
  12. Упражнение 10
  13. Упражнение 11
  14. Упражнение 12
  15. Упражнение 13
  16. УПРАЖНЕНИЕ 2
  17. Упражнение 3 (сахадж пранаяма 3)
  18. Физические упражнения
  19. УПРАЖНЕНИЯ И МЕДИТАЦИИ
  20. Упражнение первое