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

Очереди с приоритетами

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

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

Читать »

Нотация большого О

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

Пусть f(n)ng (п) являются функциями, которые преобразуют неотрицательные целые числа в действительные. Докажем, что/(п) есть 0(g (п)), если существует действительная константа с > 0 и целочисленная константа по > 1, такие, что/(п) < eg (п) для любого целого числа п > щ. Такое определение функции зачастую называется нотацией большого О, так как иногда говорят, что f(n) является большим О функции g(n). Другими словами, можно сказать, что/(п) есть порядковая функция g(n) (определение показано на рис. 3.4).

Читать »

Производительность AVL-дерева

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

Результаты анализа производительности AVL-дерева выглядят следующим образом. Операции findElement, insertltem и removeElement проходят узлы на пути от корня к листу, добавляя, возможно, и их соседние узлы, и затрачивают на каждый узел 0(1) времени. Таким образом, поскольку высота Г составляет 0(log п), и в соответствии с утверждением 9.2, каждая из этих операций занимает 0(log ri) времени. Детали реализации и анализа операций findAHElements и removeAllElements интересны как упражнения. В табл. 9.2 сведены показатели словаря, реализованного с помощью AVL-дерева. Иллюстрация производительности приводится на рис. 9.12.

Читать »

В-деревья

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

Наиболее известной версией структуры данных (я,6)-дерева для содержания словаря во внешней памяти является В-дерево (см. рис. 9.33). В-дерево порядка d — это (я,6)-дерево, в котором а = \d/2], a b = d. Но поскольку рассматриваются стандартные словарные методы запроса и обновления для (а,6)-дерева, ограничимся изучением 1/О-сложности В-деревьев.

Читать »

Перехват исключений Java

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

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

Читать »

Сегментная сортировка

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

В предыдущем разделе показано, что для выполнения алгоритма сравнительной сортировки последовательности из п элементов максимально требуется Q(n log п) времени. Вполне закономерен вопрос о наличии других алгоритмов, позволяющих работать быстрее, чем за 0(п log п). Известно, что такие алгоритмы существуют, но для них требуются определенные предварительные условия. И даже с учетом этого такие алгоритмы часто используются в практике, и с ними следует ознакомиться. В этом разделе рассматривается проблема сортировки последовательности объектов, каждый из которых является парой «ключ-элемент».

Читать »

Программирование на языке Java

Добавлено Дата: 31 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Читать »

Объектно-ориентированное программирование

Добавлено Дата: 31 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Читать »

Простейшие операции

Добавлено Дата: 31 December, 2011 категория: Java, Структуры данных и алгоритмы

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

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

Читать »

Асимптотическая нотация

Добавлено Дата: 31 December, 2011 категория: Java, Структуры данных и алгоритмы

Очевидно, что анализ времени выполнения такого простого алгоритма, как аггауМах, проведен слишком глубоко. В ходе анализа возникает несколько вопросов:

•    Действительно ли необходим такой уровень детализации?

•          Действительно ли так важно установить точное число простейших операций, выполняемых алгоритмом?

Читать »

Реализация локаторных методов очереди с приоритетами

Добавлено Дата: 30 December, 2011 категория: Java, Структуры данных и алгоритмы

Расширить возможности очереди с приоритетами, реализованной с помощью последовательности или пирамиды, за счет поддержки локаторов не представляет особого труда. В частности, за счет преимущества наследования, помня о том, что последовательность и бинарное дерево являются позиционными контейнерами и могут использоваться для реализации АТД «очередь с приоритетами», можно сортировать пары «ключ-элемент» (объекты) как элементы. Соответственно можно создать локатор, расширив объект «ключ-элемент» из фрагмента кода 7.2 для реализации локатор- ного АТД и добавив позиционную ссылку в качестве переменной экземпляра, как это показано во фрагменте кода 7.9. При таком подходе реализация методов локаторного АТД достаточно проста, и каждая занимает 0(1) времени. Наиболее значимым фактом такой реализации является автома- тическсЪприсоединение локаторов к объектам (по существу, локаторы сохраняют объекты), и необходима отслеживать позиции, в которых размещаются объекты в последовательности или пирамиде.

Читать »

Требования к методологии общего анализа

Добавлено Дата: 30 December, 2011 категория: Java, Структуры данных и алгоритмы

Экспериментальные исследования, безусловно, очень полезны, однако при их проведении существуют три основных ограничения:

•          эксперименты могут проводиться лишь с использованием ограниченного набора исходных данных; результаты, полученные с использованием другого набора, не учитываются;

Читать »

Поддержка локаторов в словаре

Добавлено Дата: 30 December, 2011 категория: Java, Структуры данных и алгоритмы

В словарях, как и в очередях с приоритетами, можно использовать модель проектирования «локатор» (раздел 7.4). В АТД «словарь» локаторы обеспечивают дополнительные возможности как для неупорядоченных, так и для упорядоченных словарей. В неупорядоченном словаре локаторы позволяют методу удаления отказаться от неявного поиска, предоставляя указатель на удаляемый объект. Точно так же в упорядоченном словаре локаторы позволяют обращаться к объектам, расположенным до и после некоторого объекта.

Читать »

Однонаправленные связные списки

Добавлено Дата: 30 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Читать »

Иерархия последовательностей Методы контейнера

Добавлено Дата: 29 December, 2011 категория: Java, Структуры данных и алгоритмы

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

Читать »