Дискретная математика УМК

22.Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w.

23.Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w.

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

25.Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

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

27.Цепь (цикл) в G называется гамильтоновой (гамильтоновыми), если она (он) проходит по одному разу через каждую вершину псевдографа G.

28.Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

29.Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

30.Сетью называется связный граф (обычно, не орграф и не мультиграф), в котором заданы «пропускные способности» ребер.

31.Потоком в сети между вершиной t (источником) и s (стоком) называется набор чисел сij, (т. е. количество условного груза, перевозимого из вершины с номером i в вершину с номером j).

32.Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция попарно различных элементарных конъюнкций.

33.Конъюнктивной нормальной формой (КНФ) называется конъюнкция попарно различных элементарных дизъюнкций.

30

34.Совершенной дизъюнктивной формулой формулы алгебры высказыва-

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

35.Совершенной конъюнктивной формулой формулы алгебры высказыва-

ний (СКНФ) называется КНФ, в которой: различны все члены конъюнкции; различны все члены каждой дизъюнкции; ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной; каждая дизъюнкция содержит все переменные, входящие в исходную формулу.

36.Булевой функцией f(x1, x2, …, xn) называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.

37.Минимальной ДНФ (МДНФ) функции f(x1, x2, …, xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f.

38.N-местным предикатом, определенном на множествах M1, M2, …, Mn,

называется предложение, содержащее n переменных x1, x2, …, xn, превращающееся в высказывание при подстановке вместо этих переменных

любых элементов из множеств M1, M2, …, Mn соответственно.

39.Квантор – это логическая операция, которая по предикату Р(х) строит высказывание, характеризующее область истинности предиката Р(х).

40.Сеть Петри – это асинхронная сеть, связывающая между собой условия

исобытия. Реализация событий выполняется отдельными действиями. Последовательность действий образует моделируемый процесс. Формально структура сети Петри задается четверкой: S = < T, P, I, O >, где T – множество переходов; P – множество позиций; I – входная функция инцидентности; O – выходная функция инцидентности. Для сети Петри имеются два типа вершин: позиции и переходы. Позиции связаны только

31

с переходами. Переходы связаны только с позициями. Присвоение позициям сети фишек – неотрицательных чисел – называется ее маркиров-

кой. Маркировкой также называется вектор Μ = (μ1, …, μn), где n – чис-

ло позиций, μi N {0}. Сеть Петри, заданная структурой и маркировкой, называется маркированной сетью Петри: MS = < T, P, I, O, M >.

32

9.ТЕМЫ РЕФЕРАТОВ

1.Основные понятия теории множеств.

2.Мощность множеств. Мощность бесконечных множеств

3.Моделирование систем с помощью графов.

4.Сетевые модели.

5.Использование сетевых графиков для моделирования бизнеспроцессов.

6.Сложность графов. Оценка сложности систем с помощью теории графов.

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

8.Функционально-полные системы. Преобразование систем.

9.Исчисление предикатов.

10.Исчисление высказываний.

11.Алгебра логики.

12.Алгебра предикатов первого порядка.

13.Автоматический вывод теорем.

14.Сложность алгоритмов и программ.

15.Формальные определения понятия «алгоритм».

16.Эффективность алгоритмов. Разрешимость алгоритмов.

17.Алгоритмически неразрешимые проблемы.

18.Конечные автоматы.

19.Сети конечных автоматов.

20.Формальные грамматики. Автоматные грамматики.

33

10.ВОПРОСЫ К ЭКЗАМЕНУ

1.Определение множества.

2.Простейшие операции над множествами.

3.Отношения. Графические представления отношений. Свойства отношений.

4.Отношения эквивалентности. Разбиения и отношения эквивалентности.

5.Отношения порядка.

6.Отношения на базах данных и структурах данных составные отношения. Замыкание отношений.

7.Соответствия. Взаимно-однозначные соответствия и мощности множеств. Равномощность.

8.Отображения и функции. Обратные функции и отображения. Способы задания функций. Функционал, оператор.

9.Размещения, перестановки и сочетания (без повторений и с повторениями).

10.Основные теоремы комбинаторики.

11.Биномиальные и полиномиальные коэффициенты.

12.Решение комбинаторных задач.

13.Графы, их вершины и ребра.

14.Графы и бинарные отношения. Изображение графов.

15.Матрица инцидентности графа. Матрица смежности графа.

16.Подграфы. Степени вершин графа. Маршруты, цепи и циклы.

17.Планарные графы. Теоремы Эйлера и Куратовского.

18.Эйлеровы графы. Условия, при которых граф эйлеров. Раскраска графов.

19.Структуры данных для представления графа. Представление графа списком смежности.

20.Обход графа. Обход графа по глубине. Обход графа по ширине.

34

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

22.Маршруты и связность в орграфах. Упорядоченные орграфы и обходы.

23.Высказывания и логические связки. Булевы функции (БФ).

24.Способы задания БФ. Функциональный базис, композиция функций. Формулы, эквивалентные преобразования формул.

25.Элементы булевой алгебры.

26.Специальные разложения БФ. СДНФ и СКНФ.

27.Минимизация булевых функций. Схемы из логических элементов.

28.Связь сложности схем и сложности формул. Минимизация БФ аналитическим способом. Нормальные формы БФ.

29.Минимизация БФ методом Квайна – Мак-Класки. Табличный способ минимизации на картах Карно.

30.Функциональная полнота систем булевых функций.

31.Замечательные классы БФ. Теорема о функциональной полноте. Примеры функционально-полных базисов. Построение схем в универсальных базисах.

32.Функции k-значной логики.

33.Предикаты, операции над ними.

34.Формулы логики предикатов.

35.Исчисление предикатов. Кванторы существования и всеобщности.

36.Основные понятия теории алгоритмов.

37.Машины Тьюринга.

38.Понятие об алгоритмической разрешимости и неразрешимости задач.

39.Функции сложности алгоритмов.

40.Методы построения эффективных алгоритмов.

41.Метод разбиения и рекурсии.

42.Сложность рекурсивных алгоритмов.

43.Определение и основные понятия конечных автоматов.

44.Автомат Мили. Автомат Мура.

35

45.Способы задания автоматов.

46.Языки и грамматика.

47.Классификация грамматик.

48.Контекстно-свободные грамматики.

49.Эквивалентность состояний.

50.Сети Петри.

51.Расширенные сети Петри.

36

11. ТЕСТОВЫЕ ЗАДАНИЯ

Варианты ответов:

1)A B =[−3,6)

