WWW.METODICHKA.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Методические указания, пособия
 

«УТВЕРЖДАЮ И.о. декана физико-математического факультета ФГБОУ ВПО БГПУ _ А.В. Василенко «23» апреля 2015 г. Рабочая учебная программа дисциплины ДИКРЕТНАЯ МАТЕМАТИКА 02.03.03 ...»

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

ФГБОУ ВПО Благовещенский государственный

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

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

УТВЕРЖДАЮ

И.о. декана физико-математического

факультета

ФГБОУ ВПО БГПУ

_______________ А.В. Василенко «23» апреля 2015 г.

Рабочая учебная программа дисциплины

ДИКРЕТНАЯ МАТЕМАТИКА

02.03.03 МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И

АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ

Профиль

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ

Квалификация (степень) выпускника - бакалавр Принята на заседании кафедры математики и методики обучения математике (протокол № 8 от «15» апреля 2015 г.) Благовещенск 201

Рабочая программа дисциплины разработана на основе:

ФГОС ВПО по направлению подготовки 02.03.03 «Математическое обеспечение и администрирование информационных систем» (квалификация (степень) «бакалавр»), утверждённого Министерством образования и науки РФ от 12 марта 2015 г. № 222.

Учебного плана по профилю «Технологии программирования», утвержденного Ученым советом БГПУ от «22» апреля 2015 г. Протокол № 4.

Приказа Министерства образования и науки РФ № 1367 от 19.12.2013 г. «Об утверждении порядка организации и осуществления образовательной деятельности по образовательным программам высшего образования – программам бакалавриата, программам специалитета, программам магистратуры».

Разработчик: старший преподаватель кафедры математики и методики обучения математики Б.Г. Федорищев.

СОДЕРЖАНИЕ

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

2 Тематический план

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

Интерактивные формы организации учебной работы на занятиях

Методические рекомендации для студентов по изучению учебной дисциплины...... 8 4 Практикум по дисциплине

5 6 Дидактические материалы для контроля (самоконтроля) усвоенного материала............... 9 7 Перечень информационных технологий используемых в процессе обучения........... 12 8 Список литературы и информационных ресурсов

8.1 Основная литература

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

8.3 Интернет ресурсы:

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

10 Лист изменений и дополнений

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

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

Дисциплина «Дискретная математика» относится к базовой части профессионального модуля (Б1.М3.Б.1). Преподавание дисциплины связано с другими дисциплинами государственного образовательного стандарта: «Математическая логика», «Алгебра и теория чисел», «Математический анализ», «Физика», «Геометрия и топология».

Требования к результатам освоения дисциплины:

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

должен обладать способностью применять в профессиональной деятельности знания математических основ информатики (ОПК-2).

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

Основные комбинаторные объекты и числа;

Свойства комбинаторных чисел;

Основные понятия теории графов;

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

Классификацию графов;

Решение краевых задач на графах;

Сети;

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

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

уметь:

решать комбинаторные задачи;

выполнять операции над графами;

обосновывать изоморфизм графов;

решать типовые краевые задачи на графах;

решать линейные рекуррентные соотношения;

находить суммы конечных последовательностей.

владеть:

- навыками решения типовых задач комбинаторики и теории графов.

Общая трудоемкость дисциплины составляет 3 зачетные единицы (108 часов).

–  –  –

1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Напоминание основных понятий. Определение прямого произведения множеств.

Разбиения множеств и их свойства. Сравнение разбиений. Произведение разбиений.

2. ОТНОШЕНИЯ Отношения Основные определения. Классификация отношений. Эквивалентность.

Частичный порядок. Топологическая сортировка. Использование многоместных отношений в реляционных базах данных.

3. КОМБИНАТОРИКА Векторы из нулей и единиц, различные их трактовки. Способы перебора и нумерации векторов из нулей и единиц. Перестановки, размещения, сочетания, способы их перебора и нумерации. Бином Ньютона и треугольник Паскаля. Числа Фибоначчи, их свойства.

4. ГРАФЫ Основные определения: граф, частичный граф, подграф. Путь, простой путь, цепь, контур, цикл. Связность, бисвязность, сильная связность. Остовное дерево. Свойства деревьев.

Экстремальные задачи на графах: остовное дерево минимальной длины, дерево кратчайших путей и т.п. Сетевое планирование и поиск критического пути.

Связь теории графов с линейной алгеброй. Матрица инциденций и ее свойства.

Решение линейных систем с матрицей инциденций. Связь с методами решения разреженных линейных систем.

Паросочетания в двудольных графах. Теорема о максимальном паросочетании.

Теорема Дилворта. Теорема Биркгофа-фон Неймана. Венгерский метод для задачи о назначениях.

