double arrow

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

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

Раздел 6. Графы и сети.

Определение графа. Различные типы графов.

Матричные способы задания графов.

Изоморфизм графов.

Маршруты, циклы в неориентированном графе.

Пути, контуры в ориентированном графе.

Связность неориентированного графа. Матрица связности.

Связность ориентированного графа. Матрицы односторонней и сильной связности.

Экстремальные пути в нагруженных ориентированных графах.

Алгоритм Форда – Беллмана нахождения минимального пути.

Деревья. Остовные деревья.

Минимальное остовное дерево. Алгоритм Краскала.

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

Тесты для самоконтроля

ЗАДАНИЯ ВАРИАНТЫ ОТВЕТОВ
1. Установите соответствие между высказываниями 1. Объединением множеств А и В называется множество А È В, все элементы которого являются…. 2. Пересечением множеств А и В называется множество А Ç В, все элементы которого являются …. 3. Относительным дополнением множества В до множества А называется множество А \ В, все элементы которого являются … 4. Симметрической разностью множеств А и В называется … А) элементами обоих множеств А и В. В)элементами множества А, но не являются элементами множества В С) элементами хотя бы одного из множеств А или В. D)множество всех таких элементов x Î U, которые не принадлежат множеству А: = U \ A. Е) множество А + В: А + В = (А \ В) È (В \ А).
2. Установите соответствие между левой и правой частями тождеств алгебры множеств 1. A È B  = 2. = 3. A È (A Ç B) = 4. = А) A В) È С) B È A D) Ç Е) B Ç A
3.Установите соответствие между списками двух множеств,заданных различным образом: 1. 2. 3. 4. А){2:3} В)(2;3) С)(-∞; 2) (3; +∞) D)(-∞; 2] [3; +∞) Е) [2; 3]
4. Пусть U= {1,2,3,4}, А={1,3,4}, В={2,3}, С={1,4}. Тогда 1. Ç = 2. = 3. (В\А) È = А) {1,2,4}, В) {1,4}, С) {2,3},
5.Сколько имеется пятизначных чисел, которые делятся еа 5? 1) 12000; 2) 15000; 3) 18000; 4) 9000
6. На рояле 88 клавиш. Сколько существует последовательностей из шести попарно различных звуков? (В последовательности звуки идут один за другим) Сколько существует аккордов из шести звуков? (Аккорд получается, если любые 6 клавиш нажаты одновременно). 1) аккордов и последовательностей; 2) аккордов и последовательностей; 3) последовательностей и аккордов.
7. При обследовании читательских вкусов оказалось, что 60% студентов читают журнал А, 50% - журнал В, 50% - журнал С, 30% - журналы А и В, 20% - журналы В и С, 40% - журналы А и С, 10% - журналы А, В и С. Сколько процентов студентов не читает ни одного журнала? 1) 10%; 2) 20%; 3) 15%; 4) 25%
8. Число положительных чисел, не превосходящих 100 и не делящихся ни на одно из чисел 3, 5 и 7 равно… 1) 258; 2) 457; 3) 287; 4) 241.
9. Установите соответствие между высказываниями 1.Областью определения бинарного отношения r называется … 2. Областью значений бинарного отношения r называется… 3. Областью задания бинарного отношения r называется… А) множество Rr = {y çсуществует x, что xr y}. В) множество Mr = Dr È Rr. С) множество Dr = {x çсуществует y, что xr y}.
10. Установите соответствие между высказываниями 1. Отношение r называется рефлексивным на множестве X, если ….. 2. Отношение r называется симметричным на множестве X, если … 3.Отношение r называется транзитивным на множестве X, если … 4.Отношение r называется антисимметричным на множестве X, если… А) для любых x, y Î X из xry следует yr x. В) для любого x Î X выполняется xr x. С) для любых x, y Î X из xry и yr x следует x = y. D) для любых x, y, z Î X из xry и yr z следует xr z.
11. Пусть отношение R – «быть руководителем», определенное на множестве сотрудников организации М. Каковы свойства этого отношения? 1) рефлексивно; 2) антирефлексивно; 3) симметрично; 4) транзитивно.
12. Дана реализация графа. Соответствующим ей множеством вершин (V) и списком дуг (Е) является
 
 

