swinggoodru

Автор: Роберт Седжвик, Кевин Уэйн Год: 2013 ISBN: 978-5-8459-1781-2 Страниц: 848 Язык: Русский Формат: PDF Размер: 56 Мб Книга Седжвика и Уэйна «Алгоритмы на Java» является классическим справочным руководством в котором содержится необходимый объем знаний для программиста в области алгоритмов, накопленных за последние несколько десятилетий В книге «Алгоритмы на Java» представлен широкий спектр рассматриваемых тем: исчерпывающее толкование структур данных и алгоритмов сортировки, поиска, обработки графов и строк, включая пятьдесят алгоритмов, которые должен знать каждый программист. Описываются новые реализации алгоритмов на Java, написанные в ясном модульном стиле, при котором весь код доступен читателю и полностью готов к использованию. В книге изучение алгоритмов на Java ведется в контексте важнейших научных, инженерных и коммерческих приложений. Клиенты и алгоритмы выражены с помощью реального кода, а не псевдокода, как во многих других книгах. Книга «Алгоритмы на Java» отличается от множества других ясным и кратким текстом, детальными примерами с иллюстрациями, тщательно подобранным кодом, историческим и научным контекстом, а также упражнениями для самостоятельной проработки на всех уровнях. В книге представлены точные соображения относительно производительности, поддерживаемые соответствующими математическими моделями и эмпирическими исследованиями, которые подтверждают достоверность этих моделей. О сновные понятия 1.1.

1. Роберт Седжвик Алгоритмы На Java Скачать

Базовая модель программирования 1.2. Абстракция данных 1.3. Контейнеры, очереди и стеки 1.4.

Купить книгу Алгоритмы на Java по выгодным ценам оптом и в розницу вы. Роберт Седжвик —. Роберт Седжвик Фундаментальные алгоритмы на JAVA. Структуры данных. Поиск, цена 208 грн., купить в Харькове. Книги Программирование Java Роберт Седжвик, Кевин Уэйн - Алгоритмы на Java Роберт Седжвик.

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

Раздел 1.1 содержит сводку по конструкциям и компонентам языка и библиотекам, ко­торые используются в данной книге. Потом мы рассмотрим абстракцию данных и определим абстрактные типы данных (АТД), которые делают возможным модульное программирование. В разделе 1.2 мы по­знакомимся с процессом реализации АТД на Java с помощью интерфейса прикладного программирования (applications programming interface — API), а затем воспользуемся меха­низмом классов Java для разработки реализации, которая может использоваться в кли­ентском коде. После этого в качестве важных и полезных примеров мы рассмотрим три фундамен­тальных АТД: контейнер, очередьи стек.

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

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

Мы исследуем в книге свойства многих структур данных, так что саму книгу можно было бы назвать “Алгоритмы и структуры данных”. Когда мы используем компьютер для решения задач, то обычно сталкиваемся с не­сколькими возможными подходами. Для небольших задач почти нет разницы, какой из подходов использовать, если они все правильно решают задачу. Однако в случае боль­ших задач (или в приложениях, где требуется решать много маленьких задач) быстро осознается необходимость методов, которые эффективно используют время и память. Основной причиной изучения алгоритмов является то, что эта дисциплина в прин­ципе позволяет значительно экономить ресурсы — вплоть до того, что становится воз­можным выполнять задачи, которые иначе были бы недоступны.

В приложении, которое обрабатывает миллионы объектов, совсем не редкость ускорение работы в миллионы раз с помощью отточенного алгоритма. Мы неоднократно встретимся с такими примерами на протяжении книги. А вложение дополнительных денег или усилий на приобретение и установку нового компьютера может ускорить работу программы раз в 10 или, скажем, в 100. Тщательная разработка алгоритма — невероятно эффективная часть процесса реше­ния большой задачи в любой прикладной области. При разработке большой или сложной компьютерной программы следует потра­тить много усилий на понимание и четкое определение решаемой задачи, управление ее сложностью и разложение на меньшие подзадачи, которые несложно реализовать.

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

Мы изучаем фундаментальные алгоритмы, которые позволяют решать сложные задачи в широком диапазоне прикладных областей. Использование чужих разработок в компьютерных системах постоянно ширится, поэтому следует ожидать не только того, что нам придется использовать значительную часть алгоритмов из этой книги, но и того, что реализовывать придется лишь неболь­шую их часть. Например, библиотеки Java содержат реализации огромного количества фундаментальных алгоритмов. Однако реализация простых вариантов базовых алгорит­мов поможет нам лучше понять их и поэтому более эффективно использовать, а также осмысленно настраивать сложные версии из библиотек. И, что более важно, зачастую возникает необходимость в самостоятельной реализации базовых алгоритмов. Обычно такая необходимость возникает, если приходится начинать работу в новых вычислительных средах (как аппаратных, так и программных) с новыми возможностями, которые не учитываются в старых реализациях. В данной книге в основном описываются наиболее простые и разумные реализации наилучших алгоритмов.

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

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