5. СВЯЗЬ ДИСКРЕТНОГО И НЕПРЕРЫВНОГО АНАЛИЗА

Производящие функции. Асимптотика. Рекуррентные соотношения. Способы решения рекуррентных соотношений. Суммы и рекуррентности. Полиномиальная формула.

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

–  –  –

Деревья и леса. Помеченные графы. Перечисление [8] помеченных деревьев. Матрицы графов.

Занятие №9 Мосты графа. Эйлеровы и гамильтоновы графы. [1], [2], [5], [6], Деревья и леса. Помеченные графы. Перечисление [8] помеченных деревьев. Матрицы графов.

Занятие №10-11 Взвешенные графы. Обходы графов. Кратчайшие 4 [1], [2] [5], [8] пути. Окраска графов. Хроматические многочлены. [ Занятие №12 Сетевые задачи. Максимальный поток в 2 [1] двухполюсной сети.

Занятие №13 Суммирование конечных последовательностей. 2 [8], [12] Формула суммирования Эйлера.

Занятие №14 2 [8], [12] Решение линейных однородных рекуррентных

–  –  –

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

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

Рабочая программа призвана помочь в подготовке лекционных и практических занятий для изучения последовательных разделов: «Элементы теории множеств», «Отношения», «Комбинаторика», «Графы», «Связь дискретного и непрерывного анализа».

В каждом разделе даны:

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

2) учебно-методические материалы по подготовке практических занятий, содержащие планы проведения занятий с указанием последовательности рассматриваемых тем, задания для самостоятельной работы. Выполнение упражнений даст возможность студентам глубже усвоить теоретический материал.

Прежде чем приступить к выполнению заданий для самоконтроля, студентам необходимо изучить рекомендуемую по каждой теме литературу. Общий список учебной, учебно-методической и научной литературы представлен в отдельном разделе пособия.

Кроме того, в лекционном курсе по каждой теме указана основная и дополнительная литература.

Рабочая программа содержит краткие рекомендации по выполнению курсовых работ.

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

–  –  –

НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ (2 часа) 1.

Множества. Операции над ними. Метод включения и исключения. Декартово произведение, множество-степень. n-местные отношения. Булевы алгебры отношений и матриц. Бинарные отношения на множестве. Свойства бинарных отношений. Отношение порядка и доминирования. Отношение эквивалентности. [10] КОМБИНАТОРИКА (6 часов) 2.

Комбинаторные конфигурации без повторений. Размещения, перестановки, сочетания. [1], [2], [7], [8], [9], [11], [12] Комбинаторные конфигурации с повторениями. Размещения, перестановки с кратностями, сочетания. [1], [2], [9], [11], [12] Основные свойства комбинаторных чисел. Биномиальная и полиномиальная теоремы.

Числа Фибоначчи. [1], [2], [8], [9] ГРАФЫ (8 часов) 3.

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

Связность, компоненты. [1], [2], [3], [4], [5], [6], [8], [11] Мосты графа. Эйлеровы и гамильтоновы графы. Деревья и леса. Помеченные графы.

Перечисление помеченных деревьев. Матрицы графов. [1], [2], [5], [6], [8] Взвешенные графы. Обходы графов. Кратчайшие пути. Окраска графов. Хроматические многочлены. [1], [2] [5], [8] Сетевые задачи. Максимальный поток в двухполюсной сети. [1] СВЯЗЬ ДИСКРЕТНОГО С НЕПРЕРЫВНЫМ (4 часа) 4.

Суммирование конечных последовательностей. Формула суммирования Эйлера. [8], [12] Решение нелинейных однородных соотношений. Асимптотические решения рекуррентных соотношений. [8], [12] 6 Дидактические материалы для контроля (самоконтроля) усвоенного материала

6.1 Паспорт фонда оценочных средств по дисциплине «Дискретная математика»

–  –  –

Критерии оценки:

оценка «зачтено» выставляется студенту, если: а) выполнены все контрольные мероприятия из фонда оценочных средств по разделу; б) даны полные обоснованные ответы на два пункта билета;

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

–  –  –

Разбиения множеств и их свойства. Сравнение разбиений. Произведение разбиений.

1.

Топологическая сортировка.

2.

Использование многоместных отношений в реляционных базах данных.

3.

Способы перебора и нумерации комбинаторных объектов.

4.

Связь теории графов с линейной алгеброй. Матрица инциденций и ее свойства.

5.

Решение линейных систем с матрицей инциденций. Связь с методами решения 6.

разреженных линейных систем.

7. Паросочетания в двудольных графах. Теорема о максимальном паросочетании.

