Структуры данных и модели вычислений

Классы функций, используемые для оценки сложности алгоритмов
Амортизационный анализ

Амортизационный анализ работы двоичного счетчика

Структуры данных и модели вычислений

Общие сведения о списках

Списки с прямым доступом


Списки с последовательным доступом
Некоторые дополнительные операции со связными списками
Моделирование списков с последовательным доступом при помощи массивов
Деревья и графы

Структуры данных и модели вычислений

Операции над разделенными множествами
Примеры использования разделенных множеств

Представление разделенных множеств с помощью массива
Реализация операций с помощью массива
Представление разделенных множеств древовидной структурой
Реализация операций с помощью древовидной структуры
Представление разделенных множеств с использованием рангов вершин
Реализация операций с использованием рангов вершин
Анализ трудоемкости
Сводные данные о сложности операций с разделенными множествами

Структуры данных и модели вычислений

Основные определения
Представление приоритетной очереди с помощью d-кучи
Операции с d-кучей
Применение приоритетных очередей в задаче сортировки

Бесхитростная сортировка в памяти с прямым доступом.
Сортировка методом "разделяй и властвуй".
Сортировка "слиянием".
Сортировка с помощью d-кучи.
Нахождение кратчайших путей в графе
Алгоритм Дейкстры

Структуры данных и модели вычислений

Левосторонние кучи
Свойства левостороннего дерева
Операции с левосторонними кучами
Сводные данные о трудоемкости операций с левосторонними кучами

Структуры данных и модели вычислений

Ленивая левосторонняя куча
Сводные данные о трудоемкости операций с ленивыми левосторонними кучами
Самоорганизующаяся куча
Сводные данные о трудоемкости операций с самоорганизующимися кучами

Структуры данных и модели вычислений

Биномиальные кучи
Свойства биномиальных деревьев

Фибоначчиевы кучи

Структуры данных и модели вычислений

Основные определения
Представление тонкой кучи в памяти компьютера.
Реализация основных операций и оценки трудоемкости

Структуры данных и модели вычислений

Избыточное представление чисел
Толстые деревья
Толстая куча
Вспомогательные структуры
Вспомогательные процедуры
Основные операции

Структуры данных и модели вычислений

Общие сведения
Представление двоичных деревьев поиска
Операции с двоичным поисковым деревом
Добавление элемента.
Удаление элемента
Упражнения
Случайные двоичные деревья поиска
Красно-черные деревья
Комбинаторные свойства красно-черных деревьев
Упражнения

Упражнения
АВЛ-деревья
Упражнения
Б-деревья
Особенности работы с информацией, размещаемой на диске

Структуры данных и модели вычислений

Исторические сведения

Тьюрингова модель переработки информации
Алгебра тьюринговых программ
Начальное математическое обеспечение
Методика доказательства правильности программ
Вычислимость и разрешимость
Вычисление числовых функций
Частично-рекурсивные функции

Универсальная тьюрингова программа и пример невычислимой функции
Об измерении алгоритмической сложности задач

Структуры данных и модели вычислений

Абак
Примеры неразрешимости
Алгорифмы Маркова

Равнодоступная адресная машина

Структуры данных и модели вычислений

Основные понятия и обозначения
Способы задания формальных языков
Регулярные выражения

Решение уравнений в словах
Автоматное задание языков
Применение конечных автоматов в программировании

Структуры данных и модели вычислений

Язык предикатов
Некоторые сведения из математической логики
Элементы языка Пролог

Содержание раздела

---