Дискретная математика (190,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

УДК 519.6 (075.8) ББК 22.176 я73 Б 48 Печатается по решению редакционно-издательского совета Северо-Кавказского федерального университета Бережной В. В., Шапошников А. В. Б 48 Дискретная математика: учебное пособие (курс лекций). – Ставрополь: Изд-во СКФУ, – 2016. – 199 с. Пособие подготовлено в соответствии с Федеральным государственным образовательным стандартом высшего образования, раскрывает основные принципы и особенности изучения современной информатики и состоит из разделов «Множества и отношения», «Теория графов», «Комбинаторика», «Математическая логика» и «Конечные автоматы». Предназначено для организации и проведения лекционных занятий по дисциплине «Дискретная математика» для направления подготовки 01.03.02 Прикладная математика и информатика (Бакалавр). Также может быть использовано студентами направлений 11.03.02 Инфокоммуникационные технологии и системы связи (Бакалавр), 10.05.03 Информационная безопасность автоматизированных систем (Специалист), 09.03.02 Информационные системы и технологии. УДК 519.6 (075.8) ББК 22.176 я73 Авторы: канд. техн. наук, доцент В. В. Бережной, канд. техн. наук, доцент А. В. Шапошников Рецензенты: д-р техн. наук, проф. И. А. Калмыков, канд. техн. наук С. В. Аникуев (филиал МИРЭА в г. Ставрополе) © ФГАОУ ВО «Северо-Кавказский федеральный университет», 2016

Стр.2

СОДЕРЖАНИЕ Предисловие ................................................................................................................. 4 ГЛАВА 1. МНОЖЕСТВА И ОТНОШЕНИЯ .................................................... 7 Множества и их спецификации ............................................................... 7 Отношения ..................................................................................................20 Виды отношений .......................................................................................28 Отображения и функции ........................................................................38 ГЛАВА 2. ТЕОРИЯ ГРАФОВ ...............................................................................47 Введение в теорию графов ......................................................................47 Связность графов ......................................................................................63 Маршруты и пути в графе .....................................................................76 Раскраска графов .......................................................................................91 Потоки в графах ........................................................................................98 ГЛАВА 3. КОМБИНАТОРИКА ........................................................................106 Основы комбинаторики ........................................................................106 Методы решения комбинаторных задач ............................................118 Комбинаторные алгоритмы ...................................................................127 ГЛАВА 4. МАТЕМАТИЧЕСКАЯ ЛОГИКА ....................................................135 Основы математической логики ..........................................................135 Преобразование логических функций ..............................................147 Минимизация логических функций аналитическим методом ...156 Минимизация ЛФ методом карт Карно ............................................164 ГЛАВА 5. КОНЕЧНЫЕ АВТОМАТЫ .............................................................174 Конечные автоматы без памяти ..........................................................174 Конечные автоматы с памятью ............................................................183 ЗАКЛЮЧЕНИЕ .......................................................................................................198

Стр.3

ДИСКРЕТНАЯ МАТЕМАТИКА ПРЕДИСЛОВИЕ Учебное пособие по дисциплине «Дискретная математика. Курс лекций» подготовлено в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования. Дисциплина «Дискретная математика» имеет целью сформировать у студентов в систематизированной форме понятия об основных дискретных математических структурах: множествах, комбинаторных объектах, графах, логических функциях, дискретных автоматах, изучить методы решения тождеств с множествами, комбинаторных задач, экстремальных задач теории графов, синтеза логических функций и дискретных автоматов. Изучение дисциплины способствует выработке умений применять методы дискретной математики для решения задач возникающих в процессе математического моделирования явлений конкретной предметной области, использованию алгоритмов дискретной математики для разработки вычислительных программ в различных сферах деятельности человека. Дисциплина «Дискретная математика» относится к базовой части Б.1 Блока дисциплин (модулей) ОП подготовки студентов по направлению 01.03.02 «Прикладная математика и информатика». В ходе изучения дисциплины «Дискретная математика» необходимо использовать ранее полученные знания по дисциплинам: «Математический анализ», «Высшая алгебра и аналитическая геометрия», «Основы информатики», «Алгоритмизация и программирование». В свою очередь, знания и практические навыки, полученные в ходе изучения дисциплины, используются студентами при освоении дисциплин «Информационно-логические и алгоритмические основы вычислительной техники», «Базы данных и экспертные системы», «Основы математического и информационного моделирования», «Математическое и программное обеспечение компьютерных сетей», «Вычислительные системы, сети и телекоммуникации». - 4 -

Стр.4

Предисловие Освоение дисциплины «Дискретная математика» позволит будущему бакалавру по направлению подготовки 01.03.02 – «Прикладная математика и информатика» полноценно осуществлять свою профессиональную деятельность, в частности, обладать следующими общепрофессиональными и профессиональными компетенциями: Общепрофессиональные компетенции (ОПК) 1. Способностью приобретать новые научные и профессиональные знания, используя современные образовательные и информационные технологии (ОПК-2). 2. Способностью к разработке алгоритмических и программных решений в области системного и прикладного программирования, математических, информационных и имитационных моделей, созданию информационных ресурсов глобальных сетей, образовательного контента, прикладных баз данных, тестов и средств тестирования систем и средств на соответствие стандартам и исходным требованиям (ОПК-3). Профессиональные компетенции (ПК) 1. Способностью понимать, совершенствовать и применять современный математический аппарат (ПК-2). 2. Способностью к разработке и применению алгоритмических и программных решений в области системного и прикладного программного обеспечения (ПК-7). Учебное пособие представляет курс лекций по одноименной дисциплине и включает все темы и разделы дисциплине согласно рабочей программы. В учебном пособии изложены основы теории множеств и отношений между элементами этих множеств, приведены свойства и виды отношений. Достаточно интересно изложен раздел, посвященный теории графов, в котором большое внимание отведено прикладным задачам теории графов: определению связности вершин графа, поиску кратчайших путей, раскраске графа, потокам в сетях. В комбинаторике рассмотрены не только математические подходы решению комбинаторных алгоритмов, но и приведены алгоритмы генерации выборок элементов. В разделе «Математическая логика» и «Конечные автоматы» рассмотрены аспекты использования логических функций для синтеза различных цифровых устройств. - 5 -

Стр.5

ДИСКРЕТНАЯ МАТЕМАТИКА Данное учебное пособие будет полезным не только для студентов бакалавриата направления 01.03.02 «Прикладная математика и информатика», но и для студентов практически всех направлений Института информационных технологий и телекоммуникаций, также изучающих дисциплину «Дискретная математика». - 6 -

Стр.6