Geum.ru

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

Вид материалаРабочая программа

Содержание


Дискретная математика
Индекс по учебному плану
Форма Обучения
Иметь представление
Аудиторные занятия (всего)
Самостоятельная работа (всего)
Другие виды самостоятельной работы
6.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами
6.3. Разделы дисциплин и виды занятий
Подобный материал:

М

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

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ




Государственное образовательное учреждение высшего профессионального образования

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

УТВЕРЖДАЮ



Проректор по учебной работе

_______ Т.В. Маркелова


«_____» __________2010 г.


рабочая программа




Наименование дисциплины

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

По направлению подготовки 230400 - Информационные системы и технологии


По профилю подготовки

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

(указывается наименование профиля в соответствии с ПрООП)


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

Кафедра Информационные системы


Квалификация (степень) выпускника бакалавр


Москва — 2010


Разработчики:

Зав. кафедрой_______ д.т.н., проф. Марков А.А.________

(занимаемая должность) (учёная степень и учёное звание) (инициалы, фамилия)


Рецензенты:

Профессор_______ д.т.н., проф. Винокур А.И.__________

(занимаемая должность) (учёная степень и учёное звание) (инициалы, фамилия)


Зав. кафедрой_______ д.т.н., проф. Попов Д.И._____________

(занимаемая должность) (учёная степень и учёное звание) (инициалы, фамилия)


Рабочая программа обсуждена на заседании кафедры «___Информационных систем__»

(дата) ____________ 2010 г, протокол № .


Зав. кафедрой __Марков А.А.____/ /


Одобрена Советом факультета _Цифровых систем и технологий________________________________

(дата) ____________ 2010 г, протокол №


Председатель__ Иванова А.Е.____________/



Индекс по учебному плану
Цикл
Компонент

Базовая часть
вариативная часть

по выбору студента

Б2.Вар1
Гуманитарный и социальный

и экономический цикл









Математический и естественнонаучный цикл



Х



Профессиональный цикл












Форма

Обучения
курс
семестр
Трудоемкость дисциплины в часах
Форма

итогового

контроля

Всего часов
Аудиторных часов
Лекции
Семинарские (практически) занятия
Лабораторные занятия
Курсовая

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

Очная
3
6
180
85
51



34



95
Экзамен

Очно-заочная






























Заочная
































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


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

логические исчисления, графы, теория и сложность алгоритмов, языки и грамматики, автоматы, комбинаторика; теория множеств, теория графов, булева алгебра

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



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


Данная учебная дисциплина входит в раздел «Б.2.Математические и естественнонаучные дисциплины. Пункт Б2.Вар1 Вариативная часть» ФГОС по направлению подготовки ВПО «Информационные системы и технологии».

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

Данная учебная дисциплина взаимосвязана с другими дисциплинами, входящими в модуль Б.2. Математический, естественнонаучный цикл ФГОС по направлению подготовки ВПО «Информационные системы и технологии», а именно: «Математика », «Информатика», «Основы современных алгоритмов».

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

_______________________________________________________________________

(указывается цикл, к которому относится дисциплина; формулируя требования к входным знаниям, умениям и компетенциям студента, необходимым для ее изучения; определяются дисциплины, для которых данная дисциплина является предшествующей)

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


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

Данная дисциплина способствует формированию следующих компетенций, предусмотренных ФГОС по направлению подготовки «Информационные системы и технологии»:


а) общекультурные (ОК):
  • Готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);
  • Способность к письменной, устной и электронной коммуникации на государственном языке и необходимое знание иностранного языка (хороший английский язык) (ОК-11);


б) профессиональные (ПК):

    Проектно-конструкторская деятельность:
  • Способность проводить выбор исходных данных для проектирования (ПК-4);
  • Способность проводить моделирование процессов и систем (ПК-5);
  • Готовность разрабатывать, согласовывать и выпускать все виды проектной документации (ПК–10).

    Проектно-технологическая деятельность:
  • Способность разрабатывать средства реализации информационных технологий (методические, информационные, математические, алгоритмические, технические и программные) (ПК-12);

    Производственно-технологическая деятельность:
  • Способность использовать технологии разработки объектов профессиональной деятельности в полиграфии и издательском бизнесе (ПК-18);

    Организационно-управленческая деятельность:
  • Готовность осуществлять организацию контроля качества входной информации (ПК-22);

    Научно-исследовательская деятельность:
  • Способность проводить сбор, анализ научно-технической информации, отечественного и зарубежного опыта по тематике исследования (ПК-23);
  • Способность участвовать в постановке и проведении экспериментальных исследований (ПК-24);
  • Способность обосновывать правильность выбранной модели, сопоставляя результаты экспериментальных данных и полученных решений (ПК-25);
  • Готовность использовать математические методы обработки, анализа и синтеза результатов профессиональных исследований (ПК-26);
  • Способность оформлять полученные рабочие результаты в виде презентаций, научно-технических отчетов, статей и докладов на научно-технических конференциях (ПК–27).

    Инновационная деятельность:

    Монтажно-наладочная деятельность:





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

    ____________________________________________________________________________ (указываются в соответствии с ФГОС ВПО)

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

Иметь представление:

о направлениях и истории развития дискретной математики;

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



  • элементы математической логики и теории алгоритмов.

уметь использовать:

современные алгоритмические методы решения дискретных задач;


владеть:

навыками построения алгоритмов для решения логических и комбинаторных задач;


иметь опыт:

синтеза логических схем, оценки сложности алгоритмов


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


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


