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

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


Смотрите также:
Рабочая программа по курсу “Теория компиляции.” ( наименование дисциплины по учебному плану )...
Рабочая программа дисциплина Математика (наименование дисциплины согласно учебному плану)...
Рабочая программа дисциплина Математика (наименование дисциплины согласно учебному плану)...
Рабочая программа математика наименование дисциплины по учебному плану Код дисциплины по...
Рабочая программа дисциплина Информатика и математика (часть 1) (наименование дисциплины...
Рабочая программа дисциплина Информатика и математика (часть 2) (наименование дисциплины...
Рабочая программа социальная антропология наименование дисциплины по учебному плану Код...
Рабочая программа математика ( наименование дисциплины по учебному плану )...
Рабочая программа математика ( наименование дисциплины по учебному плану )...
Рабочая программа математика ( наименование дисциплины по учебному плану )...
Рабочая программа учебной дисциплины спасательная техника и базовые машины (наименование...
Рабочая программа учебной дисциплины тактика Сил рсчс и го (наименование дисциплины по учебному...



Загрузка...
скачать
Нижегородский государственный технический университет

Факультет ИРИТ

( наименование факультета )


УТВЕРЖДАЮ:

Первый проректор

Кошелев О.С.

“ ” ________2009 г.


Р А Б О Ч А Я П Р О Г Р А М М А

по курсу “Дискретная математика”

( наименование дисциплины по учебному плану )

Направление подготовки 510200 Прикладная математика и информатика

( шифр и наименование )

Направление специальности 010000 Естественнонаучные специальности

( шифр и наименование )

Специальность 010200 Прикладная математика и информатика

( шифр и наименование )

Кафедра “Прикладная математика “

( наименование )


Курс 1

Семестр 1, 2


Общая трудоемкость дисциплины 200 ( час )

Аудиторные занятия 144 ( час )


Лекции 72 ( час ) Самостоятельная

работа 56 ( час )

Лабораторные

занятия ( час )


Практические Экзамен 1, 2 ( семестр )

занятия 72 ( час )


Курсовой проект Зачет ( семестр )

( работа ) ( час )


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

Работы ( час )


Рабочая программа утверждена на заседании кафедры

“ ” ___________ 2009 г.


Зав. кафедрой ________________ ___Митяков С Н.__

( подпись ) ( Ф.И.О.)

Председатель координационного научно-методического совета

по направлению подготовки 510200 Прикладная математика и информатика

( шифр, наименование )

Митяков С Н.__

( подпись ) ( Ф.И.О. )

“ ” 2009 г.


Председатель НМС по блоку общепрофессиональных дисциплин

( шифр, наименование специальности )

Ершов Н.Ф.

( подпись ) ( Ф.И.О. )

“ ” 2009 г.


^ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки бакалавра 510200 – Прикладная математика и информатика и направлению специальности дипломированного специалиста 010200 – Прикладная математика и информатика.

Курс «^ Дискретная математика» изучается студентами специальности 010200 в первом и втором семестрах. Целью данного курса является изучение фундаментальных свойств дискретных математических объектов, к которым относятся множества, графы, логические функции, комбинаторные модели, алгоритмы. Знание и овладение методами и понятиями дискретной математики необходимо инженеру-исследователю, призванному решать сложные задачи в научной и инженерной областях, а также иных областях человеческой активности. В результате изучения данной дисциплины студенты осваивают теоретико-множественный подход к решению многих практических задач, овладевают методами математической логики, комбинаторного анализа, теории графов и алгоритмов.

Курс состоит из пяти разделов. Параллельно с чтением курса проводятся практические занятия, направленные на закрепление теоретического материала путём решения задач.


^ ОПИСАНИЕ СОДЕРЖАНИЯ ТЕМ ЛЕКЦИЙ ПО РАЗДЕЛАМ КУРСА

  1. Введение.

Цель курса, его связь с другими курсами. О сферах применения дискретно-математических методов. Некоторые прикладные примеры.

  1. ^ Математическая логика.

Понятие о математической логике. Логика высказываний и логика предикатов.

Определения двоичного набора и логической функции. Область определения и значения логических функций, существенные и фиктивные переменные. Число логических функций, зависящих от n аргументов. Элементарные логические функции. Логические формулы. Алгебра логических функций. Дизъюнктивная и конъюнктивная нормальные формы. Булева алгебра и теория множеств. Основные классы логических функций. Функционально полная система логических функций. Теория Поста-Яблонского. Понятие о минимальной логической функции. Алгоритмы минимизации логической функции. Схемы из логических элементов. Синтез логических схем.

Определение предиката. Операции над предикатами, кванторы существования и всеобщности. Формулы логики предикатов.

  1. ^ Комбинаторный анализ.

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

  1. ^ Теория графов.

Понятие о графе и основные определения теории графов. Бинарные отношения и графы. Операции над графами. Матрицы графов. Отношение связность в графе.

Эйлеров цикл и критерий его существования. Алгоритм нахождения эйлерова цикла. Гамильтонов цикл и его свойства. Алгоритм нахождения оптимального Гамильтонова цикла.

Деревья и основные формулы подсчета числа покрывающих деревьев. Алгоритмы нахождения минимального и максимального покрывающего дерева в неориентированном и ориентированном графе. Задача о дереве кратчайших расстояний и алгоритм её решения.

Задача о раскраске графа. Хроматическое число. Функция Грани.

  1. ^ Теория алгоритмов.

Интуитивное понятие алгоритма. Проблема слов в ассоциативном исчислении. Нормальный алгоритм Маркова. Сведение любого алгоритма к численному алгоритму (гёделизация).

Элементарные функции. Примитивно-рекурсивные функции. Общерекурсивные функции. Тезис Чёрча.

Описание и примеры машин Тьюринга. Композиция машин Тьюринга. Вычисления на машинах Тьюринга.


^ СЕТКА РАСПРЕДЕЛЕНИЯ ЧАСОВ ПО ТЕМАМ.




Наименование темы


Лекции


Практич. занятия


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. Логика высказываний.

  3. Логика предикатов.

  4. Определения двоичного набора и логической функции.

  5. Элементарные логические функции.

  6. Логические формулы.

  7. Алгебра логических функций.

  8. Дизъюнктивная и конъюнктивная нормальные формы.

  9. Булева алгебра и теория множеств.

  10. Основные классы логических функций.

  11. Теория Поста-Яблонского.

  12. Понятие о минимальной логической функции.

  13. Алгоритмы минимизации логической функции.

  14. Определение предиката.

  15. Операции над предикатами, кванторы существования и всеобщности.

  16. Формулы логики предикатов.

  17. Предмет комбинаторики. Правила суммы и произведения.

  18. Производящие функции для сочетаний и перестановок.

  19. Циклы перестановок.

  20. Цикловые классы.

  21. Принципы включений и исключений в комбинаторике.

  22. Понятие о графе. Бинарные отношения и графы. Операции над графами.

  23. Эйлеров цикл и критерий его существования.

  24. Гамильтонов цикл и его свойства.

  25. Понятие дерева.

  26. Нормальный алгоритм Маркова.

  27. Примитивно-рекурсивные функции.

  28. Общерекурсивные функции.

  29. Тезис Чёрча.

  30. Описание и примеры машин Тьюринга.

ЛИТЕРАТУРА




^ Автор(ы), ниаменование

Изд-во

Год изд.


Кол-во в НГТУ


Основная

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.
ТипРабочая программа, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх