Графы. Модели вычислений. Структуры данных

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Author(s): Алексеев В.Е., Таланов В.А.
Year: 2004

Language: Russian
Pages: 294
City: Н.Новг.

Alekseev&Talanov_2.pdf......Page 0
Предисловие......Page 2
1.1.1. Определение графа......Page 4
1.2. Изоморфизм......Page 12
1.3. Операции над графами......Page 14
1.3.3. Алгебраические операции......Page 16
1.4. Маршруты, связность, расстояния......Page 19
1.5. Деревья......Page 24
1.6. Эйлеровы графы......Page 28
1.7. Двудольные графы......Page 30
1.8. Планарные графы......Page 33
Задачи......Page 37
2.1. Поиск в ширину......Page 41
2.2. Поиск в глубину......Page 47
Задачи и упражнения......Page 72
3.1.1. Три задачи......Page 74
3.2.1. Раскраска вершин......Page 84
3.3.1. Паросочетания и реберные покрытия......Page 92
3.3.2. Метод увеличивающих цепей......Page 93
3.2.3. Паросочетания в двудольных графах......Page 95
3.2.4. Паросочетания в произвольных графах (алгоритм Эдмондс......Page 98
3.4.1. Задача об оптимальном каркасе и алгоритм Прима......Page 100
3.4.2. Алгоритм Краскала......Page 103
3.5. Жадные алгоритмы и матроиды......Page 104
3.5.1. Матроиды......Page 105
3.5.2. Теорема Радо – Эдмондса......Page 106
3.5.3. Взвешенные паросочетания......Page 108
Список литературы к гл. 1-3......Page 111
Оглавление......Page 112
Исторические сведения......Page 116
Глава 1. ТЬЮРИНГОВА МОДЕЛЬ ПЕРЕРАБОТКИ ИНФОРМАЦИИ......Page 118
1.1. Алгебра тьюринговых программ......Page 120
1.2. Начальное математическое обеспечение......Page 122
1.3. Методика доказательства правильности программ......Page 124
1.4. Вычислимость и разрешимость......Page 125
Упражнения......Page 126
1.6. Частично-рекурсивные функции......Page 127
Доказательство. Представим программу, предлагаемую для вычис......Page 129
1.7. Универсальная тьюрингова программа......Page 131
1.8. Об измерении алгоритмической сложности задач......Page 133
2.1. Основные определения......Page 136
2.2. Примеры неразрешимости......Page 138
Глава 3. АЛГОРИФМЫ МАРКОВА......Page 142
Коды операций:......Page 145
вес......Page 146
5.1. Основные понятия и обозначения......Page 149
5.2. Способы задания формальных языков......Page 150
5.3. Регулярные выражения......Page 152
5.4. Решение уравнений в словах......Page 153
5.5. Автоматное задание языков......Page 155
5.6. Применение конечных автоматов в программировании......Page 161
Глава 6. ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ......Page 166
6.1. Язык предикатов......Page 167
6.2. Некоторые сведения из математической логики......Page 171
6.3. Примеры формальных доказательств......Page 174
6.4. Элементы языка ПРОЛОГ......Page 177
Глава 1. СПИСКИ......Page 182
Удалить из списка S элемент, находящийся в позиции pos......Page 193
Preced......Page 195
2.1. Операции над разделенными множествами......Page 200
2.2. Примеры использования разделенных множеств......Page 201
с помощью древовидной структуры......Page 204
с использованием рангов вершин......Page 208
с использованием рангов вершин и сжатия путей......Page 212
Для анализа трудоемкости выполнения операций нам потребуются......Page 213
Реализация с помощью древовидной cтруктуры......Page 217
с использованием рангов и сжатия путей......Page 218
3.1. Основные определения......Page 219
с помощью d-кучи......Page 220
Замечания......Page 224
Операция ВСТАВКА. Если перед выполнением этой операции куча......Page 227
Реализация операции ВСТАВКА......Page 228
Îïåðàöèÿ ÓÌÅÍÜØÅÍÈÅ_ÊËÞ×À.......Page 229
Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА:......Page 230
MINKEY......Page 231
Упражнения......Page 233
Упражнения......Page 234
3.4. Нахождения кратчайших путей в графе......Page 235
4.1. Левосторонние кучи......Page 237
Операция СЛИЯНИЕ. Эта операция позволяет слить две левосторо......Page 239
Операция ВСТАВКА. Эта операция позволяет осуществить вставку......Page 242
Операция УДАЛЕНИЕ. Эта операция позволяет удалить из кучи h......Page 243
Îïåðàöèÿ ÓÌÅÍÜØÈÒÜ_ÊËÞ×. Êë......Page 247
Реализация операции УМЕНЬШИТЬ_КЛЮЧ......Page 250
4.2. Биномиальные и фибоначчиевы кучи......Page 251
4.3. Тонкие кучи......Page 256
4.3. Толстые кучи......Page 265
Общие сведения. Деревья поиска предназначены для представлен......Page 281
5.2. Красно-черные деревья......Page 286
5.3. Б-деревья......Page 290