Алгоритмы и структуры данных Зайцев Валентин Евгеньевич

АиСД: фундаментальное алгоритмическое введение A1 Деревья. Типичные примеры применения деревьев: задачи искусственного интеллекта и синтаксического анализа. Рекурсивное определение дерева. Конструктивное поуровневое построение. Нелинейность рекурсии. Противопоставление рекурсивному определению линейных структур. Теоретико-множественный и топологический подходы к определению деревьев. Деревья общего вида (сильноветвящиеся). Особенности генеалогических, династических и турнирных деревьев. Визуализация деревьев: графовая, диаграммы Эйлера-Венна, иерархические скобочные структуры, многоуровневая ступенчатая запись. Пример текстового описания дерева на LaTeX (макропакет PSTricks). Матрицы смежности и инциденций. Натурное моделирование (каркасно-проволочные модели). Терминология деревьев общего вида: элементы (узлы, вершины), степень узла и дерева, листы и внутренние (нетерминальные) вершины, уровень узла (рекурсивное определение), глубина вершины и дерева (рекурсивное определение), отец-сын, предок-потомок, братья, дочерняя вершина, страшинство сыновей.

АиСД: фундаментальное алгоритмическое введение A2 Двоичные деревья. Определение. Отличия двоичных деревьев и деревьев общего вида. Особенности визуализации двоичных деревьев. Причины частого использования двоичных деревьев: простота хранения и обработки. Выражения. Примеры из арифметики, логики, информатики. Нелинейность и рекурсивность выражений. Деревья выражений. Фон Неймановская причина их бинарности. Бесскобочность представления выражений деревьями. Фон Неймановская нежелательность скобочных структур. Преобразование деревьев общего вида в двоичные деревья. Идея и илюстрация. Рекурсивный алгоритм с построением каскада сыновей. Обратное преобразование. Доказательство индукцией по глубине дерева. Концептуальное значение алгоритма как конструктивного доказательства эквивалентности двух подходов к определению деревьев. Функциональная спецификация двоичного дерева. Соотношения и их свойства. Логическое описание двоичного дерева. Причины отсутствия стандартных реализаций деревьев в STL. Альтернативы: Лисп, Пролог, динамические структуры на фон Неймановских языках программирования.

АиСД: фундаментальное алгоритмическое введение A3 Описание типа данных для реализации двоичных деревьев на динамических структурах. Графическая иллюстрация. Алгоритмы обработки деревьев. Понятие обхода дерева. Важность обхода для нелинейных структур. Рекурсивные алгоритмы обхода двоичных деревьев: прямой обход, обратный обход, концевой обход. Псевдокод. Графическая иллюстрация. Нерекурсивный обход: использование стека для отражения текущего положения в дереве. Сравнение с рекурсивным алгоритмом. Пример программы нерекурсивного обхода. Построение и визуализация дерева. Псевдокод. Трудности ввода. Распечатка дерева: ASCII-визуализация с отступами. Деревья выражений. Разнофиксные формы записи выражений: префиксная, инфиксная, постфиксная и их связь с обходами деревьев выражений. Фон Неймановские преимущества бесскобочной записи. Пример: псевдокод программы построения и распечатки дерева выражения по его линейной скобочной (инфиксной записи). Особенности примера: упрощённые арифметические выражения, рекурсивно-итеративная интерпретация при удалении распечатанного дерева. Полурекурсивная версия: сочетание рекурсивного спуска направо с итеративной обработкой слева.

АиСД: фундаментальное алгоритмическое введение A4 Реализация парсера по грамматике. Другой пример: преобразование выражения из инфиксной формы в постфиксную. Нерекурсивная версия. Особенности представления и обхода деревьев общего вида. Поиск в глубину и поиск в ширину. Псевдокод. Деревья поиска. Идея. Логарифмическая оценка времени поиска. Псевдокод. Упрощение поиска с помощью барьерного элемента. Гамак как вариант терминированного представления дерева. Недостаток барьерного метода: усложнение более редких процедур вставки и удаления. Поиск по дереву с включениями. Псевдокод. Дерево поиска для предыдущего примера. Модификация схемы хранения для одинаковых элементов. Соблюдение хронологии. Характерный пример: составление таблицы перекрёстных ссылок слов текста. Исключение из деревьев поиска. Случаи различного вида вершин: терминальная, внутренняя с одним или с двумя потомками. Процедура удаления с рекурсивным спуском вдоль правой ветви левого поддерева. Сложностные оценки вставки и удаления. Их ухудшение при разбалансировке дерева. Крайний случай. Сравнение средней и оптимальной оценок.

АиСД: фундаментальное алгоритмическое введение A5 Сбалансированные деревья. Идея AVL-метода. AVL-деревья. Сложностные оценки: худший случай невозможен! Оправданность затрат на балансировку при частых операциях поиска и редких – включения и удаления. Включение в сбалансированное дерево. Графическая иллюстрация. Исключение из сбалансированного дерева. Графическая иллюстрация. Понятие о деревьях оптимального поиска. Физическое представление деревьев. Отображение на массив турнирного дерева. Достоинства (простота и быстрота) и недостатки (трудоёмкость поиска, вставки и удаления). Прошивка деревьев. Итеративный обход. Итераторы. Графы. Определения. Терминология. Матричные представления. Алгоритм Уоршалла. Представление плексами. Примеры алгоритмов на графах: поиск в глубину, поиск в ширину.

Конец лекции 10