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

Латкин Иван Васильевич

*InstructorProfile(zh-CN)*

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

贷款数: 3

*СomplexityDiscipline(zh-CN)*:

*TypesOfClasses(zh-CN)* *hours(zh-CN)*
*Lectures(zh-CN)* 30
*PracticalWork(zh-CN)* 30
*LaboratoryWork(zh-CN)*
*srop(zh-CN)* 15
*sro(zh-CN)* 15
*FormOfFinalControl(zh-CN)* экзамен
*FinalAssessment(zh-CN)*

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

循环次数: Базовые дисциплины

Цель
  • Подготовка специалистов для проектирования архитектуры, элементов математического, информационного и программного обеспечения аппаратно-программных комплексов и систем и других видов проектно-конструкторской и проектно-технологической деятельности;. изучение основных методов дискретной математики для дальнейшего использования при решении задач анализа алгоритмов защиты информации.
Задача
  • Приобретение студентами базовых знаний по теории графов, теории булевых функций, комбинаторике, теории алгоритмов и сложности вычислений.
  • На практических занятиях необходимо развить навыки составления и анализа математических моделей несложных задач прикладного характера, связанных с будущей деятельностью инженера.
Результат обучения: знание и понимание
  • обладать базовыми знаниями в области дискретной математики, способствующих формированию высокообразованной личности с широким кругозором и культурой мышления;
  • понимать фундаментальную основу современной математики и ее логическую структуру;
Результат обучения: применение знаний и пониманий
  • применять современные математические методы при решении различных задач науки и техники, уметь оценивать надёжность и безопасность вычислительных систем и сетей;
  • знать и уметь использовать математические модели, методы, информационные технологии в научных исследованиях и других видах деятельности;
Результат обучения: формирование суждений
  • ставить новые научные задачи в области приложений математики к решению задач в профессиональной деятельности;
Результат обучения: коммуникативные способности
  • способность работать индивидуально и в коллективе для проведения теоретических и прикладных научных исследований в области математики; международного сотрудничества в области математики и ее приложений;
Результат обучения: навыки обучения или способности к учебе
  • опираясь на понимание фундаментальных основ современной математики и ее логической структуры, студент должен быть способен к освоению специальных дисциплин и иметь навык самостоятельной работы.
*TeachingMethods(zh-CN)*

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

Темы лекционных занятий
  • Основные понятия теории множеств (в основном повторение): множества, способы задания, операции над множествами и их свойства, декартово (прямое) произведение. Доказательство теоретико-множественных равенств.
  • Элементы комбинаторики. Принцип умножения, принципы сложения и дополнения. Правило включений и исключений. Перестановки, размещения и сочетания.
  • Булевы функции. Основные булевы функции, их свойства, логический смысл.
  • Двойственные функции, принцип двойственности. Существенные и фиктивные переменные. ДНФ и КНФ. Полином Жегалкина.
  • Монотонные функции. Основные замкнутые классы. Полные системы булевых функций. Теорема о полноте.
  • Необходимость формализации логики. Исчисление высказываний как пример формальной логической системы. Предикаты и кванторы. Формальные логические теории. Применения в математике и информатике.
  • Теория алгоритмов и сложность вычислений. Интуитивное понимание алгоритма, его недостаточность. Формализация понятия вычислимой функции на основе машин Тьюринга. Примеры.
  • Разновидности машин Тьюринга: многоленточные, двухсторонние, с разными алфавитами. Совпадение классов вычислимых функций.
  • Частично рекурсивные функции, совпадение с классом функций, вычислимых на машинах Тьюринга.
  • Другие формализации – алгорифмы Маркова, машины Шёнфилда, РАМ-машины и др. – упоминание; их равносильность для натуральных функций. Тезис Чёрча.
  • Алгоритмически неразрешимые проблемы: проблема остановки, примеры из логики.
  • Сложность вычислений. Полиномиальные и переборные алгоритмы. Не детерминированные вычисления. Проблема P = ? NP.
  • Теория графов. Графы и их изображения (диаграммы). Обыкновенные (простые), ориентированные графы, мультиграфы. Степени (валентности) вершин, основные ограничения на степени.
  • Изоморфизм графов. Эйлеровы и гамильтоновы обходы. Планарность. Деревья и их свойства. Способы задания графов в ЭВМ.
  • Простые экстремальные алгоритмы на графах: Дейкстры, Прима и Краскала.
Основная литература
  • С.В. Яблонский Введение в дискретную математику.– М., Наука, 2019.
  • С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2017.
  • И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск, ВКГТУ, 2016.
  • Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
  • В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2010.
  • Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 2012.
  • А.И. Мальцев Алгоритмы и рекурсивные функции.– М.: Наука, 2012.
  • А.А. Зыков Основы теории графов.– М.: Наука. 2013.
  • А.Е. Андреев и др. Дискретная математика: прикладные задачи и сложность алгоритмов. М.: Юрайт, 2019. – 317 с.
  • В.Н. Крупский, В.Е. Плиско. Математическая логика и теория алгоритмов: Учебное пособие для студентов учреждений высшего проф. образования. М.: ИЦ Академия, 2013. – 416 с.
Дополнительная литература
  • М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
  • И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории множеств. М.: Наука, 2015.
  • А.С. Морозов, Н.Г. Хисамиев. Теория алгоритмов. ВКГТУ, 2014.
  • И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003.