|
Содержание
Введение
Наиболее значимой областью применения методов дискретной математики является область компьютерных технологий. Это объясняется необходимостью создания и эксплуатации электронных вычислительных машин, средств передачи и обработки информации, автоматизированных систем управления и проектирования. С момента появления компьютера и начала использования вычислительной техники для решения разнообразных задач получила развитие системная область знаний математики, связанная с программированием. При всех своих огромных возможностях компьютер может работать только с конечным множеством объектов, причем на этом множестве должно быть определено отношение порядка. Потребности программирования определяют развитие «стыка» информатики и математики. Это область знаний не исчерпывается дискретной математикой, однако она является характерной, основополагающей. Многие задачи экономики и математического моделирования также непосредственно связаны с дискретной математикой. Например, к числу этих задач относятся задачи оптимизации: задача о назначениях, задача о максимальном потоке, сетевое планирование и многие другие. Дискретная математика и примыкающие к ней дисциплины изучаются во всех университетах, где осуществляется подготовка специалистов в областях программирования, математики, экономики, а также по техническим и гуманитарным дисциплинам. В настоящее время имеется масса доступной литературы, покрывающей многие разделы дискретной математики, в том числе иностранные издания [1]-[3], переиздания известних учебников Яблонского С.В. [4], задачника Гаврилова Г.П. и Сапоженко А.А. [5], лекций команды математиков из Минска [6], книги Зыкова А.А. [7] и многочисленных пособий от авторов из российских университетов, например, [8]–[16]. Список авторских учебников достаточно обширен, поскольку в зависимости от направления подготовки студентов, содержания сопутствующих курсов, требований работодателей меняется и теоретическое наполнение данного курса. Так, студенты математических специальностей каждый раздел курса изучают в рамках отдельных дисциплин. Программистам необходимо сделать упор на роль дискретной математики в современных компьютерных технологиях, вооружить их методами, применяемыми для решения широкого круга задач, научить на примерах классических задач представлять выполнение алгоритма по шагам. Особое внимание при обучении программистов и специалистов в области информатики уделяется и вопросу практической реализации на компьютере, в частности, для задач большой размерности. Что касается экономистов и специалистов по статистике, тут ключевыми разделами являются комбинаторика и теория графов и также необходимо уделить внимание компьютерной реализации рассмотренных алгоритмов. Данное учебное пособие основано на лекционных курсах «Комбинаторика и теория графов» и «Дискретная математика» который автор преподает студентам специальностей «Прикладная информатика в экономике» и «Математические методы в экономике» (2005–2011), «Прикладная математика и информатика» (2011–2015), «Фундаментальная инфрматика и информационные технологии» (с 2011) Южно-Уральского государственного университета. Одна из главных задач этого курса – обучение студентов методам мышления, характерным для дискретной математики, основным понятиям комбинаторики и теории графов. Поскольку указанные специальности предполагают умение эффективно решать задачи с помощью компьютера, также была поставлена цель развить у студентов навыки алгоритмического мышления на примерах решения задач из разных разделов дискретной математики. Пособие охватывает следующие разделы дискретной математики: основы теории множеств, комбинаторику и теорию графов. Из основных разделов отсутствуют общая алгебра, теория алгоритмов, арифметика, математическая логика. Это объясняется тем, что данные разделы студенты изучают в рамках других курсов. Пособие ориентировано на семестровый лекционный курс. Книга также может составить основу разделов курсов, примыкающих к дискретной математике (информатика, алгоритмизация, структуры данных). Учебное пособие состоит из 17 глав. Первая глава содержит материал из элементарной теории множеств, необходимый для чтения последующих глав. Во второй главе кратко изложен метод математической индукции, который является одним из основных методов доказательства в дискретной математике. В главах 3 – 7 рассмотрены основные принципы комбинаторики, алгоритмы формирования выборок, размещений и сочетаний. Отдельное внимание уделено технике доказательства комбинаторных тождеств. В этих (а также некоторых других) главах существенно использованы материалы книги [13]. Эвнин А.Ю. (24 сентября 1960 – 19 ноября 2020), автор талантливых книг [11, 13, 15, 16] был моим преподавателем по курсу «Дискретная математика» в 1998 году, поэтому сложно было написать о многом иными словами. Он умел излагать материал настолько понятно и красиво, что даже самые сложные моменты курса становились доступными к осмыслению многими студентами. Главы 8 – 9 посвящены введению в теорию графов, приведены основные понятия теории графов и рассмотрены принципы представления графов на компьютере. В главе 10 приведены определения деревьев и приведены прикладные задачи, математической моделью которых является дерево. Рассмотрен частный случай – бинарные деревья, и их применение на практике. Описаны основные способы обхода бинарных деревьев. Проанализирована одна из классических задач теории графов – построение минимального остова. Для решения этой задачи приведено два алгоритма. Глава 11 посвящена двум старейшим задачам теории графов: поиску эйлеровых и гамильтоновых циклов. В главе 12 рассмотрены двудольные графы и их применение при решении практических задач: поиск максимального паросочетания, решение задачи о назначениях. Глава 13 знакомит с укладкой графов на плоскости. Приведены критерии планарности графа, а также алгоритм построения плоской укладки, если таковая существует. Главы 14 – 16 посвящены решению прикладных задач, в которых необходимо применить объекты теории графов: поиск кратчайшего пути, решение задач сетевого планирования и задачи о максимальном потоке. В 17 главе рассмотрены вопросы раскраски графов и приведены точный и приближенные алгоритмы решения этой задачи. О некоторых других применениях теории графов, не классических для данного курса алгоритмах можно прочитать в моей монографии [18]. В конце каждой главы приведены задачи различного уровня сложности, в том числе и связанные с разработкой алгоритмов и программ. Студенту предлагается самостоятельно решить предложенные задачи без использования уже имеющихся библиотек. Непосредственно вопросы программирования подробно рассматриваются в книгах [18–23]. Отдельно выделим книгу [19], в которой реализация и анализ алгоритмов рассмотрены наиболее подробно и на высоком профессиональном уровне. Автор благодарит профессора Уфимского государственного авиационного технического университета Бронштейна Ефима Михайловича и доцента Южно-Уральского государственного университета Эвнина Александра Юрьевича за критические замечания и предложения.
Об авторе
 Макаровских Татьяна Анатольевна Доктор физико-математических наук, доцент, профессор кафедры «Системное программирование» Южно-Уральского государственного университета. В 2003 г. с отличием окончила ЮУрГУ по специальности «Прикладная математика». В 2006 г. защитила кандидатскую диссертацию по специальности «Теоретические основы информатики» в Вычислительном центре имени А. А. Дородницына РАН. В 2020 г. защитила докторскую диссертацию по той же специальности в ЮУрГУ. Является автором более 100 научных публикаций, 7 учебных пособий, монографии «Маршруты-покрытия специального вида в графах: Теоретические основы и применение в ресурсосберегающих технологиях» (М.: URSS), а также более 10 зарегистрированных программ для ЭВМ.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
