УТВЕРЖДАЮ
Проректор по учебной работе
____________ Тритенко А.Н.
«___»______________ 2011 г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Дискретная математика
Направление подготовки: 230400.62 – информационные системы и технологии
Профиль подготовки: информационные системы и технологии
Квалификация (степень) выпускника: бакалавр
Форма обучения: очная
Факультет: электроэнергетический
Кафедра: информационные системы и технологии
Вологда
2012 г.
Составители рабочей программы
Профессор кафедры ИСиТ, д.т.н., профессор __________________ /В.В.Мухин/
(подпись)
Рабочая программа утверждена на заседании кафедры ИСиТ
Протокол заседания № ___ от «___» __________ 2012 г.
Заведующий кафедрой
«____»_______________ 2012 г. _________________ /В.А. Горбунов/
(подпись)
Рабочая программа одобрена методическим советом электроэнергетического факультета.
Протокол заседания № ______от «____»_______________ 2012 г.
Председатель методического совета
«____»_______________ 2012 г. _________________ /В.А. Бабарушкин/
(подпись)
ЦЕЛИ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ
ЦЕЛЯМИ ОСВОЕНИЯ ДИСЦИПЛИНЫ ЯВЛЯЮТСЯ: изучение основных понятий дискретной математики; необходимых для самостоятельного чтения специальной математической и теоретико-программистской литературы; овладение методами дискретной математики, наиболее употребительными при решении практических задач, связанных с обеспечением работы вычислительной техники, комплексов, систем и сетей; формирование практических навыков разработки и анализа алгоритмов дискретной математики.
МЕСТО УЧЕБНОЙ ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП ВПО
Дисциплина относится к математическому и естественно-научному циклу ООП ВПО, к дисциплине базовой части, изучается в 4 семестре.
Курс математической логики и теории алгоритмов не требует для его освоения каких-то специфических знаний из других математических дисциплин. Достаточно некоторой общей математической культуры, которая может быть приобретена студентами при изучении курсов математики и информатики. Он связан с курсами геометрии и алгебры, а также математической логики и теории алгоритмов
Сам же этот курс в известном смысле завершает математическое образование студента – бакалавра по информационным системам и технологиям.
3. КОМПЕТЕНЦИИ СТУДЕНТА, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ / ОЖИДАЕМЫЕ РЕЗУЛЬТАТЫ ОБРАЗОВАНИЯ И КОМПЕТЕНЦИИ СТУДЕНТА ПО ЗАВЕРШЕНИИ ОСВОЕНИЯ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ (МОДУЛЯ)
В результате освоения дисциплины обучающийся должен:
- Знать: основные понятия и теоремы и алгоритмы дискретной математики
· Уметь использовать методы дискретной математики при решении задач синтеза цифровых устройств и разработке программного обеспечения
- Владеть навыками разработки и анализа алгоритмов дискретной математики
В процессе обучения дисциплины формируются следующие компетенции (частично):
способность проводить сбор, анализ научно-технической информации, отечественного и зарубежного опыта по тематике исследования (ПК–23);
способность участвовать в постановке и проведении экспериментальных исследований (ПК-24);
готовность использовать математические методы обработки, анализа и синтеза результатов профессиональных исследований (ПК-26);
СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ (МОДУЛЯ)
Общая трудоемкость дисциплины составляет 3 ЗЕТ (108 час.), в том числе в семестрах:
| Семестр № | Трудоемкость | Домашняя контрольная работа | Форма промежуточной аттестации | ||||
| Всего | Аудиторная | СРС | Экз. | ||||
| ЗЕТ | час. | час. | час. | час. | |||
| 36 лек. 36 пр.. | + | Защита контрольной работы |
Взаимосвязь тем в дисциплине отражает матрица межтематических связей. Элементы матрицы характеризуют последовательность изучения тем и факт принадлежности темы в соответствии с ее содержанием к опирающейся и опорной.
Распределение результатов обучения и компетенций по семестрам, темам учебной дисциплины с указанием видов учебной деятельности и их содержания, образовательных технологий, последовательности учебных недель, трудоемкости, форм текущего контроля и промежуточных аттестаций представлено в соответствующей таблице.
Матрица межтематических связей в дисциплине
| № п/п наименование темы опорной | № п/п, наименование темы опирающейся | ||||
| 1 Множества и отношения | 2. Алгебраические структуры | 3 Булевы функции | 4. Кодирование | Графы и сети | |
| 1. Множества и отношения | + | + | + | + | |
| 2. Алгебраические структуры | + | + | + | ||
| 3Булевы функции | |||||
| 4. Кодирование | |||||
| 5. Графы и сети |
И функции
2 Операции и алгебры
Алгебраические структуры. Замыкания и подалгебры. Алгебра термов. Свойства операций. Изоморфные алгебры.
Алгебры с одной операцией
Определения. Полугруппы. Моноиды. Группы. Свойства алгебр с одной операцией. Примеры алгебр.
Алгебры с двумя операциями
Определения. Кольца. Области целостности. Поля. Свойства алгебр с двумя операциями. Примеры алгебр.
Решетки
Ограниченные решетки. Решетки с дополнением. Частичный порядок в решетке. Булева алгебра – дистрибутивная ограниченная решетка.
Матроиды
Максимальные независимые подмножества. Базисы. Ранг. Жадный алгоритм. Примеры матроидов из различных областях дискретной математики.
Графы
Задание и характеристики графов
Виды графов. Подграфы. Матрицы ассоциированные с графами. Степени вершин. Маршруты, цепи и циклы. Расстояние между вершинами. Диаметр и радиус графа.
Операции над графами
Унарные и бинарные операции над графами. Дополнение графа. Удаление и добавление вершин. Удаление и добавление ребер. Отождествление вершин. Расщепление вершин. Объединение графов. Пересечение графов. Колцевая сумма.
Связность графов
Компоненты связности. Точки сочленения. Мосты. Вершинная и реберная связность. Связность ориентированных графов. Алгоритмы вычисления связности.
Независимость и покрытия
Внутренняя устойчивость. Вершинное число независимости. Реберное число независимости. Вершинное и реберное покрытие графа. Внешняя устойчивость. Вершинное и реберное число внешней устойчивости.
Циклы и разрезы
Определения. Матрицы циклов и разрезов. Независимые множества циклов и разрезов (коциклов). Эйлеровы циклы.
Деревья
Ориентированные деревья. Упорядоченные деревья. Бинарные деревья. Дереья сортировки. Алгоритм поиска в дереве сортировки.
Булевы функции
Булевы функции
Булевы или двоичные функции. Способы задания. Булевы функции одной и двух переменных и их свойства.
Булева алгебра
Формулы булевой алгебры. Основные законы булевой алгебры. Эквивалентность формул. Принцип двойственности.
Нормальные формы представления
Конституенты единицы и нуля. Разложение булевых функций по переменным. Совершенные дизъюктивные (СДНФ) и совершенные конъюктивные нормальные формы (СКНФ). Переход от СДНФ к СКНФ и наоборот. Геометрическое представление булевых функций.
Функциональная полнота и замкнутость
Системы элементарных булевых функций. Определение функционально полной системы элементарных булевых функций. Примеры функционально полных базисов. Важнейшие замкнутые классы. Теорема о функциональной полноте. Понятие о реализации булевых функций. Условная цена реализации по Квайну.
Минимизация булевых функций
Основные понятия и определения: каноническая задача минимизации; импликанта и простая импликанта; сокращенная, тупиковая и минимальная формы; операции элементарного и неполного склеивания; операция поглощения. Метод Квайна – Мак-Клоски. Метод карт Карнау или диаграмм Вейча. Минимизация неполностью определенных функций. Минимизация конъюктивных нормальных форм. Проблема факторизации при упрощении функций. Совместная минимизация систем функций. Минимизация функций в других базисах.
Кодирование
Алфавитное кодирование. Оптимальное и помехоустойчивое кодирование. Шифрование. Применение методов дискретной математики.
