Программа дисциплины «Дискретная математика» Индекс дисциплины по учебному плану ен. Ф. 01. 2 Направление 230200 Информационные системы

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

Программа дисциплины

Содержание Всего часов аудиторных занятий Всего часов самостоятельной работы 2.2. Разделы дисциплины и виды занятий Содержание курса 2. Элементы комбинаторного анализа. 4. Основные понятия общей алгебры. 5. Элементы теории графов. 6. Теория кодирования. Перечень практических занятий Распределение учебных часов по темам и видам занятий

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

• Программа дисциплины «вычислительная математика» Индекс дисциплины по учебному плану:, 550.42kb.
• Программа дисциплины «информационные сети» Индекс дисциплины по учебному плану: опд., 123.28kb.
• Самостоятельная работа студентов 34 Курсовой проект. Форма итогового контроля: экзамен, 371.54kb.
• Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
• Программа дисциплины «Информационная безопасность и защита информации» Направление, 280.62kb.
• Рабочая программа учебной дисциплины дн. Ф. 13 Операционные системы Для направления, 227.68kb.
• Рабочая программа дисциплины (модуля) Дискретная математика, 101.32kb.
• Многоуровневая учебная программа дисциплины электротехника и электроника для подготовки, 409.29kb.
• Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
• Рабочая программа дисциплины (указывается шифр и наименование дисциплины по учебному, 610.49kb.

Министерство образования и науки Российской Федерации

Самарский государственный архитектурно-строительный университет

Факультет информационных систем и технологий


Утверждаю

Декан факультета ИСТ

Пиявский С.А.


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

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


Индекс дисциплины по учебному плану ЕН.Ф.01.2


Направление 230200 Информационные системы


Специальность 230201 Информационные системы и технологии


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

Всего часов на дисциплину: 156

В том числе

Аудиторных часов – 86

Самостоятельная работа студента – 71 час

Форма итогового контроля: экзамен

Курс(ы) обучения – 2

Семестр(ы) обучения – 3


Разработана: к.ф.-м.н., доц. каф. ПМ и ВТ ________________________ Трусова А.Ю.


Рассмотрена и одобрена на заседании кафедры ПМ и ВТ

от “ 30 “ ___09_____2009 г., протокол №____2________

Зав. кафедрой ____________ ________________________ Пиявский С.А.

Рассмотрена и одобрена на заседании методической комиссии

по специальности № 230201

от “ 30 “ ____09____2009 г., протокол №____2________

Председатель методической комиссии _________________ _____________ Пиявский С.А.

1. Цели и задачи изучения дисциплины
   

Курс дискретной математики – это сравнительно молодой раздел математики. Бурное развитие дискретной математики в последнее время связано с развитием вычислительной техники.

Преподавание дисциплины имеет следующие цели:

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

После изучения курса студенты должны:

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

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


2. Содержание дисциплины

2.1. Объем дисциплины и виды учебной работы (час.)

ОЧНАЯ ФОРМА ОБУЧЕНИЯ, 3-й семестр –экзамен

Вид учебных занятий	Количество часов
Всего часов аудиторных занятий	86
Лекции	52
Практические занятия (семинары)	34
Лабораторные занятия	-
Всего часов самостоятельной работы	71
Подготовка к лекционным и практическим занятиям
Подготовка к экзамену
Всего часов по дисциплине

2.2. Разделы дисциплины и виды занятий

N П/п	Раздел дисциплины	Лекции	Практ. занятия
1	Множества. Отношения	8	8
2	Элементы комбинаторного анализа.	10	8
3	Отображение.	8	4
4	Основные понятия общей алгебры	8	4
5	Элементы теории графов.	10	6
6	Теория кодирования	8	4

Содержание курса

1. Множества. Способы задания множеств. Операции над множествами. Декартово произведение множеств. Отношения. Способы задания отношений. Операции над отношениями. Примеры отношений. Операции из теории множеств, удовлетворяющие отношению эквивалентности. Замыкание отношений. Графическое представление отношений. Отношение порядка. Аксиоматика Цермеля-Френкеля.

2. Элементы комбинаторного анализа. Основное правило комбинаторики. Правило суммы. Число различных к-элементных подмножеств n-элементного множества. Геометрическая интерпретация. Формула симметрии. Формула сложения. Свойство числа сочетаний. Число подмножеств данного множества. Перестановки и размещение упорядоченных множеств. Перестановки с повторениями. Размещение элементов множества. Комбинации элементов с повторениями. Бином Ньютона. Полиномиальная теорема. Свойства биномиальных коэффициентов. Свойства биномиальных коэффициентов. Метод рекуррентных соотношений. Метод включений и исключений.

3. Отображение. Способы задания отображений. Инъекция. Сюръекция. Биекция. Принцип биекции. Разложение целых чисел. Мультимножества и действия над ними. Числа Стирлинга. Числа Белла. Естественная факторизация отображений. Прообразы и образы. Естественная факторизация. Число сюръекций. Числа Стирлинга первого рода. Оценки и асимптотики для комбинаторных чисел.

4. Основные понятия общей алгебры. Универсальные алгебры. Общие сведения. Гомоморфизмы универсальных алгебр. Язык (алгебра) термов. Произвольные операции и конечные алгебры. Свободные алгебры: а) абсолютно свободные алгебры; б) свободный группоид; в) свободные полугруппы; г) свободная коммутативная полугруппа; д) свободные группы; е) свободные абелевы группы; ж) свободное кольцо. Векторные пространства. Булева алгебра. Законы булевой алгебры. Приведение к конъюнктивно нормальной форме. Принцип двойственности. Принцип двойственности в булевой алгебре. Алгебра Жегалкина.

