Показать ещё...
Дискретность – понятие, противоположное непрерывности. Традиционно к дискретной математике относят такие области знаний, как комбинаторика, теория чисел, общая алгебра, математическая логика, комбинаторный анализ, теория графов, теория кодирования, целочисленное программирование, теория автоматов и пр. Список областей знаний, являющихся разделами дискретной математики можно продолжать и продолжать. Вообще, дискретная математика всегда была очень динамичной областью, т.к. она непосредственно связана с различными прикладными науками. Наиболее значимой областью применения методов дискретной математики является область компьютерных технологий. Это объясняется необходимостью создания и эксплуатации электронных вычислительных машин, средств передачи и обработки информации, автоматизированных систем управления и проектирования. С момента появления компьютера и начала использования вычислительной техники для решения разнообразных задач получила развитие системная область знаний математики, связанная с программированием. При всех своих огромных возможностях компьютер может работать только с конечным множеством объектов, причем на этом множестве должно быть определено отношение порядка. Потребности программирования определяют развитие "стыка" информатики и математики. Это область знаний не исчерпывается дискретной математикой, однако она является характерной, основополагающей. Многие задачи экономики и математического моделирования также непосредственно связаны с дискретной математикой. Например, к числу этих задач относятся задачи оптимизации: задача о назначениях, задача о максимальном потоке, сетевое планирование и многие другие. Дискретная математика и примыкающие к ней дисциплины изучаются во всех университетах, где осуществляется подготовка специалистов в областях программирования, математики, экономики, а также по техническим и гуманитарным дисциплинам. В настоящее время имеется масса доступной литературы, покрывающей многие разделы дискретной математики, в том числе и переиздания известного учебника Яблонского С.В., задачника Гаврилова Г.П. и Сапоженко А.А.. Однако в зависимости от направления обучения студентов меняется и теоретическое наполнение данного курса. Так, студенты математических специальностей каждый раздел курса изучают в рамках отдельных дисциплин. Программистам необходимо сделать упор на роль дискретной математики в современных компьютерных технологиях, вооружить их методами, применяемыми для решения широкого круга задач. Особое внимание при обучении программистов и специалистов в области информатики уделяется и вопросу практической реализации на компьютере. Что касается экономистов и специалистов по статистике, тут ключевыми разделами являются комбинаторика и теория графов и также необходимо уделить внимание компьютерной реализации рассмотренных алгоритмов. Учебное пособие основано на лекционном курсе "Комбинаторика и теория графов", который автор читает студентам специальностей "Прикладная информатика в экономике" и "Математические методы в экономике" Южно-Уральского государственного университета. Одна из главных задач этого курса – обучение студентов методам мышления, характерным для дискретной математики, основным понятиям комбинаторики и теории графов. Поскольку обе указанные специальности предполагают умение эффективно решать задачи с помощью компьютера, также была поставлена цель развить у студентов навыки алгоритмического мышления на примерах решения задач из разных разделов дискретной математики. Пособие охватывает следующие разделы дискретной математики: основы теории множеств, комбинаторику и теорию графов. Из основных разделов отсутствуют общая алгебра, теория алгоритмов, арифметика, математическая логика. Это объясняется тем, что данные разделы студенты изучают в рамках других курсов. Пособие ориентировано на семестровый лекционный курс. Книга также может составить основу разделов курсов, примыкающих к дискретной математике (информатика, алгоритмизация и пр.). Учебное пособие состоит из 17 глав. Первая глава содержит материал из элементарной теории множеств, необходимый для чтения последующих глав. Во второй главе кратко изложен метод математической индукции, который является одним из основных методов доказательства в дискретной математике. В главах 3 – 7 рассмотрены основные принципы комбинаторики, алгоритмы формирования выборок, размещений и сочетаний. Отдельное внимание уделено технике доказательства комбинаторных тождеств. В этих (а также некоторых других) главах существенно использованы материалы книги [8]. Главы 8 – 9 посвящены введению в теорию графов, приведены основные понятия теории графов и рассмотрены принципы представления графов на компьютере. В главе 10 приведены определения деревьев и приведены прикладные задачи, математической моделью которых является дерево. Рассмотрен частный случай – бинарные деревья, и их применение на практике. Описаны основные способы обхода бинарных деревьев. Проанализирована одна из классических задач теории графов – построение минимального остова. Для решения этой задачи приведено два алгоритма. Глава 11 посвящена двум старейшим задачам теории графов: поиску эйлеровых и гамильтоновых циклов. В главе 12 рассмотрены двудольные графы и их применение при решении практических задач: поиск максимального паросочетания, решение задачи о назначениях. Глава 13 знакомит с укладкой графов на плоскости. Приведены критерии планарности графа, а также алгоритм построения плоской укладки, если таковая существует. Главы 14 – 16 посвящены решению прикладных задач, в которых необходимо применить объекты теории графов: поиск кратчайшего пути, решение задач сетевого планирования и задачи о максимальном потоке. В 17 главе рассмотрены вопросы раскраски графов и приведены точный и приближенные алгоритмы решения этой задачи. В конце каждой главы приведены задачи различного уровня сложности, в том числе и связанные с разработкой алгоритмов и программ. Автор благодарит профессора Уфимского государственного авиационного технического университета Бронштейна Ефима Михайловича и доцента Южно-Уральского государственного университета Эвнина Александра Юрьевича за критические замечания и предложения. Макаровских Татьяна Анатольевна Доктор физико-математических наук, доцент, профессор кафедры «Системное программирование» Южно-Уральского государственного университета. В 2003 г. с отличием окончила ЮУрГУ по специальности «Прикладная математика». В 2006 г. защитила кандидатскую диссертацию по специальности «Теоретические основы информатики» в Вычислительном центре имени А. А. Дородницына РАН. В 2020 г. защитила докторскую диссертацию по той же специальности в ЮУрГУ. Является автором более 100 научных публикаций, 7 учебных пособий, монографии «Маршруты-покрытия специального вида в графах: Теоретические основы и применение в ресурсосберегающих технологиях» (М.: URSS), а также более 10 зарегистрированных программ для ЭВМ.
|
2023. 720 с. Твердый переплет. 16.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) 2023. 696 с. Твердый переплет в суперобложке. 119.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) |