WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 11 |
зованных асинхронных систем процессов с синхронным обменом сообщениями.

В статье П.Е. Булычева, В.А. Захарова и И.В. Коннова исследован один из новейших методов проверки различных отношений симуляции и бисимуляПредисловие ции между конечными размеченными системами переходов, которые используются для моделирования и верификации систем распределенных взаимодейВ настоящем сборнике представлены статьи, посвященные разработке мествующих процессов. Этот метод позволяет сводить задачу проверки указантодов синтеза и анализа алгоритмов для различных задач дискретной матеманых отношений к проблеме существования выигрышных стратегий в паритеттики и теоретического программирования.

ных играх, порожденных проверяемыми системами переходов. Метод паритетСтатья С.Н. Жука посвящена задаче упаковки произвольного множеных игр был применен авторами для построения эффективных алгоритмов проства прямоугольников в несколько полубесконечных полос. Эта задача верки простых и справедливых отношений симуляции и бисимуляции по прореявляется обобщением нескольких известных NP-трудных задач: задачи об живанию (stuttering simulation/bisimulation). В результате были впервые разm-процессорном расписании, задачи об упаковке в контейнеры, задачи об работаны алгоритмы проверки отношения симуляции по прореживанию, котоупаковке прямоугольников в одну полосу. Основным результатом работы рые имеют такую же сложность по времени и объему памяти, как и наилучшие является доказательство существования алгоритма для рассматриваемой заалгоритмы проверки обычной симуляции конечных размеченных систем передачи, работающего в режиме on-line и гарантирующего нахождение решения, ходов. Предложенные в этой статье алгоритмы проверки симуляции могут быть отличающегося от оптимального не более, чем в константу раз.

использованы для верификации систем распределенных программ.

В статье Н.Н. Кузюрина и А.И. Поспелова рассматривается задача упаковСтатья В.А. Захарова, Н.Н. Кузюрина, Р.И Подловченко и В.С. Щербики множества прямоугольников в вертикальную полубесконечную полосу едины посвящена проблемам обнаружения сложных компьютерных вирусов — так ничной ширины. Изучен важный подкласс онлайновых алгоритмов для этой заназываемых полиморфных и метаморфных вирусов, обладающих способностью дачи – так называемые шельфовые алгоритмы. Предложен общий метод веромодифицировать (обфускировать) свою подпись. Показано, что задача обнаруятностного анализа шельфовых алгоритмов, позволяющий для многих шельфожения таких вирусов может быть сведена к проблеме проверки эквивалентновых алгоритмов оценивать математическое ожидание незаполненной площади.

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

преобразований. Дан обзор основных результатов по сложности проблемы экУчебно-методическая статья Н.П. Варновского и А.В. Шокурова знакомит вивалентности в различных алгебраических моделях программ.

читателя (не претендуя на полноту обзора результатов) с важным криптографиВ статье И.А Лаврова освещены важные аспекты классической теории алческим примитивом — гомоморфным шифрованием, представляющим интерес горитмов и теории сложности вычислений. Показано, что ряд подходов к форкак с прикладной, так и с чисто математической точек зрения. В статье затронумализации понятия сложности вычислений неадекватно отражает данное поняты также и некоторые смежные вопросы. Отмечено, что несмотря на многолеттие. Более последовательным представляется построение различных иерархий ние исследования в области гомоморфного шифрования, основные проблемы классов сложности. С помощью подобных классов удается локализовать уровостаются нерешенными.

ни сложности ряда классических математических задач.

Статья В.А. Захарова и И.В. Коннова посвящена униформной проблеме верификации параметризованных систем взаимодействующих процессов. Для верификации параметризованных систем применяется метод поиска инварианЧл.-корр. РАН В.П.Иванников тов с использованием специальных отношений порядка на множестве конечных систем переходов. Введен новый тип предпорядка — так называемая квазиблочная симуляция. В статье доказано, что квази-блочная симуляция сохраняет выполнимость формул из ACT L, и асинхронная композиция процессов -X монотонна по отношению квази-блочной симуляции. Показано, каким образом можно использовать квази-блочную симуляцию для верификации параметри5 ет эффективный алгоритм, позволяющий решить эту задачу точно. Поэтому рассматривают различные приближённые алгоритмы, которые позволяют достаточно быстро найти некоторое решение с определённой точностью.

Онлайновый алгоритм упаковки Для оценки точности приближенных алгоритмов можно использовать прямоугольников в несколько полос с следующие характеристики. Пусть T — некоторая последовательность прягарантированными оценками точности моугольников, C — множество полос, HO(T, C) и HA(T, C) – высота оптимального размещения прямоугольников и высота размещения, получающаяся с помощьюалгоритма A, на множестве полос C. Тогда абсолютная точность С.Н. Жук алгоритма A определяется как Аннотация. В работе описан онлайновый алгоритм упаковки произвольного множества прямоугольников в несколько полос и доказано, что он гарантирует нахождение решеRA =sup{HA(T, C)/HO(T, C)}, ния, отличающегося от оптимального не более чем в константу раз. T,C а асимптотическая как 1. Введение RA = lim sup{HA(T, C)/HO(T, C) | HO(T, C) k}.



Задача упаковки прямоугольников в несколько полос заключается в следуk T,C ющем: имеется несколько полубесконечных полос определённой ширины и наОсобый интерес представляют так называемые online алгоритмы. Эти алгобор прямоугольников. Требуется найти ортогональное размещение этих пряморитмы отличаются от обычных тем, что они производят последовательное расугольников по полосам (без пересечений и вращений), имеющее минимальную смотрение всех размещаемых объектов. В таких алгоритмах, каждый приходявысоту. Эта задача возникает, например, при распределении ресурсов в глощий объект сразу же размещается, и его положение не изменяется с прихобальных вычислительных сетях Grid, объединяющих различные вычислительдом следующих. Как правило такие алгоритмы более эффективны, кроме того ные ресурсы (кластеры). Проблема оптимального размещения задач на группе их удобнее использовать на практике, так как не всегда с самого начала известкластеров имеет простую геометрическую интерпретацию [17]. Кластер можны все размещаемые объекты.

но представить как бесконечнуюв одну строну полосу определенной ширины (ширина характеризует число процессоров кластера, другое измерение соответНаиболее исследованы частные случаи рассматриваемой задачи. Один из ствует времени), а задачу — как прямоугольник с высотой и шириной равныних — уже упомянутая классическая задача об упаковке в контейнеры (binми времени выполнения и требуемому числу процессоров соответственно. Тоpacking).

гда естественно возникает задача упаковки данного множества задач (прямоДругой частный случай, когда у нас имеется всего одна полоса, — это также угольников) в несколько полос (кластеров): требование, что прямоугольники не известная и хорошо исследованная задача. Впервые её изучали Baker, Coffman должны пересекаться означает, что каждая задача на некоторое время (равное и Rivest [2] в 1980 году. Ими был предложена простая эвристика Bottom-Left, высоте прямоугольника) занимает некоторое число процессоров (равное шипозволяющая размещать прямоугольники внутри одной полосы с абсолютной рине прямоугольника).

точностью3. Затем в 1981 году Baker, Brown и Katseff [4] представили offline алгоритм гарантирующий асимптотическую точность 5/4. И этот алгоритм остаДаже для случая одной полосы, рассматриваемая задача является вался лучшим до тех пока в 1996 году Kenyon и Remila [3] не построили алNP-трудной. Например, к ней сводится одномерная задача об упаковке в горитм, позволяющий за полиномиальное время находить почти оптимальное контейнеры (bin-packing [1]). Если высоты всех прямоугольников равны 1, то решение (с асимптотической точностью 1+ для любого >0).

слои, которые будут получаться при их размещении, как раз и соответствуют Что касается online алгоритмов, то здесь тоже имеется значительное колиэтим контейнерам. Следовательно, вряд ли можно ожидать, что существучество исследований. В 1983 году Baker и Shwartz [5] представили так называеРабота выполнена при поддержке РФФИ, проект 05-01-00798.

