Рабочая программа по дисциплине «Дискретная математика» Направление подготовки 654600 Информатика и вычислительная техника icon

Рабочая программа по дисциплине «Дискретная математика» Направление подготовки 654600 Информатика и вычислительная техника


Смотрите также:
Основная образовательная программа высшего профессионального образования Направление подготовки...
Рабочая учебная программа по дисциплине вычислительная математика направление: 5528 “Информатика...
Рабочая программа по дисциплине “элементы электронных систем “ Направление подготовки 654600...
Рабочая учебная программа по дисциплине вычислительная математика специальность: 230100...
Образовательный стандарт по направлению подготовки дипломированных специалистов 654600 [230100]...
Рабочая учебная программа по дисциплине «Дискретная математика» Направление №230100 «Информатика...
Рабочая программа по дисциплине «Основы тео р ии управления» Направление подготовки 654600...
Рабочая программа по дисциплине «Основы тео р ии управления» Направление подготовки 654600...
Программа дисциплины ен...
Рабочая программа по дисциплине “Вычислительная математика” д...
Рабочая программа по дисциплине «Методы и Средства Защиты Информации» Направление подготовки...
Рабочая учебная программа по дисциплине «Информатика» Направление №230100 «Информатика и...



Загрузка...
скачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

«Утверждаю»

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

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

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

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

Направление подготовки - 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. Методические рекомендации по организации изучения дисциплины.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Азаров В.Н.


« » 2004 г.

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

« » 200 г.



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




Скачать 103,87 Kb.
оставить комментарий
Дата18.10.2011
Размер103,87 Kb.
ТипРабочая программа, Образовательные материалы
Добавить документ в свой блог или на сайт

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

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

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

наверх