- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
№ 1.30. В студенческом потоке 37 человек хорошо знают математику, а 25 человек – электронику, и 19 человек хорошо знают и математику и электронику. Если в потоке каждый из студентов знает хотя бы один из этих предметов, то сколько студентов в потоке?
№ 1.31. Из 250 студентов 151 изучают немецкий язык, 136 – французский язык, 27 – итальянский, 63 – французский и немецкий, 7 – итальянский и французский, 11 – немецкий и итальянский, 4 – все три языка.
а) Сколько студентов изучают немецкий или французский язык?
б) Сколько студентов изучают только итальянский язык?
в) Сколько студентов изучают немецкий и французский язык, но не
итальянский?
г) Сколько студентов не изучают ни одного языка?
д) Сколько студентов изусают хотя два иностранных языка?
№ 1.32. В отчете о количестве студентов, изучающих иностранные языки, сообщалось, что из 100 студентов все три языка изучают 5 человек, немецкий и английский – 10 человек, французский и английский – 8 человек, немецкий и французский – 20 человек, английский – 30, немецкий – 23, французский – 50. Инспектор, представивший этот отчет, был отстранен от работы. Почему?
№ 1.33 Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике, астрономии. Три спецкурса посещают 10 студентов, по математике и астрономии –25 студентов, спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по асирономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?
№ 1.34. Экзамен по математике содержал три задачи: по алгебре, геометрии и тригонометрии. Из 800 абитурентов задачу по алгебре решили 250 человек; по алгебре или геометрии – 660 человек; по две задачи решили 400 человек, из них две задачи по алгебре и и геометрии решили 150 человек, по алгебре и тригонометрии – 50 человек; ни один абитуриент не решил все задачи; 20 абитуриентов не решили ни одной задачи; только по тригонометрии задачи решили 120 человек. Сколько абитуриентов решили только одну задачу? Сколько абитуриентов решили задачи по тригонометрии?
№ 1.35. На курсах иностранных языков учится 600 человек. Из них французский изучают 220 человек, английский – 270 человек. Слушатели, изучающие английский язык, не изучают немецкий язык; один французский язык изучают 100 человек, один немецкий язык изучают 180 человек. Сколько человек изучает по два иностранных языка? Сколько человек изучает один иностранный язык?
№ 1.36. На кафедре иностранных языков работают 18 преподавателей. Из них 12 преподают английский язык, 11 – немецкий язык, 9 – французский язык. 5 преподавателей преподают английский и немецкий языки, 4 – английский и французский, 3 – немецкий и французский. Сколько преподавателей преподают все три языка? Сколько преподавателей преподают только два языка?
№ 1.37. Группа студентов из 25 человек сдала экзаменационную сессию со следующими результатами: 2 человека получили только “отлично”; 3 человека получили отличные, хорошие и удовлетворительные оценки; 4 человека только “хорошо”; 3 человека только хорошие и удовлетворительные оценки. Число студентов, сдавших сессию только на “удовлетворительно”, равно числу студентов, сдавших сессию только на “хорошо” и “отлично”. Студентов, получивших только отличные и удовлетворительные оценки – нет. Удовлетворительные или хорошие оценки получили только 22 студента. Сколько студентов сдали сессию только на “удовлетворительно”?
№ 1.38. Преподаватели кафедры Прикладной математики преподают на трех факультетах: механическом, технологическом, экономическом. На технологическом факультете работает 22 преподавателя, на механическом – 23 преподавателя, на механическом и экономическом –36 преподавателей. Только на технологическом факультете работают 10 преподавателей. 2 –на трех факультетах. 5 преподавателей работают только на механическом и экономическом факультетах. Число преподавателей, работающих только на механическом и технологическом факультетах, равно числу преподавателей, работающих на экономическом и технологическом факультетах. Сколько преподавателей работает на кафедре? Сколько преподавателей работает только на одном факультете?
№ 1.39. Экзамен по математике содержал три задачи: по алгебре, геометрии и тригонометрии. Из 750 абитуриентов задачу по алгебре решили 400 абитуриентов, по геометрии – 480, по тригонометрии – 420. Задачи по алгебре или геометрии решили 630 абитуриентов; по геометрии или тригонометрии – 600 абитуриентов; по алгебре или тригонометрии – 620 абитуриентов. 100 абитуриентов не решили ни одной задачи. Сколько абитуриентов решили все задачи? Сколько абитуриентов решили только одну задачу?
№ 1.40. Доказать аналитически, что для любых трех множеств А, В и С справедливы равенства:
а)
б)
в) если и
г) если
д)
е)
ж) если и
з) если
-
Теория графов.
-
Основные определения теории графов.
-
Определение.
Граф G — это упорядоченная пара G=(V,E), где V — это множество вершин или узлов, E — это множество пар различных вершин, называемых рёбрами.
Определение.
Ориентированным графом (графом или орграфом) будем называть тройку , где () — множество, называемое множеством вершин графа, — множество (возможно и пустое), называемое множеством дуг, — отображение, действующее из в , называемое отображением инцидентности.
Моментом рождения теории графов как математической дисциплины считают появление в 1736 году статьи Эйлера, в которой рассматривалась задача о Кёнигсбергских мостах (см. раздел дополнительные сведения). Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.
Определение.
Граф называется не ориентированным, если каждое его ребро не ориентировано, и ориентированным, если ориентированы все его рёбра.
Определение.
Графы G и G' изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин V и V', что вершины соединены рёбрами в одном графе в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если рёбра ориентированы, то их направления так же должны соответствовать друг другу.
Определение.
Вершина, не инцидентная никакому ребру, называется изолированной.
Определение.
Граф, состоящий только из изолированных вершин, называется нуль-графом.
Определение.
Полным графом называется граф ребрами, которого являются всевозможные пары для двух различных вершин из V.
Рис. 2.1. Полные графы.
Определение.
Рёбра у которых обе концевые точки совпадают называются петлёй. Петля обычно считается не ориентированной.
Определение.
Для каждого графа G существует обратный граф G*, получаемый изменением ориентации каждого из рёбер G на противоположную.
Определение.
Граф называется плоским, если он может быть изображён на плоскости так, что все пересечения рёбер являются вершинами G.
Рис. 2.2 Плоский и не плоский граф.
-
Планарные графы.
Определение.
Планарный граф — это граф, который может быть изображён на плоскости без пересечения рёбер.
Теорема Понтрягина-Куратовского.
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных (топологически эквивалентных) и .
, полный граф с 5 вершинами граф иллюстрирующий задачу о трёх колодцах
Критерий непланарности:
Достаточное условие — если граф содержит двудольный подграф или полный подграф ,то он является не планарным.
Необходимое условие — если граф не планарный, то он должен содержать больше четырёх (4) вершин, степень которых больше трёх (3) или больше пяти (5) вершин степени больше двух (2).
-
Локальные степени графа. Части и подграфы.
Определение.
Пусть G — неориентированный граф. Число рёбер, инцидентных одной вершине а, будем обозначать . Это число называется локальной степенью или просто степенью графа в вершине а.
Так же существует понятие локальной степени и для ориентированного графа. Это обозначается, как и числа рёбер, соответственно выходящих из вершины а и входящих в а.
Теорема: В конечном графе число вершин нечётной степени чётно.
Определение.
Граф Н называется частью графа G, HG, если его множество вершин содержится в множестве вершин графа b, и все рёбра Н являются рёбрами G.
Нуль-граф считается частью каждого графа.
Определение.
Граф называют подграфом графа то есть , если и .
Определение.
Для любой части Н графа G существует единственная дополнительная часть (дополнение) , состоящая из всех рёбер графа G, которые не принадлежат Н, то есть .