Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Реферат - Структуры данных и алгоритмы - файл 1.docx


Реферат - Структуры данных и алгоритмы
скачать (43.6 kb.)

Доступные файлы (1):

1.docx44kb.04.12.2011 00:24скачать

содержание

1.docx

Содержание

 2

1 «Жадные» алгоритмы 3

 8

2 Практическая часть 9

 11

Библиографический список 12




1 «Жадные» алгоритмы


Алгоритмы, предназначенные для решения задач оптимизации, обычно представляют собой последовательность шагов, на каждом из которых предоставляется некоторое множество выборов. Определение наилучшего выбора, руководствуясь принципами динамического программирования, во многих задачах оптимизации напоминает стрельбу из пушки по воробьям; другими словами, для этих задач лучше подходят более простые и эффективные алгоритмы. В жадном алгоритме (greedy algorithm) всегда делается выбор, который кажется самым лучшим в данный момент — т.е. производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи. Жадные алгоритмы не всегда приводят к оптимальному решению, но во многих задачах они дают нужный результат.

^ Элементы жадной стратегии

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

Процесс разработки жадных алгоритмов можно описать в виде последовательности следующих этапов:

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

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

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

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

В основе каждого жадного алгоритма почти всегда находится более сложное решение в стиле динамического программирования.

^ Свойство жадного выбора

Свойство жадного выбора: глобальное оптимальное решение можно получить, делая локальный оптимальный (жадный) выбор. Другими словами, рассуждая по поводу того, какой выбор следует сделать, мы делаем выбор, который кажется самым лучшим в текущей задаче; результаты возникающих подзадач при этом не рассматриваются.

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

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

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

^ Оптимальная подструктура

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

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

^ Алгоритм Хаффмена

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

  1. Однозначно расшифровывалась;

  2. Имела минимальную длину.

Для первого условия достаточно выбрать различные кодовые слова одинаковой длины. Например, двоичными последовательностями длины 7 можно зашифровать 27=128 различных символов. Тогда текст из 1000 символов всегда будет иметь длину 7000. Эту длину можно уменьшить. Если использовать последовательности длины 6, то длина текста уменьшится до 6000 символов, однако алфавит станет вдвое меньше и его не хватит, 

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

Другой путь состоит в том, чтобы использовать короткие последовательности для обозначения часто используемых символов и длинные – для редко используемых. Тогда возникает другая проблема – как отделить символы друг от друга. Это можно сделать по-разному. Один из способов состоит в том, чтобы длинные последовательности, кодирующие одни буквы, не начинались с более коротких последовательностей, кодирующих другие. Коды с таким свойством называются префиксными.

Если бы в нашем алфавите было только две буквы «а» и «б», то построить такой код было бы просто, кодируя «а» нулем, «б» единицей. Если наш алфавит состоит из трех букв «а», «б», «в», то, зашифровав «а» нулем, коды для других букв придется начать с единицы: 10 и 11. Тогда любая правильная двоичная последовательность однозначно расшифруется, например, 1000101011 как «бааббв».

При кодировании символов последовательностями разной длины возникает возможность оптимизировать суммарную длину кода. Для этого надо знать частоту, с которой встречаются буквы. ( Заметим, что для кодирования алфавита из двух букв частота не имеет значения, так как длина кода каждой буквы равна 1). Например, если «а» встречается вдвое чаще, чем «б» и «в», а последние встречаются поровну, то в среднем на текст из 1000 букв понадобится 1500 двоичных цифр. Если бы мы зашифровали буквы по другому, например, «в» - 0, «б» - 10, «а» - 11, то длина кода на каждые 1000 букв в среднем равнялась бы 1750.

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

Теперь можно сформулировать сам алгоритм Хаффмена.



Его первая часть сводит задачу к задаче кодирования алфавита с двумя символами.

^ ПОКА в алфавите не остались две буквы

  1. Упорядочить буквы в порядке убывания частот;

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

^ КОНЕЦ ЦИКЛА

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

^ Упорядочить буквы в порядке убывания частот

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

^ КОНЕЦ ЦИКЛА

Вторая часть алгоритма осуществляет кодирование:

Сопоставить первой букве код 0, второй – код 1

ПОКА не все исходные буквы получили двоичные коды

^ ЕСЛИ буква получена слиянием двух других, сопоставить им коды, полученные добавлением 0 или 1 к коду расщепляемой буквы.

КОНЕЦ ЕСЛИ

КОНЕЦ ЦИКЛА
^



2 Практическая часть


Задача

Дан неупорядоченный массив целых чисел размером N. Рассчитать вычислительную сложность алгоритма для заданного метода сортировки для N=5. Метод сортировки – сортировка вставками.

Решение

^ Сортировка вставками

Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка A = 50, 20, 40, 75, 35 (рисунок 1).

Рисунок 1 – Процесс сортировки вставками

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

первую последовательность так, чтобы она оставалась отсортированной. Поиск места вставки осуществляют с конца, сравнивая вставляемый элемент аi с очередным элементом отсортированной последовательности aj. Если элемент ai больше aj, его вставляют вместо aj+1, иначе сдвигают aj вправо и уменьшают j на единицу. Поиск места вставки завершают, если элемент вставлен или достигнут левый конец массива. В последнем случае элемент ai вставляют на первое место.

^ Вычислительная сложность сортировки вставками

Сортировка вставками требует фиксированного числа проходов. На n-1 проходах вставляются элементы от A[1] до A[n-1]. На i-ом проходе вставки производятся в подсписок A[0]–A[i] и требуют в среднем i/2 сравнений. Общее число сравнений равно 1/2 + 2/2 + 3/2 + ... + (n-2)/2 + (n-1)/2 = n(n-1)/4.

В отличие от других методов, сортировка вставками не использует обмены. Сложность алгоритма измеряется числом сравнений и равна O(n2). Наилучший случай – когда исходный список уже отсортирован. Тогда на i-ом проходе вставка производится в точке A[i], а общее число сравнений равно n-1, т.е. сложность составляет O(n). Наихудший случай возникает, когда список отсортирован по убыванию. Тогда каждая вставка происходит в точке A[0] и требует i сравнений. Общее число сравнений равно n(n-1)/2, т.е. вычислительная сложность алгоритма составляет O(n2).

Таким образом, при N=5 вычислительная сложность алгоритма для сортировки вставками будет равна:

  1. В лучшем случае – 5;

  2. В худшем случае – 25.


^



Библиографический список


1 Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. – М.: Издательский дом «Вильямс», 2010. - 1296 с.

2 Новиков Ф.А., Поздняков С.Н. Компьютерные инструменты в образовании, №2. – Заочная школа современного программирования, 2005. – 58с.

3 Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. : Уч. пос. – М.: Издательский дом «Вильямс», 2000. – 384с.

4 http://www.okcode.ru/ - записки о программировании.

5 http://www.rsdn.ru/ - русскоязычный сайт, посвященный программированию.





Скачать файл (43.6 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации