Ebook: Графы. Модели вычислений. Структуры данных: учебник для студентов, обучающихся по специальности 010200 - Прикладная математика и информатика и по направлению 510200 - Прикладная математика и информатика

Учебник состоит из трех частей, посвященных вопросам анализа и разработки алгоритмов: графы и алгоритмы, модели вычислений, структуры данных. Для понимания материала достаточно математической подготовки в объеме первого курса университета или технического вуза. Предназначен для студентов, обучающихся по направлению 510200 Прикладная математика и информатика и по специальности 010200 Прикладная математика и информатика. "В этой книге под одной обложкой собраны учебные тексты, на первый взгляд разнородные, но относящиеся к одной сравнительно молодой области человеческой деятельности. Это деятельность по созданию и исследованию алгоритмов, для которой пока не придумано общеупотребительного объединяющего названия (она является частью того, что охватывается терминами'computer science? и'информатика?). Работа в этой области требует определенных математических знаний и представления о проблемах, связанных с разработкой компьютерных программ, но она не сводится к математике или программированию. Ее роль можно сравнить с ролью технологии по отношению к науке и производству. " Оглавление Предисловие Часть 1. Графы и алгоритмы Глава 1. Элементы теории графов 1.1. Начальные понятия 1.1.1. Определение графа 1.1.2. Графы и бинарные отношения 1.1.3. Откуда берутся графы 1.1.4. Число графов 1.1.5. Смежность, инцидентность, степени 1.1.6. Некоторые специальные графы 1.1.7. Графы и матрицы 1.1.8. Взвешенные графы 1.2. Изоморфизм 1.2.1. Определение изоморфизма 1.2.2. Инварианты 1.3. Операции над графами 1.3.1. Локальные операции 1.3.2. Подграфы 1.3.3. Алгебраические операции 1.4. Маршруты, связность, расстояния 1.4.1. Маршруты, пути, циклы 1.4.2. Связность и компоненты 1.4.3. Метрические характеристики графов 1.4.4. Маршруты и связность в орграфах 1.5. Деревья 1.5.1. Определение и элементарные свойства 1.5.2. Центр дерева 1.5.3. Корневые деревья 1.5.4. Каркасы 1.6. Эйлеровы графы 1.7. Двудольные графы 1.8. Планарные графы Глава 2. Анализ графов 2.1. Поиск в ширину 2.1.1. Метод поиска в ширину 2.1.2. BFS-дерево и вычисление расстояний 2.2. Поиск в глубину 2.2.1. Метод поиска в глубину 2.2.2. DFS-дерево 2.2.3. Другие варианты алгоритма поиска в глубину 2.2.4 Шарниры 2.3. Блоки 2.3.1. Двусвязность 2.3.2. Блоки и BC-деревья 2.3.3. Выявление блоков 2.4. База циклов 2.4.1. Пространство подграфов 2.4.2. Квазициклы 2.4.3. Фундаментальные циклы 2.4.4. Построение базы циклов 2.4.5. Рационализация 2.5. Эйлеровы циклы 2.6. Гамильтоновы циклы Задачи и упражнения Глава 3. Экстремальные задачи на графах 3.1. Независимые множества, клики, вершинные покрытия 3.1.1. Три задачи 3.1.2. Стратегия перебора для задачи о независимом множестве 3.1.3. Рационализация 3.1.4. Хордальные графы 3.1.5. Эвристики для задачи о независимом множестве 3.1.6. Приближенный алгоритм для задачи о вершинном покрытии 3.1.7. Перебор максимальных независимых множеств 3.2. Раскраски 3.2.1. Раскраска вершин 3.2.2. Переборный алгоритм для раскраски 3.2.3. Рационализация 3.2.4. Хордальные графы 3.2.5. Раскраска ребер 3.3. Паросочетания 3.3.1. Паросочетания и реберные покрытия 3.3.2. Метод увеличивающих цепей 3.3.3. Паросочетания в двудольных графах 3.3.4. Паросочетания в произвольных графах (алгоритм Эдмондса) 3.4. Оптимальные каркасы 3.4.1. Задача об оптимальном каркасе и алгоритм Прима 3.4.2. Алгоритм Краскала 3.5. Жадные алгоритмы и матроиды 3.5.1. Матроиды 3.5.2. Теорема Радо' Эдмондса 3.5.3. Взвешенные паросочетания Упражнения Часть 2. Модели вычислений Исторические сведения Глава 1. Тьюрингова модель переработки информации 1.1. Алгебра тьюринговых программ 1.2. Начальное математическое обеспечение 1.3. Методика доказательства правильности программ 1.4. Вычислимость и разрешимость 1.5. Вычисление числовых функций 1.6. Частично-рекурсивные функции 1.7. Универсальная тьюрингова программа и пример невычислимой функции 1.8. Об измерении алгоритмической сложности задач Глава 2 Абак 2.1. Основные определения 2.2. Примеры неразрешимости Глава 3. Алгорифмы Маркова Глава 4. Равнодоступная адресная машина Глава 5. Формальные языки 5.1. Основные понятия и обозначения 5.2. Способы задания формальных языков 5.3. Регулярные выражения 5.4. Решение уравнений в словах 5.5. Автоматное задание языков 5.6. Применение конечных автоматов в программировании Глава 6. Логическое программирование 6.1. Язык предикатов 6.2. Некоторые сведения из математической логики 6.3. Примеры формальных доказательств 6.4. Элементы языка Пролог Часть 3. Структуры данных Введение Глава 1. Списки 1.1. Общие сведения о списках 1.2. Списки с прямым доступом 1.3. Списки с последовательным доступом 1.4. Некоторые дополнительные операции со связными списками 1.5. Моделирование списков с последовательным доступом при помощи массивов 1.6. Деревья и графы Глава 2. Разделенные множества 2.1. Операции над разделенными множествами 2.2. Примеры использования разделенных множеств 2.3. Представление разделенных множеств с помощью массива 2.4. Представление разделенных множеств с помощью древовидной структуры 2.5. Представление разделенных множеств с использованием рангов вершин 2.6. Представление разделенных множеств с использованием рангов вершин и сжатия путей 2.7. Анализ трудоемкости Глава 3. Приоритетные очереди 3.1. Основные определения 3.2. Представление приоритетной очереди с помощью d-кучи 3.3. Применение приоритетных очередей в задаче сортировки 3.4. Нахождения кратчайших путей в графе Глава 4. Объединяемые приоритетные очереди 4.1. Левосторонние кучи 4.2. Ленивая левосторонняя и самоорганизующиеся кучи 4.3. Биномиальные и фибоначчиевы кучи 4.4. Тонкие кучи 4.5. Толстые кучи Глава 5. Поисковые деревья 5.1. Двоичные деревья поиска 5.2. Красно-черные деревья 5.3. Б-деревья