О книге
Изложен ряд основных разделов теории графов, необходимых для разработки моделей объектов и задач дискретной оптимизации. Рассмотрены модели структур сложных систем в виде различного вида графов: ультра-, гипер-, ориентированных и неориентированных, а также формальные постановки задач комбинаторной оптимизации на графах. Описаны особенности и сущность точных методов дискретной оптимизации, таких как жадный выбор, поиск в ширину и в глубину с возвращением, ветвей и границ, Дейкстры, Форда — Фалкерсона и динамического программирования.
Для студентов, обучающихся по направлению подготовки «Информатика и вычислительная техника» (уровень магистратуры), а также для преподавателей и аспирантов. Может быть полезен для научных работников, инженеров, аспирантов и студентов специальностей, связанных с проектированием сложных систем.
Список литературы
- Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. М.: Наука, 1990. 384 с
- Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с
- Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 423 с
- Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 288 с.
- Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. 368 с.
- Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. М.: Издат. дом Вильямс, 2001. 384 с
- Михалевич В.С., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983. 208 с.
- Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: пер. с англ. М.: Мир, 1985. 512 с.
- Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: учебник. М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2002. 280 с
- Харари Ф. Теория графов / пер. с англ. и предисл В.П. Козырева; под ред. Г.П. Гаврилова. 2-е изд. М.: Едиториал УРСС, 2003. 296 с
- Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов н/Д: Изд-во Ростовского ун-та, 1981. 112 с.
- Новиков Ф.А. Дискретная математика для программистов. СПб.: Пи-тер, 2011. 384 с.
- Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем: учебник для вузов по спец. «Выч. мат., компл., сист. и сети». 2-е изд., перераб. и доп. М.: Высш. шк., 1989. 312 с
- Овчинников В.А., Иванова Г.С. Информационно-логическая модель алгоритма // Вестн. МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2005. № 2 (59). C. 109–121.
- Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ–Петербург, 2003. 1104 с
- Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука, 1988. 336 с.
- Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. 304 с
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 536 с.
- Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: учеб. пособие. М.: ФИЗМАТЛИТ, 2002. 240 с.
- Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с
- Галкина В.А. Дискретная математика. Комбинаторная оптимизация на графах: учеб. пособие. М.: Гелиос АРВ, 2003. 232 с
- Алгоритмы и программы решения задач на графах и сетях / М.И. Нечепуренко, В.К. Попков, С.М. Майнагашев и др. Новосибирск: Наука. Сиб. отд-ние, 1990. 515 с.
- Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. 323 с.
- Zwick Uri. The Smallest Networks on which the Ford-Fulkerson Maximum Flow Procedure may Fail to Terminate // Theoretical Computer Science. Vol. 148, iss. 1. 21 August 1995, P. 165–170.
- Видеолекции. Введение в теорию графов. URL: http://www.intuit.ru/studies/courses/1033/241/info (дата обращения 01.09.2017).
- Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ). URL: http://discopal/ispras.ru/%D0%9A%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9_%C2%AB%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0% D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2%C2%BB_(%D0%98%D0%A1%D0%9F%D0%A0%D0%90%D0%9D,_3_%D0%BA% D1%83%D1%80%D1%81_%D0%9C%D0%A4%D0%A2%D0%98) (дата обращения 01.09.2017).
- Дискретная математика. URL: http://www.intuit.ru/studies/courses/1049/317/info (дата обращения 01.09.2017).29. Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ). URL: http://discopal/ispras.ru/%D0%9A%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9_%C2%AB%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0% D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2%C2%BB_(%D0%98%D0%A1%D0%9F%D0%A0%D0%90%D0%9D,_3_%D0%BA% D1%83%D1%80%D1%81_%D0%9C%D0%A4%D0%A2%D0%98) (дата обращения 01.09.2017).
