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




Скачать 235.46 Kb.
НазваниеУчебно-методический комплекс по дисциплине «Дискретная математика»
страница1/4
Дата10.05.2013
Размер235.46 Kb.
ТипУчебно-методический комплекс
  1   2   3   4


Автор-составитель:


Сперанский Д.В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»


Учебно-методический комплекс по дисциплине «Дискретная математика» составлен в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности: 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)».


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




1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ


1.1. Целью дисциплины «Дискретная математика» является изучение указанных в рабочей программе глав дискретной математики, необходимых при изучении дисциплин, входящих в учебный план по специальности 220100 «Вычислительные машины, комплексы, системы и сети (ЭВМ)». Изучение дискретной математики способствует развитию логического и алгоритмического мышления студентов, освоению ими приемов исследования и решения математически формализованных задач, выработке

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


1.2. Задачи изучения дисциплины.

Изучив дисциплину, студент должен:

1.2.1. Знать базовые понятия дискретной математики.

1.2.2. Владеть основами комбинаторики, теории множеств, теории графов, теории конечных автоматов и теории кодирования.

1.2.3. Уметь решать типовые задачи.

1.2.4. Иметь представление об использовании полученных знаний при решении инженерных задач.


2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ


2.1. Элементы комбинаторики. Перестановки, размещения и

сочетания. Бином Ньютона. Свойства биномиальных коэффициентов. Полиномиальная формула. Понятие о комбинаторном анализе.

Литература: [1; 2].

2.2. Обычные (четкие) множества и нечеткие подмножества,

их спецификации. Понятие множества. Четкие множества и нечеткие подмножества. Операции над четкими множествами. Диаграммы Эйлера-Венна. Степень принадлежности элемента множеству. Операции над нечеткими подмножествами. Нечеткое включение и равенство множеств. Четкие конечные множества и нечеткие подмножества. Число подмножеств данного четкого конечного множества. Упорядоченные четкие конечные множества. Множество всех нечетких подмножеств и его свойства. Четкие

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

Литература: [1; 2; 3; 7; 10; 12; 13].

2.3. Обычные (четкие) и нечеткие отношения. Четкие и нечеткие отношения на множествах. Четкие бинарные отношения и их свойства. Отображения множеств. Специальные бинарные отношения (эквивалентности, порядка, доминирования). Проекция нечеткого отношения. Носитель нечеткого отношения. Свойства нечетких бинарных отношений. Симметрия, рефлективность, транзитивность. Нечеткие отношения предпорядка, подобия, асимметрии, порядка, сходства и различия и их свойства.

Литература: [1; 2; 6; 8; 10; 11; 12].

2.4. Теория обычных (четких) и нечетких графов. Предмет теории четких и нечетких графов. Четкие неориентированные и ориентированные графы. Задание четких графов с помощью матриц. Цепи и циклы в четких графах. Достижимость и связность в четких графах. Операции над четкими графами. Деревья и прадеревья. Свойства деревьев. Древовидные структуры. Цикломатическое число графа. Разбиения и обходы графов. Эйлеровы и гамильтоновы графы. Плоские и пленарные графы. Формула Эйлера. Матрицы смежности и инцидентности для четких графов. Нечеткие графы.

Основные свойства и характеристики. Задание нечетких графов с помощью матриц. Маршруты в четких конечных и нечетких графах. Транспортные сети. Задача о наибольшем потоке. Приложения четких и нечетких графов в вычислительных алгоритмах.

Литература: [1; 2; 3; 4; 8; 13; 14; 15].

2.5. Нечеткая арифметика. Понятие нечеткого числа. Операции над нечеткими числами. Нечеткие целые положительные числа.

Экспоненциальные, геометрические и гауссовы нечеткие целые числа и их свойства.

Литература: [9; 13; 14].

2.6. Элементы теории кодирования. Определение кода. Прямые, обратные и дополнительные коды. Коды с исправлением ошибок. Линейные коды. Матричное кодирование. Коды Хемминга и групповые коды.

Литература: [1; 7].

2.7. Элементы теории конечных автоматов. Различные подходы к определению конечного автомата: микроподход и макроподход. Виды конечных автоматов. Функция перехода. Функция выхода. Способы описания конечного автомата: таблица состояний, диаграмма состояний. Примеры конечных автоматов. Минимизация конечного автомата.

Литература: [1; 2; 11].


3. ВИДЫ РАБОТ С РАСПРЕДЕЛЕНИЕМ ВРЕМЕНИ


Курс — II, семестр — III.

Всего часов — 140 ч.

Лекционные занятия— 8 ч.

Практические занятия —12 ч.

Число контрольных работ — 1.

Самостоятельная работа — 105 ч.

Экзамен— 1.














Литература


  1. Шестаков А.А., Дружинина О.В., Романков В.В., Петунин А.П. Дискретная математика: Учебное пособие/ Под ред. А.А. Шестакова. – М.: РГОТУПС, 2004.

  2. Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для ВУЗов. Новосибирск: ИНФРА – М,2009.

  3. Тишин В.В. Дискретная математика в примерах и задачах. С.- Петербург: БХВ-Петербург, 2008.

  4. Плотников А.Д. Дискретная математика : учебное пособие. М: Новое знание,2005.

  5. Карпов Ю.Г.Теория автоматов. Учебник для ВУЗов. С.-Петербург: Питер,2003..

  6. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов – М.: Наука,2009.



МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ

Методические указания предназначены для студентов II курса специальности ЭВМ. Для решения задач контрольной работы необходимы некоторые теоретические сведения, которые представлены перед типовым решением каждой упомянутой задачи.

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


Задание № 1


Следующая формула называется биномом Ньютона:

. (1)

Числа в этой формуле называются биномиальными коэффициентами и равны количеству различных k–элементных подмножеств n–элементного множества. Вычисление биноминальных коэффициентов осуществляется по формуле

, где .

Отметим, что в каждом из k-элементных подмножеств порядок расположения его элементов безразличен. Каждая такая комбинация называется сочетанием из n элементов по k.

Например, найдем число всех сочетаний из 5 элементов a, b, c, d, e по три:

.

Перечислим эти сочетания: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

Пример 1. В разложении найти член, содержащий .

По формуле (1) находим, что этот член имеет вид . Степень b равна 4, так как сумма степеней произведения должна равняться n (в нашем примере n=10, ni =6, i=4). Таким образом получаем:

.

Пример 2. В разложении найти члены, содержащие .

Введем следующие обозначения: и . Тогда исходный бином примет вид . Ясно, что член, содержащий в исходном биноме, равен члену нового бинома, содержащего . Легко видеть, что этот член таков:

.


Задание № 2


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

Множества A и B считаются равными, если они состоят из одних и тех же элементов. Этот факт записывается A=B. Если A и B различны, то это записывается .

Множество, элементами которого являются объекты a, b, c,…,z и только они, обозначают . Порядок расположения объектов в этой записи не имеет значения.

Конечное множество можно описать простым перечислением его элементов. Описание многоэлементных или бесконечных множеств обычно основано на интуитивном понятии «формы от x» (обозначается ). Для множества A, определяемого формой , принято обозначение .

Например, множество можно описать, используя форму , в виде « x – положительное целое число, меньшее 9».

А={x | x – положительное целое число, меньшее 9}.

Для получения новых множеств из уже существующих используются различные операции. Определим некоторые из них.

Объединением множеств А и В называется множество , все элементы которого являются элементами множеств А или В:

.

Здесь символ «» обозначает принадлежность элемента множеству.

Пересечением множеств А и В называется множество , элементы которого являются элементами обоих множеств А и В:

.

Дополнением множества А до множества Х называется множество всех тех элементов множества Х, которые не принадлежат множеству А:

.

Поясним эти определения на примерах. Пусть заданы три следующих множества:

, , .

Тогда , , .

Обычно принято считать, что все рассматриваемые множества являются подмножествами некоторого универсального множества U.

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



А

В










Пример 1. Проверить тождество с помощью диаграмм Эйлера-Венна: .

Для решения задачи сначала (возможно поэтапно) построим с помощью диаграмм множество, стоящее в левой части множества. Затем аналогичное построение выполним для правой части тождества. Если полученные в результате этих построений диаграммы совпадут, то тождество справедливо. Для нашего примера диаграмма множества левой части тождества такова:






Для правой части тождества имеем:


В

А







Поскольку диаграммы множеств для обеих частей тождества совпадают, то тождество справедливо.

Пример 2. Проверить тождество . Пусть исходные множества таковы:


А

В

С


Выполним поэтапно операции для левой части тождества:


А

В

С









Выполним поэтапно операции для правой части тождества:



В

С




А




Поскольку диаграммы множеств для обеих частей тождества совпадают, то тождество справедливо.

  1   2   3   4

Похожие:

Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине дискретная математика
Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»
Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине вычислительная математика
Учебно-методический комплекс по дисциплине «Вычислительная математика» составлен в соответствии с требованиями Государственного образовательного...
Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине «Математика»
Учебно-методический комплекс «Математика» составлен в соответствии с требованиями Государственного образовательного стандарта высшего...
Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс для специальности 030501 Юриспруденция Москва 2007 Автор составитель: к э. н., доцент И. А. Кашина Учебно-методический комплекс «Информатика и математика»
Учебно-методический комплекс «Информатика и математика» составлен в соответствии с требованиями Государственного образовательного...
Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине информатика и математика

Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине дс. 02. 1
Учебно-методический комплекс по дисциплине дс. 02 “Экологическая анатомия растений” составлен в соответствии с требованиями Государственного...
Учебно-методический комплекс по дисциплине «Дискретная математика» iconДжеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон
Индивидуальное домашнее задание по дисциплине «Дискретная математика» для студентов групп ас – 08, аи – 08, пм – 08, ук – 08, см...
Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине Математика и информатика для специальности 03060265 Связи с общественностью гуманитарного факультета
Учебно-методический комплекс (умк) составлен на основании гос впо и учебного плана Улгту специальноси (направления) 350400 – Связи...
Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине «Философия». Таганрог: Изд-во трту, 2006. 80 с. Учебно-методический комплекс по дисциплине «Философия» подготовлен в соответствии с новым государственным образовательным стандартом по дисциплине «Философия».
Составители: М. А. Дедюлина, В. А. Ивлиев, Е. В. Папченко, В. С. Поликарпов, О. В. Шипелик
Учебно-методический комплекс по дисциплине «Дискретная математика» iconУчебно-методический комплекс по дисциплине ен. Ф. 07. «Геология» как часть образовательной программы является совокупностью учебно-методических материалов, способствующих
Учебно-методический комплекс по дисциплине ен. Ф. 07. «Геология» составлен в соответствии с требованиями Государственного образовательного...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница