Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика



Скачать 90.21 Kb.
Дата11.10.2012
Размер90.21 Kb.
ТипПрограмма дисциплины
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»

(ТГПУ)


«УТВЕРЖДАЮ»

Декан физико-математического факультета
_______________А.Н. Макаренко

«___» ______________ 2008 года
ПРОГРАММА ДИСЦИПЛИНЫ
ДПП.Ф.02. «ДИСКРЕТНАЯ МАТЕМАТИКА»
Специальность 030100 (050202.65) – информатика
Квалификация – учитель информатики

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

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

Задачи: познакомить с рекуррентными соотношениями и задачами, приводящими к ним, с некоторыми методами решения рекуррентных соотношений; познакомить с целочисленными функциями; познакомить с элементами теории графов.
2.Требования к уровню освоения содержания дисциплины:
В результате изучения курса «Дискретная математика» студенты должны научиться решать простейшие задачи по указанным темам :

  • знать свойства сумм, уметь оперировать суммами;

  • иметь представление о числовых функциях;

  • Изучить свойства чисел Фибоначчи, познакомиться с задачами, которые решаются с помощью чисел Фибоначчи;

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

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



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


Вид учебной работы


Всего часов

Семестры


4

Общая трудоемкость дисциплины

130

130

Аудиторные занятия

72

72

Лекции

36

36

Практические занятия (ПЗ)

36

36

Семинары (С)

-




Лабораторные работы (ЛР)

-




И (или) др. виды аудиторных занятий

-




Самостоятельная работа (СР)

58

58

Курсовая работа








Расчетно-графические работы

-




Реферат

-




И (или) др. виды

-




Вид итогового контроля

(зачет, экзамен)




экзамен


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

4.1. Разделы дисциплины и виды занятий ( Тематический план)




п/п

Раздел дисциплины

Лекции


Практические занятия

Самост. работа



Введение

2


-

-



Метод математической индукции.

2


4

4



Числовые множества.

2


2

2



Прямое произведение множеств.

2


4

4


Рекуррентные соотношения


8

4

8



Суммы

10

12

18



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

10

10

22



4.2. Содержание разделов дисциплины
1. Введение

Цели и задачи курса в подготовке учителя информатики.

2. Метод математической индукции.

Применение метода математической индукции к решению различных задач. Фигурные числа. Разные виды теорем. Теорема Никомаха.

3. Числовые множества.

Числовые множества. Мощность бесконечного множества. Мощность множества натуральных чисел - счетное множество. Мощность континуума.

4. Прямое произведение множеств.

Бинарные отношения, их свойства. Отображение. Свойства отображений. Инъективное, сюръективное, биективное отображения.

5. Рекуррентные соотношения

Задачи, приводящие к рекуррентным соотношениям. Числа Фибоначчи. Их свойства. Применение к решению задач. Производящие функции. Их свойства. Метод производящих функций. Теорема Бине. Разные способы доказательства.

6.Суммы

Целочисленные функции. Функция Эйлера. Теорема Ферма. Теорема Эйлера. Биномиальные коэффициенты. Их свойства. Суммы. Свойства сумм. Формула суммирования Эйлера

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

Основные понятия теории графов: виды графов, полные, связные графы, деревья, лес, колесо, 0 – граф, степени, объединение, соединение графов. Теорема о сумме степеней вершин графа. Эйлеровы графы. Критерий Эйлеровости. Гамильтоновы графы. Планарные графы, плоские графы. Укладка графа. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.

5. Лабораторный практикум

Не предусмотрен.
6. Учебно-методическое обеспечение дисциплины

6.1. Рекомендуемая литература

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

  1. Новиков, Ф. А. Дискретная математика для программистов: Учебное пособие для вузов/Ф. А. Новиков. - 2-е изд.- СПб.: Питер, 2004.-363 с.


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

  1. Акимов, О.Е. Дискретная математика: Логика, группы, графы: Уч. пособие для втузов/О.Е. Акимов. - 2-е изд., доп.- М: Лаборатория Базовых Знаний, 2003.- 376 с.

  2. Иванов, Б.Н. Дискретная математика: Алгоритмы и программы: Учебное пособие/Б. Н. Иванов. – М.: Лаборатория Базовых Знаний, 2002. – 288 с.

  3. Кнут, Д. Искусство программирования: в 2 т. / Д. Э. Кнут. – 3-е изд., испр. и доп. – М.: Вильямс, 2003. – T. 1-2.

  4. Редькин, Н. П. Дискретная математика: курс лекций для студентов-механиков: учебное пособие для вузов/Н.П. Редькин. – Изд. 2-е, стереотип. – СПб.: Лань, 2006. – 95 с.

  5. Романовский, И.В. Дискретный анализ: Уч. пособие по прикладной математике и информатике/ И.В. Романовский. - 2-е изд., испр. - СПб.: Невский диалект, 2001 с.- 239 с.



6.2. Средства обеспечения освоения дисциплины

Рабочие программы по дискретной математике.
7. Материально-техническое обеспечение дисциплины

Не предусмотрено
8. Методические рекомендации по организации изучения дисциплины.

8.1. Методические рекомендации преподавателю.

Настоящая программа по дисциплине «Дискретная математика» составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности 050202.65 - информатика и учебного плана, утвержденного ученым Советом ТГПУ.

Программа по курсу «Дискретная математика» рассчитана на 72 часа аудиторных занятий со студентами.

