Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное общее образовательное учреждение Высшего Профессионального образования

Тобольский Государственный педагогический институт имени Д.И. Менделеева

Кафедра информатики и МПИ

Курсовая работа

на тему: Методы алгоритмизации. Метод бинарного поиска

План

Введение

1. Традиционный подход к алгоритмам сортировки

2. Сортировка перебором

3. Сокращение числа операций сравнения

4. Ограничение на количество сравниваемых первых операндов

5. Одновременное сравнение только с соседними элементами

6. Сортировки слиянием

7. Алгоритмы сортировки одномерных массивов и поиска элементов. Сортировка методом "пузырька"

8 Бинарный поиск

Заключение

Введение

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

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

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

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

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

1. Традиционный подход к алгоритмам сортировки

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

1. Сортировка с помощью прямого включения (Straight Insertion);

2. Сортировка методом деления пополам (Binary Insertion);

3. Сортировка с помощью прямого выбора (Straight Selection);

4. Сортировка с помощью прямого обмена (Bubble Sort);

5. Шейкерная сортировка (Shaker Sort);

6. Сортировка Шелла (Shell Sort);

7. Сортировка с помощью "дерева" (Heap Sort);

8. Сортировка с помощью разделения (Quick Sort);

9. Сортировка с помощью прямого слияния (Straight Merge);

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

2. Сортировка перебором

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

1. Каждый элемент Ai вектора A[0..n-1] сравнивается со всеми другими (включая и себя) с использованием отношения:

2. (Ai > Aj) или ((Ai = Aj) и (i > j)).

3. Все проверки осуществляются одновременно.

4. Для всех элементов вектора одновременно подсчитывается количество истинных результатов сравнения с формированием вектора сумм в соответствии с расположением элементов.

5. Вектор сумм используется как набор индексов для одновременного размещения значений соответствующих ему элементов в новом векторе.

Пример, демонстрирующий использование данного алгоритма, приведен на рисунке 1. Значения элементов вектора заимствованы из [2].

Рисунок 1. Пример, демонстрирующий выполнение сортировки перебором

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

3. Сокращение числа операций сравнения

Один из путей связанных с повышением эффективности использования ресурсов может заключаться в удалении избыточных симметричных проверок. В частности, для получения результата достаточно осуществить сравнение только пар операндов, расположенных выше главной диагонали (рисунок 2). В этом случае количество проверок будет сопоставимым с их числом в простых последовательных алгоритмах (Straight Selection, Bubble Sort). Значения для отношений, определяемых главной диагональю, можно проставить без вычислений, Элементы, расположенные, ниже главной диагонали, можно вычислить путем отрицания результатов, симметрично расположенных выше нее. В связи с тем, что для элементов, расположенных выше главной диагонали, i всегда будет больше j, условие можно свести к проверке отношения Ai > Aj.

Рисунок 2. Уменьшение количества одновременных проверок

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



Рисунок 3. Использование только половины сравнений для получения результата

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

Рисунок 4. Формирования индекса относительно текущего положения

4. Ограничение на количество сравниваемых первых операндов

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

Рисунок 5. Перераспределение относительно текущего элемента

Процесс сортировки рекурсивно повторяется, одновременно и асинхронно как для левой, так и для правой последовательности до тех пор, пока не будет получен окончательный результат.

5. Одновременное сравнение только с соседними элементами

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

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

Рисунок 6. Сортировка сравнением и обменом соседних элементов

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

Рисунок 7. Сортировка сравнением и обменом внутри последовательности, расположенной в порядке убывания

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

6. Сортировки слиянием

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

Слияние тоже можно рассматривать как параллельный процесс и в общем случае можно реализовать как неограниченный алгоритм, аналогичный сортировке перебором:

1. Каждый элемент первого упорядоченного подсписка проверяется на отношение "больше" (">") со всеми элементами второго упорядоченного подсписка. Все проверки проводятся одновременно. Подсписки могут быт разной длины.

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

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

Пример использования этого алгоритма для частично упорядоченных векторов представлен на рисунке 8.

