Главная » Структуры данных и алгоритмы

Рандомизированная быстрая сортировка

Добавлено Дата: 28 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

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

Добавлено Дата: 28 January, 2012 категория: Java, Структуры данных и алгоритмы

Предположим, что при реализации последовательности время каждого обращения и перемещения элементов, выполняемых сортирующим алгоритмом, составляет 0(1). Таким образом, время выполнения /-го обхода равно 0(п — / + 1). Значит, общее время выполнения алгоритма пузырьковой сортировки составляет

Читать »

Алгоритмы шаблонного сопоставления Алгоритм Кнута-Морриса-Пратта

Добавлено Дата: 28 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Поиск в ширину для графа

Добавлено Дата: 27 January, 2012 категория: Java, Структуры данных и алгоритмы

В этом разделе рассматривается алгоритм поиска в ширину (breadth-first search — BFS). Как и в случае с поиском в глубину (DFS), поиск в ширину обходит связные компоненты графа и в процессе этого обхода определяет соответствующее остовное дерево. При этом поиск в ширину более предсказуем, чем поиск в глубину. Вместо путешествий по лабиринту графа BFS выполняет круговые обходы и распределяет узлы по уровням. BFS также можно рассматривать как поход с нитью и баллончиком краски, только в этом случае используется более консервативный способ разматывания нити.

Читать »

Генерация исключений Java

Добавлено Дата: 27 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Принципы объектно-ориентированного программирования

Добавлено Дата: 26 January, 2012 категория: Java, Структуры данных и алгоритмы

Основными принципами объектно-ориентированного программирования, которые обеспечивают достижение вышеперечисленных целей, являются (рис. 2.2):

•            абстракция,

•            инкапсуляция,

Читать »

(2,4)-деревья

Добавлено Дата: 26 January, 2012 категория: Java, Структуры данных и алгоритмы

Многопроходные поисковые деревья, обеспечивающие небольшие размеры вторичных структур данных в каждом узле и сбалансированность первичного многопроходного дерева, называются ми, иногда 2—4 или 2-3-4-деревьями. Такая структура данных реализует поставленные цели при наличии всего двух простых свойств (см. рис. 9.14):

Читать »

Абстрактный тип данных «вектор»

Добавлено Дата: 26 January, 2012 категория: Java, Структуры данных и алгоритмы

Вектор S является абстрактным типом данных (АТД), который поддерживает следующие основные методы:

elemAtRank (г): возвращает элемент S с. разрядом г; если г < 0 или г > п – 1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число; Output: объект.

Читать »

Взвешенные графы

Добавлено Дата: 26 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Быстрая сортировка

Добавлено Дата: 25 January, 2012 категория: Java, Структуры данных и алгоритмы

Следующим сортировочным алгоритмом, приводимым ниже, будет быстрая сортировка (quick-sort). Этот алгоритм также основан на принципе «разделяй и властвуй», но применяет его методику в обратном порядке, так как вся основная работа выполняется в начале, до рекурсивного вызова.                                                                                                                    ‘

Читать »

Внешний поиск

Добавлено Дата: 25 January, 2012 категория: Java, Структуры данных и алгоритмы

В этом разделе рассматривается проблема реализации упорядоченного словаря для большого количества объектов, не помещающихся в основной памяти. Одним из наиболее распространенных применений больших словарей является система баз данных. Когда данные не помещаются в основной памяти, они хранятся во внешней памяти (external memory), которой обычно служит жесткий диск. Время доступа к информации значительно выше времени ее передачи, поэтому объекты сгруппированы в смежные секции, называемые блоками, дисковыми блоками (disc blocks). Аналогично назовем процесс передачи блоков между внешней и основной памятью дисковой передачей (disk transfer). Но и при использовании этой терминологии приведенные методики поиска применимы и в случаях, когда основной памятью является кэш центрального процессора, а в качестве внешней рассматривается основная (RAM) память, так как строки кэша также группируются в блоки.

Читать »

Словари

Добавлено Дата: 25 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

Хеш-таблицы примеры применения

Добавлено Дата: 25 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Читать »

«Родственники» большого О

Добавлено Дата: 24 January, 2012 категория: Java, Структуры данных и алгоритмы

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

Пусть f{n)wg (п) — функции, которые преобразуют целые числа в реальные числа. Покажем, что/(п) есть Q(g(n)) (говорят, что/(п) есть большая омега g(n), если g(n) есть О (f (п)), то есть существует действительная константа с > 0 и целая константа щ > 1, такие, что/(п) > eg (п) для п > щ. Такое определение позволяет асимптотически утверждать, что одна функция больше или равна другой функции до постоянного множителя. Аналогично можно утверждать, что /(п) есть Q(g(ri)) (говорят, что «/(п) есть большая тета g (п)»), если/(п) есть 0(g (п)) и/(п) есть Q(g(n)), то есть существуют действительные константы с’ > 0 и с" > 0, а также целая константа по > 1, такие, что c’g(ri) < f(n) < c"g(n) для п > Такое определение позволяет утверждать, что две функции асимптотически равны до постоянного множителя. Ниже приводится несколько примеров подобных нотаций.

Читать »

Остовное дерево наименьшего размера

Добавлено Дата: 24 January, 2012 категория: Java, Структуры данных и алгоритмы

Предположим, требуется объединить компьютеры в новом офисном здании, расходуя наименьшее количество кабеля. Такая задача моделируется с помощью взвешенного графа G, узлы которого будут представлять компьютеры, а пути — возможные пары компьютеров (w,v), где вес w(v,u) пути (v,u) равен длине кабеля, необходимого для соединения компьютера v с компьютером и. Вместо вычисления кратчайшего пути из некоторого узла v создадим (свободное) дерево Т, содержащее все узлы G и имеющее наименьший общий вес по сравнению с любым другим деревом.

Читать »