Discrete Mathematics

Askerbekova Zhanar Askerbekkyzy

The instructor profile

Description: Discipline provides fundamental mathematical training for students, focused on the use of computer models in scientific and professional activities. Discipline also forms a mechanism for estimating the quantitative parameters of discrete models and configurations and includes the main sections: set theories, formal logical theories and Boolean functions, formalizing the concept of an algorithm based on Turing machines, introducing graph theory.

Amount of credits: 3

Course Workload:

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

Component: University component

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
  • С.В. Яблонский Введение в дискретную математику.– М., Наука, 2019.
  • С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2017.
  • И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск, ВКГТУ, 2016.
  • Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
  • В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2010.
  • Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 2012.
  • А.И. Мальцев Алгоритмы и рекурсивные функции.– М.: Наука, 2012.
  • А.А. Зыков Основы теории графов.– М.: Наука. 2013.
  • А.Е. Андреев и др. Дискретная математика: прикладные задачи и сложность алгоритмов. М.: Юрайт, 2019. – 317 с.
  • В.Н. Крупский, В.Е. Плиско. Математическая логика и теория алгоритмов: Учебное пособие для студентов учреждений высшего проф. образования. М.: ИЦ Академия, 2013. – 416 с.
Further reading
  • М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
  • И.А. Лавров, Л.Л. Максимова. Задачи по теории множеств, математической логике и теории множеств. М.: Наука, 2015.
  • А.С. Морозов, Н.Г. Хисамиев. Теория алгоритмов. ВКГТУ, 2014.
  • И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003.