Примерная рабочая программа по дисциплине: «Дискретная математика» Факультет экономический

Вид материала

Примерная рабочая программа

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

Подобный материал:

• Примерная рабочая программа по дисциплине Вычислительная математика Экономический факультет, 92.59kb.
• Темы курсовой работы по дисциплине "дискретная математика" (Приложение к рабочей программе, 128.96kb.
• Учебная программа для специальности: (рабочий вариант) 1-310301-02 Математика (научно-педагогическая, 120.64kb.
• Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
• Рабочая программа дисциплины (модуля) Дискретная математика, 101.32kb.
• Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
• Примерная рабочая программа по дисциплине математические модели в экономике экономический, 74.05kb.
• Джеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон, 42.79kb.
• Примерная рабочая программа по дисциплине: «информацтонные технологии» Факультет экономический, 77.34kb.
• Примерная рабочая программа по дисциплине «Компьютерная обработка изображений» Факультет:, 75.51kb.

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

Томский государственный университет систем управления и радиоэлектроники

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

По дисциплине: «Дискретная математика»


Факультет экономический

Профилирующая кафедра: кафедра ЭМИС


2009

1. Цели и задачи дисциплины, ее место в учебном процессе.
   

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

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

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

знать:

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

иметь опыт:

• в осуществлении основных операций над множествами, решении систем уравнений, исследовании бинарных отношений, в том числе специальных;
  
• в построении таблиц истинности логических функций, эквивалентных преобразований, построении СКНФ и СДНФ, минимизации булевых функций;
  
• в распознавании типа комбинаторных расстановок, применении известных формул подсчета их количества, формул включения и исключения, кругов Эйлера;
  
• в составлении модели графа, осуществлении операций над графами
  

уметь:

• строить дискретные модели практически реальных объектов;
  
• применять положения и методы дискретной математики для решения задач, относящимся к темам дисциплины.
  

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

1. Содержание лекционных занятий.
   

2.1.1. Множества и их спецификации.

Определение множества, элемента множества, подмножества, способы задания множества. Операции объединения, пересечения, разности, дополнения. Свойства операций над множествами. Диаграммы Венна.

Прямые произведения множеств. Определение прямого произведения. Примеры. Теорема о мощности множества, образованного декартовым произведением n множеств.

Отношения, свойства отношений. Обратное отношение. Образ и прообраз множества А. Область определения и область значения бинарного отношения R. Композиция отношений. Определение функции и отображения. Понятие обратной функции.

Взаимнооднозначные соответствия и мощности множеств. Теоремы и мощности множеств, между которыми существует взаимнооднозначное соответствие , о количестве подмножеств конечного множества. Понятия равномощных множеств, счетных множеств. Теорема Кантора.

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


2.1.2 . Алгебра логики, логические функции.

Алгебра логики, логические функции (или переключательные функции (ПФ) и способы их задания.). Суперпозиции и формулы. Представление логических функций различными формулами. Эквивалентные (равносильные) функции. Существенные и фиктивные переменные. Двойственные функции.

Булева алгебра функций и эквивалентные преобразования в ней. Определение булевой алгебры функций. Основные свойства (аксиомы) булевых операций: ассоциативность, коммутативность, дистрибутивность, правила де Моргана и т.д. Правила подстановки и замены.

Специальные разложения ПФ. Совершенные нормальные формы. Определения совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ). Составление СДНФ и СКНФ по таблицам истинности. Приведение к СДНФ. Понятие дизъюнктивной нормальной формы (ДНФ). Построение ДНФ с помощью эквивалентных преобразований. Переход от конъюнктивной нормальной формы (КНФ) к ДНФ. Правило «расщепления» для перехода от ДНФ к СДНФ. Приведение к СКНФ. Понятие КНФ. Построение КНФ с помощью эквивалентных преобразований, переход от ДНФ к КНФ. Правило «расщепления» для перехода от КНФ к СКНФ.

Минимизация логических(переключательных) функций. Теорема о возможности и однозначности представления логических функций в виде сокращенной дизъюнктивной (конъюнктивной) нормальной формы. Понятие импликанты. Тупиковые ДНФ. Понятие минимальной ДНФ (МДНФ). Графический способ построение МДНФ.

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

Определение базиса. Примеры функционально-полных базисов.

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

Разрешимые и неразрешимые проблемы. Схемы алгоритмов. Схемы потоков данных.


2.1.3. Основы комбинаторики .

Основы комбинаторики. Общие правила комбинаторики. Формула включений и выключений. Правила суммы и произведения. Примеры решения задач. Круги Эйлера. Типы расстановок.

Размещения с повторениями и без них. Основные признаки расстановки типа «размещения с повторениями». Теорема о количестве таких расстановок. Основные признаки «размещения без повторений». Теорема о подсчете числа расстановок указанного типа.

Перестановки с повторениями и без них. Основные признаки перестановок без повторений. Теорема о подсчете числа расстановок указанного типа. Перестановки с повторениями. Теорема о подсчете количества таких перестановок.

Сочетания с повторениями и без них. Основные признаки сочетаний без повторений. Теорема о подсчете количества таких сочетаний. Основные признаки сочетаний с повторениями. Теорема о подсчете количества сочетаний с повторениями. Основные свойства сочетаний. Производящие функции.


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

Элементы теории графов. Основные определения, типы графов. Определение графа, вершины, ребра (дуги, петли, звена), отношение инцидентности, степень вершины. Основные типы графов (орграф, неорграф, униграф, мультиграф, полный граф). Маршруты, цепи, циклы. Связность. Граф типа «дерево», остов, разрез.

Планарные графы. Способы задания графов. Матрица инцидентности для ориентированного и неориентированного графа. Список ребер. Матрица смежности для ориентированного и неориентированного графа.

Определение путей и кратчайших путей в графах.

2. Содержание практических занятий .
   

Темы	Деятельность студента. Решая задачи, студент:
Операции над множествами. Доказательство известных тождеств. Операции над множествами. Доказательство тождеств.	использует определения операций над множествами; выбирает способ доказательства тождеств. использует знания, полученные ранее и самостоятельно доказывает тождества.
Решение систем уравнения.	учиться решать системы уравнений относительно множеств; совместно с преподавателем разрабатывает методику решения таких задач.
Отношения и функции	использует определения, отношения и функции; решает совместно с преподавателем соответствующие задачи.
Специальные бинарные отношения	использует практически такие понятия как «эквивалентность», «частичный порядок на А», «линейный порядок на А», «монотонное отображение».
Таблицы истинности	учится строить таблицы истинности; определяет существенные и фиктивные переменные; определяет двойственные функции.
Совершенные ДНФ и КНФ. Минимизация булевых функций.	Преобразует ПФ. строит СДНФ и СКНФ, используя таблицу истинности и эквивалентные преобразования; учится переходить от одних форм к другим.
Правила суммы и произведения. Типы расстановок. Типы расстановок.	учится различать различные типы расстановок, их отличие друг от друга; решает задачи на типы расстановок; устанавливает роль правил суммы и произведения для анализа этих расстановок. использует полученные ранее знания для решения конкретных задач.
Способы задания графов. Операции над графами.	формирует графы различных типов; производит над ними соответствующие операции.
Поиск кратчайших путей в графе методом Дейкстры	излагает сущность основных методов поиска кратчайших путей между парами вершин графа; разрабатывает алгоритм метода Дейкстры и программу, реализующую данный алгоритм. приводит примеры применения программы на графе

3. Содержание самостоятельной работы.
   

№	Наименование работы	Аннотация	План	Форма контроля
1.	Методы определения связности вершин графа	В работе необходимо изложить сущность основных методов определения связности вершин графа. Разработать алгоритмы этих методов и программы, реализующие данные алгоритмы. Привести примеры применения данных программ.	1. Основные понятия и определения теории графов. 2. Методы определения связности вершин графа. 3. Алгоритмы определения связности вершин графа. 4. Разработка программного обеспечения. 5. Примеры применения программ.	Опрос. Отчет.
2.	Поиск кратчайших путей в графе методом Форда-Беллмана	В работе необходимо изложить сущность основных методов поиска кратчайших путей между парами вершин графа. Разработать алгоритм метода Форда-Беллмана и программу, реализующую данный алгоритм. Привести примеры применения программы на графе.	1. Основные понятия и определения теории графов. 2. Методы определения кратчайших путей в графе. 3. Алгоритм Форда-Беллмана определения кратчайших путей в графе. 4. Разработка программного обеспечения. 5. Примеры применения программы. Оценка сложности алгоритма.	Опрос. Отчет.
3	Поиск кратчайших путей в графе методом Флойда	Изложить сущность основных методов поиска кратчайших путей между парами вершин графа. Разработать алгоритм метода Флойда и программу, реализующую данный алгоритм. Привести примеры применения программы на графе	1. Основные понятия и определения теории графов. 2. Методы определения кратчайших путей в графе. 3. Алгоритм Флойда определения кратчайших путей в графе. 4. Разработка программного обеспечения. 5. Примеры применения программы. Оценка сложности алгоритма.	Опрос. Отчет.
4	Определение максимального потока в сети	Необходимо изложить сущность основных методов определения максимального потока в сети. Разработать алгоритм метода увеличивающих цепей и программу, реализующую данный алгоритм. Привести примеры применения программы на графе.	1. Основные понятия и определения теории графов. 2. Методы определения максимального потока в сети. 3. Алгоритм наращивания потока в сети. 4. Разработка программного обеспечения. 5. Примеры применения программы. Оценка сложности алгоритма.	Опрос. Отчет.
5	Применение теории графов в технике	Изложить прикладные аспекты теории графов в электротехнике. Рассмотреть различные физические системы с сосредоточенными компонентами: электрические и электронные цепи, механические и пневматические системы. Возможность их представления в виде полюсных графов	1. Основные понятия и определения теории графов. 2. Физические системы с сосредоточенными компонентами. 3. Полюсные графы. 4. Электрические цепи. 5. Механические поступательные системы.	Опрос. Отчет.
6	Алгоритмы раскраски графов	Рассмотреть операторные алгоритмические системы: логические схемы алгоритмов Ляпунова, блок-схемный метод алгоритмизации. Применение их для записи алгоритмов и процесса функционирования конечных автоматов с памятью.	1. История задачи о четырех красках. 2. Правильная раскраска графа. Количество правильных раскрасок графа. 3. Хроматическое число. 4. Алгоритмы раскраски графа. 5. Разработка программного обеспечения. 6. Примеры применения программы. Оценка сложности алгоритма.	Опрос. Отчет.
7	Поиск кратчайших путей в графе методом динамического программирования	Изложить сущность основных методов поиска кратчайших путей между парами вершин графа. Разработать алгоритм поиска кратчайших путей методом динамического программирования и программу, реализующую данный алгоритм. Привести примеры применения программы на графе	1. Основные понятия и определения теории графов. 2. Методы определения кратчайших путей в графе. 3. Определение кратчайших путей в графе методом динамического программирования. 4. Разработка программного обеспечения. 5. Примеры применения программы. Оценка сложности алгоритма.	Опрос. Отчет.
8	Сравнительный анализ поисков кратчайших путей в графе различными известными методами	Изложить сущность основных методов поиска кратчайших путей между парами вершин графа. Анализировать алгоритмы поиска кратчайших путей. Привести примеры их предпочтительного применения.	1. Основные понятия и определения теории графов. 2. Методы определения кратчайших путей в графе. 3. Анализ алгоритмов кратчайших путей в графе. 4. Оценка надежности соответствующего программного обеспечения. 5.Оценка сложности алгоритмов.	Опрос. Отчет.

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

3.1. Основная:

1. Смыслова З.А. Дискретная математика: Учебное пособие. - Томск: ТМЦДО, 2000.
   
2. Зюзьков В.М. Дискретная математика. - Томск: ТМЦДО, 1999.
   

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

1. Новиков Ф.А. Дискретная математика для программистов. – СПб. Питер: 2001.
   
2. Жигалова Е.Ф. Дискретная математика. - Томск: ТМЦДО, 2000.
   
3. Липский В. Комбинаторика для программистов. - М.: Наука, 1989.
   

3.3. Рекомендуемая литература для самостоятельной работы:

1. Хаггарти Р. Дискретная математика для программистов. - Москва: Техносфера, 2003. – 320с
   
2. Кузнецов О.П., Андельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 476с.
   
3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1997 – 367с.
   
4. Вольвачев Р.Т. Элементы математической логики и теории множеств. – Минск: Университетское, 1986 – 112с.
   
5. Белов В.В. и др. Теория графов. - М.: Высшая школа, 1976.
   
6. Ф.Харари Теория графов. - М.: Мир, 1973.
   
7. Нефедов В. Н., Осипова В. А. Курс дискретной математики: учебное пособие для вузов. - М.: МАИ, 1992.
   
8. Лавров В.И., Максимова Л.Л. Задачи по теории множеств, математической логики и теории алгоритмов. – М.: Наука, 1984 – 223с.
   

ПРИЛОЖЕНИЕ К РАБОЧЕЙ ПРОГРАММЕ

по дисциплине «Дискретная математика»


Балльно-рейтинговая система оценки знаний


Оценка объема и качества знаний студентов по результатам семестровой аттестации определяется в соответствии с Положением о балльно-рейтинговой системе оценки знаний и обеспечения качества учебного процесса. Семестровая балльная раскладка по дисциплине приведена в таблице 1.


Таблица 1. Дисциплина Дискретная математика (зачет, лекции, практические работы)

Элементы учебной деятельности	Максимальный балл на 1-ую КТ с начала семестра	Максимальный балл за период между 1КТ и 2КТ	Максимальный балл за период между 2КТ и на конец семестра	Всего за семестр
Посещение занятий	4	4	4	12
Тестовый контроль	6	11		17
Выполнение практических работ	5	6	18	29
Компонент своевременности	4	4	4	12
Выполнение и защита творческих самостоятельных работ			30	30
Итого максимум за период:	19	25	56	100
Нарастающим итогом	19	44	70	100