Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Филиал ФГБОУ ВПО «Красноярский государственный педагогический университет им. В.П. Астафьева» в г. Канске ДИСКРЕТНАЯ МАТЕМАТИКА УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Специальность: 050202.65 – Информатика Канск 2011 УМКД составлен преподавателем филиала, к.ф.-м.н., доцентом Рашкиным Л.Д. Обсужден на заседании Совета филиала «_05»_сентября_2011 г. Председатель Совета филиала А.Л. Андреев Протокол согласования рабочей программы дисциплины «Дискретная математика» с другими дисциплинами специальности 050202.65 ИНФОРМАТИКА Наименование дисциплин, изучение которых опирается на данную дисциплину Предложения об изменениях в пропорциях материала, порядка изложения и т.д. Принятое решение (протокол №, дата) Совета филиала Теория алгоритмов. Численные методы. Теоретические основы информатики. Теория вероятностей и математическая статистика. Исследование операций - 01/11 от 05.09.2011 лист внесения изменений Дополнения и изменения рабочей программы на 2012/2013 учебный год В рабочую программу вносятся следующие изменения: 1. ____________________________________________________________ 2. ____________________________________________________________ 3. ____________________________________________________________ Внесенные изменения утверждаю: Директор филиала КГПУ им. В.П. Астафьева "____"___________ 20__г. СОДЕРЖАНИЕ 1. Пояснительная записка 6 2 Рабочая программа дисциплины 7 Выдержка из стандарта 8 Введение 9 Содержание теоретического курса дисциплины 11 Тематический план 12 Учебно-методическая (технологическая) карта дисциплины 13 Карта литературного обеспечения 15 Технологическая карта рейтинга 17 Методические рекомендации для студентов 19 Банк тестовых заданий 23 Тематика рефератов 36 Вопросы для самостоятельной работы 37 Вопросы к экзамену 38 ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Учебно-методический комплекс дисциплины (УМКД) «Дискретная математика» для студентов очной формы обучения по специальности 050202.65 «Информатика» состоит из следующих элементов: Рабочей программы дисциплины, включающей в себя основное её содержание и учебные ресурсы: литературное обеспечение, мультимедиа и электронные ресурсы. Методических рекомендаций для студентов, которые содержат советы и разъяснения, позволяющие студенту оптимальным образом организовать процесс изучения дисциплины «Дискретная математика». Банка тестовых заданий для организации самостоятельной работы студентов и самоконтроля по дисциплине «Дискретная математика». Тематики рефератов, которая отражает наиболее актуальные и значимые проблемы дискретной математики, и проверяет освоение вопросов рекомендованных для самостоятельного изучения студентом. Вопросы для самостоятельной работы студентов по дисциплине «Дискретная математика» для проверки знаний студентов. Вопросов к экзамену, который является итоговым контролем освоения студентом компетенции в области дискретной математики. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ ДИСКРЕТНАЯ МАТЕМАТИКА ВЫДЕРЖКА ИЗ СТАНДАРТА Настоящая рабочая модульная программа дисциплины (далее программа) составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 050202.65 – Информатика, утвержденного заместителем Министра образования и науки Российской Федерации А.Г. Свинаренко 31 января 2005 г., номер государственной регистрации № 661 пед/сп (новый) ДПП.Ф.02 Дискретная математика Рекуррентные соотношения. Способы решения рекуррентных соотношений. Суммы и рекуррентности. Целочисленные функции ëxû, éxù, mod. Бином Ньютона. Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Полиномиальная формула. Введение в асимптотические методы. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера. Основные комбинаторные конфигурации. Метод включения-исключения. Основные понятия теории графов. Связные графы. Изоморфизм графов. Эйлеровы и гамильтоновы графы. Деревья. Паросочетания, независимые множества и клики. Пленарные графы. Теорема Эйлера и ее следствия. Непланарность графов К5 и Кз,з. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок. 130 Введение Место дисциплины в реализации основных задач ОПП: дисциплина «Дискретная математика» относится к циклу дисциплин предметной подготовки. Она занимает одно из центральных мест в системе подготовки учителя по специальности 050202.65 – Информатика. Место дисциплины в обеспечении образовательных интересов личности студента и в удовлетворении требований заказчиков выпускниками университета по данной ОПП: дисциплина «Дискретная математика» является одной из основных дисциплин профессиональной образовательной программы по специальности 050202 Информатика, в рамках изучения которой осуществляется специальная подготовка учителя для преподавания предмета Информатика в учреждениях среднего (полного) общего образования. Содержание дисциплины «Дискретная математика» глубоко интегрировано в структуру блока дисциплин предметной подготовки. Изучение данной дисциплины базируется на следующих дисциплинах: Математика. Математическая логика. Элементы абстрактной и компьютерной алгебры. Информатика. Программирование. Программное обеспечение ЭВМ. Материал данной дисциплины непосредственно используется для изучения следующих дисциплин: Теория алгоритмов. Численные методы. Теоретические основы информатики. Теория вероятностей и математическая статистика. Исследование операций. Целью дисциплины является формирование основных понятий дискретной математики, которые необходимы для решения связанных с этими понятиями задач, составления формул и схем, а также для изучения учебных дисциплин: теория алгоритмов, численные методы, теоретические основы информатики, теория вероятностей и математическая статистика. Задачи дисциплины: усвоение студентами научных знаний по разделам дискретной математики; овладение основными понятиями комбинаторики и теории графов; знакомство с новейшими достижениями в дискретной математике. Технология процесса обучения по дисциплине «Дискретная математика» осуществляется в форме лекций и практических занятий, внеаудиторной самостоятельной работы. Дисциплина рассчитана на один семестр. СОДЕРЖАНИЕ ТЕОРЕТИЧЕСКОГО КУРСА ДИСЦИПЛИНЫ МОДУЛЬ № 1. Основные методы дискретной математики Введение. Различие между дискретной и непрерывной, математикой. Счет и перечисление (перебор) как основные методы дискретной математики. Эффект “комбинаторного взрыва”, примеры. Что такое дискретная математика? Конечные суммы и рекуррентные соотношения Способы записи конечных сумм. Преобразования сумм. Кратные суммы. Некоторые методы суммирования. Понятие рекуррентного соотношения. Примеры задач, приводящих к рекуррентным соотношениям. Числа Фибоначчи, числа Каталана. Некоторые способы решения рекуррентных соотношений. Комбинаторные числа Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля. Бином Ньютона. Некоторые применения бинома Ньютона. Числа Стирлинга 1-го и 2-го рода. Полиномиальные коэффициенты. Полиномиальная теорема. Введение в асимптотические методы Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений. Формула Стирлинга (без доказательства). МОДУЛЬ № 2. Основные понятия комбинаторики и теории графов Основные понятия комбинаторики Выборки, размещения, перестановки, сочетания, разбиения; их пересчет. Комбинаторный смысл биномиальных коэффициентов. Комбинаторный смысл полиномиальных коэффициентов и чисел Стирлинга. Метод включения-исключения и его применения (оценки для числа элементов, не обладающих ни одним из свойств; формула для числа элементов, обладающих в точности р свойствами). Формулы обращения. Функция Мебиуса. Формула обращения Мебиуса. Начала теории Рамсея Принцип Дирихле. Теорема Рамсея (конечный случай). Числа Рамсея. Применения теоремы Рамсея (теорема Ван дер Вардена). Элементы теории графов Понятие графа и мультиграфа; различные способы их представления. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Путь, цепь, простая цепь, цикл, простой цикл. Связные графы. Компоненты связности графа, их число. Изоморфные графы. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы. Деревья. Характеризационная теорема. Планарные графы. Укладка графа. Теорема Жордана (без доказательства). Плоские графы. Не планарность графов и . Раскраска вершин графа. Хроматическое число графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Теорема о четырех красках (без доказательства). . ТЕМАТИЧЕСКИЙ ПЛАН изучения дисциплины «Дискретная математика» по специальности 050202.65 «Информатика» № п/п Название модулей и тем Количество часов Всего Из них аудиторные занятия: Лекции Практические Лабораторные Самостоятельная работа I. Основные методы дискретной математики 51 24 12 12 - 27 1 Конечные суммы и рекуррентные соотношения. 17 8 4 4 - 9 2 Комбинаторные числа. 17 8 4 4 - 9 3 Введение в асимптотические методы. 17 8 4 4 - 9 II. Основные понятия комбинаторики и теории графов 79 52 26 26 - 27 1 Основные понятия комбинаторики. 29 20 10 10 - 9 2 Начала теории Рамсея. 21 12 6 6 - 9 3 Элементы теории графов. 29 20 10 10 - 9 Итого: 130 76 38 38 - 54 учебно-методическая (ТЕХНОЛОГИЧЕСКАЯ) КАРТА дисциплины

Похожие:

	Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Программирование» для студентов очной формы обучения по специальности 050202. 65...		Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Физика» для студентов очной формы обучения по специальности 050202. 65 «Информатика»...
	Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Сайтостроение» для студентов очной формы обучения по специальности 050202. 65 «Информатика»...		Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Эстетика» для студентов очной формы обучения по специальности 050202. 65 «Информатика»...
	Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Химия» для студентов очной формы обучения по специальности 050202. 65 «Информатика»...		Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «История информатики» для студентов очной формы обучения по специальности 050202....
	Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Информационные системы» для студентов очной формы обучения по специальности 050202....		Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Основы микроэлектроники» для студентов очной формы обучения по специальности 050202....
	Учебно-методический комплекс дисциплины специальность: 050202 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Математическая логика» для студентов очной формы обучения по специальности 050202...		Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Информационная культура» для студентов очной формы обучения по специальности 050202....
	Учебно-методический комплекс дисциплины специальность: 050202 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Архитектура компьютера» для студентов очной формы обучения по специальности 050202...		Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск Протокол согласования рабочей программы дисциплины «культурология» с другими дисциплинами специальности 050202. 65 Информатика
	Учебно-методический комплекс дисциплины специальность: 050202. 65 Информатика Канск ...		Учебно-методический комплекс дисциплины специальность: 050502. 65 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Политология» для студентов очной формы обучения по специальности 050202 «Информатика»...
	Учебно-методический комплекс дисциплины специальность: 050502 Информатика Канск Учебно-методический комплекс дисциплины (умкд) «Социология» для студентов очной формы обучения по специальности 050202 «Информатика»...		Вводный курс информатики учебно-методический комплекс дисциплины... Учебно-методический комплекс дисциплины (умкд) «Вводный курс информатики» для студентов очной формы обучения по специальности 050202....