мые шельфовые алгоритмы. В данных алгоритмах полоса разбивается на гори7 зонтальные слои(шельфы) различной высоты, а для размещения прямоуголь- тической точности.

ников внутри шельфов используется какая-нибудь эвристика для одномерной 2. Постановка задачи упаковки в контейнеры(bin-backing). Один из таких алгоритмов с очень простой эвристикой First Fit позволяет добиться асимптотической точности 1.7.

Вход: T = {T1,..., Tn} — конечная последовательность прямоугольников, Затем Csirik и Woeginger [8] показали, что никакой шельфовый алгоритм не h(Tj) и w(Tj) — соответственно высота и ширина прямоугольника Tj (максиможет иметь асимптотическуюточность меньше чем 1.69103 и построили алмальная высота одного прямоугольника равна hmax), и C = {C1,..., Cm} многоритм, позволяющий сколь угодно близко подойти к данному значению. Также жество полубесконечных полос, wi — ширина i-й полосы.

Van Vliet [10] показал, что никакой online алгоритм упаковки прямоугольников в Задача: Найти ортогональное размещение последовательности прянесколько полос не позволяет добиться асимптотической точности лучшей чем моугольников T по этим полосам, минимизирующее полную высоту этого 1.5401.

размещения, то есть максимум по всем прямоугольникам и по всем полосам Еще один важный частный случай — это задача о составлении расписания расстояния от дна полосы до верхней грани прямоугольника.

для m машин. Если предположить, что имеется m одинаковых полос ширины 1 и все прямоугольники также имеют ширину равную 1, то как раз получится Пусть C и T — заданные множества полос и прямоугольников, и пусть A — данная задача. Впервые её исследовал Graham [11], он предложил очень пронекоторый алгоритм размещающий прямоугольники по полосам. Тогда будем стой online алгоритм, который размещает каждуюновуюзадачу на наименее заобозначим HO(T, C) — оптимальное значение высоты размещения последовагруженнуюмашину. Точность этого алгоритма равна 2 - 1/m, для m машин.

тельности прямоугольников T на полосах C, иHA(T, C) — высота размещения Несмотря на простоту данного алгоритма, долгое время не удавалось построить этих прямоугольников на C, получающегося при использовании алгоритма A.

алгоритм, точность которого бы была меньше 2 - для любого m (для фиксиДля оценки точности приближенных алгоритмов мы будем использовать рованного положительного ). Только в 1992 году Bartal et al.[13] предложили следующие характеристики.





алгоритм с точностьюне хуже 1.986 для всех m>70. Это значение затем было 1. Абсолютная точность алгоритма A определяется как улучшено до 1.945, а затем и до 1.923 в работах [15] и [12]. Также было получено несколько результатов о нижних оценках для таких алгоритмов. Bartal, RA =sup{HA(T, C)/HO(T, C)}.

Karloff и Rabani [16] показали, что ни один детерминированный алгоритм не моT,C жет иметь точность лучше, чем 1.837 для достаточно большого m. Этот резуль2. Асимптотическая точность алгоритма A определяется как тат был улучшен Albers [12] до 1.852.

Что касается задачи об упаковке прямоугольников в несколько полос, то она RA = lim sup{HA(T, C)/HO(T, C) | HO(T, C) k}.

до сих пор остается в значительной степени не исследованной. А. Поспелов [21] k T,C предложил offline алгоритм, основанный на эвристике Bottom-Left, позволяющий размещать прямоугольники с абсолютной точностью равной 3. В работе 3. Шельфовый алгоритм [18] был рассмотрен алгоритм, размещающий прямоугольники по полосам в реДля размещения прямоугольников внутри каждой из полос будет испольжиме online, позволяющий добиться точности 10.

зоваться так называемый шельфовый алгоритм. Он был рассмотрен в [4] для Во данной работе предложен алгоритм, работающий полностью в режиме случая одной полосы.

