Род Стивенс

Книги → Delphi. Готовые алгоритмы → Введение

Содержание глав

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

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

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

Глава 4 посвящена специальным типам массивов. Треугольные, неправильные и разреженные массивы позволяют использовать удобные представления данных для экономии памяти.

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

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

 

 

В главе 7 затронута более широкая тема. Сбалансированные деревья обла­дают некоторыми свойствами, которые позволяют им оставаться уравновешен­ными и эффективными. Алгоритмы сбалансированных деревьев просто описать, но довольно трудно реализовать в программе. В этой главе для построения слож­ной базы данных используется одна из наиболее мощных структур - Б+ дерево.

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

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

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.