Рисунок 8. Пример, демонстрирующий выполнение слияния перебором

Как и сортировка перебором, слияние перебором может использоваться для построения алгоритмов с ограниченным параллелизмом по схемам, описанным выше.

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

Рисунок 9. Сортировка слиянием

7. Алгоритмы сортировки одномерных массивов и поиска элементов. Сортировка методом "пузырька"

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

procedure TForm1.Button1Click(Sender: TObject);

const

SIZE = 5;

var

a: array[1..SIZE] of integer;

k: integer; // текущий элемент массива

i: integer; // индекс для ввода и вывода массива

changed: boolean; // TRUE, если в текущем цикле были обмены

buf: integer; // буфер для обмена элементами массива

begin

// ввод массива

for i := 1 to SIZE do

a[i] := StrToInt(StringGrid1.Cells[i - 1, 0]);

label2.caption := '';

// сортировка массива

repeat

Changed := FALSE; // пусть в текущем цикле нет обменов

for k := l to SIZE - 1 do

if a[k] > a[k + l] then

begin // обменяем k-й и k+1-й элементы

buf := a[k]; a[k] := a[k + l]; a[k + l] := buf;

changed := TRUE;

end;

// вывод массива

for i := l to SIZE do

Label2.caption := label2.caption + ' ' + IntTostr(a[i]);

Label2.caption := label2.caption + #13;

until

not changed; // если не было обменов, значит

// массив отсортирован

Label2.caption := label2.caption + #13 + 'Maccив отсортирован.';

