Матрица межтематических связей в дисциплине

УТВЕРЖДАЮ

Проректор по учебной работе

____________ Тритенко А.Н.

«___»______________ 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Операции и алгебры

Алгебраические структуры. Замыкания и подалгебры. Алгебра термов. Свойства операций. Изоморфные алгебры.

Алгебры с одной операцией

Определения. Полугруппы. Моноиды. Группы. Свойства алгебр с одной операцией. Примеры алгебр.

Алгебры с двумя операциями

Определения. Кольца. Области целостности. Поля. Свойства алгебр с двумя операциями. Примеры алгебр.

Решетки

Ограниченные решетки. Решетки с дополнением. Частичный порядок в решетке. Булева алгебра – дистрибутивная ограниченная решетка.

Матроиды

Максимальные независимые подмножества. Базисы. Ранг. Жадный алгоритм. Примеры матроидов из различных областях дискретной математики.

Графы

Задание и характеристики графов

Виды графов. Подграфы. Матрицы ассоциированные с графами. Степени вершин. Маршруты, цепи и циклы. Расстояние между вершинами. Диаметр и радиус графа.

Операции над графами

Унарные и бинарные операции над графами. Дополнение графа. Удаление и добавление вершин. Удаление и добавление ребер. Отождествление вершин. Расщепление вершин. Объединение графов. Пересечение графов. Колцевая сумма.

Связность графов

Компоненты связности. Точки сочленения. Мосты. Вершинная и реберная связность. Связность ориентированных графов. Алгоритмы вычисления связности.

Независимость и покрытия

Внутренняя устойчивость. Вершинное число независимости. Реберное число независимости. Вершинное и реберное покрытие графа. Внешняя устойчивость. Вершинное и реберное число внешней устойчивости.

Циклы и разрезы

Определения. Матрицы циклов и разрезов. Независимые множества циклов и разрезов (коциклов). Эйлеровы циклы.

Деревья

Ориентированные деревья. Упорядоченные деревья. Бинарные деревья. Дереья сортировки. Алгоритм поиска в дереве сортировки.

Булевы функции

Булевы функции

Булевы или двоичные функции. Способы задания. Булевы функции одной и двух переменных и их свойства.

Булева алгебра

Формулы булевой алгебры. Основные законы булевой алгебры. Эквивалентность формул. Принцип двойственности.

Нормальные формы представления

Конституенты единицы и нуля. Разложение булевых функций по переменным. Совершенные дизъюктивные (СДНФ) и совершенные конъюктивные нормальные формы (СКНФ). Переход от СДНФ к СКНФ и наоборот. Геометрическое представление булевых функций.

Функциональная полнота и замкнутость

Системы элементарных булевых функций. Определение функционально полной системы элементарных булевых функций. Примеры функционально полных базисов. Важнейшие замкнутые классы. Теорема о функциональной полноте. Понятие о реализации булевых функций. Условная цена реализации по Квайну.

Минимизация булевых функций

Основные понятия и определения: каноническая задача минимизации; импликанта и простая импликанта; сокращенная, тупиковая и минимальная формы; операции элементарного и неполного склеивания; операция поглощения. Метод Квайна – Мак-Клоски. Метод карт Карнау или диаграмм Вейча. Минимизация неполностью определенных функций. Минимизация конъюктивных нормальных форм. Проблема факторизации при упрощении функций. Совместная минимизация систем функций. Минимизация функций в других базисах.

Кодирование

Алфавитное кодирование. Оптимальное и помехоустойчивое кодирование. Шифрование. Применение методов дискретной математики.