Скачать 123.91 Kb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования Московский государственный институт электроники и математики (технический университет) «Утверждаю» Декан факультета АВТ Петросянц К.О РАБОЧАЯ ПРОГРАММА по дисциплине «Дискретная математика» Направление подготовки - 654600 Информатика и вычислительная техника Номер специальности - 220100 Вычислительные машины, комплексы, системы и сети Факультет - Автоматики и вычислительной техники Кафедра - ЭВА Москва - 2004 г. 1. Цели и задачи дисциплины. Целью преподавания дисциплины является овладение студентами математическим аппаратом дискретной математики для решения задач конечной структуры предметной области инженера-системотехника. Задачи курса:
2. Требования к уровню освоения содержания дисциплины. (требования к знаниям, умениям и навыкам, приобретенным в результате изучения дисциплины). 3. Объем дисциплины и виды учебной деятельности.
4. Содержание дисциплины 4.1 Разделы дисциплины и виды занятий (допускается название п.4.1 «Тематический план»)
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 Информатика и вычислительная техника, примерной программы,... |