end;

Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем, возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.

Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение FALSE. Процесс сортировки (цикл repeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (цикл for), ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.

Сортировка массива методом пузырька - медленная, но если скорость не главное, можно применить и его. Алгоритм очень прост - если два соседних элемента расположены не по порядку, то меняем их местами. Так повторяем до тех пор, пока в очередном проходе не сделаем ни одного обмена, т.е. массив будет упорядоченным. Ниже текст процедуры, реализующей алгоритм сортировки методом пузырька (Arr - массив для сортировки с начальным индексом 0, n - размерность массива)

procedure SortPuz (var Arr : array of Integer; n : Integer);

var

i : Integer;

Temp : Integer;

Flag : Boolean;

begin

repeat

Flag := False;

for i := 0 to n - 1 do

if Arr [i ] > Arr [i + 1] then begin

Temp := Arr [i ];

Arr [i ] := Arr [i + 1];

Arr [i + 1] := Temp;

Flag := True;

end;

until Flag = False;

end;

8 Бинарный поиск

Бинарный поиск - поиск исходного сообщения, основанный на проверке четностей чисел (отдельных элементов сообщения).

Исходные данные:

(N,e): параметры открытого ключа алгоритма RSA

C=me

(modN): зашифрованный текст

Механизм чётности - восстановление младшего значащего бита соответствующего исходного текста (решение второй задачи).

Решение:

Поиск осуществляется в интервале (a,b), который называется текущий и обозначается CI. (a,b)=(0,N) - первоначальный. Бинарный поиск обеспечивается утверждением:

Пусть N - нечетное число и xЄ(a,b), то 2x(mod N) является чётным тогда и только тогда, когда x (mod N)Є(0,N/2) И выполняются следующие условия: На каждой итерации интервал CI делится пополам. Искомый исходный текст по-прежнему принадлежит интервалу CI.

Этапы поиска

Итерация. Известно, что исходный текст принадлежит интервалу (a,b)=(0,N). Передадим механизму четности число 2e c(mod N). Заметим, что 2 e c=(2m) e (mod N). Тогда из результата механизма и утверждения следует, что либо mЄ(0, N-N/2), либо mЄ(N/2, N). Таким образом, возникает новый текущий интервал, содержащий исходный текст имеющий вдвое меньшую длину. Итак, на вход итерации поступил интервал (a,b)=(0,N), а на выходе получается один из двух интервалов: (a,b)=(0,N/2) или (a,b)=(N/2,N).

Итерация. Рассмотрим случай (a,b)=(N/2,N). Передадим механизму четности число 2, 2e c=(2 2 m) e (modN). Если ответ равен 0 (М(2 2e c)=0), то 2m=4m(modN) является чётным числом. Получаем, что 2m(modN)Є(0,N/2). Учитывая, что 2m<2N, то неравенство 2m(modN) < N/2 возможно, если 2m<2N - N/2=3N/2. Итак, m<3N/4, mЄ(N/2,3N/4). Обновим текущий интервал, выполнив преобразование (a,b)< (a,b-N/2 2).

Варианты преобразования текущего интервала

Если ответ:0, исходный текст принадлежит левой половине текущего интервала CI=(a,b), а число b следует уменьшить на величину CI/2. Если ответ:1, исходный текст принадлежит правой половине текущего интервала CI = (a,b), число a необходимо увеличить на значение CI/2. Очевидно, что после шагов поиска длина текущего интервала станет меньше единицы: |CI|=b-a<1. В этом случае алгоритм прекращает работу и выдаёт число m=b.

Реализация алгоритма бинарного поиска

1. Выполнить (a,b)< (0,N)

(Пока выполняется условие mЄ(a,b), длина текущего интервала CI=(a,b) на каждой итерации делится пополам.)

2. for i = 1,2,…,[log 2 N]+1 do {

(Длина отрезка (a,b) никогда не превышает число N/2 i-1)

If М(2 2e c)=0 then b< b-N/2i

(число m лежит в левой половине интервала)

Else a< a+ N/2 i

(число m лежит в правой половине интервала)

}

3. retun (b)

Пример: Допустим, что открытым ключом алгоритма RSA является пара (N,e)=(15,3), а зашифрованный текст с =13. Зададим владельцу секретного ключа четыре вопроса и попробуем восстановить секретный текст m. Передадим оракулу следующие запросы:

(2 3 Ч13, 4 3 Ч13, 8 3 Ч13, 16 3 Ч13) =(14,7,11,13)(mod15)

Ответы: 0,1,1,1. На их основе можно сделать следующие выводы.

Первый ответ: 0, mЄ(0, 15-15/2) = (0, 15/2), mЄ[1,7]

Второй ответ: 1, mЄ(0+15/4, 15/2) = (15/4, 15/2), mЄ[4,7]

Третий ответ: 1, mЄ(15/4+15/8, 15/2) = (48/8, 15/2), mЄ[6,7]

Четвёртый ответ: 1, mЄ(48/8+15/16, 15/2) = (48/8, 15/2), mЄ[7,7]

Итак, m=7. Исходным сообщением является число 7.

(73=13(mod15))

Выводы: Итак, доказав, что сложность восстановления отдельного бита исходного сообщения из зашифрованного текста сравнима с расшифровкой всего блока, можно утверждать, что обеспечивается защита битов исходного сообщения. Но стойкость младшего значащего бита в алгоритме RSA означает, что пользователь не должен предоставлять услуги владельца открытого ключа. Следовательно, несмотря на то, что восстановить младший значащий бит так же сложно, как и весь блок, функция шифрования в алгоритме RSA остаётся уязвимой для активной атаки. Исследование битовой стойкости позволило прийти к выводам: каждый отдельный бит исходного текста, скрытый криптографическими функциями, распознать так же сложно, как и весь блок. Если исходное сообщение является случайным, то извлечь информацию об исходном тексте так же трудно, как и вычислить обратную функцию. алгоритм массив операнд бинарный

Заключение

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

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

Список литературы

1. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

2. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. - 360 с.

3. Grama A., Gupta A., Karypis G., Kumar V. Introduction to Parallel Computing, Second Edition. - Addison Wesley, 2003. 856 pp.

4. Легалов А.И. Методы сортировки, полученные из анализа максимально параллельной программы. - Распределенные и кластерные вычисления. Избранные материалы Третьей школы-семинара. / Институт вычислительного моделирования СО РАН. Красноярск, 2004, с. 119-134.

Размещено на Allbest.ru

...