Discrete Mathematics

Askerbekova Zhanar Askerbekkyzy

The instructor profile

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

Amount of credits: 5

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

  • Algebra and Geometry

Course Workload:

Types of classes hours
Lectures 15
Practical works 30
Laboratory works
SAWTG (Student Autonomous Work under Teacher Guidance) 45
SAW (Student autonomous work) 60
Form of final control Exam
Final assessment method

Component: Component by selection

Cycle: Base disciplines

Goal
  • Подготовка специалистов для проектирования архитектуры, элементов математического, информационного и программного обеспечения аппаратно-программных комплексов и систем и других видов проектно-конструкторской и проектно-технологической деятельности.
Objective
  • Приобретение студентами базовых знаний по теории графов, теории булевых функций, теории множеств, формальных исчислений.
  • На практических занятиях необходимо развить навыки составления и анализа математических моделей несложных задач прикладного характера, связанных с будущей деятельностью инженера.
Learning outcome: knowledge and understanding
  • Обладать базовыми знаниями в области дискретной математики, способствующих формированию высокообразованной личности с широким кругозором и культурой мышления.
  • Понимать фундаментальную основу современной математики и ее логическую структуру.
Learning outcome: applying knowledge and understanding
  • Применять современные математические методы при решении различных задач науки и техники. Уметь оценивать надёжность и безопасность вычислительных систем и сетей.
  • Знать и уметь использовать математические модели, методы, информационные технологии в научных исследованиях и других видах деятельности
Learning outcome: formation of judgments
  • Ставить новые научные задачи в области приложений математики к решению задач в профессиональной деятельности.
Learning outcome: communicative abilities
  • Способность работать индивидуально и в коллективе для проведения теоретических и прикладных научных исследований в области математики; международного сотрудничества в области математики и ее приложений
Learning outcome: learning skills or learning abilities
  • Опираясь на понимание фундаментальных основ современной математики и ее логической структуры, студент должен быть способен к освоению специальных дисциплин и иметь навык самостоятельной работы
Teaching methods

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

Topics of lectures
  • Множества
  • Бинарные отношения, их основные свойства
  • Важнейшие типы бинарных отношений: эквивалентности, частичные порядки, функции
  • Логика высказываний и основные булевы функции
  • Исчисление высказываний
  • Предикаты и кванторы
  • Применения матлогики в математике и информатике
  • Нормальные формы и многочлен Жегалкина
  • Полнота и замкнутость систем булевых функций
  • Проблема минимизации булевых функций
  • Методы нахождения сокращённых и тупиковых ДНФ
  • Методы нахождения минимальных ДНФ
  • Определения, начальные понятия теории графов
  • Метрические характеристики графов
  • Некоторые оптимизационные алгоритмы на графах
Key reading
  • С.В. Яблонский Введение в дискретную математику.– М., Наука, 2009.
  • С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2007.
  • И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск: ВКГТУ, 2016
  • Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
  • М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
  • В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2012.
Further reading
  • Л.Ю. Березина Графы и их применение. М.: Просвещение, 1979
  • С.Г. Горбатов Основы дискретной математики. М.: Высшая школа, 1977г.
  • Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 1992
  • С.Г. Горбатов Фундаментальные основы дискретной математики.– М.: Наука, 2000
  • И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003
  • И.В. Латкин Конспект лекций по дискретной математике. – Усть-Каменогорск: ВКГТУ, 2010.