2)A B =[−3,3)

3)A B =[−3,6]

4)A B =(−3,6)

Варианты ответов:

1)(A B)∩C =(−2,2)

2)(A B)∩C =(−2,2]

3)(A B)∩C =(1,2]

4)(A B)∩C =(−3,2]

Варианты ответов:

1)A ∩B ∩C =(1,2).

2)A ∩B ∩C =(−2,2].

3)A ∩ B ∩C =(1,2]

4)A ∩ B ∩C =(1,6)

4.Бинарное отношение задано матрицей:

Представить его матрицей.

37

Варианты ответов:

1)R ={(1,1),(1,2),(1,4),(2,1),(2,2),(2,3),(3,2),(3,3),(4,1)}

2)R ={(1,1),(2,1),(2,2),(2,3),(3,2),(3,3),(4,1)}

3)R ={(1,2),(1,4),(2,1),(2,3),(3,2),(4,1)}

4)R ={(1,1),(1,2),(1,4),(2,3),(3,2),(3,3),(4,1)}

5.Из 6 человек надо выбрать 4 человека и разместить их на четырех занумерованных стульях. Сколькими способами это можно сделать?

Варианты ответов:

1)120.

2)360.

3)125.

4)240.

6.Сколькими способами можно выбрать двух элемента из восьми?

Варианты ответов:

1)120.

2)64.

3)28.

4)72.

7.Из полной колоды карт (52 листа) вынимается сразу несколько

карт. Сколько возможных исходов, что в случае, если вынуто четыре карты, то среди них будут две семерки?

Варианты ответов:

1)620.

2)1164.

3)6768.

4)1282.

38

8. Выполнить операцию объединения над графами.

Варианты ответов:

39