Введение в теорию алгоритмов и структур данных, Бабенко М.А., Левин М.В., 2016

Введение в теорию алгоритмов и структур данных, Бабенко М.А., Левин М.В., 2016.

  В курсе дается краткое изложение классических способов построения и анализа алгоритмов. Первая часть курса, представленная в данном пособии, в большей степени сконцентрирована на базовых структурах данных, а также задачах сортировки и поиска. Теоретический материал дополняется рядом задач.
Несмотря на «олимпиадный» вид, многие из них имеют под собой вполне практическую основу и представляют собой модельные варианты тех проблем, с которыми приходится сталкиваться на практике.
Знания, которые даются в этой книге, представляют собой необходимую (хотя и недостаточную) базу для работы с произвольными данными большого объема, дают понимание о возможности или невозможности точного решения конкретных задач за приемлемое на практике время.




Массивы переменного размера.
Читатель, без сомнения, знаком с понятием массива. Массив — это средство языка C++, а не библиотеки. Библиотека же предлагает более удобный аналог массива, а именно вектор (класс std : : vector). С точки зрения интерфейса ключевое различие между вектором и массивом состоит в том, что массив имеет фиксированный, выбираемый в момент его создания размер, а вектор — напротив, может изменять количество лежащих в нем элементов динамически во время работы. Как же реализуется такая возможность на практике? Вопрос этот не вполне тривиальный, но достаточно простой, чтобы начать изложение материалов курса с него.

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

ОГЛАВЛЕНИЕ.
Предисловие (Елена Бунина).
Глава 1. Введение.
1.1. Массивы переменного размера.
1.2. Анализ учетных стоимостей.
1.3. Задачи.
Глава 2. Сортировка.
2.1. Введение.
2.2. Квадратичная сортировка.
2.3. Оптимальная сортировка, основанная на сравнениях.
2.4. Сортировка слиянием.
2.5. Быстрая сортировка.
2.6. Порядковые статистики.
2.7. Задачи.
Глава 3. Поиск.
3.1. Введение.
3.2. Линейный поиск.
3.3. Бинарный поиск.
3.4. Деревья поиска.
3.5. Сплей-деревья.
3.6. Задачи.
Глава 4. Кучи.
4.1. Приоритетные очереди.
4.2. Бинарные кучи.
4.3. Сортировка кучей.
4.4. k-ичные кучи.
4.5. Сливаемые приоритетные очереди.
4.6. Левацкие кучи.
4.7. Косые кучи.
4.8. Структуры данных с хранением истории.
4.9. Декартовы деревья и дучи.
4.10. Задачи.
Глава 5. Хеширование.
5.1. Прямая адресация.
5.2. Хеш-функции.
5.3. Примеры хеш-функций.
5.4. Вероятностный анализ алгоритмов хеширования.
5.5. Совершенная хеш-функция.
5.6. Фильтр Блюма.
5.7. Задачи.
Глава 6. Системы непересекающихся множеств.
6.1. Постановка задачи.
6.2. Лес непересекающих множеств.
6.3. Дополнительные операции.
6.4. Задачи.
Глава 7. Задачи RMQ и LCA.
7.1. Постановка задачи.
7.2. Динамическая задача RMQ, деревья отрезков.
7.3. Статическая задача RMQ, предобработка.
7.4. Задача LCA, сведение к задаче RMQ.
7.5. Декартово дерево, сведение задачи RMQ к задаче LCA
7.6. Задачи.
Глава 8. Динамическое программирование.
8.1. Наибольшая возрастающая подпоследовательность.
8.2. Перемножение последовательности матриц.
8.3. Общие принципы.
8.4. Сегментация запросов.
Список литературы.

Купить .





Теги: учебник по информатике :: информатика :: компьютеры :: Бабенко :: Левин