Рабочая программа дисциплины «Дискретная математика» Направление подготовки

Вид материала

Рабочая программа

Содержание Разработка программно-информационных систем 1. Цели освоения дисциплины 2. Место дисциплины в структуре ООП бакалавриата 3. Компетенции обучающегося, формируемые в результате освоения дисциплины 4. Структура и содержание дисциплины Формы текущего контроля успеваемости (по неделям семестра) Основы теории множеств (6 часов). Бинарные отношения (8 часов). Булева алгебра (8 часов). Основы общей алгебры (4 часа). Теория графов (6 часов). Основы теории множеств (6 часов). Бинарные отношения (6 часа). Булева алгебра (8 часов). Основы общей алгебры (4 часа). 5. Образовательные технологии 7. Учебно-методическое и информационное обеспечение дисциплины

Подобный материал:

• Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
• Рабочая программа дисциплины (модуля) Дискретная математика, 101.32kb.
• Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
• Рабочая программа Наименование дисциплины дискретная математика по направлению подготовки, 201.9kb.
• Рабочая программа дисциплины «дискретная математика» Рекомендуется для направления, 220.81kb.
• Рабочая программа учебной дисциплины «Математика» Направление подготовки, 206.48kb.
• Рабочая программа учебной дисциплины ен. Ф. 01. 03 Дискретная математика для специальности, 184.39kb.
• Рабочая программа дисциплины Дискретная математика (Наименование дисциплины), 129.54kb.
• Аннатационная программа дисциплины теория вероятностей, случайные процессы направление, 46.02kb.
• Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


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

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

«Чувашский государственный университет имени И.Н.Ульянова»


Факультет дизайна и компьютерных технологий


«УТВЕРЖДАЮ»

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


______________ А.Ю. Александров


«______»______________ 20__ г.


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

«Дискретная математика»


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

231000 Программная инженерия


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

Разработка программно-информационных систем


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

Бакалавр


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

очная


Чебоксары

2011

Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению подготовки 231000 Программная инженерия, утвержденного Приказом Минобрнауки 09.11.2009 г. № 542.


Составитель: старший преподаватель Кузнецова Н.А._____________


Рабочая программа рассмотрена и одобрена на заседании обеспечивающей кафедры – компьютерных технологий (протокол № _____ от ___________2010 г.).


Зав. кафедрой: профессор Желтов В.П. ___________________


Рабочая программа согласована с Методической комиссией выпускающего факультета Дизайна и компьютерных технологий.


Председатель комиссии, декан: профессор Желтов В.П. ___________________


СОГЛАСОВАНО:

Зам. начальника УМУ: доцент Харитонов М.Ю. __________________


1. Цели освоения дисциплины


Целями освоения дисциплины «Дискретная математика» являются: ознакомление студентов второго курса с теоретическими основами дискретной математики, приобретение студентами практических навыков по решению задач дискретной математики.


2. Место дисциплины в структуре ООП бакалавриата


Дисциплина входит в базовую часть математического и естественнонаучного цикла образовательной программы бакалавра. Студент должен иметь начальные сведения об алгебре и начале анализа в объеме школьного курса. Дисциплина является предшествующей для изучения дисциплин «Математическая логика и теория алгоритмов».


3. Компетенции обучающегося, формируемые в результате освоения дисциплины


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

- владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1);

- стремится к саморазвитию, повышению своей квалификации и мастерства (ОК-6);

- способен применять методы анализа прикладной области на концептуальном, логическом, математическом и алгоритмическом уровнях (ПК-17);

- способен выбирать необходимые для организации информационные ресурсы и источники знаний в электронной среде (ПК-20);

- способен применять системный подход и математические методы в формализации решения прикладных задач (ПК-21);

- способен готовить обзоры научной литературы и электронных информационно-образовательных ресурсов для профессиональной деятельности (ПК-22);


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

• Знать:
  

-основные понятия, теоретические положения и методы дискретной математики (теории множеств и отношений, теории булевых функций, теории графов; общей алгебры).

• Уметь:
  

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

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

4. Структура и содержание дисциплины


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

Общая трудоемкость дисциплины составляет 5 зачетных единиц, 180 часов.

№ п/п	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)							Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам)
				Лекции	Практ. зан.	Лабор. зан.	КСР *	СРС **	Всего	Из ауд. зан. в интер. форме
1	Основы теории множеств.	3	1-3	6		6		12
2	Бинарные отношения.	3	4-7	8		8		12
3	Булева алгебра.	3	8-11	8		8		12
4	Основы общей алгебры.	3	12-13	4		4		12
5	Теория графов.	3	14-16	6		6		12
	Проведение экзамена	3	17				2				экзамен
	Итого			32		32	2	60			54

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

** Самостоятельная работа студента, включая курсовой проект, курсовую работу, расчетно-графические работы.


4.2. Содержание лекционных занятий


Основы теории множеств (6 часов).

Понятие множества, его элементов, способы задания множеств. Сравнение множеств. Булиан. Операции над множествами. Диаграммы Эйлера-Венна. Мощность множеств. Конечные и бесконечные множества.

Бинарные отношения (8 часов).

Декартово произведение множеств. Бинарные отношения, способы их задания. Обратные бинарные отношения. Композиция бинарных отношений. Классификация бинарных отношений (по свойствам): рефлексивные, симметричные, антисимметричные, транзитивные. Специальные бинарные отношения: отношения порядка и эквивалентности. Функциональные и всюду определенные бинарные отношения. Виды отображений: инъекции, сюрьекции, биекции. Композиции отображений.

Булева алгебра (8 часов).

Алгебра логики. Булевы функции, способы их задания. Таблицы элементарных булевых функций. Суперпозиция функций. Равносильные функции. Нормальные формы булевых функций, совершенные нормальные формы. Применение булевых функций к релейно-контактным схемам.

Основы общей алгебры (4 часа).

Алгебраические операции, их свойства, носитель алгебры. Поле, полугруппа, моноид, группа, абелева группа. Гомоморфизм и изоморфизм алгебр.

Теория графов (6 часов).

Понятие графа. Виды графов. Способы представления графов. Операции над графами. Цепи и циклы графов. Связные графы. Минимальные пути в графах. Деревья. Раскраска графов. Сети.


4.4. Содержание лабораторных занятий


Основы теории множеств (6 часов).

Способы задания множеств. Операции над множествами. Способы доказательств. – 2 часа.

Диаграммы Эйлера-Венна. Упрощение выражений теории множеств. – 4 часа.

Бинарные отношения (6 часа).

Бинарные отношения, способы их задания. Обратные бинарные отношения. Композиция бинарных отношений. – 2 часа.

Специальные бинарные отношения. – 2 часа.

Виды отображений. Композиции отображений. – 2 часа.

Булева алгебра (8 часов).

Булевы функции, способы их задания. Таблицы истинности функций. Равносильные функции. – 2 часа.

Нормальные и совершенные нормальные формы булевых функций. – 4 часа.

Применение булевых функций к релейно-контактным схемам. – 2 часа.

Основы общей алгебры (4 часа).

Основные алгебраические структуры. – 4 часа.

Теория графов (8 часов).

Виды графов. Способы представления графов. Операции над графами. – 2 часа.

Цепи и циклы графов. – 2 часа.

Минимальные пути в графах. – 2 часа.

Деревья. Раскраска графов. Сети. – 2 часа.


5. Образовательные технологии


В процессе изучения дисциплины используются:


-раздаточный материал для изучения лекционного материала;

-учебный материал в электронном виде;

-контрольные программы по курсу для подготовки к сдаче семестровой аттестации и экзамена;

-программное обеспечение в соответствии с содержанием дисциплины;


6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.


6.1. Перечень заданий для самостоятельной работы и проведения текущего контроля.


Варианты тестовых заданий.


6.3. Перечень вопросов к промежуточной аттестации.


1. Понятие множества, его элементов, способы задания множеств.

2. Мощность множеств. Конечные и бесконечные множества.

3. Декартово произведение множеств.

4. Бинарные отношения, способы их задания.

5. Обратные бинарные отношения. Композиция бинарных отношений.

6. Классификация бинарных отношений.

7. Специальные бинарные отношения: отношения порядка

8. Специальные бинарные отношения: эквивалентности.

9. Виды отображений: инъекции, сюръекции, биекции.

10. Композиции отображений.

11. Булевы функции, способы их задания.

12. Таблицы элементарных булевых функций.

13. Суперпозиция функций.

14. Равносильные функции.

15. Нормальные формы булевых функций, совершенные нормальные формы.

16. Применение булевых функций к релейно-контактным схемам.

17. Алгебраические операции, их свойства.

18. Поле, полугруппа, моноид, группа, абелева группа.

19. Гомоморфизм и изоморфизм алгебр.

20. Понятие графа. Виды графов. Способы представления графов.

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

22. Цепи и циклы графов.

23. Минимальные пути в графах.

24. Деревья.

25. Раскраска графов.

26. Сети.


7. Учебно-методическое и информационное обеспечение дисциплины


а) основная литература:

1. Березина Л.Ю. Графы и их применения. - М.: Просвещение, 1979.
   
2. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: ВШ, 1976.
   
3. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: учеб. пособ.- М.: Форум: ИНФРА-М, 2007.
   
4. Кольман Э. Зих О. Занимательная логика. — М.: Наука, 2008. —127с.
   
5. Мендельсон Э. Введение в математическую логику. — М.: Наука, 2006. — 319с.
   