Вид учебной работы
Всего часов
Семестры

6









Аудиторные занятия (всего)
85
85









В том числе:



-
-
-
-

Лекции
51
51









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















Семинары (С)















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









Самостоятельная работа (всего)
95
95









В том числе:
-
-
-
-
-

Курсовой проект (работа)















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









Реферат















Другие виды самостоятельной работы
36
36



























Вид промежуточной аттестации (зачет, экзамен)
экзамен
Экз









Общая трудоемкость час

зач. ед.
180
180









5
5










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


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


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

1.
Тема 1. Введение
Цели и задачи дисциплины. Место и роль дисциплины в общей структуре подготовки специалистов, связь с другими дисциплинами.

2.
Тема 2. Элементы теории множеств
Понятие множества, операции над множествами, мощность множества. Отношения. Свойства отношений. Отношения эквивалентности и частичного порядка

3.
Тема 3. Функции и матрицы
Функции. Специальные функции. Обратные функции и композиция функций. Матрицы. Операции над матрицами

4.
Тема 4. Основные понятия теории графов.
Понятие графа. Типы графов. Ориентированные графы и деревья. Гамильтоновы графы. Пути и циклы Эйлера. Матрицы инцидентности и смежности.

Гиперкубы и код Грея.

5.
Тема 5. Логические схемы и автоматы.
Булева алгебра. Булевы функции. Нормальные формы. Полные системы булевых функций. Минимизация булевых функций. Логические схемы. Синтез логических схем. Оценки сложности логических схем. Конечные автоматы и их задание. Методы минимизации. Грамматики.

6.
Тема 6. Методы комбинаторики.
Основные принципы комбинаторики. Перестановки и сочетания. Комбинаторные формулы. Бином Ньютона. Задачи о размещении. Комбинаторика и вероятность.

7.
Тема 7. Сложность алгоритмов
Определения сложности алгоритма. Алгоритмически неразрешимые проблемы. Машина Тьюринга. Нижние и верхние оценки сложности. Задача о симметрии. Оптимальные алгоритмы. Алгоритмы сортировки. Алгоритм решения задач линейного программирования

(Содержание указывается в дидактических единицах. По усмотрению разработчиков материал может излагаться не в форме таблицы)


6.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами


№ п/п
Наименование обеспе-чиваемых (последую-щих) дисциплин
№ № разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин

1
2
3
4
5
6
7






1.
Интеллектуальные информационные системы и технологии
Х
Х
Х
Х
Х
Х
Х






2.
Корпоративные информационные системы



Х
Х
Х
Х
Х
Х






3.
Инструментальные средства информационных систем
Х
Х
Х
Х
Х
Х
Х






4.
Управление информационными ресурсами












Х
Х
Х






5.
Управление программными проектами



Х
Х
Х
Х
Х










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


№ п/п
Наименование раздела дисциплины
Лекц.
Практ.

зан.
Лаб.

зан.
Семин
СРС
Все-го

час.

1.
Введение
3









5
8

2.
Элементы теории множеств

8



5



15
28

3.
Функции и матрицы
8



5



15
28

4.
Основные понятия теории графов.
8



6



15
29

5.
Логические схемы и автоматы.
8



6



15
29

6.

Методы комбинаторики.
8



6



15
29

7.

Сложность алгоритмов
8



6



15
29


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



№ п/п
№ раздела дисциплины
Наименование лабораторных работ
Трудо-емкость

(час.)

1.
2.
Представление множеств. Моделирование операций над множествами.
5

2.
3.
Отношения. Композиция отношений. Функции.

5

3.
4.
Алгоритмы поиска пути. Построение остовного дерева
6

4.
5.
Минимизация булевых функций. Построение автомата Мили.
6

5.
6.
Оптимизационные задачи. Задачи о размещении.
6

6.
7.
Задача коммивояжера. Эвристические алгоритмы.

6


8. Практические занятия не предусмотрены


9. Примерная тематика курсовых работ (проектов) не предусмотрена


10. Учебно-методическое и информационное обеспечение дисциплины:


а) Основная литература
  1. О.П. Кузнецов, Г.М. Адельсон-Вельский Дискретная математика для инженеров, М.,Энергоатомиздат, 1988
  2. Р.Хаггарти, Дискретная математика для программистов, М. Техносфера, 2005
  3. Д.Андерсон Дискретная математика и комбинаторика ИД «Вильямс», 2003


б) Дополнительная
  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.–М.: МЦНМО, 2001.


в) Программное обеспечение и Интернет-ресурсы не предусмотрены


г) Базы данных, информационно-справочные и поисковые системы не предусмотрены


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


Учебная дисциплина должна быть обеспечена учебно-методической документацией и материалами. Ее содержание должно быть представлено в сети Интернет или локальной сети вуза (факультета). Для обучающихся должна быть обеспечена возможность оперативного обмена информацией с отечественными и зарубежными вузами, предприятиями и организациями, обеспечен доступ к современным профессиональным базам данных, информационным справочным и поисковым системам.

Возможности доступа в Internet.

Компьютерный класс, оснащенный современными компьютерами (IBM PC или МАС) с лицензионным программным обеспечением.

Комплекс технических средств, позволяющих проецировать изображение из программ подготовки презентаций (экран, медиапроектор, Notebook).


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


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


Рабочая программа пересмотрена и одобрена на заседании


кафедры « »____________________2010 г.


Заведующий кафедрой __________/ Марков А.А. /

_______________________________________________________