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



Скачать 67.28 Kb.
Дата17.06.2015
Размер67.28 Kb.
ТипРабочая программа

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

Воронежский государственный педагогический университет


РАБОЧАЯ ПРОГРАММА

дисциплины Дискретная математика

для подготовки специалиста по специальности 030100 «Информатика»

с дополнительной специальностью 032100 «Математика»


(1 семестр)
Трудоемкость: 90 часов

Всего: 51 час.

Из них: 17 лекционных

34 практич.

39 СРС

Форма отчетности: экзамен 1 сем.



по учебному плану 2000-2001 уч.г.

Составитель: доц. Миловская Л.С.


Программа утверждена на заседании

кафедры информатики и МПМ

10 мая 2001 г., протокол №9

Заведующий кафедрой, профессор

_______________________А.С.Потапов

Воронеж 2001



1. Пояснительная записка

Поскольку работа и функционирование компьютера - это дискретный процесс, то роль дискретной математики, как самостоятельной дисциплины резко возросло. В настоящее время для многих учебных курсов, построенных для самой разнообразной учебной аудитории, считается необходимым включение общих ознакомительных или более глубоких, специальных разделов дискретной математики. Настоящий курс представляет собой первое систематическое знакомство с предметом. Курс обобщает данные в математических и компьютерных дисциплинах понятие дискретности. Целью курса является выделение некоторых дискретных задач и изучение общих методов решения дискретных задач на примерах выделенных – рекуррентных соотношениях основных разделов теории графов. Данный курс находит продолжение в ряде других курсов специальности, также изучающих задачи дискретной математики. Это такие курсы, как элементы абстрактной и компьютерной алгебры, элементы теории алгоритмов, теоретические основы информатики, исследование операций, элементы математической логики и ряд других. По курсу предполагается провести 1 контрольную работу.



2. Тематическое планирование


Тема


Всего в трудоемкости

В том числе

аудиторных



СРС

Всего

Лекции

Практ.

1.

Рекуррентные соотношения. Примеры. Методы решения рекуррентных соотношений

11


6


2


4


5

2.

Суммы и рекуррентности. Кратные суммы. Методы суммирования.

11


6


2


4

5

3.

Асимптотические методы. Формула суммирования Эйлера

11


6


2

4


5

4.

Элементы теории графов. Основные понятия теории графов.

21


12


4


8

9

5.

Деревья. Характеризационная теорема

11

6


2


4

5

6.

Планарные, плоские графы. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига

14


9


3


6

5

7.

Раскрашивание планарного графа 5 красками. Гипотеза 4-х красок.

11


6


2


4

5




Всего:

90

51

17

34

39



3. Содержание учебной дисциплины

1. Элементы комбинаторики. Размещения, сочетания, перестановки без повторений и с повторениями. Бином Ньютона. Биномиальные коэффициенты и их свойства. Полиномиальная теорема. Биномиальные коэффициенты и их свойства. Полиномиальная теорема. Основные комбинаторные конфигурации. Метод включений и исключений.

2. Реккурентные соотношения. Однородные и неоднородные рекуррентные соотношения. Способы решения реккурентных соотношений. Суммы и рекуррентности. Некоторые целочисленные функции.

3. Введение в асимптотические методы. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера.

4. Основные понятия теории графов. Связные графы. Изоморфные графы. Эйлеровы и гамильтоновы графы. Ориентированные и неориентированные графы, Задание графов с помощью матриц смежности и инцидентности. Паросочетания, независимые множества, клики.

5. Деревья. Характеризационная теорема. Примеры деревьев. Некоторые применения.

6. Определение планарного и плоского графа. Примеры планарных и непланарных графов, Графы К5 и К3.,3. Критерии планарности графа. Теорема о реализации любого графа в трехмерном пространстве. Формула Эйлера и следствия из нее.

7. Раскраска вершин графа. Хроматическое число графа. Критерий двуцветности графа. Раскраска ребер графа. Хроматический индекс графа. Двудольные графы. Критерий двудольности (теорема Кенига): граф является двудольным тогда и только тогда, когда все его простые циклы четны.

8. Теорема о 5 красках: каждый планарный граф 5-раскрашиваем. Гипотеза 4-х красок: каждый планарный граф 4-х раскрашиваем. Некоторые частные решения гипотезы 4-х красок. Раскраска плоской карты.
4. РЕКОМЕНДАЦИИ ПО ОРГАНИЗАЦИИ РАБОТЫ СТУДЕНТОВ

