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

Скачать 123.9 Kb.

Дата	12.10.2012
Размер	123.9 Kb.
Тип	Рабочая программа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования Московский государственный институт электроники и математики (технический университет)

«Утверждаю»

Декан факультета АВТ

Петросянц К.О

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

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

Направление подготовки - 654600 Информатика и вычислительная техника

Номер специальности - 220100 Вычислительные машины, комплексы, системы и сети

Факультет - Автоматики и вычислительной техники Кафедра - ЭВА

Москва - 2004 г.

1. Цели и задачи дисциплины.

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

Задачи курса:

изучение методик составления математических моделей объектов и процессов конечной структуры с позиций системного подхода,
изучение методов поиска и оценки решений с привлечением математических моделей дискретных структур.

2. Требования к уровню освоения содержания дисциплины.

(требования к знаниям, умениям и навыкам, приобретенным в результате изучения дисциплины).

3. Объем дисциплины и виды учебной деятельности.

Вид учебной работы	Всего часов	Семестры
Общая трудоемкость дисциплины	90	4	5
Аудиторные занятия
Лекции (Л)	54	4	5
Практические занятия (ПЗ)	36	4	5
Семинары
Лабораторные работы (ЛР)
И (или) другие виды аудиторных занятий
Самостоятельная работа
Курсовой проект
Расчетно-графические работы
Реферат
И (или) другие виды самостоятельной работы
Вид итогового контроля (зачет, экзамен)	Экз.	4

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

4.1 Разделы дисциплины и виды занятий

(допускается название п.4.1 «Тематический план»)

		Аудиторные занятия
№ п/п	Раздел дисциплины	Лекции	ПЗ (или С)	ЛР
1	Вводные положения	*
2	Множества	*
3	Графы	*
4	Математическая логика	*
5	Алгоритмы	*

4.2 Содержание разделов дисциплины

(указывается название каждого раздела, количество часов, отводимое на изучение, и его содержание)

1 вводные положения 2 час.

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

- задачи, подходы, языки, математические модели и методы решения задач конечной структуры
2. множества 18 час.

- конечные и бесконечные множества: основные определения, спецификации, порождающие процедуры, описание соответствия между множествами, счетное, несчетное множества,

нечеткие множества,
алгебра множеств: свойства операций над множествами. Принцип двойственности, тождественные преобразования, уравнения с множествами, круги Эйлера и диаграммы Венна, произведения множеств, покрытия и разбиения,

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

3 ГРАФЫ 14 час

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

-орграфы и матрицы, построение графа по системе уравнений, преобразования графов,

- обходы графов, эйлеровы и гамильтоновы графы,

- планарность, плоские и планарные графы, теорема Понтрягина - Куратовского, -раскраски графов, хроматическое число,теорема о 5 красках, однозначно

раскрашиваемые графы, критические графы.

4 МАТЕМАТИЧЕСКАЯ ЛОГИКА 12 час,

- булевы функции многих переменных, неоднородные функции,

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

- исчисления: исчисление высказываний и исчисление предикатов.
5 АЛГОРИТМЫ 8 час

типы алгоритмов, общие свойства алгоритмов, машины Тьюринга,
алгоритмическая разрешимость, рекурсивные функции, тезис Черча.
разрешимые и неразрешимые проблемы, эффективные алгоритмы.

4.3 Понедельный план проведения занятий лекционных и практических.

1-я неделя

Лекция: Вводные положения. Предмет, цель и содержание курса. Основные понятия и определения. Диалектика непрерывного и дискретного. Задачи, решаемые инженером-системотехником с помощью дискретной математики. Задачи, подходы, языки, математические модели и методы решения задач конечной структуры.

2 часа

2-я, 3-я недели

