МИНОБРНАУКИ РОССИИ

Федеральное государственное автономное образовательное

учреждение высшего профессионального образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Факультет математики, механики и компьютерных наук

УТВЕРЖДАЮ

Декан факультета математики, механики

и компьютерных наук

________________________М. И.Карякин

«03» июля 2012 г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

«Дискретная математика и математическая логика»

Направление подготовки

математика 010100

Профиль подготовки общий

Квалификация (степень) выпускника

Бакалавр

Кафедра алгебры и дискретной математики

Курс 1 семестры 1 и 2

Форма обучения очная

Программа разработана Г., ст. преподаватель

А., доцент, к. ф.-м. н.

Рецензент(ы) О., должность, уч. степень, уч. звание

Ростов-на-Дону - 2012

Рассмотрена и рекомендована к Рассмотрена и рекомендована к утверждению на заседании учебно - утверждению на заседании кафедры методического совета факультета алгебры и дискретной математики математики, механики и компьютер - протокол заседания ных наук, направление подготовки от _________________ №_________ «Математика» протокол заседания от _________________ № ________

СОГЛАСОВАНО

Протокол заседания кафедры/учебно -

методического совета факультета

_________________________________

(название выпускающей кафедры/

факультета, реализующего ООП ВПО)

от ______________ № _____________

I. ЦЕЛИ И ЗАДАЧИ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Цели освоения дисциплины (модуля): основной целью курса является овладение студентами основами дискретной математики и математической логики.

НЕ нашли? Не то? Что вы ищете?

Задачи: освоение методов исследования, применяемые в дискретной математике и математической логике, изучение областей приложения их как в других разделах математики, так и в других научных дисциплинах.

II. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП ВПО

2.1. Учебная дисциплина «Дискретная математика и математическая логика» относится к циклу Б3 «Профессиональный цикл».

2.2. Для изучения данной учебной дисциплины необходимо знание элементарной математики на уровне средней общеобразовательной школы.

2.3. Перечень последующих учебных дисциплин, для которых необходимы знания, умения и навыки, формируемые данной учебной дисциплиной:

- алгебра,

- аналитическая геометрия,

- математический анализ,

- функциональный анализ,

- теория вероятностей и математическая статистика,

- теория случайных процессов,

- дисциплины компьютерного цикла.

Курс «Дискретная математика и математическая логика» входит в базовую часть учебного цикла Б3 «Профессиональный цикл». Настоящий курс связан с такими базовыми курсами, как алгебра, аналитическая геометрия, математический анализ, дисциплины компьютерного цикла.

Разделы курса, необходимые для изучения других дисциплин: алгебра высказываний, исчисление высказываний и предикатов – дисциплины компьютерного цикла, физика; предикаты и кванторы – математический анализ, алгебра, функциональный анализ; теория отображений – математический анализ, функциональный анализ; элементы комбинаторики – алгебра, математический анализ, теория вероятностей и математическая статистика: алгебры отношений и 0-1 матриц – дисциплины компьютерного цикла, алгебра; булевы функции – дисциплины компьютерного цикла; элементы теории алгоритмов – дисциплины компьютерного цикла, численные методы.

Требования к знаниям студентов, начинающих изучение курса «Дискретная математика»: знание элементарной математики на уровне средней общеобразовательной школы.

Для оценки успешности освоения курса по окончании изучения каждого модуля студентам предлагается тестирование и, кроме того, для первого и четвертого модуля – контрольная работа.

Зачет (в первом семестре) выставляется при достижении удовлетворительных результатов всех тестирований и контрольных работ.

Итоговой формой контроля (второй семестр) является экзамен.

III. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ «Дискретная математика и математическая логика»

В результате освоения дисциплины обучающийся должен:

ЗНАТЬ:

- основные понятия, их свойства и теоретические положения алгебры высказываний и предикатов, теории множеств и отображений, комбинаторики, исчисления высказываний и предикатов, теории графов и теории алгоритмов

- общие формы, закономерности и инструментальные средства дискретной математики и математической логики ПК-1

УМЕТЬ:

- решать комбинаторные задачи, исследовать типы отображений и бинарных отношений, приводить формулы алгебры высказываний к нормальным формам, строить выводы в логике высказываний и предикатов, определять функциональную полноту системы булевых функций, применять алгебру логики к теории переключательных схем

- находить, анализировать и контекстно обрабатывать научно-техническую информацию ОК-10

- демонстрировать способность к анализу и синтезу ОК-14

- демонстрировать способность к письменной и устной коммуникации на русском языке ОК-15

- понимать поставленную задачу в рамках дисциплины ПК-2

- формулировать результат ПК-3

- строго доказывать утверждение ПК-4

- на основе анализа увидеть и корректно сформулировать результат ПК-5

- самостоятельно увидеть следствия сформулированного результата ПК-6

- ориентироваться в постановках задач ПК-8

- выделять главные смысловые аспекты в доказательствах ПК-16

- публично представить собственные и известные научные результаты ПК-18

ВЛАДЕТЬ:

- навыками преобразования логических формул и формул теории множеств, методами минимизации булевых формул, формализацией понятия алгоритма в виде машины Тьюринга

- проблемно-задачной формой представления математических знаний ПК-22

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

4.1. Содержание модулей дисциплины

№ модуля	Наименование модуля	Содержание модуля	Формы текущего контроля
1	2	3	4
1.	Алгебра высказываний	Опреации над высказываниями, формулы алгебры высказываний, двойственность, нормальные формы, основные проблемы алгебры высказываний, релейно-контактные схемы	Контрольная работа №1 Тестирование
2.	Алгебры предикатов и множеств	Операции над предикатами, кванторы, операции над множествами, системы множеств	Тестирование
3.	Теория отображений	Образ и прообраз при отображении, типы отображений, обратимость и односторонняя обратимость	Тестирование
4.	Элементы комбинаторики	Основной принцип комбинаторики, аксиомы, декартово произведение, размещения, перестановки, Бином Ньютона, тождество Вандермонда, сочетания, сочетания с повторениями	Контрольная работа №2
5.	Алгебры отношений и «0-1» матриц	Типы отношений, операции над отношениями, отношения порядка, доминирование, отношения эквивалентности, классы эквивалентности, фактор-множество	Тестирование
6.	Булевы функции	Многочлены Жегалкина, классы Поста, полнота и замыкание, предполные классы	Тестирование
7.	Элементы теории алгоритмов	Машина Тьюринга, итерации, разветвление и объединение машин, понятие об универсальном алфавите, алгоритмическая неразрешимость	Тестирование
8.	Элементы теории графов	Локальные характеристики графа, пути, цепи, контуры, циклы, части графа, мосты и точки сочленения, эйлеровость графов, деревья и леса, пространства циклов и разрезов	Тестирование

4.2. Структура дисциплины.

Общая трудоемкость дисциплины составляет 6 зач. ед. (216 часов).

Вид работы	Трудоемкость, часов
	семестр 1	семестр 2	Всего
Общая трудоемкость	126	90	216
Аудиторная работа:	52	34	86
Лекции (Л)	36	34	70
Практические занятия (ПЗ)	16	0	16
Самостоятельная работа:	74	56	130
Самоподготовка (проработка и повторение лек-ционного материала и материала учебников и учебных пособий, подготовка к лабораторным и практическим занятиям, коллоквиумам, рубежному контролю и т. д.)	74	20	94
Подготовка и сдача экзамена (при наличии экзамена по дисциплине)	0	36	36
Вид итогового контроля (зачет, экзамен)	зачет	экзамен

Модули дисциплины, изучаемые в семестре 1

№ модуля	Наименование модулей	Количество часов
Всего	Аудиторная работа	Вне-ауд. работа СР
Л	ПЗ	ЛР
1.	Алгебра высказываний	38	10	6	22
2.	Алгебры предикатов и множеств	24	8	4	12
3.	Теория отображений	26	6	2	18
4.	Элементы комбинаторики	24	6	4	14
5.	Алгебры отношений и «0-1» матриц	14	6		8
	Итого:	126	36	16	74