Рабочая программа по дисциплине "Дискретная математика" для специальности 230105 (220400)
|
Скачать 71.62 Kb.
|
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Томский государственный университет систем управления и радиоэлектроники ( ТУСУР )
РАБОЧАЯ ПРОГРАММА по дисциплине “Дискретная математика” для специальности 230105 (220400) “Программное обеспечение вычислительной техники и автоматизированных систем” Факультет - систем управления Профилирующая кафедра - автоматизированных систем управления Курс - 1 Семестр - 2 Учебный план набора 2005 года и последующих лет Распределение учебного времени (всего часов) Лекции - 34 часа Практические занятия - 51 час Всего ауд. занятий - 85 часов Самостоятельная работа - 55 часов Общая трудоемкость - 140 часов Экзамен – 2 семестр Зачет - 2 семестр 2007 Рабочая программа составлена на основании ГОС ВО по направлению 654600 Информатика и вычислительная техника (специальность 230105 (220400) – “Программное обеспечение вычислительной техники и автоматизированных систем”), утвержденного 27.03.2000г, рассмотрена и утверждена на заседании кафедры АСУ “____“ ____________2007 г, протокол №______ Разработчик, доцент кафедры АСУ Е.Н.Сафьянова Зав. обеспечивающей кафедрой АСУ А.М.Кориков Рабочая программа согласована с факультетом, профилирующей и выпускающей кафедрой специальности Декан ФСУ Н.В. Замятин Зав. профилирующей кафедрой АСУ А.М.Кориков
ПРОЦЕССЕ Цель дисциплины «Дискретная математика» изучение основ теории множеств, теории графов, комбинаторного анализа как аппарата для построения моделей дискретных систем. Дискретная математика является обязательной дисциплиной цикла «Математические и общие естественнонаучные дисциплины». Знания и навыки, полученные при ее изучении, используются в дисциплинах: «Программирование», «Структуры и алгоритмы обработки данных в ЭВМ» и т.д. 2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 2.1. Лекции. Тема 1. Основные понятия теории множеств. Лекции – 4 часа, самостоятельная работа – 2 часа. Основные термины. Операции над множествами. Свойства операций. Понятие отношения на множестве. Свойства отношений. Виды отношений. Экстремальные элементы множеств. Отображения множеств. Тема 2. Основные определения теории графов. Лекции – 4 часа, самостоятельная работа – 4 часа. Способы задания графа. Ориентированные и неориентированные графы. Цепи, циклы, пути, контуры графов. Частичные графы, подграфы, частичные подграфы. Связность в графах. Изоморфизм графов. Отношения на множествах и графы. Тема 3. Операции над графами. Лекции – 4 часа, самостоятельная работа – 2 часа. Сумма, пересечение, композиция и транзитивное замыкание графов. Декартово произведение и декартова сумма графов. Тема 4. Характеристики графов. Лекции – 4 часа, самостоятельная работа – 4 часа. Матрицы смежности и инциденций графов. Степени графов. Цикломатическое число. Хроматическое число. Множества внутренней и внешней устойчивости. Тема 5. Характеристики расстояний в графах. Лекции – 7 часов, самостоятельная работа – 4 часа. Отклонение, отклоненность, радиус, диаметр, центр и периферийные вершины графа. Определение путей и кратчайших путей в графах. Алгоритм Дейкстры. Обход графа. Эйлеровы и гамильтоновы цепи, циклы, пути, контуры. Тема 6. Предмет комбинаторного анализа. Лекции – 4 часа, самостоятельная работа – 2 часа. Виды задач комбинаторного анализа. Постановка и примеры задач комбинаторного программирования. Тема 7. Основные понятия и операции комбинаторики. Лекции – 4 часа, самостоятельная работа – 3 часа. Упорядоченные и неупорядоченные выборки. Обобщенные правила суммы и произведения. Определение числа сочетаний и перестановок. Разложение на циклы. Размещения и заполнения. Тема 8. Аппарат производящих функций. Лекции – 4 часа, самостоятельная работа – 2 часа. Производящие функции для сочетаний и перестановок. Обычная и экспоненциальная производящие функции. Всего часов лекций 35, самостоятельная работа 23 часа. 2.2. Практические занятия. 1. Операции над множествами - 4 часа 2. Отношения на множествах и их свойства - 2 часа 3. Виды отношений на множествах - 2 часа 4. Неориентированные и ориентированные графы. Изоморфизм - 4 часа 5. Матрицы графов - 4 часа 6. Отношения на графах - 4 часа 7. Операции над графами - 6 часов 8. Характеристики графов - 2 часа 9. Характеристики расстояний в графах - 4 часа 10. Определение кратчайшего пути в графе - 4 часа 11. Эйлеровы пути, цепи, циклы, контуры - 4 часа 12. Гамильтоновы пути, цепи, циклы, контуры - 4 часа 13. Правила суммы и произведения - 2 часа 14. Перестановки и сочетания - 4 часа 15. Перечислительные задачи комбинаторики - 2 часа Часть практических заданий выполняется с использованием вычислительной техники, что требует увеличения затрат времени на самостоятельную работу. Всего часов практических занятий 52. Для подготовки к практическим занятиям и выполнения домашних заданий к ним требуется 30 часов самостоятельной работы. 2.3. Самостоятельная работа. № Наименование работы Число часов Формы контроля 1 Проработка лекционного материала 23 экзамен 2 Выполнение практических заданий 30 опрос 3. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ 3.1. Основная литература.
3.2. Дополнительная литература.
4. ПРИМЕНЕНИЕ РЕЙТИНГОВОЙ СИСТЕМЫ Контроль обучения – зачет, экзамен. Элементы контроля – практические занятия. Максимальный рейтинг – 120 баллов. Правила формирования рейтинга.
|
