Тема 1. Дискретные множества

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И КОНТРОЛЬНЫЕ ЗАДАНИЯ

 

по дисциплине

 

«ДИСКРЕТНАЯ МАТЕМАТИКА»

для студентов уровня ВО заочной формы обучения

специальности 1-45 01 03 «Сети телекоммуникаций»

 

 

МИНСК 2009

 

 

 

Составитель: Петрович А.В.

 

Рецензент: Колодная Е.М.

 

Издание утверждено на заседании кафедры М и Ф

12.04.2009г., протокол № 8

Зав. кафедрой Гладков Л.Л.

ВВЕДЕНИЕ

В соответствии с учебным планом студенты третьего курса ВГКС специальности 1-45 01 03 – Сети телекоммуникаций в шестом семестре выполняют контрольную работу по дискретной математике.

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

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

Выбор варианта контрольной работы определяется двумя последними цифрами номера зачетной книжки. Получив проверенную работу, студент обязан выполнить указания, сделанные рецензентом. Если работа не зачтена, следует сделать работу над ошибками в той же тетради и представить работу на повторную рецензию.

К сдаче экзамена или зачета допускаются студенты, имеющие на руках зачтенные контрольные работы.

Таблица 1

Варианты контрольных заданий

№ варианта	№№ задач

РАБОЧАЯ ПРОГРАММА

Раздел 1. Множества

Тема 1. Дискретные множества

Дискретные множества. Способы задания и операции над множествами. Булеан. Мощность прямого произведения множеств.

Тема 2. Элементы комбинаторики

Число размещений, перестановок и сочетаний, число разбиений на множества заданной мощности.

 

Раздел 2. Булевые функции

Тема 3. Булевые переменные и функции

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

Тема 4. Дизъюнктивная и конъюнктивная нормальные формы

Дизъюнктивная и конъюнктивная нормальные формы (ДНФ, КНФ) формул и их построение. Совершенные ДНФ, КНФ. Минимизация ДНФ, КНФ. Полиномиальное разложение: СПНФ, канонический полином Жегалкина, арифметический полином.

Раздел 3. Основы теории алгоритмов

Тема 5. Понятие алгоритма и сложность алгоритма

Понятие алгоритма и оценка сложности алгоритма. Эвристические алгоритмы. «Жадные» алгоритмы.

Раздел 4. Теория графов

Тема 6. Основные понятия теории графов

Граф как абстрактное математическое понятие. Вершины, рёбра, дуги. Понятие инцидентности. Способы задания графов. Матрицы графов и их свойства. Степени вершин графа. Теорема о вычислении вершин нечётной степени в графе (лемма о рукопожатиях).

Тема 7. Виды графов, операции над ними

Простой граф, мультиграф, псевдограф. Неориентированный и ориентированный графы (орграфы). Полный граф, звёздный граф и т.д. Двудольный граф, критерий двудольности. Понятие изоморфности графов. Инварианты.

Части графа. Подграфы. Дополнение графа. Реберный граф. Основные операции над графами.

Тема 8. Пути в графах, связность

Пути в графах. Меры графов (эксцентриситет, диаметр, радиус, сумма расстояний, центр и центр тяжести). Связность графов. Компоненты графов. Теорема Менгера.

Тема 15. Взвешенные графы

Взвешенные графы. Взвешенные направленные графы (сети). Кратчайшее остовное дерево в графе. Деревья Штейнера.

КОНТРОЛЬНАЯ РАБОТА

 

I. Докажите тождество

 

1.(A Ç(()È()))È() = A.

2. (A Ç C)È(B Ç )È( Ç C)È() = U.

3. (A \ B)È(A Ç B)È( =U.

4. (A Ç C)È(A \ C)È = .

5. (A Ç B)È()È( È( Ç ))=U.

6. ((A \ B)È(A Ç B)) Ç ( =Ø.

7. (A Ç B Ç C)È(C \ А)È( Ç C) = C.

8. .

9. (A Ç B Ç C)È( Ç B Ç C)È È = U.

10. = .

 

II. С помощью основных равносильностей (без построения таблицы истинности) привести заданную булеву функцию к виду СДНФ.

 

11. . 16. .

12. . 17. .

13. . 18. .

14. 19. .

15. . 20. .

III. Составить таблицу истинности для заданной булевой функции. По таблице истинности составить СДНФ, СКНФ этой булевой функции и получить представление этой булевой функции в виде полинома Жегалкина и арифметического полинома.

 

21. . 26. .

22. . 27. .

23. . 28. .

24. . 29. .

25. . 30. .

 

IV. Построить по матрице смежности граф и его реберный граф.

 

31. . 36. .

 

32. . 37. .

 

33. . 38. .

 

34. . 39. .

 

35. . 40. .

V. Для изображенного графа записать последовательность степеней, построить матрицу смежности, найти центр и центр тяжести.

41. 46.

 

42. 47.

 

 

43. 48.

 

 

4
4.
49.

 

 

45. 50.

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

 

51.
56.

 

52. 57.

53. 58.

 

54. 59.

 

5
5.
60.

 

 

VII. С помощью алгоритма Флойда найти кратчайшие пути между всеми па рами вершин графа.

 

 

61.66.

 

 

 

62. 67.

 

 

 

63. 68 .

 

 

 

64. 69.

 

 

65. 70.
РЕШЕНИЕ ТИПОВОГО ВАРИАНТА

 

I. Докажите тождество = .

Решение:

=

= =

= =

= =

= =

= = .

 

При преобразовании были использованы следующие формулы:

,

,

,

,

,

,

,

.

 

 

II. С помощью основных равносильностей (без построения таблицы истинности) привести заданную булеву функцию к виду СДНФ.

.

 

Решение. С помощью основных равносильностей преобразуем к ДНФ:

= = = =

= - ДНФ.

 

Применяя закон склеивания (в обратном порядке: ), дополняем конъюнкции , до полных элементарных конъюнкций:

= .

 

Т.к. , после сокращения одинаковых конъюнкций, получаем СДНФ: F = .

III. Составить таблицу истинности для заданной булевой функции. По таблице истинности составить СДНФ, СКНФ этой булевой функции и получить представление этой булевой функции в виде полинома Жегалкина и арифметического полинома.

Решение.

Составим таблицу истинности для этой булевой функции

Таблица истинности СДНФ

					()			Элементарные конъюнкции СДНФ

 

СДНФ состоит из дизъюнкций полных элементарных конъюнкций наборов переменных , на которых функция принимает значение 1. Переменные берутся без отрицания, если им соответствует в таблице истинности 1, с отрицанием, если 0. Следовательно, СДНФ имеет вид:

.

 

СКНФ состоит из конъюнкций полных элементарных дизъюнкций наборов переменных , на которых функция принимает значение 0. Переменные берутся без отрицания, если им соответствует в таблице истинности 0, с отрицанием, если 1.

Таблица истинности СКНФ

					()			Элементарные дизъюнкции СКНФ

 

Следовательно, СКНФ этой булевой функции имеет вид:

()()()()().

 

Получим представление этой булевой функции в виде полинома Жегалкина. Заменим в СДНФ операцию дизъюнкции операцией сложения по модулю два по . При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю (т.е. , если ). Следовательно, СПНФ будет иметь вид:

.

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

.

Т.е. P(F) .

 

Найдем представление этой булевой функции в виде арифметического полинома. Заменим в СДНФ операцию дизъюнкции на операцию "арифметическое сложение" по формуле . При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю (, если ):

.

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

Получаем, что G(F)

 

Ответ: СДНФ имеет вид: , СКНФ: ()()()()(), полином Жегалкина: P(F) , арифметический полином: G(F)

 

IV. Построить по матрице смежности граф и его реберный граф.

.

Решение.

По матрице смежности строим граф:

Строим реберный граф. Вершинами реберного графа являются ребра исходного графа. Вершины смежны, если смежны соответствующие им ребра исходного графа. Получаем следующий реберный граф:

V. Для изображенного графа записать последовательность степеней, построить матрицу смежности, найти центр и центр тяжести.

Решение.

1) Запишем последовательность степеней графа.

deg A =1, deg D =1,

deg B =2, deg E =4,

deg C =1, deg F =3.

Значит последовательность степеней графа имеет вид: (1, 1, 1, 2, 3, 4).

 

2) Постоим матрицу смежности:

 

3) Найдем эксцентриситеты вершин графа

,

,

,

,

,

.

Следовательно, центр графа составляют вершины B, E, F.

 

4) Найдем сумму расстояний для каждой вершины графа

Следовательно, центр тяжести графа находится в вершине Е.

VII. С помощью алгоритма Флойда найти кратчайшие пути между всеми парами вершин графа.

 

 

 

Решение.

Для выполнения алгоритма Флойда построим матрицу весов, которая является разновидностью матрицы смежности:

 

.

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

 

1) Проход через вершину А. С помощью построенной матрицы (а не по графу) сравниваем пути. Например, между вершинами C и E «расстояние» , а путь C – А – E равен 11, поэтому меняем соответствующий элемент в матрице. Получаем следующую матрицу:

.

2) Проход через вершину B. Выполняется аналогично, но основой для его выполнения служит матрица, полученная в результате прохода через матрицу А.

.

3) Проход через вершину С.

.

В результате этого прохода матрица не изменилась, так как в вершину С не входит ни одна дуга, а следовательно путь из одной вершины в другую через С невозможен.

 

4) Проход через вершину D.

.

 

5) Проход через вершину E.

.

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

 

 

Ответ: матрица расстояний между вершинами графа имеет вид

 

.

 

ЛИТЕРАТУРА

1 Горбатов, В. А. Дискретная математика / В. А. Горбатов, А. В. Горбатов, М. В. Горбатова. – М.: АСТ Астрель, 2006.

2 Горбатов, В. А. Основы дискретной математики / В. А. Горбатов. – М.: Высшая школа, 1986.

3 Новиков, Ф. А. Дискретная математика для программистов / Ф. А. Новиков. – СПб.: Питер, 2007.

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

5 Супрун, В. П. Теория булевых функций. Теория автоматов. Полиномиальное разложение булевых функций: метод. указания к семинарским занятиям по специальным курсам / В. П.Супрун. – Мн.: БГУ, 1991.

6 Шапорев, С. Д. Дискретная математика. Курс лекций и практических занятий / С. Д. Шапорев. – СПб.: БХВ-Петербург, 2007.

7 Яблонский, С. В. Введение в дискретную математику / С. В.Яблонский. – М.: Наука,1988.

 

 

СОДЕРЖАНИЕ

Введение…………………………………………………………………… 3

Варианты контрольных заданий…………………………………………..4

Рабочая программа…………………………….……………………….......5

Контрольная работа…………………………………………………………7

Решение типового варианта……………………………….………………12

Литература…………………………………………………………………..19

 

План 2009/2010, поз. 30

 

Петрович Ася Вениаминовна

 

 

Методические указания и контрольные задания по дисциплине «Дискретная математика» для студентов уровня ВО заочной формы обучения специальности 45. 01. 03 «Сети телекоммуникаций»

 

Редактор Вердыш Н.В.

 

Подписано к печати

Формат

Усл. Печ. Л. 1,5. Уч. - изд. Л. 1,3

Тираж 60 экз. Заказ

 

 

Высший государственный колледж связи

220114 г. Минск, Скорины 8, к. 2.

 

 

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ И КОНТРОЛЬНЫЕ ЗАДАНИЯ

 

по дисциплине

 

«ДИСКРЕТНАЯ МАТЕМАТИКА»

для студентов уровня ВО заочной формы обучения

специальности 1-45 01 03 «Сети телекоммуникаций»

 

 

МИНСК 2009

 

 

 

Составитель: Петрович А.В.

 

Рецензент: Колодная Е.М.

 

Издание утверждено на заседании кафедры М и Ф

12.04.2009г., протокол № 8

Зав. кафедрой Гладков Л.Л.

ВВЕДЕНИЕ

В соответствии с учебным планом студенты третьего курса ВГКС специальности 1-45 01 03 – Сети телекоммуникаций в шестом семестре выполняют контрольную работу по дискретной математике.

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

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

Выбор варианта контрольной работы определяется двумя последними цифрами номера зачетной книжки. Получив проверенную работу, студент обязан выполнить указания, сделанные рецензентом. Если работа не зачтена, следует сделать работу над ошибками в той же тетради и представить работу на повторную рецензию.

К сдаче экзамена или зачета допускаются студенты, имеющие на руках зачтенные контрольные работы.

Таблица 1

Варианты контрольных заданий

№ варианта	№№ задач

РАБОЧАЯ ПРОГРАММА

Раздел 1. Множества

Тема 1. Дискретные множества

Дискретные множества. Способы задания и операции над множествами. Булеан. Мощность прямого произведения множеств.