online, размещающий прямоугольники в несколько полос с константной мульПусть задана некоторая константа r (0, 1). Шельф — это прямоугольная типликативной точностью17 и асимптотической точностьюсколь угодно близчасть полосы, с шириной равной ширине полосы. Как только приходит новый кой к 8. В разделе 2 дано более формальное описание задачи. В разделе 3 распрямоугольник Ti, шельфовый алгоритм определяет целое число k, такое что смотрены шельфовые алгоритмы, которые будут использоваться для упаковки rk+1 r · h1, то ники внутри каждого шельфа размещаются по горизонтали в ряд. Таким обраhmax зом, упаковка прямоугольников, попавших в один класс по высоте (то есть коH1. (2) r(1 - r) торым соответствует одно значение k), производится с помощьюнекоторой эвОценим теперь H2. Каждый из шельфов в G2 заполнен по ширине не меньше ристики, осуществляющей одномерную упаковку в контейнеры (Bin-Packing).

чем на половину и высота любого прямоугольника в нем составляет не менее r Мы будем использовать эвристику First Fit(FF), которая каждый прямоугольот высоты шельфа. Поэтому, ник помешается в первый шельф в который он вообще может быть размещен, и если таких нет, то создает новый шельф.

1 2 S S rH2w = H2. (3) 2 r w Описанный выше алгоритм будем обозначать Shelf(r). Нам понадобится следующее свойство шельфовых алгоритмов.

Подставляя (2) и(3) в(1), получим Теорема 1. Пусть суммарная площадь прямоугольников упакованных на 2 S hmax данную полосу равна S, ширина данной полосы равна w и максимальная HShelf(r) · +.

r w r(1 - r) высота прямоугольника равна hmax, тогда для высоты упаковки получившейся с помощью алгоритма Shelf(r) справедливо 4. Описание алгоритма A(r, ) 2 S hmax Будем считать, что все полосы упорядочены по ширине, т.е. для C1,..., Cm HShelf(r) · +.

r w r(1 - r) выполняется w1 w2 · · · wm. И пусть задано некоторое число (0, 1).

Будем использовать следующие обозначения:

last(Tj) =max k : wk w(Tj) last(Tj) last(Tj) Доказательство. Пусть множество шельфов данной полосы — это first(Tj) =max r : wk wk E = {e1,..., ep}.

k=r k=Разобьем все шельфы на две группы:

Полосы с номерами first(Tj), first(Tj) +1,..., last(Tj) будем называть допустимыми для прямоугольника Tj.

G1 = {e E : e заполнен меньше чем на половину по ширине} G2 = {e E : e заполнен не меньше чем на половину по ширине} Алгоритм для размещения прямоугольников.

Обозначим также Hi = h(e), i = 1, 2 ( h(e) — высота шельфа e).

eGi 1. Для каждого поступающего прямоугольника Tj производится рассмотHi — суммарная высота шельфов из группы Gi. Тогда для высоты размещения рение всех допустимых для него полос. И затем прямоугольник Tj отс помощьюалгоритма A можно записать Si правляется на одну из допустимых полос Ci, у которой отношение wi минимально. Здесь Si – суммарная площадь прямоугольников уже разHShelf(r) H1 + H2. (1) мещённых на i-й полосе.

2. Для упаковки прямоугольников внутри каждой полосы используется Получим теперь оценки для H1 и H2. Рассмотрим сначала группу G1. Кажшельфовый алгоритм Shelf(r).

дый шельф в этой группе заполнен меньше, чем на половину. Поэтому, так как мы используем эвристику First Fit, то каждой высоты у нас не больше одного Описанный выше алгоритм зависит от двух параметров: r и. Будем его шельфа.

обозначать A(r, ).

Пусть h1 — высота самого большого шельфа в G1, тогда hH1

1 - r 11 5. Верхняя оценка для алгоритма A(r, ) Далее, m l Теорема 2. Для алгоритма A = A(r, ) для любых множества полос C и HO · wi Si. (5) последовательности прямоугольников T справедлива оценка:

i=f0 i=f Подставляя сюда (4) и используя (5), получаем 1 2 HA(T, C) · · HO(T, C) +hmax +1.

(1 - ) r r(1 - r) l l l Sk Sk HO · wi · wi (1 - ) · · wi.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 11 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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