Методические рекомендации по курсу

Методические рекомендации по курсу

Методические рекомендации по курсу

Б2.Б.2 Дискретная математика

подготовки бакалавриата 080500.62 «Бизнес-информатика»

Автор: , ст. преподаватель кафедры М и ММЭ

1. Цели и задачи курса, место дисциплины в структуре ООП ВПО, компетенции обучающегося, формируемые в результате освоения дисциплины.

Целями освоения дисциплины «дискретная математика» являются формирование систематизированных знаний в области высшей математики и основ информатики, о ее месте и роли в системе математических наук.

В результате освоения дисциплины обучающийся должен:

1) Знать:

- основные понятия дискретной математики;

- основные свойства графов и булевых функций, теоремы курса;

2) Уметь:

- строить матрицы смежности и инцидентности для графов, таблицы истинности булевых функций, сднф и скнф;

- используя определения и алгоритмы, проводить исследования, связанные с основными понятиями;

3) Владеть

- современными знаниями о дискретной математике и ее приложениях;

- основными понятиями дискретной математики.

Дисциплина «Дискретная математика» относится к базовой части профессионального цикла (Б2.Б.2).

Для освоения дисциплины «Дискретная математика» студенты используют знания, умения и виды деятельности, сформированные в процессе изучения предмета «Математика» и «Информатика» на предыдущем уровне образования.

Освоение данной дисциплины является необходимой основой для последующего изучения дисциплин математической направленности, информатики, экономики, дисциплин по выбору студентов.

Формируются компетенции:

-  Владением культурой мышления, способностью к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1);

-  способностью использовать знания о современной естественнонаучной картине мира в образовательной и профессиональной деятельности, применять методы математической обработки информации, теоретического и экспериментального исследования (ОК-4);

-  готовностью использовать основные методы, способы и средства получения, хранения, переработки информации, готовностью работать с компьютером как средством управления информацией (ОК-8);

-  способностью работать с информацией в глобальных компьютерных сетях (ОК-9);

-  способностью понимать сущность и значение информации в развитии современного информационного общества, сознавать опасности и угрозы, возникающие в этом процессе, соблюдать основные требования информационной безопасности, в том числе защиты государственной тайны (ОК-12);

-  осознанием социальной значимости своей будущей профессии, обладанием мотивацией к осуществлению профессиональной деятельности (ОПК-1).

2. Структура курса.

Теория графов. Понятие графов. Операции с графами. Степени вершин графов. Способы задания графов. Маршруты, цепи, циклы. Эйлеровы графы. Гамильтоновы графы. Двудольные графы и жесткость ферм. Деревья. Коды Прюфера. Задача об остове минимального веса. Мультиграфы. Расстояния в графах.

Булевы функции. Функции алгебры логики. Формулы. Реализация функций формулами.

Эквивалентность формул. Свойства элементарных функций. Принцип двойственности. Разложение булевых функций по переменным. СДНФ и СКНФ.

3. Содержание дисциплины.

№ п/п	Наименование раздела, темы	Количество часов	Семестр, Форма отчетности
Всего ауд. ч./в интеракт. ф.	ЛК	ПР/ СМ	ЛБ	Часов на СРС
1	Теория графов	21/13	8	13	–	21	1 семестр зачет
2	Булевы функции	21/13	8	13	–	21

4. Учебно-методическое обеспечение и информационное обеспечение дисциплины

Основная

и др. Теория графов. – М.: Высш. Школа, 1976. Конечные графы и сети. – М.: Наука, 1974. , Овчинникова математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005. Теория графов и ее применения. – М.: ИЛ, 1962. Зыков конечных графов. – Новосибирск: Наука, 1969. Теория графов. – М.: Наука,1968. , Адельсон – Вельский математика для инженера. – М.: Энергия, 1980. Теория графов: Пер. с англ. – М.: Мир,1988. Теория графов. – М.: Мир, 1973. Яблонский в дискретную математику. – М.: Наука, 1979. Игошин практикум по математической логике. – М.: Просвещение, 1986.

Дополнительная

Оре. О. Графы и их применение. – М.: Мир, 1965. Введение в теорию графов. – М.: Мир, 1977. Березина и их применение: Пособие для учителей. – М.: Просвещение, 1979.

Электронные образовательные ресурсы (ЭОР)

1. http://eqworld. *****/ru/library. htm — Электронная библиотека сайта EqWorld.

2. http://www. *****

3. http://dictionary. *****

5. Примерные вопросы к зачету

Примерные вопросы к зачету

1.  Понятия теории графов.

2.  Операции с графами.

3.  Степени вершин графов.

4.  Способы задания графов.

5.  Маршруты, цепи, циклы.

6.  Эйлеровы графы.

7.  Гамильтоновы графы.

8.  Двудольные графы и жесткость ферм.

9.  Деревья.

10.  Коды Прюфера.

11.  Задача об остове минимального веса.

12.  Мультиграфы

13.  Понятие булевой функции.

14.  Понятие фиктивной переменной.

15.  Основные булевы функции от 1-ой и 2-х переменных.

16.  Понятие формулы над Р.

17.  Операция суперпозиции.

18.  Эквивалентность формул.

19.  Свойства элементарных функций.

20.  Принцип двойственности.

21.  Разложение булевых функций по переменным.

22.  СДНФ.

23.  СКНФ.

6. Примерная тематика практических занятий.

тема «Графы, их вершины, рёбра и дуги».

№1. Подбирается экипаж космического корабля из 3-х человек: командира, инженера и врача. Имеются 4 кандидата на должность командира к1, к2, к3, к4, 3 кандидата на должность инженера и1, и2, и3 и 3 кандидата на должность врача в1, в2, в3. Известно, что

·  к1 психологически совместим с и1, и3, в2, в3; к2 - с и1, и2, в1, в2, в3;

·  к3 - с и1, и2, в1, в3; к4 - с и1, и2, и3, в2.

Кроме того, и1 психологически несовместим с в3, и2 - с в1, и3 - с в2.

Сколькими способами можно составить экипаж?

№2.Лист бумаги Плюшкин разрезает на три части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листочков он вновь разрезает на три более мелких и т. д. сколько Плюшкин получает листочков бумаги, если разрезает к листов?

№3. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

тема «Изоморфные графы».

№1. Доказать, что графы изоморфные, построить изоморфизм графов.

№2. Нарисуйте диаграммы всех неизоморфных неориентированных графов

а) с 3 вершинами (их четыре);

б) с 4 вершинами (их 11).

тема «Операции над графами »

Построить дополнение графа, объединение, соединение, композицию и произведение двух графов.

тема «Эйлеровы и гамильтоновы графы»

Построение эйлеровых и гамильтоновых циклов и цепей, применение их для решения прикладных задач (задача коммивояжёра).

тема «Способы задания псевдографов »

Различные задания графов: диаграмма, список ребер, матрица и список смежности, матрица инцидентности.

тема «Деревья и их свойства. »

1. Сколько ребер в деревьях:

а) с 6 и 12 вершинами;

б) с 7 и 15 вершинами.

2. Сколько рёбер следует удалить из связного графа F, имеющего т рёбер и n вершин, чтобы получить дерево, содержащее все вершины F?

3. Привести пример графа, из которого нельзя выделить дерево, содержащее все вершины графа.

4. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделать проверку.

а) (3, 3, 7, 1, 1, 1); в) (7, 11, 11, 6, 6, 6, 2, 2, 10, 1);

б) (1, 2, 2, 4, 9, 5, 5, 5); г) (2, 3, 1, 4, 4, 4, 1, 2, 6, 6).

тема «Функции алгебры логики»

№ 1. Какие из предложенных формул являются тавтологиями? Для ответа на вопрос постройте таблицу истинности. Назовите известные вам законы.

a) 

b) 

c) 

d) 

e) 

f) 

g)  .

№ 2. Составьте таблицы истинности для следующих формул и укажите, какие из формул являются выполнимыми, какие – тождественно ложными, какие тождественно истинными:

b)  ;

c)  ;

d)  ;

e)  ;

f)  ;

g)  .

№ 3. Следующие формулы преобразуйте равносильным образом так, чтобы они содержали операции отрицание, конъюнкцию и дизъюнкцию:

1.  ;

2.  ;

3.  ;

4.  .

№ 4. С помощью равносильных преобразований докажите, что следующие формулы являются тождественно ложными:

1)  ;

2)  ;

3)  ;

4)  .

№ 5. Преобразовать формулу так, чтобы она содержала только операции и :

1.  ;

2.  ;

3. 

4.  .

тема «Законы алгебры логики»

№1. Построить таблицу истинности следующих булевых функций.

а) ;

б) ;

в) ;

г) .

№2. Выписать векторы значений булевых функций из предыдущего примера.

№3. По векторам значений функций и найти вектор значений функции .

а) , , ;

б) , , .

№4. Булева функция задана вектором своих значений. Найти вектор значений двойственной к ней булевой функции .

а) ;

б) ;

в) .

№5. Найти функцию двойственную к данной.

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

№6. Найти функцию двойственную к данной, пользуясь принципом двойственности.

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

тема «Разложение функции по одной, двум и всем переменным»

№1. Построить ДНФ, КНФ, СДНФ, СКНФ булевой функции с помощью эквивалентных преобразований.

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

№2. Найти СДНФ и СКНФ булевой функции , заданной вектором своих значений.

а) ;

б) ;

в) ;

г) .

№3. По СКНФ функции найти СДНФ функций и .

а) ;

б) .

№4. По СДНФ функции найти СКНФ функций и .

а) ;

б) .