Рабочая программа по курсу “Дискретная математика” ( наименование дисциплины по учебному плану )

скачать Нижегородский государственный технический университет Факультет ИРИТ ( наименование факультета ) УТВЕРЖДАЮ: Первый проректор Кошелев О.С. “ ” ________2009 г. Р А Б О Ч А Я П Р О Г Р А М М А по курсу “Дискретная математика” ( наименование дисциплины по учебному плану ) Направление подготовки 510200 Прикладная математика и информатика ( шифр и наименование ) Направление специальности 010000 Естественнонаучные специальности ( шифр и наименование ) Специальность 010200 Прикладная математика и информатика ( шифр и наименование ) Кафедра “Прикладная математика “ ( наименование ) Курс 1 Семестр 1, 2 Общая трудоемкость дисциплины 200 ( час ) Аудиторные занятия 144 ( час ) Лекции 72 ( час ) Самостоятельная работа 56 ( час ) Лабораторные занятия ( час ) Практические Экзамен 1, 2 ( семестр ) занятия 72 ( час ) Курсовой проект Зачет ( семестр ) ( работа ) ( час ) Расчетно-графические Работы ( час ) Рабочая программа утверждена на заседании кафедры “ ” ___________ 2009 г. Зав. кафедрой ________________ ___Митяков С Н.__ ( подпись ) ( Ф.И.О.) Председатель координационного научно-методического совета по направлению подготовки 510200 Прикладная математика и информатика ( шифр, наименование ) Митяков С Н.__ ( подпись ) ( Ф.И.О. ) “ ” 2009 г. Председатель НМС по блоку общепрофессиональных дисциплин ( шифр, наименование специальности ) Ершов Н.Ф. ( подпись ) ( Ф.И.О. ) “ ” 2009 г. ^ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки бакалавра 510200 – Прикладная математика и информатика и направлению специальности дипломированного специалиста 010200 – Прикладная математика и информатика. Курс «^ Дискретная математика» изучается студентами специальности 010200 в первом и втором семестрах. Целью данного курса является изучение фундаментальных свойств дискретных математических объектов, к которым относятся множества, графы, логические функции, комбинаторные модели, алгоритмы. Знание и овладение методами и понятиями дискретной математики необходимо инженеру-исследователю, призванному решать сложные задачи в научной и инженерной областях, а также иных областях человеческой активности. В результате изучения данной дисциплины студенты осваивают теоретико-множественный подход к решению многих практических задач, овладевают методами математической логики, комбинаторного анализа, теории графов и алгоритмов. Курс состоит из пяти разделов. Параллельно с чтением курса проводятся практические занятия, направленные на закрепление теоретического материала путём решения задач. ^ ОПИСАНИЕ СОДЕРЖАНИЯ ТЕМ ЛЕКЦИЙ ПО РАЗДЕЛАМ КУРСА Введение. Цель курса, его связь с другими курсами. О сферах применения дискретно-математических методов. Некоторые прикладные примеры. ^ Математическая логика. Понятие о математической логике. Логика высказываний и логика предикатов. Определения двоичного набора и логической функции. Область определения и значения логических функций, существенные и фиктивные переменные. Число логических функций, зависящих от n аргументов. Элементарные логические функции. Логические формулы. Алгебра логических функций. Дизъюнктивная и конъюнктивная нормальные формы. Булева алгебра и теория множеств. Основные классы логических функций. Функционально полная система логических функций. Теория Поста-Яблонского. Понятие о минимальной логической функции. Алгоритмы минимизации логической функции. Схемы из логических элементов. Синтез логических схем. Определение предиката. Операции над предикатами, кванторы существования и всеобщности. Формулы логики предикатов. ^ Комбинаторный анализ. О предмете комбинаторики. Правила суммы и произведения. Сочетания из n элементов при различных спецификациях. Перестановки из n элементов при различных спецификациях. Производящие функции для сочетаний и перестановок. Примеры использования производящих функций для получения комбинаторных формул. Размещения и занятость. Циклы перестановок. Цикловые классы. Принципы включений и исключений в комбинаторике. ^ Теория графов. Понятие о графе и основные определения теории графов. Бинарные отношения и графы. Операции над графами. Матрицы графов. Отношение связность в графе. Эйлеров цикл и критерий его существования. Алгоритм нахождения эйлерова цикла. Гамильтонов цикл и его свойства. Алгоритм нахождения оптимального Гамильтонова цикла. Деревья и основные формулы подсчета числа покрывающих деревьев. Алгоритмы нахождения минимального и максимального покрывающего дерева в неориентированном и ориентированном графе. Задача о дереве кратчайших расстояний и алгоритм её решения. Задача о раскраске графа. Хроматическое число. Функция Грани. ^ Теория алгоритмов. Интуитивное понятие алгоритма. Проблема слов в ассоциативном исчислении. Нормальный алгоритм Маркова. Сведение любого алгоритма к численному алгоритму (гёделизация). Элементарные функции. Примитивно-рекурсивные функции. Общерекурсивные функции. Тезис Чёрча. Описание и примеры машин Тьюринга. Композиция машин Тьюринга. Вычисления на машинах Тьюринга. ^ СЕТКА РАСПРЕДЕЛЕНИЯ ЧАСОВ ПО ТЕМАМ. № Наименование темы Лекции Практич. занятия 1. Введение 4 2. Математическая логика 20 24 3. Комбинаторика 16 24 4. Теория графов 16 20 5. Теория алгоритмов 12 4 Всего часов 72 72 ^ ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ Виды самостоятельной работы Объем самостоятельной работы по рабочему плану (час) 1. Проработка лекционного материала (а так же дополнительных тем, указанных лектором) 10 2. Подготовка к практическим занятиям 30 3. Подготовка к лабораторным занятиям. - 4. Подготовка реферата по теме. - 5. Выполнение курсовой работы (проекта) - 6. Выполнение расчетно-графической работы. - 7. Подготовка к текущему контролю (тестированию и т.д.) - 8. Подготовка к промежуточному контролю. 6 9. Подготовка к экзамену (зачету). 10 Итого 56 Контрольные вопросы Понятие математической логики. Логика высказываний. Логика предикатов. Определения двоичного набора и логической функции. Элементарные логические функции. Логические формулы. Алгебра логических функций. Дизъюнктивная и конъюнктивная нормальные формы. Булева алгебра и теория множеств. Основные классы логических функций. Теория Поста-Яблонского. Понятие о минимальной логической функции. Алгоритмы минимизации логической функции. Определение предиката. Операции над предикатами, кванторы существования и всеобщности. Формулы логики предикатов. Предмет комбинаторики. Правила суммы и произведения. Производящие функции для сочетаний и перестановок. Циклы перестановок. Цикловые классы. Принципы включений и исключений в комбинаторике. Понятие о графе. Бинарные отношения и графы. Операции над графами. Эйлеров цикл и критерий его существования. Гамильтонов цикл и его свойства. Понятие дерева. Нормальный алгоритм Маркова. Примитивно-рекурсивные функции. Общерекурсивные функции. Тезис Чёрча. Описание и примеры машин Тьюринга. ЛИТЕРАТУРА № ^ Автор(ы), ниаменование Изд-во Год изд. Кол-во в НГТУ Основная 1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров., 2-е изд., переработанное и дополненное. М.: Энергоатомиздат 1988 20 2. Колмогоров А.Н., Фомин С.В. Элементы теории функции и функционального анализа М.: Наука 1968 10 3. Поспелов Д.А. Логические методы анализа и синтеза схем М.: Мир 1974 23 Яблонский С.В. Введение в дискретную математику М.: Наука 1979 Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие М.: Изд-во МАИ 1992. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер 2001 Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука 1977 Дополнительная 4. Риордан Д. Введение в комбинаторный анализ М.: Наука 1963 2 5. Оре 0. Теория графов М.: Мир 1980 2 6. Айзерман и др. Логика. Алгоритмы. Автоматы М.: Наука 1981 4 Харари Ф. Теория графов.,. М.: Мир 1973 Белова Р.В. Элементы теории конечных автоматов: Учеб. пособие Горький: Горьк. гос. ун-т 1987 Гилл А. Введение в теорию автоматов. М.: Наука 1966 Алексеев В.Е., Белова Р.В. Ограниченно-детерминированные функции: Метод. разработка Горький: ГГУ 1983 Сайт для студентов www.kovriguineda.ucoz.ru Н.Новгород 2009 Составил: Ковригин Д.А. Скачать 105,95 Kb. оставить комментарий Дата 25.09.2011 Размер 105,95 Kb. Тип Рабочая программа, Образовательные материалы