close

Вход

Забыли?

вход по аккаунту

?

ДМ МП 20 25 11 12

код для вставкиСкачать
УЧЕБНАЯ ДИСЦИПЛИНА
"ДИСКРЕТНАЯ МАТЕМАТИКА"
(2011-2012 гг., лектор - Олейник Т.А.)
1. ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
1.1. ЛИТЕРАТУРА 1. Олейник Т.А. Основы дискретной математики: теория и практика: уч. Пособие. - М.:МИЭТ, 2010. - 252 с.2. Новиков Ф.Н. Дискретная математика для программистов. - СПб.: Питер, 2001, 2002, 2003, 2004. - 304 с.3. Яблонский С.В. Введение в дискретную математику: учеб. пособие для вузов. / Под. ред. В.А. Садовничего. - 3-е изд., стер. - М.: Высшая школа, 2001, 2003. - 384 с.4. Клюшин А.В, Кожухов И.Б., Олейник Т.А. Сборник задач по дискретной математике. - М.: МИЭТ, 2008. - 120 с.5. Кожухов И.Б., Прокофьев А.А., Соколова Т.В. Курс дискретной математики. - М.: МИЭТ, 2000, 2003, 2004. - 208 с.
1.2. ЭЛЕКТРОННЫЕ РЕСУРСЫ
1. Клюшин А.В, Кожухов И.Б., Олейник Т.А. Сборник задач по дискретной математике. http://www.orioks.miet.ru/oroks-miet/srs.shtml2. Кожухов И.Б., Прокофьев А.А., Соколова Т.В. Курс дискретной математики. Учебное пособие. http://www.orioks.miet.ru/oroks-miet/srs.shtml
2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
2.1. ЛЕКЦИОННЫЕ ЗАНЯТИЯ
№СодержаниеЛекция 1Множества и бинарные отношения. Множества и операции над ними. Свойства операций над множествами. Формулы подсчета элементов конечных множеств. Бинарные отношения на множестве. Отношение эквивалентности и отношение порядка.
Л-1, § 1.1.Лекция 2Элементы комбинаторики. Выборки, размещения и сочетания без повторений и с повторениями, перестановки. Правило произведения и правило суммы, формулы подсчета числа сочетаний и размещений. Бином Ньютона. Комбинаторные соотношения. Л-1, § 1.2.Лекция 3Булевы функции и способы их задания. Понятие булевой функции. Задание булевой функции таблицей истинности и вектором значений. Элементарные функции. Задание функций формулами. Основные равносильности над множеством . Фиктивные и существенные переменные. Л-1, § 2.1.Лекция 4Совершенные дизъюнктивные и конъюнктивные нормальные формы. Двойственные функций. Принцип двойственности. Разложение булевых функций по переменным. Задание функций в виде СДНФ и СКНФ. Л-1, § 2.2.Лекция 5Минимизация дизъюнктивных нормальных форм. Понятие о ДНФ, минимальных ДНФ, постановка задачаи о минимизации ДНФ. Понятие о сокращенной и тупиковых ДНФ. Алгоритм построения сокращенной, тупиковых и минимальных ДНФ. Л-1, § 2.3.Лекция 6Классы Поста и замыкание. Полином Жегалкина. Функции, сохраняющие 0, 1. Самодвойственные, монотонные, линейные функции. Замыкание системы булевых функций. Замкнутость классов Поста. Л-1, § 2.4.Лекция 7,8Полнота системы булевых функций. Понятие полной системы. Теорема о полноте двух систем. Критерий полноты системы булевых функций (теорема Поста). Базисы. Л-1, § 2.5.Лекция 9Первичные понятия теории графов. Понятие неориентированного графа, классификация его элементов, представление графа диаграммой. Изоморфизм графов. Специальные виды графов. Задание графов матрицами. Подграфы. Операции над графами. Л-1, § 3.1.Лекция 10Достижимость и компоненты связности, циклы и мосты, цикломатическое число. Пути, цепи, циклы на графе. Отношение достижимости (связности), компоненты связности графа. Мосты графа, связь между мостами и циклами. Цикломатическое число графа. Л-1, § 3.2.Лекция 11Деревья и леса. Дерево, лес, их характеристические свойства. Остовы графа. Алгоритм Краскала отыскания минимального остова. Кодирование деревьев. Л-1, § 3.3.Лекция 12Планарность. Укладка графов в трехмерном пространстве. Укладка графа на плоскости. Планарные графы. Связь между числом вершин, ребер и граней плоского графа. Гомеоморфные графы. Критерии планарности.
Л-1, § 3.4.Лекция 13Обходы графов. Эйлеровы цикл и цепь, критерии их существования. Алгоритм построения Эйлерова цикла. Гамильтоновы цикл и цепь.
Раскраска графов. Раскраска графа. Хроматическое число графа. Критерий бихроматичности. Л-1, § 3.5, § 3.6.Лекция 14Фундаментальная система циклов графа. Линейное пространство циклов. Алгоритм построения фундаментальной системы циклов.
Ориентированные графы. Понятие орграфа, классификация его элементов. Изоморфные орграфы. Матрицы смежности и инцидентности орграфа. Пути, цепи, циклы на орграфе. Слабая и сильная связность орграфа. Понятие ориентированного дерева. Л-1, § 3.7, § 3.8.Лекция 15Задача о максимальном потоке в сети. Потоки в сети, задача о максимальном потоке. Алгоритм Форда-Фалкерсона. Л-1, § 3.10.Лекция 16Отыскание кратчайших путей на графе. Постановка задачи об отыскании кратчайших путей в сети. Алгоритм Дейкстры. Схемы из функциональных элементов. в базисе .
Л-1, § 3.9, 3.11.Лекция 17Упорядоченная бинарная диаграмма решений. Понятие об УБДР. Минимальные УБДР. Сокращенные УБДР., их построение для функции, заданной таблицей и формулой. Л-1, § 3.12.
2.2. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
№СодержаниеЗанятие 1Множества и бинарные отношения. Элементы комбинаторики. Л-4: № 1.1 - 1.10, 2.1 - 2.3.
ЭМИРС. Гл. 1  § 1.1; Гл. 1  § 1.2. Занятие 2Булевы функции и способы их задания. Совершенные дизъюнктивные и совершенные конъюнктивные нормальные формы. Л-4: № 2.4, 2.5, 2.8 - 2.10, 2.13 - 2.23, 2.27 - 2.33, 2.35 -2.37.
ЭМИРС. Гл. 2  § 2.1  2.1.1, 2.1.2; Гл. 2  § 2.2  2.2.1, 2.2.2.Занятие 3Минимизация дизъюнктивных нормальных форм. Классы Поста и замыкание. Выдача БДЗ 1.
Л-4: № 2.38-2.41, 2.43 (а, б), 2.45, 2.46 - 2.49, 2.51, 2.52, 2.56 (а), 2.57 (а), 2.59, 2.61, 2.65, 2.70, 2.77, 2.78
ЭМИРС. Гл. 2  § 2.3; Гл. 2  § 2.4  2.4.2, 2.4.3.Занятие 4Полнота системы булевых функций. Л-3: № , 2. 81, 2.83, 2.85 - 2.88.
ЭМИРС. Гл. 2  § 2.4  2.4.1, 2.4.4.Тест/контрольная работа по модулю: "Множества, бинарные отношения, комбинаторика. Алгебра логики". Прием БДЗ 1.Занятие 5Первичные понятия теории графов. Достижимость и компоненты связности, циклы и мосты, цикломатическое число.
Л-4: № 3.1 - 3.8, 3.11 - 3.15, 3.11 - 3.15, 3. 54 - 3.57, 3.60 - 3.62.
ЭМИРС. Гл. 3  § 3.1  3.1.1, 3.1.2, 3.1.3, 3.1.4; Гл. 3  § 3.2  3.3.1.Занятие 6Деревья и леса. Планарность. Выдача БДЗ 2.
Л-4: № 3.46, 48 - 3.50, 3.52, 53, 3.68 - 3. 70, 3.78, 3.79, 3.83 - 3.85.
ЭМИРС. Гл. 3  § 3.2; Гл. 3  § 3.4.Занятие 7Обходы графов. Раскраска графов. Фундаментальная система циклов. Ориентированные графы.
Л-4: № 3.37 - 3.42, 3.64 - 3.67, 3.72 - 3.74, 3.9, 3.10.
ЭМИРС. Гл. 3  § 3.3  3.3.1, 3.3.2; Гл. 3  § 3.5.Занятие 8Задача о максимальном потоке в сети. Отыскание кратчайших путей на графе. Схемы из функциональных элементов в базисе .
Л-4: № 3.90, 3.91.
ЭР. § 3.9, § 3.10, § 3.11.Тест/контрольная работа по модулю "Теория графов". Прием БДЗ 2.
2.3. САМОСТОЯТЕЛЬНАЯ РАБОТА
(адрес: http://www.orioks.miet.ru/oroks-miet/srs.shtml - кафедра ВМ-1 - логин: u<номер студенческого билета>, пароль: <дата рождения> в формате ДД.ММ.ГГГГ) №Темы ЭМИРСИспользуемый ППСРС Алгебраические структуры:
1.1. Множества; 1.2. Бинарные отношенияСРС Булевы функцииСРС Графы
1
Автор
mr.korotkov.m
Документ
Категория
Без категории
Просмотров
276
Размер файла
103 Кб
Теги
дм_мп_20_25_11_12
1/--страниц
Пожаловаться на содержимое документа