1) V= {1,2,3,4}; Е={(1,3),(3,1), (3,2),(4,4), (4,3)}; 2) V= {1,2,3,4}; Е={(1,3),(3,1), (3,2),(4,4), (3,4)}; 3) V= {1,2,3,4}; Е={(2,3),(1,3), (3,1),(4,4), (3,4)}; 4) V= {1,2,3,4}; Е={(1,3),(3,4), (2,32),(3,1)}.
  14. Матрица смежности изображенного графа имеет вид
 
 


1) ; 2) ; 3) ; 4)
  15. Матрица смежности изображенного графа имеет вид
 
 

1) ; 2) ; 3) ; 4)
16. Среди приведенных графов указать те, которые имеют собственный Эйлеров цикл. 1) 2)
 
 


3)

17. Сумма степеней вершин первого и второго типа изображенного графа равна… 1) 6; 2) 7; 3) 4; 4) 5.
18. Компонентой связности неориентированного графа называется …. 1) его односторонне связный подграф, не являющийся собственным подграфом никакого другого односторонне связного подграфа данного графа 2) его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа данного графа 3) его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа.
19. Какая модель теории графов адекватна следующей задаче: Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины. 1) нахождение минимального пути; 2) нахождение максимального пути 3)нахождение минимального остовного дерева; 4)нахождение экстремального пути.
20. Какая модель теории графов адекватна следующей задаче: Имеется схема городских дорог с перекрестками и, возможно, однос­торонним движением. Необходимо найти маршрут, соединяющий две точки на карте. Как найти такой маршрут при условии, что его длина минимальна? 1) нахождение минимального пути; 2) нахождение максимального пути 3)нахождение минимального остовного дерева; 4)нахождение экстремального пути.
21. Установите последовательность действий алгоритма Форда Беллмана: Шаг 1 Шаг 2. Шаг 3 Шаг 4. А) Восстановление минимального пути. Для любойвершины xs предшествующая ей вершина xr определяется из соотношения: lr (n – 2) + crs = ls (n – 1), xr Î G- 1(xs), где G- 1(xs) - прообраз вершины xs. В)Установка начальных условий. Ввести число вершин графа n и матрицу весов C = (cij). С) Положить k = 0. Положить li (0) = ¥ для всех вершин, кроме х 1; положить l 1(0) = 0. D)В цикле по k, k = 1,..., n – 1, каждой вершине xi на k -ом шаге приписать индекс li (k) по следу­ющему правилу: li (k) = { lj (k – 1)+ cji } для всех вершин, кроме х 1, положить l 1(k) = 0.
22. Всего существует ……. Различных булевых функций для п переменных. 1) ; 2) ; 3) ; 4)
23. Какое из следующих утверждений верно? 1) Переменные булевой функции и сама булева функция принимают значения 0 или 1; 2) Переменные булевой функции принимают значения 0 или 1, а значения самой булевой функции совпадают с множеством действительных чисел; 3) Значения переменных булевой функции совпадают с множеством действительных чисел, а сама булева функция принимает значения 0 или 1; 4) Значения переменных булевой функции и значения самой функции совпадают с множеством действительных чисел;
24. Укажите номера выражений, являющихся формулами 1) (Ø x V y)&((y É z) ~ x) 2) Ø x & y É z Ø ~ x 3) x &(y É z )
26. Установите соответствие 1. Дистрибутивность. 2. Закон де Моргана. 3. Идемпотентность. 4. Поглощение. 5. Расщепление (склеивание). А) а) A &(A V B) º A; б) A V A & B º A. В) а) A & A º A (для конъюнкции); б) A V A º A (для дизъюнкции). С) а) Ø(A & B) ºØ AB (отрицание конъюнкции есть дизъюнкция отрицаний); б) Ø(A V B) º Ø AB (отрицание дизъюнкции есть конъюнкция отрицаний). D) а) A &(B V C) º A & B V A & C (для конъюнкции относительно дизъюнкции); б) A V(B & C) º (A V B)&(A V C) (для дизъюнкции относительно конъюнкции). Е) а) A & B V A &(Ø B) º A); б) (A V B) & (AB) º A.
27. Дизъюнктивная нормальная форма для функции f (x 1, x 2, x 3) = Ø(x 2 Ø x 3) ~ (Ø x 1V x 2) имеет вид   1) f (x 1, x 2, x 3) º x 2& x 3 V x 1x 2 2) f (x 1, x 2, x 3) º x 2x 3 V x 1x 2 3) f (x 1, x 2, x 3) º x 2& x 3 x 1x 2
28. Совершенная конъюнктивная нормальная форма для функции f (x 1, x 2, x 3) = Ø(x 2 Ø x 3) ~ (Ø x 1V x 2) имеет вид 1 ) f (x 1, x 2, x 3) º ≡ (x 1V x 2V x 3)V(x 1V x 2x 3)&(x 1x 2V x 3)&(Ø x 1x 2V x 3), 2) f (x 1, x 2, x 3) º ≡ (x 1V x 2V x 3)&(x 1V x 2x 3)&(x 1x 2V x 3)&(Ø x 1x 2V x 3), 3) f (x 1, x 2, x 3) º ≡⌐ (x 1V x 2V x 3)&(x 1V x 2x 3)&(x 1V x 2V x 3)&(Ø x 1x 2V x 3).
29. Выберите правильный вариант ответа 1 – 4 для следующих вопросов: А) Сколько может быть различных ДНФ у булевой функции? В) Сколько может быть различных СДНФ у булевой функции? С) Сколько может быть различных КНФ у булевой функции? D) Сколько может быть различных СКНФ у булевой функции? Варианты ответа: 1 – ноль или одна; 2 – ноль или бесконечно много; 3 – бесконечно много; 4 – одна; 5 – одна или бесконечно много.
30. В какой из нормальных форм находится данная формула булевой функции трех переменных f (x, y, z): 1.ДНФ 2. СДНФ 3. КНФ 4. СКНФ А) x V y & z; В) x & y & z; С)(x V y)&(xz); D) x V y V z.