Лекция: Множества. Конечные и бесконечные множества: основные определения, спецификации, порождающие процедуры, описание соответствия между множествами, счетное, несчетное множества. Нечеткие множества. Алгебра множеств: свойства операций над множествами. Принцип двойственности, тождественные преобразования, уравнения с множествами, круги Эйлера и диаграммы Венна, произведения множеств, покрытия и разбиения. Отношения: бинарные и многомерные отношения, области определения и значения, сечения, композиция отношений, общие свойства отображения и функции: функциональные отношения, типы отображений и мощность множеств, образы и прообразы, композиция, позиционные системы счисления: 2-ичная система, прямые, обратные и дополнительные коды, представление чисел с фиксированной и плавающей точкой и операции над ними, диапазон и погрешности представления. Семинар: Способы представления, операции над множествами, отношения и функции, спец. бинарные отношения.

18 часов

4-я, 5-я, 6-я недели

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

Семинар: Операции над графами. Эйлеровы и гамильтоновы графы. Матрицы графов. Орграфы, деревья. Сети.

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

14 часов

7-я, 8-я недели

Лекция: Математическая логика. Булевы функции многих переменных, неоднородные функции. Алгебра логики: двойственность формул булевой алгебры, нормальная форма, функциональная полнота. Логические схемы: логические элементы, минимальные формы, многовыходные схемы. Исчисления: исчисление высказываний и исчисление предикатов.

Семинар: Алгебра высказываний, функции алгебры логики. Исчисление высказываний и предикатов.

12 часов

9-я, 10-я недели

Лекция: Алгоритмы. Типы алгоритмов, общие свойства алгоритмов, машины Тьюринга. Алгоритмическая разрешимость, рекурсивные функции, тезис Черча. Разрешимые и неразрешимые проблемы, эффективные алгоритмы.

Семинар. Частично-рекурсивные функции, машины Тьюринга, рекурсивные и рекурсивно-перечислимые множества.

8 часов

11-я неделя

Лекция: Цифровые функции.

12-я, 13-я недели Лекция: Комбинаторика.

14-я, 15-я недели

Лекция: Теория графов.

16-я, 17-я, 18-я недели

Лекция: Дискретное программирование.

5. Лабораторный практикум. е предусмотрен.

6. Учебно-методическое обеспечение дисциплины. 6.1 Рекомендуемая литература

а) основная литература

1.Кузнецов О.П.. Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М. : Энергоатомиздат, 1988. - 480 с.

2.Яблонский СВ. Введение в дискретную математику. - М.: Наука. Гл. ред. физ.мат.лит.. 1979. - 272 с.

З.Харари Ф. Теория графов. -М.:Мир. 1973. - 302 с.

б) дополнительная литература

_______________________________________

_______________________________________

_______________________________________

6.2 Средства обеспечения дисциплины.

Материально-техническое обеспечение дисциплины.
Методические рекомендации по организации изучения дисциплины.

Тема 1. Отмечается, что дискретный анализ, являясь составной частью

математического аппарата инженера-системотехника, представляет собой важное направление в математике. Выделяются характерные для дискретной математики объекты, метод и задачи исследования. Специфика задач - необходимость отказа от понятий предела и непрерывности.

Темы 2-5. Систематически излагаются основы теории множеств, графов, мат. логики и теории алгоритмов с примерами практики проектирования ЭВС. При этом:

акцентируется внимание на системности всех этапов решения задач конечной математики, формулировании подхода, языка формализации, математической модели и метода решения задач,
обращается особое внимание на выбор методов решения задач дискретной математики с учетом их специфичности, на задачи компоновки, размещения и трассировки структурных уровней ЭВС, решаемых методами дискретной математики, рассматриваются на практических занятиях.

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

220100 Вычислительные машины, комплексы, системы и сети

(указывается номер направления подготовки (специальности))

Программу составил(и)

Доцент, к.т.н. Маркин П.М.

Настоящая рабочая программа рассмотрена на заседании (методическом семинаре)

кафедры « » 200 г. протокол № и рекомендована к применению

в учебном процессе.

Зав. Кафедрой «ЭВА»

Азаров В.Н.

« » 2004 г.

Программа согласована с выпускающей (выпускающими) кафедрой (кафедрами)
«ЭВА» /Подпись зав. кафедрой/

« » 200 г.

Срок действия программы продлен на:

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

Похожие: