x-uni.com
регистрация / вход
сейчас на линии 57 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 57 чел.
Дискретная математика: графы, матроиды, алгоритмы - Асанов М.О., Баранский В.А., Расин В.В.

Дискретная математика: графы, матроиды, алгоритмы - Асанов М.О., Баранский В.А., Расин В.В.

Название: Дискретная математика: графы, матроиды, алгоритмы. 2001.

Автор: Асанов М.О.,  Баранский В.А., Расин В.В.

Изложен  ряд  основных  разделов  теории  графов  и  матроидов.  Рассмотрены
алгоритмы  дискретной  оптимизации  на  сетях  и  графах,  наиболее  часто
используемых программистами.  
Для  студентов  и  аспирантов,  специализирующихся  в  области  компьютерных
наук.

Основой для данного учебного пособия послужили лекции, которые читались авторами для студентов математико-механического факультета Уральского государственного университета им. А. М. Горького, обучающихся по специальностям «Математика, прикладная математика», «Математика, компьютерные науки» и «Компьютерная безопасность».
В книге излагается ряд разделов теории графов и приводятся алгоритмы дискретной оптимизации на графах и сетях. Материал, посвященный теории графов, содержит достаточно обширное введение в теорию матроидов. Матроиды, в частности, составляют теоретическую основу для изучения и анализа алгоритмов, использующих «жадную» стратегию. Понимание же природы и областей применимости жадных алгоритмов безусловно необходимо каждому специалисту по компьютерной математике и ее приложениям.

Содержание
Предисловие
1. Основные понятия теории графов
Основные определения
Маршруты, связность, циклы и разрезы
Ориентированные графы
Матрицы, ассоциированные с графом
2. Деревья
Леса, деревья, остовы
Блоки и точки сочленения
Число остовов в связном обыкновенном графе
3. Обходы графов
Эйлеровы графы
Гамильтоновы графы
4. Матроиды
Полумодулярные решетки, условие Жордана--Дедекинда
Конечномерные геометрические решетки и матроиды
Основные понятия теории матроидов
Различные аксиоматизации матроидов
Двойственный матроид
Жадный алгоритм
Изоморфизмы матроидов
Пространство циклов бинарного матроида
Пространство циклов и пространство разрезов графа
Монотонные полумодулярные функции. Индуцированный матроид
Трансверсальные матроиды
Дизъюнктное объединение и сумма матроидов
5. Планарность
Укладки графов, планарные графы
Формула Эйлера для плоских графов
Критерий планарности графа
Двойственные графы
6. Раскраски
Хроматические числа
Хроматические многочлены
Коэффициенты хроматических многочленов
7. Введение в алгоритмы
Алгоритмы и их сложность
Запись алгоритмов
Корневые и бинарные деревья
Сортировка массивов
8. Поиск в графе
Поиск в глубину
Алгоритм отыскания блоков и точек сочленения
Алгоритм отыскания компонент сильной связности в орграфе
Поиск в ширину
Алгоритм отыскания эйлеровой цепи в эйлеровом графе
9. Задача о минимальном остове
10. Пути в сетях
Постановка задачи
Общий случай. Алгоритм Форда-Беллмана
Cлучай неотрицательных весов. Алгоритм Дейкcтры
Случай бесконтурной сети
Задача о максимальном пути и сетевые графики
Задача о maxmin-пути
Задача о кратчайших путях между всеми парами вершин
11. Задача о максимальном потоке
Основные понятия и результаты
Алгоритм Форда-Фалкерсона
12. Паросочетания в двудольных графах
Основные понятия
Задача о наибольшем паросочетании. Алгоритм Хопкрофта-Карпа
Задача о полном паросочетании. Алгоритм Куна
Задача о назначениях. Венгерский алгоритм
13. Задача коммивояжера
Основные понятия
Алгоритм отыскания гамильтоновых циклов
Алгоритмы решения задачи коммивояжера с гарантированной оценкой
точности 
Решение задачи коммивояжера методом ветвей и границ
Литература
Предметный указатель

Скачать бесплатно на сайте fileskachat.com
Скачать бесплатно на сайте depositfiles.com

Предложения интернет-магазинов

Математика. Теория вероятностей и дискретная математика: Элементы теории, решение задач

Автор(ы): Баюк Олег Александрович, Маркарян Елена Георгиевна   Издательство: Просвещение, 2013 г.  Серия: Сложные темы ЕГЭ

Цена: 333 руб.   Купить

Пособие предназначено учащимся общеобразовательных учреждений (школ, гимназий, колледжей) для углублённого изучения теории вероятностей и связанных с ней разделов дискретной математики (теории множеств, математической логики, комбинаторики, теории графов и математической статистики) в целях успешной сдачи ЕГЭ по математике. В пособии изложены основные теоретические сведения, необходимые для решения задач, приводятся решения типичных заданий ЕГЭ, а также содержатся задания для самостоятельной работы (с ответами, указаниями к решению или решениями). Книга может быть использована в качестве сборника задач на подготовительных курсах, факультативных занятиях, при самостоятельной подготовке к поступлению в вуз и при последующем обучении в вузе.


Алгоритмы - ключ к решению задач. Математика. 5-6 классы

Автор(ы): Михайлова Жанна Николаевна   Издательство: Литера, 2014 г.  Серия: Средняя школа

Цена: 541 руб.   Купить

Книга адресована учащимся 5-6 классов, в том числе детям, обучающимся на дому. Книга содержит основные определения и формулы, алгоритмы решения задач и упражнений по курсу математики 5-6 классов, а также примеры решения заданий с помощью предложенных алгоритмов. К заданиям для самостоятельной работы даны ответы.


Алгоритмы - ключ к решению задач. Алгебра. 7-9 классы

Автор(ы): Михайлова Жанна Николаевна   Издательство: Литера, 2014 г.  Серия: Средняя школа

Цена: 688 руб.   Купить

Книга содержит справочные материалы: определения, формулы, алгоритмы решения типовых уравнений, неравенств и их систем и т. д. по всем разделам школьного курса алгебры, а также образцы решений заданий БГЭ. В пособии предложена методика работы с формулами, способствующая их лучшему применению и запоминанию.


Алгоритмы - ключ к решению задач. Алгебра и элементарные функции. 10-11 классы

Автор(ы): Михайлова Жанна Николаевна   Издательство: Литера, 2014 г.  Серия: Средняя школа

Цена: 656 руб.   Купить

Книга содержит справочные материалы: определения, формулы, алгоритмы решения типовых уравнений, неравенств и их систем и т. д. по всем разделам школьного курса алгебры и начала анализа, а также образцы решений заданий ЕГЭ. В пособии предложена методика работы с формулами, способствующая их лучшему применению и запоминанию.

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!