Место дисциплины в структуре ооп ВПО. Дисциплина «дискретная математика» относится к циклу математических дисциплин (базовой части)

Дисциплина «Дискретная математика» относится к циклу математических дисциплин (базовой части). Преподавание опирается на знание студентами следующих дисциплин: «Информатика», «Линейная алгебра», «Математический анализ».

Знания, умения и навыки, полученные в процессе изучения дисциплины, необходимы при исследовании систем управления, формальных языков, построении баз данных и будут использованы в таких дисциплинах, как «Алгоритмические языки и методы трансляции», «Базы данных», «Исследование операций», «Моделирование экономических процессов и систем».

СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Общая трудоемкость дисциплины составляет 1 семестр, 3 зачетные единицы, 108 (48 + 60) часов.

№модуля	Наименование модуля (дидактической единицы) дисциплины	Виды учебной нагрузки и их трудоемкость, часы
Лекции	Практические занятия	СРС	Всего часов
	Формальные языки и булевы функции
	Алгебраические структуры и конечные автоматы
	ИТОГО:

Содержание (дидактика) дисциплины

Модуль 1. Формальные языки и булевы функции

1.1. Формальные языки.

1.2. Булева алгебра булевых функций.

1.3. Формы представления булевой функции.

1.4. Анализ и синтез логических схем из функциональных элементов.

1.5. Анализ и синтез контактных схем.

1.6. Коды Хемминга, исправляющие ошибки.

Модуль 2. Алгебраические структуры и конечные автоматы

2.1. Основные алгебраические структуры и гомоморфизмы однотипных алгебраических структур.

2.2. Гомоморфизмы групп.

2.3. Конечные группы и циклические группы.

2.4. Арифметические кольца классов вычетов.

2.5. Детерминированные автоматы.

2.6. Минимизация автоматов.

Лекции

Номер модуля дисциплины	№ п/п	Объем, часов	Тема лекции
			Алфавиты и формальные языки. Лексикографическое упорядочение. Соответствия, отображения, функции, бинарные отношения
		Основные логические операции. Булево поле и его булево кольцо (алгебра). Линейные пространства (алгебры) над булевым полем и многомерные булевы алгебры. Булева алгебра булевых функций
		Совершенные нормальные формы и полином Жегалкина булевой функции
		Ориентированные и неориентированные графы, их классификация. Анализ и алгоритм синтеза логических схем из функциональных элементов
		Орграфы с отмеченными рёбрами. Контактные (переключательные) схемы. Анализ контактной схемы. Алгоритм синтеза контактной схемы методом каскадов
		Помехоустойчивое кодирование. Коды Хемминга
			Основные алгебраические структуры. Прямое произведение структур. Гомоморфизмы однотипных алгебраических структур и их классификация
		Гомоморфизмы групп, ядро и образ гомоморфизма, нормальные подгруппы; фактор-группа и каноническая проекция. Теорема о гомоморфизме
		Конечные группы, порядок группы и индекс её подгруппы, теорема Лагранжа; порядок элемента группы. Циклические группы и их классификация
		Арифметические кольца (поля) классов вычетов. Малая теорема Ферма
		Понятие детерминированных автоматов Мили и Мура, классификация автоматов, табличное задание автомата, диаграмма автомата, канонические уравнения
		Автоматные отображения и эквивалентность состояний автомата. Алгоритм минимизации автомата по состояниям
Итого: