Институт информационных технологий и интеллектуальных систем

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

Высшая школа информационных технологий и интеллектуальных систем  

Направление: 09.03.04 «Программная инженерия»

Учебный план: «Технологии разработки информационных систем» (очное, 2019)

Дисциплина: «Дискретная математика» (бакалавриат, 1 курс, очное обучение)

Количество часов: 288 ч. (в том числе: лекции – 72, лабораторные занятия – 72, самостоятельная работа – 108), форма контроля:  зачет и экзамен (36 часов).

Аннотация: В ЭОР изложены основные разделы курса «Дискретная математика», изучаемые на первом курсе студентами Высшей школы информационных технологий и интеллектуальных систем. Курс содержит теоретический материал, материал для практических занятия, приводятся примеры решения типовых задач. Также  ЭОР содержит промежуточные тесты по изучаемым темам и итоговые тесты для промежуточных и итоговых форм контроля дисциплины - зачёта в первом семестре и экзамена во втором семестре.

Темы: 

1. Основные понятия теории булевых функций. Дизъюнктивные и конъюнктивные нормальные формы.

2. Замкнутые и полные классы булевых функций. Теорема Поста о полноте.

3. Леса и деревья. Нахождение остова наименьшего веса.

4. Основные понятия теории ориентированных графов. Нахождение кратчайшего пути.

5. Потоки в сетях. Нахождение максимального потока и минимального разреза.

6. Конечные детерминированные и недетерминированные автоматы, регулярные языки. Регулярные выражения

7. Машины Тьюринга. Вычислимые и частично вычислимые функции.

Ключевые слова: булевы функции, неориентированные графы, ориентированные графы, детерминированные автоматы, недетерминированные автоматы, регулярные выражения, машина Тьюринга, вычислимость 

Автор ЭОР:  Корнеева Наталья Николаевна, доцент кафедры алгебры и математической логики, кандидат физико-математических наук, тел.: (843) 233-70-39 , email: Natalia.Korneeva@kpfu.ru.

Дата начала эксплуатации:  27 мая 2020 г.