Список литературы

Основная литература

1. Акимов, О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001. -ISBN 5-291-01658-5

2. Андерсон, Джеймс А. Дискретная математика и комбинаторика.: пер. с англ. – М.: Издательский дом «Вильямс», 2004. – 960 с.: ил. – Парал. Тит. англ.- ISBN 5-8459-0498-6

3. Дискретная математика для программистов / Ф.А. Новиков. – СПб.: Питер, 2001. – 304 с.: ил.- ISBN 5-272-00183-4

4. Кузнецов, О.П. Дискретная математика для инженера/ О.П.Кузнецов,Г.М. Адельсон-Вельский М.: Энергоатомиздат, 1988.- 480 с. -ISBN 5-283-01568-7

5. Лекции по теории графов / Емеличев В.А., Мельников О.И.- М.: Наука, 1990. -384 с. -ISBN 5-291-01658-5

6. Лекции по теории графов / Емеличев В.А., Мельников О.И., М.: Наука, 1990. 384 с. ISBN 5-291-01658-5

7. Лихтарников, Л. М. Математическая логика. Курс лекций. Задачник-практикум и решения/Л.М. Лихтарников, Т. Г.Сукачева. –М.:Изд-во “Лань”, 1999.- ISBN 5-578-10016-5

8. Москинова,Г.И. Дискретная математика. Математика для менеджеров в примерах и упражнениях: учебное пособие. – М.: Логос, 2000. – 240 с.: ил. ISBN5-94010-016-3

9. Нефедов, В.Н.. Курс дискретной математики: Учебное пособие/В.Н.Нефедов, В.А.Осипова.-М.: Изд-во МАИ, 1992.- 264 с.- ISBN5-56010-016-4

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

1. Горбатов, В.А. Основы дискретной математики. М.: Высшая школа, 1986. 310 с. -ISBN 5-253-02659-5

2. Липский, В. Комбинаторика для программистов: пер. с польск. - М.: Мир, 1988.- 213 с. -ISBN 5-578-10016-5

3. Чень Ч. Р. Математическая логика и автоматическое доказательство теорем/ Ч.Чень, Р.Ли. – М.: Наука, 1983.- ISBN5-94010-016-3


Приложение 1

Министерство образования И НАУКИ Российской Федерации

Бузулукский гуманитарно-технологический институт (филиал)

федерального государственного бюджетного образовательного учреждения

высшего профессионального образования

"Оренбургский государственный университет".

Факультет дистанционных технологий обучения

Кафедра физики, информатики, математики


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: