BitTorrent Трекер RusTrek.ru http://5.45.70.241/ |
|
Алексеев В.Е. - Графы. Модели вычислений. Структуры данных [2005, PDF, RUS] http://5.45.70.241/viewtopic.php?f=266&t=26395 |
Страница 1 из 1 |
Автор: | Релизер [ 2011-11-27 13:36 ] |
Заголовок сообщения: | Алексеев В.Е. - Графы. Модели вычислений. Структуры данных [2005, PDF, RUS] |
Графы. Модели вычислений. Структуры данных #777 Год: 2005 Автор: Алексеев В.Е. Издательство: Нижний Новгород ISBN: 5–85747–810–8 Язык: Русский Формат: PDF Качество: Изначально компьютерное (eBook) Количество страниц: 308 Описание: Учебник состоит из трех частей, посвященных вопросам анализа и разработки алгоритмов: графы и алгоритмы, модели вычислений, структуры данных. Для понимания материала достаточно математической подготовки в объеме первого курса университета или технического вуза. Предисловие ........................................................................................................... 3 Часть 1. Графы и алгоритмы .................................................................................. 5 Глава 1. Элементы теории графов ............................................................................. 5 1.1. Нач альные понятия .............................................................................. 5 1.1.1. Опр еделение графа ..................................................................... 5 1.1.2. Гра фы и бинарные отношения ..................................................8 1.1.3. Отк уда берутся графы ................................................................9 1.1.4. Чис ло графов ............................................................................. 10 1.1.5. Сме жность, инцидентность, степени ......................................10 1.1.6. Нек оторые специальные графы ..............................................11 1.1.7. Гра фы и матрицы ...................................................................... 11 1.1.8. Взве шенные графы ...................................................................13 1.2. Изо морфизм ........................................................................................ 13 1.2.1. Опр еделение изоморфизма ......................................................13 1.2.2. Инв арианты ............................................................................... 14 1.3. Опе рации над графами ....................................................................... 15 1.3.1. Лок альные операции ................................................................15 1.3.2. Под графы .................................................................................. 16 1.3.3. Алг ебраические операции .......................................................17 1.4. Мар шруты, связность, расстояния .................................................... 20 1.4.1. Мар шруты, пути, циклы ..........................................................20 1.4.2. Свя зность и компоненты .........................................................21 1.4.3. Мет рические характеристики графов .....................................22 1.4.4. Мар шруты и связность в орграфах .........................................24 1.5. Дер евья ................................................................................................ 25 1.5.1. Опр еделение и элементарные свойства ..................................25 1.5.2. Цен тр дерева ............................................................................. 26 1.5.3. Кор невые деревья ..................................................................... 27 1.5.4. Кар касы ..................................................................................... 28 1.6. Эйл еровы графы ................................................................................. 29 1.7. Дву дольные графы ............................................................................. 31 1.8. Пла нарные графы ............................................................................... 34 Задачи .......................................................................................................... 38 Глава 2. Анализ графов ............................................................................................ 42 2.1. Пои ск в ширину................................................................................... 42 2.1.1. Мет од поиска в ширину ...........................................................42 2.1.2. BFS -дерево и вычисление расстояний ...................................45 2.2. Пои ск в глубину ................................................................................. 48 2.2.1. Мет од поиска в глубину ..........................................................48 2.2.2. DFS -дерево ................................................................................ 50 2.2.3. Дру гие варианты алгоритма поиска в глубину ......................51 2.2.4 Шар ниры .................................................................................... 53 2.3. Бло ки .................................................................................................... 55 2.3.1. Дву связность ............................................................................. 55 2.3.2. Бло ки и BC-деревья .................................................................. 57 2.3.3. Выя вление блоков .................................................................... 59 2.4. База циклов .......................................................................................... 61 2.4.1. Про странство подграфов .........................................................61 2.4.2. Ква зициклы ............................................................................... 63 2.4.3. Фун даментальные циклы .........................................................64 2.4.4. Пос троение базы циклов ..........................................................65 2.4.5. Рац ионализация ........................................................................ 67 2.5. Эйл еровы циклы ................................................................................. 67 2.6. Гам ильтоновы циклы ......................................................................... 70 Задачи и упражнения ................................................................................. 73 Глава 3. Экстремальные задачи на графах ............................................................. 75 3.1. Нез ависимые множества, клики, вершинные покрытия .................75 3.1.1. Три за дачи ................................................................................. 75 3.1.2. Страте гия перебора для задачи о независимом множестве ..77 3.1.3. Рацио нализация ........................................................................ 78 3.1.4. Хорда льные графы ...................................................................79 3.1.5. Эврис тики для задачи о независимом множестве .................80 3.1.6. Прибл иженный алгоритм для задачи о вершинном покры- тии ............................................................................................. 82 3.1.7. Переб ор максимальных независимых множеств ...................82 3.2. Рас краски ............................................................................................. 85 3.2.1. Раскра ска вершин ..................................................................... 85 3.2.2. Переб орный алгоритм для раскраски .....................................86 3.2.3. Рацио нализация ........................................................................ 87 3.2.4. Хорда льные графы ...................................................................88 3.2.5. Раскра ска ребер ........................................................................ 90 3.3. Пар осочетания .................................................................................... 93 3.3.1. Парос очетания и реберные покрытия ....................................93 3.3.2. Метод увеличивающих цепей .................................................94 3.3.3. Парос очетания в двудольных графах .....................................96 3.3.4. Парос очетания в произвольных графах алгори(тм Эдмондса) ..............................................................99 3.4. Опт имальные каркасы ...................................................................... 101 3.4.1. Задача об оптимальном каркасе и алгоритм Прима ............101 3.4.2. Алгор итм Краскала ................................................................104 3.5. Жад ные алгоритмы и матроиды ...................................................... 105 3.5.1. Матро иды ................................................................................ 106 3.5.2. Теоре ма Радо – Эдмондса ......................................................107 3.5.3. Взвеш енные паросочетания ..................................................109 Упражнения ................................................................................................. 110 Часть 2. Модели вычислений ............................................................................. 112 Исторические сведения ........................................................................................... 112 Глава 1. Тьюрингова модель переработки информации ..................................... 114 1.1. Алг ебра тьюринговых программ ....................................................116 1.2. Нач альное математическое обеспечение .......................................118 1.3. Мет одика доказательства правильности программ ......................120 1.4. Выч ислимость и разрешимость ...................................................... 121 1.5. Выч исление числовых функций .....................................................122 1.6. Час тично-рекурсивные функции ....................................................123 1.7. Уни версальная тьюрингова программа и пример невычислимой функции ............................................................................................. 127 1.8. Об измерении алгоритмической сложности задач ........................129 Глава 2 Абак ........................................................................................................... 132 2.1. Осн овные определения .................................................................... 132 2.2. При меры неразрешимости .............................................................. 134 Глава 3. Алгорифмы Маркова ............................................................................... 138 Глава 4. Равнодоступная адресная машина .......................................................... 141 Глава 5. Формальные языки .................................................................................. 145 5.1. Осн овные понятия и обозначения ..................................................145 5.2. Спо собы задания формальных языков ...........................................147 5.3. Рег улярные выражения .................................................................... 148 5.4. Реш ение уравнений в словах ........................................................... 149 5.5. Авт оматное задание языков ............................................................ 151 5.6. При менение конечных автоматов в программировании ..............157 Глава 6. Логическое программирование .............................................................. 163 6.1. Язы к предикатов ............................................................................... 163 6.2. Нек оторые сведения из математической логики ...........................167 6.3. При меры формальных доказательств .............................................170 6.4. Эле менты языка Пролог .................................................................. 174 Часть 3. Структуры данных ................................................................................... 176 Введение ................................................................................................... 176 Глава 1. Списки ....................................................................................................... 184 1.1. Общ ие сведения о списках .............................................................. 184 1.2. Спи ски с прямым доступом ............................................................. 188 1.3. Спи ски с последовательным доступом ..........................................190 1.4. Нек оторые дополнительные операции со связными списками ...195 1.5. Мод елирование списков с последовательным доступом при по- мощи массивов ................................................................................. 196 1.6. Дер евья и графы ............................................................................... 198 Глава 2. Разделенные множества .......................................................................... 202 2.1. Опе рации над разделенными множествами ...................................202 2.2. Примеры использования разделенных множеств ......................... 204 2.3. Представление разделенных множеств с помощью массива .......206 2.4. П редставление разделенных множеств с помощью древовид- ной структуры ................................................................................... 206 2.5. П редставление разделенных множеств с использованием ран- гов вершин ........................................................................................ 210 2.6. П редставление разделенных множеств с использованием ран- гов вершин и сжатия путей .............................................................. 214 2.7. А нализ трудоемкости ....................................................................... 215 Глава 3. Приоритетные очереди ............................................................................ 221 3.1. Осн овные определения .................................................................... 221 3.2. П редставление приоритетной очереди с помощью d-кучи ..........222 3.3. При менение приоритетных очередей в задаче сортировки .........234 3.4. Нах ождения кратчайших путей в графе .........................................237 Глава 4. Объединяемые приоритетные очереди .................................................. 239 4.1. Лев осторонние кучи ......................................................................... 239 4.2. Лен ивая левосторонняя и самоорганизующиеся кучи ..................253 4.3. Бин омиальные и фибоначчиевы кучи ............................................258 4.4. Тон кие кучи ...................................................................................... 263 4.5. Тол стые кучи ..................................................................................... 271 Глава 5. Поисковые деревья .................................................................................. 288 5.1. Дво ичные деревья поиска ................................................................ 288 5.2. Кра сно-черные деревья .................................................................... 293 5.3. Б-де ревья ........................................................................................... 297 Список литературы .................................................................................................. 302 |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |