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

Скачать 123.91 Kb.

Название	Рабочая программа по дисциплине «Дискретная математика»
Дата публикации	18.11.2014
Размер	123.91 Kb.
Тип	Рабочая программа

100-bal.ru > Математика > Рабочая программа

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

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

«Утверждаю»

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

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

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

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

Направление подготовки - 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 г.

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

Добавить документ в свой блог или на сайт

Похожие:

	Рабочая программа Дискретная математика Дискретная математика: рабочая программа / А. Ю. Вальков, З. Н. Хакимова. – Спб.: Ивэсэп, 2012. – с		Рабочая программа по дисциплине «Дискретная математика» Главной целью курса является не овладение большим количеством фактического материала, а обучение методам, языку и мышлению, характерному...
	Вопросы к экзамену по дисциплине “Дискретная математика” Полнота множества функции. Понятие замкнутого класса функций: важнейшие замкнутые классы		Рабочая программа дисциплины дискретная математика (наименование)...
	Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Криптография и криптоанализ. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления...		Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Дополнительные главы дискретной математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Учебно-методический комплекс по дисциплине математика специальность... Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19		Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория автоматов. Учебно-методический комплекс. Рабочая программа для студентов направления 010200. 62 – математика...
	Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010200. 62 – математика...		Учебно-методический комплекс по дисциплине математика специальность... Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19
	Учебно-методический комплекс по дисциплине дискретная математика специальность 230101. 65 Гос впо по специальности 230101. 65 Вычислительные машины, комплексы, системы и сети, утвержденный Министерством образования РФ «27»...		Методические рекомендации по выполнению заданий по дисциплине «Дискретная... После изучения каждой темы студенту предлагается выполнить самостоятельную работу, в случае успешного выполнения которой студент...
	Программа дисциплины «Дискретная математика» для направления 010500.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки		Литература по математике (алгебра, геометрия, математический анализ,... Математика on line. В помощь студенту. Основные математические формулы по алгебре, геометрии, тригонометрии, высшей математике, исторические...
	Литература Белоусов А. И., Ткачев С. Б. Дискретная математика. М: Изд-во мгту им. Н. Э. Баумана, 2006. 744 с		Рабочая программа учебной дисциплины дискретная математика Компьютерные системы и комплексы, укрупненной группы специальности 230000 Информатика и вычислительная техника, примерной программы,...

Школьные материалы