По всем разделам проводятся практические занятия и последующей проверкой домашней работы. Следующие задачи предлагают частично для самостоятельного решения, частично разбираются в аудитории. Эти задачи выносятся на экзамен. На самостоятельное изучение выносится также ряд вопросов комбинаторики, связанных со школьным курсом математики: проверка основных свойств комбинаторики чисел, бином Ньютона и его свойства. Рекомендуемая литература [6]



5. ЛИТЕРАТУРА


Основная:

1. Новиков Ф.А. Дискретная математика для программистов. –СПб.: Питер, 2001.



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

2. Еменичев Р.И., Мельников О.И. и др. Лекции по теории графов. -М.: Наука, 1990,393с.

3. Микерова Л.Н., Чулюков В.А. Элементы теории графов в информатике. -Воронеж, изд. ВНПУ, 1994. -18с.

4. Могилев А.В. и др. Информатика. -М.: Academia, 1999, 811 с.

5. Логинов Б.М. Введение в дискретную математику. –Калуга: Изд-во МВТУ им. Баумана, 1998.
6. ВОПРОСЫ К ЭКЗАМЕНУ ПО КУРСУ

1. Конечные множества. Число подмножеств конечного множества.

2. Генерирование всех подмножеств конечного множества.

3. Размещения. Вычисление и свойства числа размещений.

4. Перестановки Вычисление и свойства числа перестановок.

5. Сочетания. Вычисление числа сочетаний.

6. Основные свойства числа сочетаний.

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

8. Размещения с повторениями.

9. Перестановки с повторениями.

10. Сочетания с повторениями.

11. Полиномиальная теорема.

12. Принцип включений и исключений: теоретико-множественный подход.

13. Принцип включений и исключений: комбинаторный подход.

14. Возвратные последовательности, реккурентные соотношения. Примеры.

15. Решение однородных реккурентных соотношений.

16. Решение неоднородных реккурентных соотношений.

17. Числа Фибоначчи. Рекуррентная формула и формула общего члена.

18. Основные определения теории графов. Связный граф.

19. Обобщения понятия графа: орграф, мультиграф, псевдограф.

20. Задание графа (ортграф, мультиграфа, псевдографа) с помощью матрицы инциденций. Примеры.

21. Задание графа ((ортграф, мультиграфа, псевдографа) с помощью матрицы смежности. Примеры.

22. Задачи, приводящие к понятию графа: задача Эйлера, заадча о раскраске карты.

23. Теорема о пяти красках. Гипотеза 4-х красок, некоторые частные решения.

24. Геометрическая реализация графа на плоскости, планарные графы, условие планарности.

25. Формула Эйлера и следствия из нее.



26. Геометрическая реализация графа в пространстве.

27. Деревья. Характеризационная теорема.

Похожие:

Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconОсновная образовательная программа подготовки специалиста по специальности 010501 Прикладная математика и информатика

Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconУчебная программа Дисциплины б4 «Дискретная математика» по специальности 090302 «Информационная безопасность телекоммуникационных систем»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconРабочая программа курса "Дифференциальные уравнения" для специальности 010100 "
Она определяет объем знаний и последовательность изучения разделов дисциплины, представляющей одну из фундаментальных составляющих...
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconРабочая программа для студентов очной формы обучения, направление 230700. 62 «Прикладная информатика»
Зайцева С. С. Дискретная математика. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направление...
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconУчебная программа дисциплины " Математика и информатика" для специальности 032900 русский язык и литература Индекс дисциплины ен
«Информатика»: лекции 18 часов, лабораторные – 18 часов, самостоятельная работа – 36 часов
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconПрограмма дисциплины «Дискретная математика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230100. 62 «Информатика...
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconПрограмма государственного экзамена по математике по направлению подготовки 01. 03. 02. Прикладная математика и информатика саранск 2014 раздел «дискретная математика»
Оценки сложности днф. Сокращенные, тупиковые, минимальные дизъюктивные нормальные формы, и алгоритмы их построения
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconРабочая программа дисциплины для специальности 230100 Информатика и вычислительная техника, направление
Рабочая программа составлена в соответствии с гос впо по направлению подготовки (специальности) 230100 Информатика и вычислительная...
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconПрограмма дисциплины для направления/ специальности подготовки бакалавра/ магистра/ специалиста
...
Рабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика» iconРабочая программа учебной дисциплины (модуля) дискретная математика для направления
Компетенции студента, формируемые в результате освоения учебной дисциплины
Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com