Другие алгоритмы взяты из более сложных тем вы­числительной техники и связанных с ними областей. Рассматриваемые нами алгорит­мы являются результатом десятилетий исследований и разработок, и они продолжают играть важную роль в постоянно растущем применении компьютерных вычислений. Основные понятия (глава 1) в контексте данной книги — это методология и базовые принципы, которые мы будем использовать для реализации, анализа и сравнения алго­ритмов. Мы рассмотрим нашу модель программирования на Java, абстракцию данных, базовые структуры данных, абстрактные типы данных для коллекций данных, методы анализа производительности алгоритмов и учебный пример. Сортировка (глава 2). Алгоритмы для упорядочивания массивов имеют фундамен­тальную важность. Мы довольно глубоко рассмотрим множество алгоритмов: сортиров­ка вставками, сортировка выбором, сортировка Шелла, быстрая сортировка, сортировка слиянием и пирамидальная сортировка.

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

Мы рассмотрим простые и более сложные методы поиска: двоичные деревья поиска, сбалансированные деревья поиска и хеширование, изучим взаимосвязи этих методов и сравним их произ­водительность. Графы (глава 4) — это наборы объектов и связей между ними, возможно, с весами и ориентацией этих связей. Графы представляют собой удобные модели для огромно­го количества сложных и важных задач, и разработка алгоритмов для обработки графов является одной из основных областей изучения. Мы рассмотрим поиск в глубину, по­иск в ширину, задачи связности и несколько других алгоритмов и приложений: алгорит­мы Крускала и Прима для поиска минимального остовного дерева, а также алгоритмы Дейкстры и Веллмана-Форда для определения кратчайших путей. Строки(глава 5) — важный тип данных в современных вычислительных приложени­ях.

Мы рассмотрим ряд методов для обработки последовательностей символов. Сначала это будут более быстрые алгоритмы для сортировки и поиска в случае, когда ключи представляют собой строки. Затем мы рассмотрим поиск подстрок, сравнение с шабло­нами регулярных выражений и алгоритмы сжатия данных.

Здесь также будет изложено краткое введение в более сложные темы на примере разбора некоторых элементарных задач, которые важны сами по себе. Контекст (глава 6) поможет связать материал, изложенный в книге, с нескольки­ми другими продвинутыми областями изучения: научные вычисления, исследование операций и теория вычислений.

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

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

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

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

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

Описываемая здесь модель — это та же модель, что и представленная в книге An Introduction to Programming in Java: An Interdisciplinary Approach (Addison Wesley, 2007 г.), но там она изложена более развернуто. 1.1.1 приведен пример полной Java-программы, которая иллюстрирует мно­гие основные черты нашей модели программирования.

Мы используем этот код про­сто для обсуждения свойств языка, а его смысл будет описан позже (в нем реализован классический алгоритм, известный как бинарный поиск, и он проверяется в приложении, которое называется фильтрацией по белому списку). Мы предполагаем, что вы имеете опыт программирования на каком-то современном языке, так что вы, видимо, сразу уз­наете многие его черты в данном коде.

В пояснениях приведены ссылки на страницы, которые помогут вам быстро найти ответы на возможные вопросы. Наш код оформлен в определенном стиле, и мы будем стараться придерживаться его в использовании различ­ных идиом и конструкций языка Java, поэтому даже опытным программистам на Java рекомендуется внимательно прочитать данный раздел. Базовая структура Java-программы Java-программа (класс) — это либо библиотека статических методов(функций), либо определение типа данных.Для создания библиотек статических методов и определений типов данных мы используем следующие семь компонентов, которые составляют фунда­мент программирования на Java и многих других современных языках. Примитивные типы данных в точности определяют в компьютерной программе значение таких терминов, как целое число, вещественное число и логическое значе­ние. В определение входят набор возможных значений и операции с этими значениями, которые можно объединять для получения выражений — например, мате­матических выражений, которые определяют значения. Операторы позволяют определять вычисления с помощью создания значений и присваивания их переменным, управлять потоком выполнения или вызывать по­бочные эффекты. Мы будем использовать шесть типов операторов: объявления, присваивания, условные операторы, циклы, вызовы и возвраты.

Массивы позволяют работать с несколькими значениями одного типа. Статические методы позволяют обособить и повторно использовать код и разра­батывать программы в виде набора независимых модулей. Строки представляют собой последовательности символов. Некоторые операции над ними встроены в Java. Ввод-вывод позволяет программам взаимодействовать с внешним миром.

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

Для ясности и краткости мы будем описывать такие действия в терминах виртуального терминала, где мы взаимодействуем с программами, вводя команды в систему. На сайте книги содержится информация об использо­вании виртуального терминала в вашей системе и о многих продвинутых средах разра­ботки ПО, доступных в современных системах. Например, класс BinarySearch на рис. 1.1.1 содержит два статических метода: rank и main. Первый статический метод, rank, состоит из четырех операторов: двух объявлений, цикла (который сам содержит присваивание и два условных операто­ра) и возврата.

Второй метод, main, состоит из трех операторов: объявления, вызова метода и цикла (который содержит присваивание и условный оператор). Чтобы вызвать Java-программу, ее вначале нужно скомпилировать с помощью коман­ды javac, а затем запустить (или выполнить) с помощью команды java. Например, для выполнения класса BinarySearch потребуется ввести команду javac BinarySearch.java (которая создает файл BinarySearch. Class с низкоуровневой вер­сией Java-программы — байт-код Java).

Роберт Седжвик Алгоритмы На Java Скачать

После этого необходимо ввести команду java BinarySearch (с последующим именем файла) для передачи управления этой байтовой версии программы. Теперь, чтобы образовать прочный фундамент, который позволит разобраться в эффекте этих действий, нам нужно подробно рассмотреть примитивные типы данных и выражения, различные операторы языка Java, массивы, статические ме­тоды строки и ввод-вывод.