Структуры и алгоритмы обработки данных

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

Во второй главе подробно изложены типовые структуры данных для представления множеств: массивы, динамические списковые структуры, стеки, очереди и деревья. Для динамических структур приводятся алгоритмы операций включения и исключения элементов, а для деревьев — стандартные способы систематического обхода вершин (прохождения деревьев). Рассматриваются такие характеристики деревьев, как высота, уровни вершин, длины внутренних и внешних путей.

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