8. Теорема Дилворта.

9. Теорема Биркгофа-фон Неймана.

10. Венгерский метод для задачи о назначениях.

–  –  –

Тесты простоты.

1.

Алгоритмы символьных преобразований.

2.

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

3.

Системы криптографии с открытым ключом.

4.

–  –  –

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

2. Разбиения множеств и их свойства. Сравнение разбиений. Произведение разбиений.

3. Отношения. Основные определения. Классификация отношений.

4. n-местные отношения в реляционных базах данных.

5. Перестановки. Число перестановок.

6. Размещения. Число размещений.

7. Сочетания. Число сочетаний.

8. Перестановки с кратностями. Число перестановок с кратностями.

9. Размещения с повторениями. Число размещений с повторениями.

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

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

12. Числа Фибоначчи, их свойства.

13. Графы. Основные определения: псевдограф, мультиграф, граф, ориентированные и неориентированные графы, подграф.

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

15. Путь, простой путь, цепь, контур, цикл. Связность, бисвязность, сильная связность.

16. Деревья и леса. Остовное дерево. Свойства деревьев.

17. Плоский и планарный граф. Критерий планарности графа.

18. Непланарность графов К5 и К3,3.

19. Укладка графа в трехмерное пространство.

20. Теорема Эйлера для сферической укладки графа и выпуклых многогранников.

21. Экстремальные задачи на графах: остовное дерево минимальной длины, дерево кратчайших путей, остовное дерево минимального/максимального веса.

22. Сетевое планирование и поиск критического пути.

23. Паросочетания в двудольных графах. Теорема о максимальном паросочетании.

24. Производящие функции. Асимптотика.

25. Рекуррентные соотношения. Способы решения рекуррентных соотношений.

26. Суммы и рекуррентности.

7 Перечень информационных технологий используемых в процессе обучения

1. Мультимедийное сопровождение лекций

2. Электронные ресурсы ЭБС «Лань», «Руконт»

–  –  –

8.1 Основная литература Дискретная математика для программистов [Текст] : учеб. пособие для вузов / 1.

Ф.А. Новиков. - 2-е изд. - М. ; СПб. [и др.] : Питер, 2007. - 364 с. : ил. - (Учебник для вузов).

Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной 2.

математики/ Г.П. Гаврилов, А.А. Сапоженко. – М.: Наука, 2002. – 294c.

Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения/ 3.

Я.М. Ерусалимский – М.: «Вузовская книга», 2000. – 280с.

Дискретная математика для программистов [Text]/ Ф. А. Новиков. - СПб. ; М. ;

4.

Харьков; Минск : Питер, 2002. - 301 с.

Фаддеев Д.К. Лекции по алгебре/ Д.К. Фаддеев. – СПб. Изд-во «Лань», 2002. – 432c.

5.

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

Матросов В.Л., Стеценко В.А. Лекции по дискретной математике: Учеб. Пособие 1.

для магистрантов мат. фак. пед. ун-тов/ В.Л. Матросов, В.А. Стеценко. – М.: МПГУ, 1997. – 256.

Хаггарти, P. Дискретная математика для программистов/ P. Хаггарти– М.:

2.

Техносфера, 2004. – 320 c.

8.3 Интернет ресурсы:

www.gramota.ru Справочно-информационный портал 1.

www.auditorium.ru Информационно-образовательный портал 2.

www.iqlib.ru Электронная библиотека образовательных и научных изданий Iqlib.

3.

http://www.cir.ru Университетская информационная система Россия. УИС РОССИЯ.

4.

www.public.ru Интернет-библиотека СМИ Public.ru.

5.

www.book.ru Электронная библиотека 6.

www.KNIGAFUND.ru Электронная библиотека 7.

–  –  –

1. компьютерные классы с выходом в Интернет

2. учебные аудитории, оборудованные мультимедийными демонстрационными комплексами

3. мультимедийные презентации

4. лицензированные специализированные компьютерные программы

–  –  –

Утверждение изменений в рабочей программе дисциплины для реализации в 2015/2016 уч. г.

Рабочая программа дисциплины пересмотрена, обсуждена и одобрена для реализации в 2015/2016 учебном году на заседании кафедры (протокол № 8 от 15 апреля 2015 г.)

В рабочую программу дисциплины внесены следующие изменения и дополнения:

–  –  –



 

Похожие работы:

«УТВЕРЖДАЮ Первый проректор по учебной работе ФГБОУ ВПО «Алтайский государственный университет» Е.С. Аничкин «» марта 2015 г. ПРОГРАММА вступительного испытания для поступающих на обучение по направлению подготовки научнопедагогических кадров в аспирантуре 46.06.01 Исторические науки и археология (наименование направления) Предмет «Иностранный язык» Утверждено на заседании экзаменационной комиссии, протокол № от «_» марта 2015 года. Председатель экзаменационной комиссии _ Деренчук О.В....»

