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

内容描述: Основные понятия теории множеств. Важнейшие виды бинарных отношений. Введение в логику высказываний. Введение в логику предикатов, кванторы. Булевы функции, их свойства. Важнейшие замкнутые классы булевых функций. Полные системы булевых функций. Минимизация булевых функций. Введение в теорию графов.

贷款数: 5

Пререквизиты:

• Алгебра и геометрия

*СomplexityDiscipline(zh-CN)*:

零件: Компонент по выбору

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

Цель

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

Задача

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

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

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

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

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

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

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

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

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

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

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

*TeachingMethods(zh-CN)*

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

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

• Множества. Основные операции над ними и их свойства. Диаграммы Эйлера-Венна.
• Бинарные отношения, их основные свойства. Граф бинарного отношения.
• Важнейшие типы бинарных отношений: эквивалентности, частичные порядки, функции. Лемма о разбиении на классы эквивалентности.
• Логика высказываний и основные булевы функции. Основные схемы логически правильных рассуждений.
• Исчисление высказываний. Сложные высказывания как булевы функции. Теорема о полноте исчисления высказываний.
• Предикаты и кванторы. Некоторые правила действий с кванторами.
• Применения матлогики в математике и информатике. Основные булевы функции и их свойства.
• Нормальные формы и многочлен Жегалкина. Двойственность и монотонность.
• Полнота и замкнутость систем булевых функций.
• Проблема минимизации булевых функций. Геометрический подход.
• Методы нахождения сокращённых и тупиковых ДНФ.
• Методы нахождения минимальных ДНФ.
• Определения, начальные понятия теории графов. Примеры. Орграфы, мультиграфы. Подграфы.
• Метрические характеристики графов. Матричные способы задания графов.
• Некоторые оптимизационные алгоритмы на графах.

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

• С.В. Яблонский Введение в дискретную математику.– М., Наука, 2009.
• С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2007.
• И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск: ВКГТУ, 2016
• Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
• М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
• В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2012.

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

• Л.Ю. Березина Графы и их применение. М.: Просвещение, 1979
• С.Г. Горбатов Основы дискретной математики. М.: Высшая школа, 1977г.
• Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 1992
• С.Г. Горбатов Фундаментальные основы дискретной математики.– М.: Наука, 2000
• И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003
• И.В. Латкин Конспект лекций по дискретной математике. – Усть-Каменогорск: ВКГТУ, 2010.