5. Элементы теории графов. Определение графов и их разновидности. Лемма о рукопожатии. Разновидности графов. Изоморфизм графов. Подграфы. Операции над графами. Свойства графов. Эйлеровы графы. Задача Эйлера для кёнигсбергских мостах. Теорема Флери. Гамильтоновы графы. Некоторые свойства гамильтоновых графов. Матрицы графов. Деревья и лес. Покрывающее дерево связного графа. Планарность и укладка графов. Жорданова кривая на плоскости. Теорема Жордана. Гомеоморфность графа. Теорема Понтрягина-Куратовского. Грани плоского графа. Формула Эйлера. Раскраска графов. Хроматическое число. Правильная раскраска. Хроматические числа некоторых графов. Деревья и сети. Укладка корневого дерева. Код дерева. Двухполюсные сети (основные понятия). Разложение сетей.

6. Теория кодирования. Понятие сообщения. Способы описания источника сообщения. Алфавитное кодирование и декодирование. Критерий однозначности декодирования. Инверсный подход. Теорема Маркова. Алгоритм распознавания однозначного декодирования. Неравенство МакМилана. Коды с минимальной избыточностью (Коды Хоффмана). Алгоритм Хоффмана. Самокорректирующиеся коды. Типы ошибок. Помехоустойчивое кодирование. Сжатие данных. Методы аддитивного сжатия.

Перечень практических занятий

№	Наименование темы занятия	Номер темы программы	№ неде-ли
1	Множества. Способы задания множеств.	1
2	Операции над множествами. Декартово произведение множеств.	1
3	Отношения. Способы задания отношений. Операции над отношениями.	1
4	Отношение эквивалентности. Замыкание отношений.	1
5	Основное правило комбинаторики. Правило суммы. Число различных к-элементных подмножеств n-элементного множества.	2
6	Геометрическая интерпретация. Формула симметрии. Формула сложения. Свойство числа сочетаний. Число подмножеств данного множества. Перестановки и размещение упорядоченных множеств.	2
7	Перестановки с повторениями. Размещение элементов множества. Комбинации элементов с повторениями.	2
8	Бином Ньютона. Полиномиальная теорема. Свойства биномиальных коэффициентов. Свойства биномиальных коэффициентов. Метод включений и исключений.	2
9	Способы задания отображений. Инъекция. Сюръекция. Биекция. Разложение целых чисел. Мультимножества и действия над ними.	3
10	Числа Стирлинга. Числа Белла. Число сюръекций. Числа Стирлинга первого рода.	3
11	Булева алгебра. Законы булевой алгебры. Приведение к конъюнктивно нормальной форме. Принцип двойственности.	4
12	Алгебра Жегалкина.	4
13	Лемма о рукопожатии. Разновидности графов. Изоморфизм графов. Подграфы. Операции над графами. Свойства графов. Эйлеровы графы. Задача Эйлера о кёнигсбергских мостах. Теорема Флери. Гамильтоновы графы. Матрицы графов.	5
14	Деревья и лес. Покрывающее дерево связного графа. Планарность и укладка графов. Гомеоморфность графа. Грани плоского графа. Формула Эйлера. Раскраска графов. Хроматическое число. Правильная раскраска. Хроматические числа некоторых графов.	5
15	Деревья и сети. Укладка корневого дерева. Код дерева. Двухполюсные сети (основные понятия). Разложение сетей.	5
16	Алфавитное кодирование и декодирование. Критерий однозначности декодирования. Инверсный подход. Теорема Маркова. Алгоритм распознавания однозначного декодирования.	6
17	Неравенство МакМилана. Коды с минимальной избыточностью (Коды Хоффмана). Алгоритм Хоффмана. Самокорректирующиеся коды. Типы ошибок. Помехоустойчивое кодирование. Сжатие данных. Методы аддитивного сжатия.	6

Распределение учебных часов по темам и видам занятий

№ темы	Название разделов и тем
		Лекции (кол-во часов)	Практ. Занятия (кол-во часов)	Аудит. Занятия (кол-во часов)	№ уч. недели
	Раздел 1. Множества и отношения
1	Множества. Операции над множествами	2	4	6
	Отношения.	6	4	10
	Раздел 2. Элементы комбинаторного анализа.
2	Основное правило комбинаторики. Размещения, сочетания, перестановки.	4	4	8
	Формула симметрии. Формула сложения. Свойство числа сочетаний.	2	2	4
	Метод рекуррентных соотношений. Метод включений и исключений.	4	2	6
3	Раздел 3. Отображения
	Способы задания отображений. Разложение целых чисел. Мультимножества и действия над ними. Числа Стирлинга. Числа Белла.	4	2	6
	Естественная факторизация отображений. Число сюръекций. Числа Стирлинга первого рода. Оценки и асимптотики для комбинаторных чисел.	4	2	6
4	Раздел 4. Основные понятия общей алгебры
	Универсальные алгебры.	4	2	6
	Булева алгебра и алгебра Жегалкина	4	2	6
5	Раздел 5. Элементы теории графов.
	Разновидности графов	6	2	8
	Хроматическое число	2	2	4
	Деревья и сети	2	2	4
6	Раздел 6. Теория кодирования
	Алфавитное кодирование и декодирование.	4	2	6
	Сжатие данных.	4	2	6
ИТОГО:		52	34	86

Литература.

Основная:

1. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.:БХВ-Петербург, 2006. – 400 с.
   
2. Капитонова Ю.В. и др. Лекции по дискретной математике. – СПб.: БХВ-Петербург, 2004. – 624 с.
   
3. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001. – 304 с.
   
4. Гаврилов Г. П., Сапоженко А. А. "Задачи и Упражнения по Курсу Дискретной Математики". Москва, ФИЗМАТЛИТ, 2004. – 416 с.
   

Дополнительная

1. Яблонский С. В. "Введение в Дискретную Математику". Москва, Наука, 1986.
   
2. Нефедов, Осипова. "Курс Дискретной Математики". Москва, Издательство МАИ, 1992.
   
