скачать Нижегородский государственный технический университет Факультет ИРИТ ( наименование факультета ) УТВЕРЖДАЮ: Первый проректор Кошелев О.С. “ ” ________2009 г. Р А Б О Ч А Я П Р О Г Р А М М А по курсу “Дискретная математика” ![]() Направление подготовки 510200 Прикладная математика и информатика ![]() ![]() ( шифр и наименование ) ![]() ( шифр и наименование ) ![]() ( наименование ) ![]() ![]() ![]() ![]() ![]() ![]() Лабораторные ![]() ![]() ![]() ![]() ![]() Расчетно-графические ![]() Рабочая программа утверждена на заседании кафедры “ ” ___________ 2009 г. Зав. кафедрой ________________ ___Митяков С Н.__ ( подпись ) ( Ф.И.О.) Председатель координационного научно-методического совета ![]() ( шифр, наименование ) ![]() ![]() ( подпись ) ( Ф.И.О. ) ![]() ![]() ( шифр, наименование специальности ) ![]() ![]() ( подпись ) ( Ф.И.О. ) ![]() ^ Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки бакалавра 510200 – Прикладная математика и информатика и направлению специальности дипломированного специалиста 010200 – Прикладная математика и информатика. Курс «^ » изучается студентами специальности 010200 в первом и втором семестрах. Целью данного курса является изучение фундаментальных свойств дискретных математических объектов, к которым относятся множества, графы, логические функции, комбинаторные модели, алгоритмы. Знание и овладение методами и понятиями дискретной математики необходимо инженеру-исследователю, призванному решать сложные задачи в научной и инженерной областях, а также иных областях человеческой активности. В результате изучения данной дисциплины студенты осваивают теоретико-множественный подход к решению многих практических задач, овладевают методами математической логики, комбинаторного анализа, теории графов и алгоритмов. Курс состоит из пяти разделов. Параллельно с чтением курса проводятся практические занятия, направленные на закрепление теоретического материала путём решения задач. ^
Цель курса, его связь с другими курсами. О сферах применения дискретно-математических методов. Некоторые прикладные примеры.
Понятие о математической логике. Логика высказываний и логика предикатов. Определения двоичного набора и логической функции. Область определения и значения логических функций, существенные и фиктивные переменные. Число логических функций, зависящих от n аргументов. Элементарные логические функции. Логические формулы. Алгебра логических функций. Дизъюнктивная и конъюнктивная нормальные формы. Булева алгебра и теория множеств. Основные классы логических функций. Функционально полная система логических функций. Теория Поста-Яблонского. Понятие о минимальной логической функции. Алгоритмы минимизации логической функции. Схемы из логических элементов. Синтез логических схем. Определение предиката. Операции над предикатами, кванторы существования и всеобщности. Формулы логики предикатов.
О предмете комбинаторики. Правила суммы и произведения. Сочетания из n элементов при различных спецификациях. Перестановки из n элементов при различных спецификациях. Производящие функции для сочетаний и перестановок. Примеры использования производящих функций для получения комбинаторных формул. Размещения и занятость. Циклы перестановок. Цикловые классы. Принципы включений и исключений в комбинаторике.
Понятие о графе и основные определения теории графов. Бинарные отношения и графы. Операции над графами. Матрицы графов. Отношение связность в графе. Эйлеров цикл и критерий его существования. Алгоритм нахождения эйлерова цикла. Гамильтонов цикл и его свойства. Алгоритм нахождения оптимального Гамильтонова цикла. Деревья и основные формулы подсчета числа покрывающих деревьев. Алгоритмы нахождения минимального и максимального покрывающего дерева в неориентированном и ориентированном графе. Задача о дереве кратчайших расстояний и алгоритм её решения. Задача о раскраске графа. Хроматическое число. Функция Грани.
Интуитивное понятие алгоритма. Проблема слов в ассоциативном исчислении. Нормальный алгоритм Маркова. Сведение любого алгоритма к численному алгоритму (гёделизация). Элементарные функции. Примитивно-рекурсивные функции. Общерекурсивные функции. Тезис Чёрча. Описание и примеры машин Тьюринга. Композиция машин Тьюринга. Вычисления на машинах Тьюринга. ^
^
Контрольные вопросы
ЛИТЕРАТУРА
Составил: Ковригин Д.А.
|