Дискретная математика
Высшая школа информационных технологий и интеллектуальных систем
Направление: 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 г.
- Преподаватель: Наталья Корнеева