3. Мощенский В. А. "Элементы Комбинаторики и Теории Конечных Графов". Минск, БГУ, 1992.
   

Приложение. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ (МАТЕРИАЛЫ) ДЛЯ ПРЕПОДАВАТЕЛЯ.

Курс дискретной математики требует от студентов умения абстрагироваться и грамотно оперировать математическими категориями. С этой целью рекомендуется использовать лекции- дискуссии. На семинарских занятиях можно использовать, так называемые деловые игры. Студенты могут быть разделены на группы, каждая из которых самостоятельно придумывает задачи. Уровень сложности задач, скорость решения, грамотное объяснение также предлагается оценивать группам-соперникам. Деловые игры рекомендуется использовать при изучении теории множеств, теории отношений, комбинаторики, теории графов.

Приложение. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ.

Широкое использование Интернета позволяет облегчить поиск информации, однако усвоение найденной информации – это качественно более высокий уровень получения знаний.

Рекомендуется систематически повторять основные понятия и законы дискретной математики. Постоянно поддерживать навыки решения «ключевых» задачи теории множеств и теории графов. Задачи по темам «Множества», «Отношения» рекомендуется решать, используя аналитические методы, наряду с графическими методами, которые являются более простыми и наглядными. Задачи раздела композиция отношений рекомендуется решать по матрицам отношений, что исключает возможность появления ошибок. Задачи комбинаторного анализа рекомендуется решать, используя основные правила комбинаторики, учитывая наличие повторений. Задачи по теории графов требуют большого внимания. Рекомендуется построить матрицы графов, а затем провести их анализ. Демонстрировать знания и умения на промежуточных и итоговом формах контроля знаний.

Инновационные методы в высшем и профессиональном образовании:

• электронные учебники и учебные пособия;
  
• мультимедийные учебники и пособия;
  
• компьютерные диалоговые учебники;
  
• электронные ресурсы библиотеки;
  
• лекционные презентации;
  
• видеолекции и материалы на СD;
  
• аудиолекции и материалы на CD;
  
• электронные практикумы;
  
• компьютерные обучающие и расчетные программы;
  
• использование ресурсов Internet;
  

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

2. выполнение домашних работ;
   
3. выполнение аудиторных контрольных работ.
   
4. контроль остаточных знаний;
   
5. экзамен.
   

Контроль остаточных знаний. Список вопросов.

1.Множества. Способы задания множеств. Операции над множествами.

2. Декартово произведение множеств. Отношения.

3. Способы задания отношений. Операции над отношениями. Операции из теории множеств, удовлетворяющие отношению эквивалентности.

4. Замыкание отношений. Графическое представление отношений. Отношение порядка.

5. Аксиоматика Цермеля-Френкеля.

6. Основное правило комбинаторики. Правило суммы.

7. Число различных к-элементных подмножеств n-элементного множества.

8. Формула симметрии. Формула сложения. Свойство числа сочетаний.

9. Число подмножеств данного множества.

10. Перестановки и размещение упорядоченных множеств.

11. Перестановки с повторениями. Размещение элементов множества.

12. Бином Ньютона. Свойства биномиальных коэффициентов.

13. Метод рекуррентных соотношений.

14. Метод включений и исключений.

15. Отображение. Способы задания отображений. Инъекция. Сюръекция. Биекция.

16. Язык (алгебра) термов.

17. Булева алгебра. Законы булевой алгебры.

18. Определение графов и их разновидности. Лемма о рукопожатии.

19. Разновидности графов. Изоморфизм графов.

20.Операции над графами. Свойства графов.

21.Эйлеровы графы. Задача Эйлера для кёнигсбергских мостах. Теорема Флери.

22. Гамильтоновы графы. Некоторые свойства гамильтоновых графов.

23. Матрицы графов.

24. Планарность и укладка графов. Гомеоморфность графа. Теорема Понтрягина-Куратовского.

25. Грани плоского графа. Формула Эйлера.

26. Раскраска графов. Хроматическое число. Правильная раскраска. Хроматические числа некоторых графов.

27. Деревья и лес.

28. Деревья и сети. Код дерева.

29. Двухполюсные сети. Разложение сетей.

Список вопросов к экзамену по дискретной математике

1. Множества. Способы задания множеств.
   
2. Операции над множествами.
   
3. Декартово произведение множеств. Отношения.
   
4. Способы задания отношений. Операции над отношениями.
   
5. Примеры отношений.
   
6. Операции из теории множеств, удовлетворяющие отношению эквивалентности.
   
7. Замыкание отношений.
   
8. Графическое представление отношений.
   
9. Отношение порядка.
   
10. Аксиоматика Цермеля-Френкеля.
    
11. Элементы комбинаторного анализа. Основное правило комбинаторики. Правило суммы.
    
12. Число различных к-элементных подмножеств n-элементного множества. Геометрическая интерпретация. Формула симметрии. Формула сложения. Свойство числа сочетаний.
    
13. Число подмножеств данного множества.
    
14. Перестановки и размещение упорядоченных множеств.
    
15. Перестановки с повторениями.
    
16. Размещение элементов множества.
    
17. Комбинации элементов с повторениями.
    
18. Бином Ньютона. Полиномиальная теорема. Свойства биномиальных коэффициентов. Полезные свойства биномиальных коэффициентов.
    
19. Метод рекуррентных соотношений.
    
20. Метод включений и исключений.
    
21. Отображение. Способы задания отображений.
    
22. Инъекция.
    
23. Сюръекция.
    
24. Биекция. Принцип биекции.
    
25. Разложение целых чисел.
    
26. Мультимножества и действия над ними.
    
27. Числа Стирлинга.
    
28. Числа Белла.
    
29. Естественная факторизация отображений.
    
30. Прообразы и образы.
    
31. Естественная факторизация.
    
32. Число сюръекций.
    
33. Числа Стирлинга первого рода.
    
34. Оценки и асимптотики для комбинаторных чисел.
    
35. Основные понятия общей алгебры. Универсальные алгебры.
    
36. Общие сведения
    
37. Гомоморфизмы универсальных алгебр.
    
38. Язык (алгебра) термов.
    
39. Произвольные операции и конечные алгебры.
    
40. Свободные алгебры.
    

а) абсолютно свободные алгебры

б) свободный группоид

в) свободные полугруппы

г) свободная коммутативная полугруппа

д) свободные группы

е) свободные абелевы группы

ж) свободное кольцо

41. Векторные пространства.
    
42. Булева алгебра. Законы булевой алгебры.
    
43. Приведение к конъюнктивно нормальной форме.
    
44. Принцип двойственности.
    
45. Принцип двойственности в булевой алгебре.
    
46. Алгебра Жегалкина.
    

Элементы теории графов.

47. Определение графов и их разновидности. Лемма о рукопожатии
    
48. Разновидности графов.
    
49. Изоморфизм графов. Подграфы.
    
50. Операции над графами.
    
51. Свойства графов.
    
52. Эйлеровы графы.
    
53. Задача Эйлера для кёнигсбергских мостах. Теорема Флери.
    
54. Гамильтоновы графы.
    
55. Некоторые свойства гамильтоновых графов.
    
56. Матрицы графов.
    
57. Деревья и лес.
    
58. Покрывающее дерево связного графа.
    
59. Планарность и укладка графов.
    
60. Жорданова кривая на плоскости. Теорема Жордана.
    
61. Гомеоморфность графа.
    
62. Теорема Понтрягина-Куратовского.
    
63. Грани плоского графа. Формула Эйлера.
    
64. Раскраска графов. Хроматическое число.
    
65. Правильная раскраска. Хроматические числа некоторых графов.
    
66. Деревья и сети. Укладка корневого дерева. Код дерева.
    
67. Двухполюсные сети (основные понятия).
    
68. Разложение сетей.