«Областной конкурс среди педагогов образовательных организаций на лучшее пособие (программу, курс) по правовому, патриотическому воспитанию Информация о профессиональных достижениях учителя Претендент: Никитина Светлана Юрьевна Образование: высшее, Нижнетагильский государственный педагогический институт, исторический факультет, 1991 г. Квалификация: учитель истории, обществознания и права Специальность: история Общий трудовой стаж: 23года Педагогический стаж: 23 года Место работы: МКОУ «СОШ №1»...»

«Государственное образовательное учреждение Высшего профессионального образования Ханты-Мансийского автономного округа Югры «Сургутский государственный педагогический университет»СОГЛАСОВАНО УТВЕРЖДАЮ декан факультета проректор по учебной работе Т.М. Захожая _ заведующий кафедрой _ Б5.П. ФОЛЬКЛОРНАЯ ПРАКТИКА Методические рекомендации Направление подготовки:050100«Педагогическое образование» Профиль подготовки: «Образование в области русского языка и Литературное образование» Квалификация...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Психология и педагогика в профессиональной деятельности юриста Учебно-методический комплекс для студентов юридического факультета по направлению подготовки 030900 – «Юриспруденция» (квалификация (степень) «Бакалавр») Махачкала УДК 174:34 ББК 67п Печатается по решению редакционно-издательского...»

«Государственное бюджетное дошкольное образовательное учреждение детский сад № 31 общеразвивающего вида с приоритетным осуществлением деятельности по познавательно-речевому развитию детей Кировского района Санкт-Петербурга Принято на заседании Утверждаю: педсовета заведующий ГБДОУ протокол №_1 Детский сад №31 «_22_»08_2014г. ПРИКАЗ № 38/1-ОД от 26.08.14г. Басова О.В. Рабочая программа совместной деятельности педагога с детьми от 1.6 до 2 лет, первая младшая группа № 1. Срок реализации программы...»

«Федеральное агентство по образованию ГОУ ВПО «Российский государственный профессионально­ педагогический университет» Уральское отделение Российской академии образования Академия профессионального образования А.В. Ефаное ЭКОНОМИКА ТУРИЗМА И ГОСТИНИЧНОГО ХОЗЯЙСТВА Учебное пособие Допущено Учебно-методическим объединением по профессионально-педагогическому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специализации «Менеджмент в туризме и...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОЛЖСКИЙ ИНСТИТУТ ЭКОНОМИКИ, ПЕДАГОГИКИ И ПРАВА» «Волжский социально-педагогический колледж» МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ И ФОС по МДК Теоретические и методические основы деятельности классного руководителя Специальность Преподавание в начальных классах Методические материалы и ФОС утверждены на заседании ПЦК социально-гуманитарных дисциплин протокол № 9 от...»

«Методические рекомендации по формированию универсальных учебных действий (в соответствии с результатами проведенного мониторинга в четвертых классах в 2014-2015 уч. году) Сейдниязова Н.В., к.п.н., доцент кафедры дошкольного и начального образования Новые стандарты начального общего образования ориентируют учителя на достижение качественно новых целей и результатов в организации образовательного процесса. Основным требованием и критерием оценки выступает уже не освоение обязательного минимума...»

«Посвящается светлой памяти Владимира Ланцберга ТЕХНОЛОГИЯ ГРУППЫ Учебное пособие для лидера молодёжной неформальной группы Москва ISBN 978-5-9900354-3-0 Кордонский М., Кожаринов М. Очерки неформальной социотехники (Учебное пособие для лидера молодёжной неформальной группы). (Серия: Технология группы), предисловие В.Хилтунена М.: Net2Net, 2008.336 c., ил. Это книга о неформалах и для неформалов, а ещё для их родителей, друзей, учителей, журналистов, политиков, социологов. О неформальном движении...»

«Министерство образования и науки Российской федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Российский государственный профессионально-педагогический университет» филиал РГППУ в г. Кемерово ПРОФЕССИОНАЛЬНОПЕДАГОГИЧЕСКОЕ ОБРАЗОВАНИЕ. РЕГИОН Приложение к Вестнику Учебно-методического объединения по профессионально-педагогическому образованию (г. Екатеринбург) № 3 (49) Екатеринбург 2015 ББК – 74.56 Профессионально-педагогическое...»







 
2016 www.metodichka.x-pdf.ru - «Бесплатная электронная библиотека - Методички, методические указания, пособия»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.