6. Набебин А.А. Логика и пролог в дискретной математике. — М.: МЭИ, 2006. —452с.
   
7. Нефедов В.Н., Осипова В.А. Курс дискретной математики — М.: Издательство МАИ, 2008. — 264с.
   
8. Новиков Ф.А. Дискретная математика для программистов. Санкт-Петербург. Питер, 2001.
   
9. Рембольд У. Введение в информатику для научных работников и инженеров. — Уфа: УГАТУ, 2007. —445с.
   
10. Спирина М.С. Дискретная математика: учеб. – М.: Академия, 2009.
    
11. Уилсон Р. Дж. Введение в теорию графов. - М.: 1977.
    
12. Яблонский С.В. Введение в дискретную математику. — М.: Наука, 2006. — 384 с.
    

б) дополнительная литература:

1. 
   Алексеев В.Б., Ложкин С.А. Элементы теории графов и схем. М.: Изд-во МГУ, 1991.
   
2. Андерсон Д. Дискретная математика и комбинаторика. М.: Издательский дом "Вильямс", 2004.
   
3. Басакер П., Саати Т. Конечные графы и сети. М.: Наука, 1974.
   
4. Бахтияров К.И. Логика с точки зрения информатики: бестселлер в духе Льюиса Кэрролла (12 этюдов). М.: Едиториал УРСС, 2002.
   
5. Белов В.В. и др. Теория графов. М.: Высл. Школа, 1976.
   
6. Березина Л.Ю. Графы и их применение. М.: Просвещение, 1979.
   
7. Берж К. Теория графов и ее применения. М.: ИЛ, 1962
   
8. Болтянский В.Г., Савин А.П. Беседы о математике. Книга 1. Дискретные объекты. М.: ФИМА, МЦНМО, 2002
   
9. Варпаховский Ф.Л., Солодовников А.С. Алгебра. Ч.1. М.: Просвещение, 1988.
   
10. Варпаховский Ф.Л., Солодовников А.С., Стеллецкий И.В. Алгебра. Ч. 2. М.: Просвещение, 1989.
    
11. Виленкин Н.Я. Комбинаторика. М.: Наука, 1969.
    
12. Виленкин Н.Я. Популярная комбинаторика. М.: Наука, 1975.
    
13. Виленкин Н.Я. Рассказы о множествах. – М.: МЦНМО, 2004
    
14. Гиндикин С.Г. Алгебра логики в задачах. М. Наука, 1972.
    
15. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. М.: Наука, 1977
    
16. Емеличев В.А., Мельников О.И., Сарванов В.А., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.
    
17. Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1979.
    
18. Зыков А.А. Основы теории графов. М.: Наука, 1987
    
19. Клини С.К. Математичекая логика, М.: Наука, 1973.
    
20. Комбинаторный анализ. Задачи и упражнения / Под ред. К.А. Рыбникова. М.: Наука, 1982.
    
21. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику, М.: МГУ, 1982.
    
22. Кострикин А.И. Введение в алгебру. М.: Высшая школа, 2001.
    
23. Кострикин А.И. Сборник задач по алгебре. М.: Высшая школа, 2000.
    
24. Кристофидес  Н.  Теория графов:  алгоритмический подход. М.: Мир, 1978.
    
25. Кофман А. Введение в прикладную комбинаторику. М.: Радио и связь, 1982.
    
26. Курош А.Г. Курс общей алгебры. М.: Высшая школа, 2000.
    
27. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
    
28. Мальцев А.И. Алгебраические системы, М.: Наука, 1970.
    
29. Мальцев А.И. Алгоритмы и рекурсивные функции, М.: Наука, 1965.
    
30. Мендельсон Э. Введение в математическую логику, М.: Мир, 1984.
    
31. Оре О. Графы и их применение. М.: Едиториал УРСС, 2002.
    
32. Оре О. Теория графов. М.: Наука, 1980.
    
33. Свами М., Тхуласираман К. Графы, сети, алгоритмы. М.: Мир, 1984.
    
34. Сидоренко Е.А. Логика. Парадоксы. Возможные миры. М.: Едиториал УРСС, 2002
    
35. Столл Р. Множества. Логика. Аксиоматические теории. М.: Мир, 1971.
    
36. Уилсон Р.. Введение в теорию графов. М.: Мир, 1977.
    
37. Фрид Э. Элементарное введение в абстрактную алгебру. М.: Мир, 1989.
    
38. Харари Ф. Теория графов. М.: Едиториал УРСС, 2003.
    
39. Энциклопедия элементарной математики, книга 1. Государственное издательство технико-теоретической литературы, 1951 г. 
    
40. Яглом И.М. О комбинаторной геометрии. М.: Едиториал УРСС, 2004.
    

8. Материально-техническое обеспечение дисциплины

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