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

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

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

по направлению
по направлению подготовки бакалавриата

010400.62 Прикладная математика и информатика (общий профиль)

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

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

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

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

1) Знать:

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

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

2) Уметь:

- строить матрицы смежности и инцидентности для графов, таблицы истинности булевых функций, сднф и скнф, полином Жегалкина, тупиковую, сокращенную минимальную ДНФ;

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

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

3) Владеть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Алгоритмы на графах. Расстояния в графах. Алгоритмы на графах нахождения кратчайшего пути. Алгоритм Белла. Алгоритм Дейкстра. Обход в глубину и ширину.

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

4. Минимизация булевых функций. Понятие ДНФ. Проблема минимизации булевых функций. Упрощение ДНФ. Тупиковые ДНФ. Постановка задачи в геометрической форме. Свойства соответствия . Сокращенная ДНФ. Алгоритм построения сокращенной днф. Метод минимизирующих карт. Как можно найти минимальную днф булевой функции.

5. Схемы функциональных элементов. Понятие схемы из функциональных элементов. Реализация функций алгебры логики схемами. Сумматор. Верхняя оценка сложности сумматора. Вычитатель. Дешифратор. Асимптотика сложности дешифратора.

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

№ п/п	Наименование раздела, темы	Количество часов	Семестр, Форма отчетности
Всего ауд. ч./в интеракт. ф.	ЛК	ПР/ СМ	ЛБ	Часов на СРС
1	Теория графов	36/11	14	22	–	36	1 семестр, зачет
2	Алгоритмы на графах	36/11	14	22	-	36
3	Булевы функции	36/2	14	22	–	36	2 семестр, экзамен
4	Минимизация булевых функций	19/2	8	11	-	19
5	Схемы функциональных элементов	17/2	6	11	-	17

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-й семестр вопросы к зачету

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

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

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

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

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

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

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

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

9.  Деревья.

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

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

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

13.  Алгоритм Дейкстра.

14.  Алгоритм Белла.

15.  Расстояние на графах.

16.  Обход в глубину.

17.  Обход в ширину.

2-й семестр вопросы к экзамену

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

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

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

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

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

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

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

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

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

10.  СДНФ.

11.  СКНФ.

12.  Полнота и замкнутость.

13.  Полином Жегалкина.

14.  Класс Т0.

15.  Класс Т1.

16.  Класс S.

17.  Класс L.

18. 

19.  Теорема о функциональной полноте.

20.  Представление о результатах Поста.

21.  Понятие ДНФ.

22.  Проблема минимизации булевых функций.

23.  Упрощение ДНФ.

24.  Тупиковые ДНФ.

25.  Постановка задачи в геометрической форме.

26.  Свойства соответствия .

27.  Сокращенная ДНФ.

28.  Алгоритм построения сокращенной днф.

29.  Метод минимизирующих карт.

30.  Как можно найти минимальную днф булевой функции.

31.  Понятие схемы из функциональных элементов.

32.  Реализация функций алгебры логики схемами.

33.  Сумматор. Верхняя оценка сложности сумматора. Вычитатель.

34.  Дешифратор. Асимптотика сложности дешифратора.

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. По СДНФ функции найти СКНФ функций и .

а) ;

б) .

тема «Полином Жегалкина»

№1. Найти полином Жегалкина булевой функции методом неопределенных коэффициентов.

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

№2. Найти полином Жегалкина булевой функции , реализуя ее формулой алгебры логики над полной системой булевых функций и пользуясь свойствами: , , , .

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

тема «Полные системы функций»

№1.Сохраняет ли булева функция константу 0.

а) ;

б) ;

в) .

№2.Сохраняет ли булева функция константу 1.

а) ;

б) ;

в) .

№3. Выяснить, является ли самодвойственной функция , заданная формулой алгебры логики

а) ;

б) ;

в) .

№4.Выяснить, является ли самодвойственной функция , заданная вектором своих значений

а) ;

в) ;

г) .

№5. Определить, какие из переменных следует заменить на , а какие на , чтобы получить из несамодвойственной булевой функции константу?

а) ;

б) ;

в) ;

Решение. Так как булева функция не монотонна, то существуют противоположные наборы значений переменных, на которых она принимает одинаковые значения. В данном случае это наборы (0,0), (1,1) и (0,1), (1,0); причем , . Поэтому (см. доказательство теоремы о несамодвойственной функции) чтобы получить из константу 1 можно переменные и заменить или на ; чтобы получить из константу 0 можно переменные и заменить соответственно на и или на и .

№6.Какие из следующих функций монотонны?

а) ;

б) ;

в) .

№7.  Представив функцию полиномом Жегалкина выяснить является ли она линейной.

а) ;

б) ;

в) .

№8. Доказать полноту следующих систем булевых функций сведением к заведомо полным системам

а) ;

б) ;

в) .

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

а) , ;

б) , 0, 1;

в)  , , .