URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Панюкова Т.А. Комбинаторика и теория графов
Id: 181633
 
269 руб.

Комбинаторика и теория графов. Изд.3, испр.

URSS. 2014. 216 с. Мягкая обложка. ISBN 978-5-9710-0924-5. Уценка. Состояние: 5-. Блок текста: 5. Обложка: 4+.

 Аннотация

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


 Оглавление

Введение
1. Множества и операции над ними
 1.1.Множества
 1.2.Способы задания множеств
 1.3.Операции над множествами
 1.4.Свойства операций над множествами
 Задачи
2. Метод математической индукции
 Задачи
3. Основные принципы комбинаторики
 3.1.Правило произведения
 3.2.Правило сложения
 Задачи
4. Размещения, перестановки, сочетания
 4.1.Выборки и размещения
 4.2.Сочетания
 4.3.Перестановки с повторениями
 4.4.Полиномиальная формула
 Задачи
5. Комбинаторные тождества
 Задачи
6. Формирование перестановок и сочетаний
 6.1.Перестановки
 6.2.Сочетания
 6.3.Размещения без повторений
 6.4.Сочетания с повторениями
 Задачи
7. Принцип включения-исключения
 Задачи
8. Введение в теорию графов. Основные понятия и определения
 8.1.Основные определения
 8.2.Лемма о рукопожатиях
 8.3.Вершинная и реберная связность
 Задачи
9. Способы представления графов и методы просмотра вершин
 9.1.Матрица инцидентности
 9.2.Матрица смежности
 9.3.Списки смежности
 9.4.Поиск в глубину
 9.5.Поиск в ширину
 Задачи
1 . Деревья и леса
 1 .1.Числовые параметры, характеризующие ориентированное дерево
 1 .2.Бинарные деревья
 1 .3.Сортировка
 1 .4.Бинарные деревья поиска
 1 .5.Остовные деревья
 1 .6.Матричная формула Кирхгофа
 Задачи
11. Эйлеровы и гамильтоновы графы
 11.1.Эйлеровы графы и задача о Кенигсбергских мостах
 11.2.Гамильтоновы графы и задача коммивояжера
 11.3.Связь между эйлеровыми и гамильтоновыми циклами
 Задачи
12. Двудольные графы и паросочетания
 12.1.Двудольные графы
 12.2.Паросочетания
 12.3.Задача о назначениях
 Задачи
13. Укладки графов
 13.1.Свойства планарных графов
 13.2.Формула Эйлера
 13.3.Критерий планарности графа
 13.4.Алгоритм укладки графа на плоскости
 Задачи
14. Нахождение кратчайших путей в графе
 Задачи
15. Задачи сетевого планирования
 15.1.Правила построения сетевых графиков
 15.2.Метод критического пути
 15.3.Управление проектами с неопределенным временем выполнения работ
 15.4.Оптимизация сетевого графика
 15.5.Общие замечания
 Задачи
16. Потоки в сетях
 16.1.Алгоритм Форда и Фалкерсона
 16.2.Метод блокирующих потоков
 Задачи
17. Раскраска графов
 17.1.Точный алгоритм раскрашивания
 17.2.Приближенный алгоритм последовательного раскрашивания
 17.3.Улучшенный алгоритм последовательного раскрашивания
 17.4.Клики и независимые множества
 Задачи
Ответы
Литература

 Введение

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

Наиболее значимой областью применения методов дискретной математики является область компьютерных технологий. Это объясняется необходимостью создания и эксплуатации электронных вычислительных машин, средств передачи и обработки информации, автоматизированных систем управления и проектирования. С момента появления компьютера и начала использования вычислительной техники для решения разнообразных задач получила развитие системная область знаний математики, связанная с программированием. При всех своих огромных возможностях компьютер может работать только с конечным множеством объектов, причем на этом множестве должно быть определено отношение порядка. Потребности программирования определяют развитие "стыка" информатики и математики. Это область знаний не исчерпывается дискретной математикой, однако она является характерной, основополагающей.

Многие задачи экономики и математического моделирования также непосредственно связаны с дискретной математикой. Например, к числу этих задач относятся задачи оптимизации: задача о назначениях, задача о максимальном потоке, сетевое планирование и многие другие.

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

В настоящее время имеется масса доступной литературы, покрывающей многие разделы дискретной математики, в том числе и переиздания известного учебника Яблонского С.В., задачника Гаврилова Г.П. и Сапоженко А.А.. Однако в зависимости от направления обучения студентов меняется и теоретическое наполнение данного курса. Так, студенты математических специальностей каждый раздел курса изучают в рамках отдельных дисциплин. Программистам необходимо сделать упор на роль дискретной математики в современных компьютерных технологиях, вооружить их методами, применяемыми для решения широкого круга задач. Особое внимание при обучении программистов и специалистов в области информатики уделяется и вопросу практической реализации на компьютере. Что касается экономистов и специалистов по статистике, тут ключевыми разделами являются комбинаторика и теория графов и также необходимо уделить внимание компьютерной реализации рассмотренных алгоритмов.

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

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

Учебное пособие состоит из 17 глав.

Первая глава содержит материал из элементарной теории множеств, необходимый для чтения последующих глав.

Во второй главе кратко изложен метод математической индукции, который является одним из основных методов доказательства в дискретной математике.

В главах 3 -- 7 рассмотрены основные принципы комбинаторики, алгоритмы формирования выборок, размещений и сочетаний. Отдельное внимание уделено технике доказательства комбинаторных тождеств.

В этих (а также некоторых других) главах существенно использованы материалы книги [8].

Главы 8 -- 9 посвящены введению в теорию графов, приведены основные понятия теории графов и рассмотрены принципы представления графов на компьютере.

В главе 10 приведены определения деревьев и приведены прикладные задачи, математической моделью которых является дерево. Рассмотрен частный случай -- бинарные деревья, и их применение на практике. Описаны основные способы обхода бинарных деревьев. Проанализирована одна из классических задач теории графов -- построение минимального остова. Для решения этой задачи приведено два алгоритма.

Глава 11 посвящена двум старейшим задачам теории графов: поиску эйлеровых и гамильтоновых циклов.

В главе 12 рассмотрены двудольные графы и их применение при решении практических задач: поиск максимального паросочетания, решение задачи о назначениях.

Глава 13 знакомит с укладкой графов на плоскости. Приведены критерии планарности графа, а также алгоритм построения плоской укладки, если таковая существует.

Главы 14 -- 16 посвящены решению прикладных задач, в которых необходимо применить объекты теории графов: поиск кратчайшего пути, решение задач сетевого планирования и задачи о максимальном потоке.

В 17 главе рассмотрены вопросы раскраски графов и приведены точный и приближенные алгоритмы решения этой задачи.

В конце каждой главы приведены задачи различного уровня сложности, в том числе и связанные с разработкой алгоритмов и программ.

Автор благодарит профессора Уфимского государственного авиационного технического университета Бронштейна Ефима Михайловича и доцента Южно-Уральского государственного университета Эвнина Александра Юрьевича за критические замечания и предложения.


 Об авторе

Макаровских Татьяна Анатольевна
Кандидат физико-математических наук, доцент кафедры «Экономико-математические методы и статистика» Южно-Уральского государственного университета. В 2003 г. окончила ЮУрГУ по специальности «Прикладная математика». В 2006 г. защитила кандидатскую диссертацию по специальности «Теоретические основы информатики» в Вычислительном центре имени А. А. Дородницына РАН. Является автором более 50 научных публикаций (в том числе 8 книг) и разработчиком пяти зарегистрированных программ для ЭВМ.

 Страницы

 
© URSS 2016.

Информация о Продавце