Что и где я могу найти в книге, или, другими словами, из чего состоит эта книга?

Что и где я могу найти в книге, или, другими словами, из чего состоит эта книга?

Книга состоит из двенадцати глав и списка использованной литературы.

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

Глава 2 покрывает практически все основные вопросы, связанные с массивами. Мы посмотрим на стандартную языковую поддержку массивов, в том числе и динамических массивов, обсудим достоинства, недостатки и методику применения класса TList, а затем разработаем класс, инкапсулирующий в себе массив записей. Ввиду того, что строка, как структура данных, также представляет собой массив, мы кратко коснемся и ее.

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

Глава 4 представляет собой введение в алгоритмы поиска, в особенности, в алгоритмы последовательного и бинарного поиска. Будет показано, как при помощи бинарного поиска осуществлять вставку элементов в сортированные массивы и связные списки.

Глава 5 посвящена алгоритмам сортировки. Мы посмотрим на различные методы сортировки: пузырьковую и шейкер-сортировку, сортировку выбором и простыми вставками, сортировку методом Шелла, быструю сортировку и сортировку слиянием. Алгоритмы сортировки будут применяться в отношении к массивам и связным спискам.

В главе 6 обсуждаются алгоритмы, которые генерируют или требуют для своего функционирования случайные числа. Будут рассмотрены различные реализации генераторов псевдослучайных чисел, а также сортированной структуры данных с возможностью пометки, именуемой списком с пропусками, в которой для поддержания сбалансированного состояния используется генератор псевдослучайных чисел.

Глава 7 вводит понятия хеширования и хеш-таблиц, включая их базовые определения, области и причины применения, а также связанные с ними достоинства и недостатки. Рассматривается множество стандартных алгоритмов хеширования. Одной из проблем, которые возникают при использовании хеш-таблиц, является так называемый конфликт, или коллизия. Мы посмотрим, как разрешать коллизии при помощи разнообразных видов зондирования и связывания.

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

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

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

Глава 11 сконцентрирована вокруг нескольких технологий сжатия. Подробно рассматриваются такие алгоритмы сжатия, как Шеннона-Фано, Хаффмана, с применением скошенного дерева и LZ77.

В главу 12 включено несколько дополнительных сложных тем, которые смогут удовлетворить аппетит даже самых искушенных программистов, склонных к исследованию алгоритмов и структур данных. Глава принесет несомненную пользу также и рядовым программистам.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Расстояние между словами

Из книги автора

Расстояние между словами Можно задать расстояние как между буквами, так и между словами, используя свойство word-spacing. В качестве значения вы можете указать желаемое значение либо normal, чтобы использовать значение браузера по умолчанию.Это свойство не представляет


(6.18) Как заставить W2k принимать входящие звонки? В Win9x был Сервер удаленного доступа, а под W2k не могу найти ничего подобного.

Из книги автора

(6.18) Как заставить W2k принимать входящие звонки? В Win9x был Сервер удаленного доступа, а под W2k не могу найти ничего подобного. Заходим в меню Пуск (Start)?Панель Управления (Control Panel)?Сеть и удаленный доступ к сети (Network and Dial-up Connections)?Файл (File)?Hовое подключение (Make New Connection)?Принимать


1.19. Что случилось с regedit32.exe? Никак не могу его найти.

Из книги автора

1.19. Что случилось с regedit32.exe? Никак не могу его найти. Этой полезной и привычной многим пользователям NT утилитки больше не существует. Все функции, которые когда то можно было выполнить только с её помощью, теперь доступны и в простом Regedit.


Из чего состоит сайт

Из книги автора

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


Из чего состоит и как работает программа

Из книги автора

Из чего состоит и как работает программа Программа Radmin состоит из двух частей: серверной и клиентской. Серверная часть не имеет своего окна и для нас практически не заметна, однако реально существует и играет очень важную роль. Это отдельная программа, которая


Глава 1. Из чего состоит система увеличения продаж интернет-магазина

Из книги автора

Глава 1. Из чего состоит система увеличения продаж интернет-магазина Для большинства владельцев интернет-магазинов продажи – «черный ящик». Представление о взаимосвязи между прилагаемыми усилиями и итоговой прибылью в большинстве случаев есть лишь на интуитивном


Из чего, собственно, состоит порт для FreeBSD?

Из книги автора

Из чего, собственно, состоит порт для FreeBSD? Порт для FreeBSD состоит из нескольких файлов, которые сами по себе ничего не делают. Даже несмотря на то, что один из них называется Makefile, все они представляют из себя файлы данных - описания и определения некоторых переменных,


Пользуйтесь обычными словами

Из книги автора

Пользуйтесь обычными словами Вставьте настоящий текст вместо lorem ipsumСлова lorem ipsum dolor — признанные друзья дизайнеров. Текст-пустышка помогает понять, как будет выглядеть дизайн, когда он будет воплощен. Но текст-пустышка может быть опасным.Lorem ipsum меняет ваш взгляд на


Для чего и для кого написана эта книга

Из книги автора

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


Из чего состоит нетбук?

Из книги автора

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


1.3. Системный блок: из чего состоит и кто за что в нем отвечает

Из книги автора

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


Из чего состоит трафик Fidonet

Из книги автора

Из чего состоит трафик Fidonet Основными видами информации, которой обмениваются между собой узлы Fidonet, являются:? личная почта, или нетмэйл (Netmail);? эхоконференции, или эхомэйл (Echomail);? файловые эхоконференции.Стандарты на представление и передачу этих видов информации


Глава 3 Из чего состоит ноутбук

Из книги автора

Глава 3 Из чего состоит ноутбук • Процессор• Оперативная память• Чипсет• Видеокарта• Жесткий диск• Оптический привод• Экран• Сети• Устройства ввода• ОстальноеНеопытный пользователь рассматривает компьютер как очень сложное устройство, которое запросто


Из чего состоит компьютер

Из книги автора

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