Дискретная математика

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

Количество кредитов: 3

Трудоемкость дисциплины:

Компонент: Вузовский компонент

Цикл: Базовые дисциплины

Цель

• Подготовка специалистов для проектирования архитектуры, элементов математического, информационного и программного обеспечения аппаратно-программных комплексов и систем и других видов проектно-конструкторской и проектно-технологической деятельности;. изучение основных методов дискретной математики для дальнейшего использования при решении задач анализа алгоритмов защиты информации.

Задача

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

Результат обучения: знание и понимание

• обладать базовыми знаниями в области дискретной математики, способствующих формированию высокообразованной личности с широким кругозором и культурой мышления;
• понимать фундаментальную основу современной математики и ее логическую структуру;

Результат обучения: применение знаний и пониманий

• применять современные математические методы при решении различных задач науки и техники, уметь оценивать надёжность и безопасность вычислительных систем и сетей;
• знать и уметь использовать математические модели, методы, информационные технологии в научных исследованиях и других видах деятельности;

Результат обучения: формирование суждений

• ставить новые научные задачи в области приложений математики к решению задач в профессиональной деятельности;

Результат обучения: коммуникативные способности

• способность работать индивидуально и в коллективе для проведения теоретических и прикладных научных исследований в области математики; международного сотрудничества в области математики и ее приложений;

Результат обучения: навыки обучения или способности к учебе

• опираясь на понимание фундаментальных основ современной математики и ее логической структуры, студент должен быть способен к освоению специальных дисциплин и иметь навык самостоятельной работы.

Методы преподавания

лекции и онлайн-лекции, практические занятия с применением слайдов и других средств мультимедиа, в частности, использование платформы Open edX. Интерактивные методики обеспечиваются решением индивидуальных задач студентами и коллективным обсуждением результатов и методов решения.

Темы лекционных занятий

• Основные понятия теории множеств (в основном повторение): множества, способы задания, операции над множествами и их свойства, декартово (прямое) произведение
• Элементы комбинаторики
• Булевы функции
• Двойственные функции, принцип двойственности
• Монотонные функции
• Необходимость формализации логики
• Теория алгоритмов и сложность вычислений
• Разновидности машин Тьюринга: многоленточные, двухсторонние, с разными алфавитами
• Частично рекурсивные функции, совпадение с классом функций, вычислимых на машинах Тьюринга
• Другие формализации – алгорифмы Маркова, машины Шёнфилда, РАМ-машины и др
• Алгоритмически неразрешимые проблемы: проблема остановки, примеры из логики
• Сложность вычислений
• Теория графов
• Изоморфизм графов
• Простые экстремальные алгоритмы на графах: Дейкстры, Прима и Краскала

Основная литература

• С.В. Яблонский Введение в дискретную математику.– М., Наука, 2019.
• С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2017.
• И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск, ВКГТУ, 2016.
• Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
• В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2010.
• Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 2012.
• А.И. Мальцев Алгоритмы и рекурсивные функции.– М.: Наука, 2012.
• А.А. Зыков Основы теории графов.– М.: Наука. 2013.
• А.Е. Андреев и др. Дискретная математика: прикладные задачи и сложность алгоритмов. М.: Юрайт, 2019. – 317 с.
• В.Н. Крупский, В.Е. Плиско. Математическая логика и теория алгоритмов: Учебное пособие для студентов учреждений высшего проф. образования. М.: ИЦ Академия, 2013. – 416 с.

Дополнительная литература

• М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
• И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории множеств. М.: Наука, 2015.
• А.С. Морозов, Н.Г. Хисамиев. Теория алгоритмов. ВКГТУ, 2014.
• И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003.