Изложение Дискретной математики должно строиться на уровне строгости, принятой в настоящее время в современной математике. Однако нет причин выходить далеко за границы, определяемые основными целями и Государственным образовательным стандартом по данной специальности. Изучение каждого раздела программы не предполагает подробные доказательства. Это вызвано недостатком времени. Изложение всех разделов курса «Дискретная математика» должно сопровождаться приведением большого числа примеров, решением достаточного количества задач и упражнений, как соответствующих духу общего теоретического изложения, так и элементарного типа, близкого к школьной математике. Изучение курса «Дискретная математика» рассчитано на 1 семестр, в конце которого проводится итоговый контроль в форме экзамена.
8.2. Методические указания для студентов.

Студентам предлагается использовать рекомендованную литературу для более прочного усвоения учебного материала, изложенного в лекциях, а также для изучения материала, запланированного для самостоятельной работы. Студентам необходимо выполнить индивидуальные задания по основным темам курса, оценки за которые учитываются при выставлении оценок на экзамене. Выполнение заданий, вынесенных на самостоятельную работу, проверяются преподавателем в течение семестра, по ним выставляются оценки, которые учитываются при выставлении оценок на экзаменах.
Перечень примерных контрольных вопросов и заданий для самостоятельной работы.

  1. Различные задачи на доказательство методом математической индукции.

  2. Числа Фибоначчи в природе, технике, искусстве.

  3. Золотое сечение.

  4. Геометрическая и арифметическая прогрессии, доказательства свойств с помощью свойств сумм.

  5. Элементы теории сравнений. Свойства. Числовые функции - число и сумма натуральных делителей, каноническое разложение n!.

  6. Задачи на нахождение остатков от деления.

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

  8. Задачи, связанные с теорией графов.


Примерный перечень вопросов к экзамену.

  1. Метод математической индукции. Теорема. Примеры.

  2. Теорема Никомаха.

  3. Свойство сумм: замена индекса.

  4. Свойство сумм: распределительное свойство.

  5. Свойство сумм: изменение порядка суммирования.

  6. Вывод формулы суммы n членов арифметической прогрессии с помощью сумм.

  7. Вывод формулы суммы n членов геометрической прогрессии с помощью сумм.

  8. Сравнения. Необходимое и достаточное условие сравнимости чисел по модулю.

  9. Свойства сравнений, связанные с операциями сложения и умножения.

  10. Свойства сравнений, связанные с модулем.

  11. Доказательство формулы Бине методом математической индукции.

  12. Числовая функция – целая часть числа, график, свойства.

  13. Биномиальные коэффициенты. Их свойства.

  14. Каноническое разложение числа n!.

  15. Симметричность биномиальных коэффициентов.

  16. Теорема Ферма.

  17. Функция Эйлера.

  18. Теорема Эйлера.

  19. Вывод формулы Бине методом производящих функций.

  20. Производящие функции. Их свойства.

  21. Свойства чисел Фибоначчи.

  22. Задание бинарного отношения с помощью графа.

  23. Виды графов. Примеры.

  24. Основные понятия теории графов. Теорема о сумме степеней вершин графа.

  25. Эйлеровы графы. Критерий Эйлеровости. Гамильтоновы графы.

  26. Планарные графы, плоские графы. Укладка графа.

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

  28. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок


Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 030100 (050202.65) - «информатика», квалификация – учитель информатики.

Программу составил:

К. п. н., доцент кафедры математики,

теории и методики обучения математике ________________ В.Н. Ксенева

Программа дисциплины утверждена на заседании кафедры математики, теории и методики обучения математике, протокол №____ от «___» ___________ 200_ г.

Зав. Кафедрой, профессор ___________________ Э.Г. Гельфман

Программа дисциплины одобрена метод. комиссией ФМФ ТГПУ.
Председатель методической комиссии

физико-математического факультета ______________ В.И. Шишковский
Согласовано:

Декан физико-математического факультета __________________ А.Н. Макаренко


Похожие:

Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconПрограмма дисциплины дпп. Ф. 06 "Уравнения математической физики" Специальность 030100 (050202. 65) Информатика
Ознакомление с методами построения математических моделей различных процессов и явлений естествознания
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconПрограмма дисциплины дпп. Ф. 01 «математическая логика» Специальность 030100 (050202. 65) Информатика Квалификация учитель информатики
Целью дисциплины является не только знакомство с проблемами логики и с основными ее понятиями, но и выработка способности студента...
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconПрограмма дисциплины дпп. Ф. 03 «элементы абстрактной и компьютерной алгебры» Специальность 030100 (050202. 65) Информатика
Программа позволяет систематизировать знания студентов, полученные при изучении курса «Алгебра» Цели достигаются достаточной абстракцией...
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconПрограмма промежуточной аттестации студентов по дисциплине Дискретная математика Специальность: 030100 Информатика
Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconПрограмма дисциплины «Дискретная математика»
...
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconУчебно-методический комплекс учебной дисциплины дпп. Ф. 10 Теория алгоритмов 030100. 00 Информатика с дополнительной специальностью
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconУчебная программа Дисциплины б2 «Дискретная математика» по направлению 010300 «Фундаментальная информатика и информационные технологии»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconПрограмма дисциплины фтд. 00 «практикум по решению математических задач» Специальность 030100 (050202. 65) «Информатика»
Цель курса – подготовка выпускников в области элементарной математики, освоение навыков решения задач (в том числе олимпиадных) по...
Программа дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика iconРабочая программа учебной дисциплины ддс. 06. Геометрия ооп: Специальность 030100. 00 Информатика
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org