B - Иркутский государственный технический университет

Министерство образования и науки Российской Федерации
ФГБОУ ВПО
«ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ»
Физико-технический институт
Кафедра квантовой физики и нанотехнологий
ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА ДИСЦИПЛИНЫ
(рабочая учебная программа дисциплины)
Дискретная математика
Направление подготовки
090900 «Информационная безопасность»
Профиль подготовки
Комплексная защита объектов
информатизации_
Квалификация (степень)
бакалавр
Форма обучения
очная
Иркутск 20___ г.
1. Информация из ФГОС, относящаяся к дисциплине
1.1. Вид деятельности выпускника
Дисциплина охватывает круг вопросов относящиеся к виду
деятельности выпускника: проектно-технологическая деятельность;
1.2 Задачи профессиональной деятельности выпускника
В дисциплине рассматриваются указанные в ФГОС задачи
профессиональной деятельности выпускника:
 проведение проектных расчетов элементов систем обеспечения
информационной безопасности;
1.3 Перечень компетенций, установленных ФГОС
Освоение программы настоящей дисциплины позволит сформировать у
обучающегося следующие компетенции:
 способностью к саморазвитию, самореализации, приобретению новых
знаний, повышению своей квалификации и мастерства (ОК - 11);
 способностью критически оценивать свои достоинства и недостатки,
определять пути и выбрать средства развития достоинств и устранения
недостатков (ОК - 12);
 способностью использовать основные естественнонаучные законы,
применять математический аппарат в профессиональной деятельности,
выявлять сущность проблем, возникающих в ходе профессиональной
деятельности (ПК- 1);
1.4.Перечень умений и знаний, установленных ФГОС
Студент после освоения программы настоящей дисциплины должен:
Уметь: использовать математические методы и модели для решения
прикладных задач.
Владеть: методами количественного анализа процессов обработки,
поиска и передачи информации.
2. Цели и задачи освоения программы дисциплины
Целью данной дисциплины является формирование у обучающихся
базовых знаний по дискретной математике, умений и навыков по
применению методов дискретной математики, необходимых для построения
математических моделей и разработки алгоритмов, применяемых для анализа
различных процессов и явлений, а также
при проектировании
вычислительных машин, комплексов, систем и сетей. Формирование
практических навыков разработки и анализа алгоритмов над объектами
дискретной математики.
Задачи
преподавания
дискретной
математики
определяются
спецификой ее предмета и метода. Конкретно, для избранного профиля в
более детальном плане задачами являются:
- изучение студентами основ теории множеств;
- освоение основных понятий комбинаторики, методов решения
комбинаторных задач;
2
- приобретение навыков осуществления операций над графами и
выполнения количественных оценок их характеристик;
3. Место дисциплины в структуре ООП
Для изучения дисциплины, необходимо освоения содержания
дисциплин:
- Математика (ОК-11, ОК-12, ПК-1)
- Информатика
Знания и умения, приобретаемые студентами после освоения
содержания дисциплины, будут использоваться в:
- Теория вероятностей и математическая статистика
(ОК-11, ОК-12, ПК-1, ПК-22)
Теория информации
(ОК-8, ОК-11, ОК-12, ПК-1, ПК-2, ПК-8
Математическая логика и теория алгоритмов
(ОК-8, ОК-11, ОК-12, ПК-1, ПК-2, ПК-23)
Системы поддержки принятия решений
(ПК-9, ПК-10, ПК-12, ПК-18, ПК-20, ПК-21, ПК-23)
Криптографические методы защиты информации
(ПК-15, ПК-18, ПК-23, ПК-27)
4. Основная структура дисциплины.
Общая трудоѐмкость дисциплины составляет 2,5 ЗЕТ (90 час).
Таблица 1 – Структура дисциплины
Вид учебной работы
Трудоемкость, часов
Всего
Семестр
№4
Общая трудоемкость дисциплины
90
90
Аудиторные занятия, в том числе:
54
54
лекции
18
18
лабораторные работы
практические/семинарские занятия
36
36
Самостоятельная работа (в том числе
36
36
курсовое проектирование)
Вид промежуточной аттестации
Зачет
Зачет
(итогового контроля по дисциплине), в
том числе курсовое проектирование
5. Содержание дисциплины
5.1.
Перечень основных разделов и тем дисциплины
Все разделы и темы способствуют достижению освоения ОК-11.
Раздел 1. Теория множеств
3
Тема 1. Множества.
Основные понятия и определения. Операции над множествами.
Диаграммы Венна. Алгебра подмножеств. Декартово произведение
множеств. Мощность множества.
Тема 2. Отношения.
Бинарные отношения. N-арные отношения. Специальные бинарные
отношения. Операции над бинарными отношениями. Матрица бинарного
отношения. Функции. Инъективные и сюръективные функции. Отношения
эквивалентности. Отношения порядка.
Тема 3. Мощность множеств.
Эквивалентность множеств. Понятие мощности множества.
Раздел 2. Комбинаторика.
Тема 1. Комбинаторные конфигурации.
Основные правила комбинаторики. Перестановки и подстановки.
Размещения и сочетания. Размещения и сочетания с повторением. Разбиения.
Бином Ньютона. Полиномиальная формула. Метод включений и
исключений.
Тема 2. Рекуррентные соотношения. Возвратные
последовательности.
Рекуррентные соотношения. Возвратные последовательности.
Тема 3. Производящие функции.
Производящие функции.
Раздел 3. Графы.
Тема 1. Основные определения.
Основные понятия и определения. Виды графов. Способы задания
графа. Операции над графами. Изоморфизм графов. Валентность.
Тема 2. Связность.
Маршруты, цепи, циклы. Связность. Метрические характеристики
графа. Эйлеровы и Гамильтоновы графы. Определение путей и кратчайших
путей в графах. Потоки в сетях.
Тема 3. Деревья.
Лес. Деревья. Обходы графа по глубине и ширине. Остов графа.
Фундаментальные циклы. Разрезы.
Тема 4. Планарность графов.
Основные определения. Теорема Эйлера. Теорема Понтрягина —
Куратовского. Искаженность. Толщина.
Тема 5. Раскраска графов.
Хроматическое число графа. Алгоритмы раскраски. Теоремы о пяти и
четырех красках.
Все лекции читаются с элементами интерактивных занятий. Лекция,
как правило, начинается с того, что студентам формулируются задачи,
которые будут рассматриваться на лекции и предлагается обсудить
подходы к решению этих задач. Обсуждение проходит в форме групповой
4
дискуссии и может продолжаться по ходу лекции.
В конце лекции подводится итог. Обсуждаются рассмотренные на
лекции темы и задачи. Дается оценка дискуссии, проходившей в начале
лекции.
5.2. Краткое описание содержания теоретической части разделов и
тем дисциплины
Раздел 1.
Тема 1. Множества.
Понятие «множество» относится к исходным
понятиям
математической теории и не является строго определяемым. Его синонимами
являются «совокупность», «семейство», «класс», «система», «собрание» и др.
Георг Кантор (1845–1918), немецкий математик, создатель теории
множеств, дал такое определение: «под множеством понимают объединение
в одно общее объектов, хорошо различаемых нашей интуицией или нашей
мыслью».
Объекты, составляющие данное множество, называют его
элементами. При этом никаких ограничений на природу элементов
множества не накладывается. Предполагается только, что для любых двух
элементов данного множества имеется возможность выяснить, различны они
или одинаковы.
Тот факт, что элемент x принадлежит множеству А (x является
элементом множества А), записывается так: x  A (x не принадлежит
множеству А x  A ).
Существенным в понятии «множество» является то, что мы
объединяем некоторые предметы в одно целое.
Понятие множества — одно из основных понятий современной
математики. Понятия и теоремы теории множеств обладают большой
общностью, так как элементы множеств могут быть различной природы, а
потому одни и те же утверждения, касающиеся множеств, можно
истолковать как утверждения о точках, натуральных числах, молекулах и т.д.
Множество называется конечным, если оно состоит из конечного
числа элементов, и бесконечным — в противоположном случае.
Возможны различные способы задания множеств.
Множества могут быть заданы следующими способами:
- перечислением (списком своих элементов);
- описанием свойств, которыми должны обладать его элементы;
- порождающей процедурой.
Например:
Множество экзаменационных оценок может быть задано:
- перечислением А={2; 3; 4; 5};
- описанием свойств А={a a- экзаменационная оценка;
- порождающей процедурой А=а а=2+i, i= 0,3 .
5
Множество, не содержащее ни одного элемента называется пустым
и обозначается  .
О п р е д е л е н и е 1 . 1 . Пусть А и В — непустые множества. Если
каждый элемент множества А является вместе с тем и элементом множества
В, то говорят что А - подмножество множества В (или А содержится в В,
или В содержит А, или А включено в В) и обозначают A  B . По
определению пустое множество  есть подмножество любого множества
В**, в том числе и пустого.
О п р е д е л е н и е 1 . 2. Пусть А и В — два множества. Множества А и
В называются равными, если каждый элемент множества А является вместе с
тем и элементом множества В, и обратно, каждый элемент множества В
является и элементом множества А.
Другими словами, множества А и В называются равными, если
выполняются два включения: A  B и B  A .
Если A  B и A  B , то А называют собственным подмножеством
множества В и обозначают A  B . Введенное отношение  называется
отношением строгого включения. Например, N  Z  Q  R  C .
О п р е д е л е н и е 1 . 3 . Пусть А — непустое множество. Совокупность
всех подмножеств множества А обозначим через Б(А) и будем называть
булеаном множества А. Ясно, что   P(A) и A  P(A) .
Например, если А = {а, b}, то Б (A) = {  , {a}, {b}, A}.
Число элементов конечного множества А будем называть его
мощностью и обозначать |А|. Пусть, например, |А| = n, тогда мощность
булеана | Б (A)| =2 n.
Во всех рассуждениях о нескольких множествах будем предполагать,
что они являются подмножествами некоторого фиксированного множества,
которое назовем универсальным, универсумом или пространством и
обозначать U (или E). На практике это множество часто явно не указывают,
предполагая, что в случае необходимости оно может быть восстановлено.
Это делается для того, чтобы избежать известных парадоксов теории
множеств.
О п р е д е л е н и е 2 . 1 . Пересечением множеств А и В называется
множество, обозначаемое A B и состоящее из всех тех и только тех
элементов, которые принадлежат как множеству А, так и множеству В.
A B  x x  A & x  B.
О п р е д е л е н и е 2 . 2 . Объединением множеств А и В называется
множество, обозначаемое A B и состоящее из всех тех и только тех
элементов, которые принадлежат хотя бы одному из множеств А, В.
A B  x x  A x  B.
О п р е д е л е н и е 2 . 3 . Разностью множеств А и В называют
множество, обозначаемое А\В и состоящее из элементов, принадлежащих
множеству А и не принадлежащих множеству В.
6
A\ B  x x  A & x  B.
О п р е д е л е н и е 2 . 4 . Пусть А — подмножество множества Е.
Дополнением множества А в множестве U называют множество,
состоящее из всех тех и только тех элементов из U, которые не принадлежат
А, и обозначают A .
A\ B  x x  E & x  A.
О п р е д е л е н и е 2 . 5 . Симметрической разностью множеств А
и В называют множество, обозначаемое А В и состоящее из элементов,
принадлежащих множеству А или множеству В не принадлежащих
множеству A B .
Это определение символически можно записать так:
А В = x x  A  x  B x  A  B.
Рассмотренные операции над множествами допускают очень наглядное
графическое истолкование с помощью так называемых кругов Эйлера (или
диаграмм Венна).
Рис. 1. Изображение операций с помощью кругов Эйлера
Пусть Б(Е) - совокупность всех подмножеств множества Е. Б(Е) замкнуто
относительно операций объединения, пересечения и дополнения множеств,
т.е. производя эти операции над элементами множества Б(Е), получаем
элементы, принадлежащие Б(Е). Множество Б(Е) с введенными операциями
объединения, пересечения и дополнения называют булевой алгеброй
подмножеств множества Е.
Основные законы, которым подчиняются эти операции:
1) A  A;
2) A  B  B A;

3) A  B  B A;
4)
5)
6)
7)
A  B   С  A  B С ;
A  B   С  A  B С ;
A  B C  A  B   A  C ;

A  B C  A  B   A  C ;
8) A  B  A  B;

9) A  B  A  B;
7
12)
A A  A;

A A  A;
A E  A;
13)
A   A;
10)
11)
14) A  A  E;
15) A  A  .
16)
17)
A  A B   A 

A  A B   A 
О п р е д е л е н и е 4 . 1. Декартовым произведением непустых множеств А
и В называется совокупность всех упорядоченных пар вида (а, b), где a  A ,
b  B , и обозначается A B . Если хотя бы одно из множеств А или В пусто,
то их декартовым произведением будем называть пустое множество  .
Другими словами, A  B  (a, b) a  A, b  B.
Пусть, например, А = {a1, a2}, В = {b1, b2, b3}. Тогда A B = {(a1, b1);
(a1, b2); (a1, b3); (a2, b1); (a2, b2); (a2, b3)}.
Если А = В, то А × В называют декартовым квадратом множества А
2
и обозначают А2. Еще раз отметим, что A  ( x, y) x  A, y  A.
По аналогии с понятием упорядоченной пары вводится понятие
упорядоченного набора из п элементов, который будем обозначать (a1, …,
аn), где ai  Ai , (i = 1, …, n). Элемент аi называется при этом i-й координатой
(компонентой), а п — длиной этого упорядоченного набора. Два
упорядоченных набора одной и той же длины (a1, …, аn) и (b1, …, bn)
считаются равными тогда и только тогда, когда ai = bi для всех i = 1, …, n.
О п р е д е л е н и е 4 . 2. Декартовым произведением непустых
множеств A1, …, An называется совокупность всех n-ок вида (a1, …, аn), где
ai  Ai (i = 1, …, n), и обозначается A1 × … × An. Если хотя бы одно из множеств A1, …, An пустое, то декартовым произведением множеств A1, …, An
будем называть пустое множество. Другими словами,
A1 × … × An = {(a1, …, аn) | ai  Ai , i = 1, …, n}.
Если A1 = … = An = А, то A1 × … × An называют n-й декартовой
степенью множества А и обозначают Аn.
Тема 2. Отношения.
О п р е д е л е н и е 5 . 1 . Бинарным отношением, определенным на
паре множеств А и В, называется любое подмножество их декартова
произведения А × В.
Если R  A  B — бинарное отношение, а упорядоченная пара (а, b),
где a  A , b  B , принадлежит R, то это записывают либо (a, b)  R
(согласно определению), либо R(а, b), либо aRb. Обозначение aRb исходит
из обозначений вида а = b, а < b, A  B и др.
Если R  A  B — бинарное отношение и А = В, то R называют
бинарным отношением, определенным на множестве А (вместо того, чтобы
говорить, что R — бинарное отношение, определенное на паре множеств А,
А).
8
Бинарные отношения иногда удобно изображать графически. Один
способ состоит в том, что элементы х А и у В, связанные отношением
R  A  B , соединяются стрелками.
Пример.
На рис. 7 графически показаны отношение R1 = {(а, 2), (b,1), (с, 2)}
между множествами А = {а, b, с} и В — {1,2,3}, а также отношение R2 = {(а,
b), (b, b), (с, а)} на множестве A.
A
a
1
b
3
b
c
B
P
1
P
2
a
c
Рис.7
О п р е д е л е н и е 6.1. Пусть A1, …, An — непустые множества. Всякое
подмножество R их декартова произведения А1×…×An называется n-арным
отношением, определенным на системе множеств A1, …, An. Т.е. R 
А1×…×An.
Если A1 = … = An = А, то отношение R, определенное на системе
множеств A1, …, An, называют n-арным (n-местным) отношением,
определенным на множестве А (вместо того, чтобы говорить: «n-арное
отношение, определенное на системе множеств A, …, A»).
При n = 2 приходим к известному понятию бинарного отношения. При
n = 3 используют термин тернарное отношение.
Пример. Пусть А – множество дней учебного года, В = {8-00,14-00}, С множество аудиторий ИрГТУ, D - множество учебных групп ИрГТУ, Е множество учебных дисциплин, изучаемых в ИрГТУ, X - множество
преподавателей ИрГТУ. Тогда расписание экзаменов – 6-арное отношение,
определенное на множестве A×B×C×D×E×X.
О п р е д е л е н и е 7 . 3 . Пусть Р - бинарное отношение на множестве
А: Р  А2. Отношение Р называется:
1. peфлексивным, если (x, x) Р для всех x A.
2. симметричным, если для любых x, y А из (x, y) Р следует (y, x) Р,
т. е. Р-1 = Р,
3. антисимметричным, если из (x, y) Р и (y, x) Р следует x = y, т. е. Р
Р-1  idA.
4. транзитивным, если из (x, y) Р и (y, z) Р следует
(x, z) Р , т. е.

Р Р Р.
Так как бинарные отношения, определенные на фиксированной паре
множеств А, В, являются подмножествами А×В, то над ними можно
производить все теоретико-множественные операции.
9
О п р е д е л е н и е 8 .1. Пусть R  A B — бинарное отношение,
определенное на паре множеств А, В. Отношением, обратным к
бинарному отношению R, называется отношение, определенное на паре
множеств В и А и состоящее из всех тех и только тех пар (b, а), для которых
(a, b)  R ( a  A, b  B ).
Бинарное отношение, обратное к отношению R, будем обозначать R–1.
1
Таким образом, R  B  A .
О п р е д е л е н и е 8 . 2 . Пусть P1  A B — бинарное отношение,
определенное на паре множеств А, В, а P2  B C — бинарное отношение,
определенное на паре множеств В, С. Произведением (или композицией)
отношений
и называется бинарное отношение, определенное на паре
множеств А и С и состоящее из всех тех и только тех пар (а, с) a  A , c  C ,
для которых существует элемент х из В такой, что a x и x c.
Произведение бинарных отношений P1  A B и P2  B C обозначим
через Р1°Р2 или Р1Р2.
Рассмотрим два конечных множества А = {a1, а2, ..., am}, В = {b1,
b2,…,bn} и бинарное отношение Р  А×В. Определим матрицу [Р] = (pij)
размера m × n бинарного отношения Р по следующему правилу:
1, если ( ai , b j )  P,
pij  
0, если ( ai , b j )  P.
Полученная матрица содержит полную информацию о связях между
элементами и позволяет представлять эту информацию графически и на
компьютере. Заметим, что любая матрица, состоящая из нулей и единиц,
является матрицей некоторого бинарного отношения.
О п р е д е л е н и е 1 0 .1. Бинарное отношение f определенное на паре
непустых множеств А и В, называется функцией, определенной на
множестве А со значениями в В (или отображением из А в В) , если для
любого элемента х А существует один и только один элемент у В,
удовлетворяющий условию x f y.
О п р е д е л е н и е 1 0 . 4. Пусть F: X → Y — отображение и A  X .
Отображение, которое каждому элементу x  A, рассматриваемому как
элемент из X, ставит в соответствие F x  Y , называется сужением, или
ограничением, F на А и обозначается FA или F/A.
О п р е д е л е н и е 1 1 . 1 . Функция (отображение) F: X→Y называется
инъективным (или инъекцией), если для любых x1 и x2 из Х выполняется
следующее условие: x1  x2  F x1   F x2  .
Другое название инъективного отображения F: X → Y — взаимно
однозначное отображение из Х в Y.
О п р е д е л е н и е 1 1 .2. Функция (отображение) F: X → Y называется
сюръективным (или сюръекцией), если каждый элемент множества Y
является образом хотя бы одного элемента из Х при отображении F: X → Y
10
(или: если каждый элемент множества Y имеет хотя бы один прообраз в
множестве Х при отображении F).
Другое название сюръективного отображения F: X → Y —
отображение множества Х на множество Y.
О п р е д е л е н и е 1 1 . 3 . Отображение F: X → Y называется
биективным (или биекцией), если оно одновременно и инъективно, и
сюръективно.
Другое название биективного отображения F: X → Y — взаимно
однозначное отображение множества Х на множество Y.
О п р е д е л е н и е 14.1. Бинарное отношение α, определенное на
множестве А, называется отношением эквивалентности или просто
эквивалентностью на множестве А, если α рефлексивно, симметрично и
транзитивно.
О п р е д е л е н и е 14.2. Пусть F: A → B — отображение. Отношение σ,
x1σx2  F ( x1 )  F ( x2 ) , является
определяемое следующим образом:
отношением эквивалентности на А. Оно называется ядерной
эквивалентностью отображения F.
Пусть σ — отношение эквивалентности на множестве А, и пусть a  A .
О п р е д е л е н и е 14.3. Множество всех таких элементов x  A , что
хσа истинно, называют смежным классом множества А по
эквивалентности σ, или классом эквивалентности, и обозначают [а]σ.
Другими словами, [а]σ = { x  A | хσа}. Вместо [а]σ часто пишут [а], если
относительно σ нет никаких неясностей.
Теорема 1. Свойство I: a [a] . Свойство II: если aσb, то [а] = [b].
О п р е д е л е н и е 14.3. Совокупность всех различных смежных
классов множества А по эквивалентности σ называется фактормножеством множества А по эквивалентности σ и обозначается А/σ.
О п р е д е л е н и е 14.4. Каноническим отображением множества А
на фактор-множестве А/σ по эквивалентности σ называется отображение,
которое каждому элементу a  A ставит в соответствие содержащий его
смежный класс [a]σ.
О п р е д е л е н и е 15. Разбиением (или расслоением) множества А
называется система S непустых подмножеств множества А таких, что каждый
элемент из А принадлежит одному и только одному подмножеству из
системы S.
Подмножества из S называются смежными классами (или слоями)
разбиения S.
Рассмотрим связи между отношениями эквивалентности некоторого
множества и его разбиениями.
О п р е д е л е н и е 1 5 .1. Бинарное отношение ρ, определенное на
множестве А, называется частичным порядком, или отношением
частичного порядка, если оно удовлетворяет следующим условиям:
1) хρх для любого x  A (рефлексивность);
2) из хρу и yρz следует xρz для любых x, y, z  A (транзитивность);
11
3) из хρу и уρх следует х = у для любых x, y  A (антисимметричность).
Множество А, на котором задан какой-нибудь частичный порядок,
называется частично упорядоченным.
О п р е д е л е н и е 15.2. Элементы а, b множества А называются
сравнимыми относительно частичного порядка ≤ на этом множестве, если a
≤ b или b ≤ a.
О п р е д е л е н и е 18. Пусть А — частично упорядоченное множество
с частичным порядком ≤. Элемент a  A называется наибольшим
элементом, если х ≤ а для любого x  A . Элемент b  A называется
наименьшим элементом, если b ≤ х для любого x  A . Наибольший элемент
часто называют единицей, а наименьший — нулем.
Если частично упорядоченное множество обладает наибольшим
(наименьшим) элементом, то он единственный.
Лемма 1. В любом частично упорядоченном множестве имеется не
более одного наибольшего (наименьшего) элемента.
О п р е д е л е н и е 15.3. Максимальным элементом частично
упорядоченного множества А называется такой элемент a  A , что каждый
элемент х из А либо не сравним с а, либо х ≤ а, т.е., другими словами, если А
не содержит элементов, строго больших а. Минимальным элементом
частично упорядоченного множества А называется такой элемент b  A , что
каждый элемент x из А либо не сравним с b, либо b ≤ х, т.е. если А не содержит элементов, строго меньших b.
В отличие от наибольшего (наименьшего) элемента частично
упорядоченное множество может содержать несколько максимальных
(минимальных) элементов. Так, например, в множестве целых
положительных чисел, отличных от 1, с отношением делимости в качестве
отношения частичного порядка (т.е. m ≤ n тогда и только тогда, когда m
делит п) минимальными элементами являются простые числа.
Лемма 2. Всякий наибольший элемент частично упорядоченного
множества является максимальным, а всякий наименьший — минимальным.
Обратное, вообще говоря, не имеет места. Действительно, предыдущий
пример показывает, что в множестве целых положительных чисел, отличных
от 1, с отношением делимости минимальными элементами являются простые
числа, а наименьшего элемента нет.
Тема 3. Мощность множеств.
1. Конечные и бесконечные множества. Рассматривая различные
множества, мы замечаем, что иногда можно, если не фактически, то хотя бы
примерно, указать число элементов в данном множестве. Посмотрим, как мы
сравниваем между собой два конечных множества. Можно, например,
сосчитать число элементов в каждом из них и, таким образом, эти два
множества сравнить. Но можно поступить и иначе, именно, попытаться
установить биекцию, т. е. взаимно однозначное соответствие между
элементами этих множеств, иначе говоря, такое соответствие, при котором
каждому элементу одного множества отвечает один и только один элемент
другого, и наоборот. Заметим теперь, что если первый способ (подсчет числа
12
элементов) годится лишь для сравнения конечных множеств, второй
(установление взаимно однозначного соответствия) пригоден и для
бесконечных.
2. Счетные множества. Простейшим среди бесконечных множеств
является множество натуральных чисел. Назовем счетным множеством
всякое множество, элементы которого можно биективно сопоставить со
всеми натуральными числами. Иначе говоря, счетное множество — это такое
множество, элементы которого можно занумеровать в бесконечную
последовательность: а1, а2…, аn, … . Приведем примеры счетных множеств.
Бесконечное множество, не являющееся счетным, называется
несчетным множеством.
Установим некоторые общие свойства счетных множеств.
1. Всякое подмножество счетного множества конечно или счетно.
2. Сумма любого конечного или счетного множества счетных
множеств есть снова счетное множество.
3. Всякое бесконечное множество содержит счетное подмножество.
3. Эквивалентность множеств.
О п р е д е л е н и е . Два множества, М и N, называются эквивалентными (обозначение М ~ N), если между их элементами можно
установить взаимно однозначное соответствие.
Всякое бесконечное множество эквивалентно некоторому своему
собственному подмножеству.
Это свойство можно принять за определение бесконечного множества.
4. Несчетность множества действительных чисел.
Т е о р е м а 1 . Множество действительных чисел, заключенных
между нулем и единицей, несчетно.
5. Теорема Кантора—Бернштейна. Следующая теорема является
одной из основных в теории множеств.
Т е о р е м а 2 (Кантор-Бернштейн). Пусть А и В — два произвольных
множества. Если существуют взаимно однозначное отображение f
множества А на подмножество В1 множества В и взаимно однозначное
отображение g множества В на подмножество А1 множества А, то А и В
эквивалентны.
6. Понятие мощности множества. Если эквивалентны два конечных
множества, то они состоят из одного и того же числа элементов. Если же
эквивалентные между собой множества М и N произвольны, то говорят, что
М и N имеют одинаковую мощность. Про множества, эквивалентные множеству всех действительных чисел отрезка [0, 1], говорят, что они имеют
мощность континуума. Эта мощность обозначается символом с (или
символом ).
13
Раздел 2. Комбинаторика.
Тема 1. Комбинаторные конфигурации.
Комбинаторика – раздел математики, посвященный решению задач выбора
и расположения элементов некоторого, обычно конечного, множества в
соответствии с заданными правилами. Каждое такое правило определяет
способ построения некоторой конструкции из элементов исходного
множества, называемой комбинаторной конфигурацией. Поэтому целями
комбинаторного анализа являются изучение комбинаторных конфигураций,
алгоритмов их построения, оптимизация таких алгоритмов, а также решение
задач
перечисления.
Простейшими
примерами
комбинаторных
конфигураций являются перестановки, размещения, сочетания и разбиения.
При подсчете комбинаторных конфигураций используются правила суммы,
произведения и степени.
При подсчете числа объектов с наперед заданными свойствами
используются следующие два правила.
Правило суммы. Если объект U может быть выбран m способами, а объект
V k способами, то выбор «либо U , либо V » может быть осуществлен m  k
способами.
Правило произведения. Если объект U может быть выбран m способами и
после каждого из таких выборов объект V в свою очередь может быть
выбран k способами, то выбор « U и V » в указанном порядке может быть
осуществлен mk способами.
Набор элементов ai , ai ,..., ai из множества A  a1, a2 ,..., an  называется
выборкой объема k из n элементов или (n, k ) -выборкой.
Выборка называется упорядоченной, если порядок следования элементов
в ней задан. Две упорядоченные выборки, различающиеся лишь порядком
следования элементов, считаются различными. Если порядок следования
элементов не является существенным, то выборка называется
неупорядоченной.
В выборках могут допускаться или не допускаться повторения
элементов.
Рассмотрим некоторые комбинаторные объекты и их комбинаторные
числа.
Размещения. Размещением элементов из A по k (или размещением из
n элементов по k) называется упорядоченная (n, k ) -выборка, в которой
элементы попарно различны.
A  a, b, c
Пример 1. Пусть
и k  2 . Выпишем все размещения из этого
множества по два:
a, b , b, a  , a, c  , c, a  , b, c  , c, b .
1
2
k
Обозначим число размещений из n по k через n k . Для подсчета числа
n k используем правило произведения. При построении конкретного
14
размещения первым элементом в нем можно взять любой из n элементов
множества A , вторым элементом – любой из n  1 оставшихся в A элементов
и т.д. Поэтому
nk  nn  1...n  k  1 
n!
(n  k )!
при 1  k  n .
При k  n не существует размещений из n по k , следовательно, nk  0
при k  n ; при k  0 полагаем 00  n0  1 .
Упражнение 1. Показать, что для чисел n k выполняются тождества:
nk  nn  1k 1 ,
nk  nk 1  n  k  1 .
Перестановки. Перестановками элементов множества A (или
перестановками из n элементов) называются упорядоченная (n, n) -выборка, в
которой элементы попарно различны A .
Пример 2. Пусть A  a, b, c . Выпишем все перестановки этого
множества:
a, b, c , b, a, c , a, c, b , c, a, b, b, c, a , c, b, a  .
Очевидно, что перестановки из n элементов – частный случай
размещений из n элементов по k , когда k  n . Поэтому их число равно
nn  nn 1...2 1  n!
Сочетания. Сочетанием элементов из A по k (или сочетанием из n
элементов по k) неупорядоченная (n, k ) -выборка, в которой элементы
попарно различны.
Пример 3. Пусть A  a, b, c и k  2 . Выпишем все сочетания из этого
множества по два:
a, b , a, c  , b, c  .
В сочетании, в отличие от размещения, порядок следования элементов
не учитывается. Поэтому из одного сочетания из n элементов по k получается
n
 
k 
k! размещений. Отсюда для числа
получается формула
сочетаний из n элементов по k
 n  n k
n!
  

k

k
!
k
!
n
 k ! , 0  k  n .
 
Из последней формулы следует
n
n  n 
   1
   

n
k
n

k
 



.
и
 0  n
      1
При k  0 полагают  0   0  . При k  n полагают
при
k  n не
существует сочетаний из
Наряду с обозначением
n
 
k 
n
n
   0
k 
,
поскольку
элементов по k .
k
часто используется обозначение Cn .
15
n
 
k 
Числа
называются также биномиальными коэффициентами,
поскольку они фигурируют в функциональном тождестве, называемом
формулой бинома Ньютона:
 n  n
 n
n
(1  x) n       x  ...    x k  ...    x n
 0 1
k 
n .
(1)
Формулу (1) несложно доказать, используя метод математической
индукции. Советуем провести доказательства в качестве упражнения.
Полагая в (1) x  1 , получим тождество
 n  n
 n
 n
      ...     ...     2n
0
1
k
   
 
 n
;
При
(2)
x  1 получим
 n n
 n
      ...  (1) n    0
 0 1
 n
.
(3)
При четном n из соотношений (2) и (3) следуют тождества
 n  n
n
      ...     2 n 1
 0  2
n
,
 n  n
 n 
      ...  
  2 n 1
1  3
 n  1
.
При нечетном n из соотношений (2) и (3) следуют тождества
 n  n
 n 
      ...  
  2 n 1
0
2
n

1
   


,
Упражнение 2. Показать, что для чисел
 n  n
 n
      ...     2n 1
 1  3
 n
.
n
 
k 
выполняется тождество
 n   n  1  n  1
   
  

 k   k   k  1 .
Из последнего тождества вытекает эффективный способ реккурентного
n
 
k  ,
вычисления биномиальных коэффициентов
который можно представить
в графической форме, известной как треугольник Паскаля.
В этом равнобедренном треугольнике каждое число (кроме единиц на
n
 
k 
боковых сторонах) является суммой двух чисел, стоящих над ним. Число
находится в ( n  1 ) ряду на ( k  1 ) месте.
Упражнение 3. Показать, что последовательность a1, a2 ,...,ak ,...,an , где
n
ak   
k 
обладает свойством:
a0  a1  ...  an / 2  an / 21  ...  an
, если n четно
и
a0  a1  ...  an / 2  an / 21  ...  an
16
, если n нечетно.
Размещения с повторениями. Размещением с повторениями
элементов из A по k (или размещением с повторением из n элементов по k)
упорядоченная (n, k ) -выборка, в которой элементы могут повторяться.
Пример 4. Пусть A  a, b, c и k  2 . Выпишем все размещения с
повторениями из этого множества по два:
a, b , b, a  , a, c  , с, a  , b, c  , c, b , a, a  , b, b, c, c  .
Для подсчета числа размещений с повторениями из n элементов по k
используем правило произведения. При построении конкретного размещения
первым элементом в нем можно взять любой из n элементов множества A ,
вторым элементом – также любой из n элементов множества A т.д. Таким
образом, число размещений из n элементов по k равно
n
 n
 ...
 n  nk

k раз
.
В частности, если в качестве множества A взято множество 0,1 , то
совокупность всех размещений с повторениями из A по k называется
B k  2k
единичным k -мерным кубом и обозначают B k .
.
Пример 5. 3-х мерный куб размера 2 состоит из следующих элементов:
(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).
Сочетания с повторениями. Сочетанием с повторениями элементов
из A по k (или сочетанием с повторением из n элементов по k)
неупорядоченная (n, k ) -выборка, в которой элементы могут повторяться.
Пример 5. Пусть A  a, b, c и k  2 . Выпишем все сочетания с
повторениями из этого множества по два:
a, b , a, c  , b, c  , a, a  , b, b, c, c  .
Можно показать, что число сочетаний с повторениями из n элементов по
k равно
 n  k  1


 k
.
Тема 2. Рекуррентные соотношения. Возвратные последовательности.
Рекуррентным соотношением, рекуррентным уравнением или
рекуррентной формулой называется соотношение вида an+k = F(n,
an,an+1,...,an+k-1), которое позволяет вычислять все члены последовательности
а0,а1,а2, …, если заданы еѐ первые k членов.
П р и м е р 5.6.1. 1. Формула аn+1 = аn + d задает арифметическую
прогрессию.
2. Формула аn+1 = q an определяет геометрическую прогрессию.
3. Формула аn+2 = аn+1 + аn задает последовательность чисел Фибоначчи.
В случае, когда рекуррентное соотношение линейно и однородно, т.е.
выполняется соотношение вида
аn+k + p1an+k-1 + ... + pkan = 0
(5.4)
(p = const), последовательность a0,a1,a2, ... называется возвратной.
17
Многочлен
Ра ( х)  х k  p1 x k 1  ...  pk
(5.5)
называется характеристическим для возвратной последовательности
{аn}. Корни многочлена Ра(х) называются характеристическими.
Множество всех последовательностей, удовлетворяющих данному
рекуррентному соотношению, называется общим решением.
Описание общего решения соотношения (5.4) имеет аналогию с
описанием решения обыкновенного дифференциального уравнения с
постоянными коэффициентами.
Теорема 5.6.1. 1. Пусть  - корень характеристического многочлена
(5.5). Тогда последовательность сn , где с – произвольная константа,
удовлетворяет соотношению (5.4).
2. Если 1 , 2 ,..., k - простые корни характеристического многочлена
(5.5), то общее решение рекуррентного соотношения (5.4) имеет вид
an  c11n  c2 n2  ...  ck nk , где с1,с2,…,сk – произвольные константы.
3. Если i - корень кратности ri ( i = 1,…,s ) характеристического
многочлена (5.5), то общее решение рекуррентного соотношения (5.4) имеет
s
вид an   (ci1  ci 2 n  ...  cir n r 1 )in , где сij – произвольные константы.
i
i 1
i
Зная общее решение рекуррентного уравнения (5.4), по начальным
условиям а0,а1,…,аk можно найти неопределенные постоянные сij и тем
самым получить решение уравнения (5.4) с данными начальными условиями.
П р и м е р 5.6.2. Найти последовательность {аn}, удовлетворяющую
рекуррентному соотношению an2  4an1  3an  0 и начальным условиям
а1=10, а2=16.
Корнями характеристического многочлена Ра(х) = х2 - 4х + 3 являются
числа х1 = 1 и х2 = 3. Следовательно, по теореме 5.6.1. общее решение имеет
вид аn = с1 + с23n. Используя начальные условия, получаем систему
с1 + 3с2 = 10,
с1 + 9с2 = 16,
решая которую, находим с1 = 7 и с2 = 1. Таким образом, аn = 7 + 3n.
Рассмотрим неоднородное линейное рекуррентное уравнение
ank  p1ank 1  ...  pk an  f (n), n  0,1,...
(5.6)
Пусть {bn} – общее решение однородного уравнения (5.4), а {сn} – частное
(конкретное)
решение
неоднородного
уравнения
(5.6).
Тогда
последовательность {bn + сn} образует общее решение уравнения (5.6), и тем
самым справедлива.
Теорема 5.6.2.
Общее решение неоднородного линейного
рекуррентного уравнения представляется в виде суммы общего решения
соответствующего однородного линейного рекуррентного уравнения и
некоторого частного решения неоднородного уравнения.
18
Таким образом, в силу теоремы 5.6.1. задача нахождения общего
решения рекуррентного уравнения (5.6) сводится к нахождению некоторого
частного решения.
В отдельных случаях имеются общие рецепты нахождения частного
решения.
Если f (n)   n (где  не является характеристическим корнем), то,
подставляя an  c n в (5.6), получаем c( k  p1  k 1  ...  pk )   n   n и отсюда
c  Pa (b)  1, т.е. частное решение можно задать формулой a n 
1
  n.
Pa (  )
Пусть f(n) – многочлен степени r от переменной n, и число 1 не
является характеристическим корнем. Тогда Pa (1)  1  p1  ...  pk  0 и частное
r
решение следует искать в виде a n   d i n i . Подставляя многочлены в
i 0
формулу
(5.6),
r
 d (n  k )
i
i 0
i
получаем
r
r
r
i 0
i 0
i 0
 pi  d i (n  k  1) i  ...  pk  d i n i   d i ((n  k ) i  p1 (n  k  1) i  ...  p k n i ) 
r
  d i ( g1 n i  ...)  f (n).
i 0
Сравнивая коэффициенты в левой и правой частях последнего равенства,
получаем соотношения для чисел di, позволяющих эти числа определить
П р и м е р 5.6.3. Найти решение уравнения
an1  2an  n  1
с начальным условием a0  1.
Рассмотрим характеристический многочлен Ра(х) = х + 2. Так как Ра(х)
= 3  0 и правая часть f(n) уравнения (5.6) равна n + 1, то частное решение
будем искать в виде сn  d 0  d1n. Подставляя сn в уравнение (5.7),
получаем
(d 0  d1 (n  1))  2(d 0  d1n)  = (3d 0  d1 )  3d1  n  1  n . Приравнивая
коэффициенты в левой и правой частях последнего равенства, получаем
систему
3d 0  d1  1,

3d1  1,
2
1
9
3
2 1
(5.7) имеет вид cn   n. По теореме 5.6.1. общее решение однородного
9 3
уравнения an1  2an  0 задается формулой bn  c  (2) n , и по теореме 5.6.2.
2 1
получаем общее решение уравнения (5.7): an   n  c  (2) n . Из начального
9 9
2
7
2 1
7
условия a0  1 находим  c  1, т.е. c  . Таким образом, an   n  (2) n .
9
9
9 3
9
откуда находим d 0  , d1  . Таким образом, частное решение уравнения
Тема 3. Производящие функции.
19
Для решения комбинаторных задач в некоторых случаях можно
использовать методы математического анализа. В качестве примера
рассмотрим основную идею метода производящих функций.
a , a , a ,...,a ,...
0 1 2
k
Пусть имеется последовательность чисел
и

(x)
k
последовательность функций
. Этой последовательности сопоставим

 a  ( x)
k k
формальный ряд
(для конечных последовательностей этот ряд
превращается в многочлен). В ряде случаев, например, при определенных
ограничениях, данный ряд может оказаться сходящимся и задавать
k 0

F ( x) 
некоторую
функцию
производящей
F (x)
 a  ( x)
k k
k 0
:
.
Эта
для
функция
a 
называется
k
последовательности
относительно
 (x) .
последовательности функций k
 (x) обычно используют x k и x k / k! .
В качестве k
В качестве примера применения производящих функций установим с их
использованием следующее комбинаторное тождество:
n
 2n 
 n
  
 
 n  k 0  k 

2
.
Прежде всего, заметим, что из формулы бинома Ньютона
n
(1  x) 
n
 n
 k  x
k
k 0
n
следует, что функция (1  x) является производящей для биномиальных
n
2n
n
коэффициентов. Возьмем тождество (1  x)  (1  x) 1  x  и разложим
n
2n
функции (1  x) и (1  x) в левой и правых частях этого тождества по формуле
бинома Ньютона:
n
n
 2n  i 
 n  k 
 n  k 
  x 
  x
  x


i 
k  
k


i 0
 k 0
 k  0    .
2n


Сравнивая коэффициенты при
тождества, получаем
xn
n

в левой и правой частях последнего
n
 2n 
 n  n 
 n
  
 
 
 
 n  k  0  k  n  k  k  0  k 


2
.
Раздел 4. Графы.
Тема 1. Основные определения.
Теория графов,
как раздел дискретной математики, имеет
многочисленные предметные интерпретации. Теория графов применяется
при анализе функционирования сложных систем, таких как сети железных
20
дорог, телефонные или компьютерные сети, ирригационные системы. Эта
теория традиционно является эффективным аппаратом формализации задач
экономической и планово-производственной практики, применяется в
автоматизации управления производством, в календарном и сетевом
планировании.
Среди дисциплин и методов дискретной математики теория графов и,
особенно алгоритмы на графах, находят наиболее широкое применение в
программировании.
Графом G = (U, V) называется совокупность двух множеств — непустого
множества U и множества V  U 2- бинарного отношения, определѐнного на
множестве U.
Элементы множества U ~ называются вершинами графа G, а
элементы бинарного отношения V — дугами. Таким образом, дугами
являются пары вершин (a,b)
R. При этом дуга (а,b) называется
исходящей из вершины а и заходящей в вершину b.
Число вершин графа G обозначим n, а число дуг - m:
Виды графов.
1. Граф, состоящий из одной вершины, называется тривиальным.
2. Если элементами множества V являются упорядоченные пары, т.е если
для всех пар (a,b)
V пары (b,a)  V, то граф называется
ориентированным (или орграфом). В этом случае элементы множества U
называются узлами, а элементы множества V- дугами.
3. Если же отношение V симметрично, т.е. из (а,b) V следует (b,a)
V, то граф G называется неориентированным (неорграфом). Если
одновременно пары (а,b) и (b,a) принадлежат V, то информацию об
этих дугах можно представить множеством [a,b] = {(а,b),(b,a) },
называемым ребром, которое соединяет вершины а и b. При этом
вершины а и b называваются концами ребра [a,b] Ребра
изображаются линиями (без стрелок), соединяющими вершины.
4. Если в графе имеются как ориентированные так и неориентированные
ребра, то граф называется смешанным.
5. Если элементом множества V может быть пара одинаковых (не
различных) элементов U, то такой элемент множества V называется
петлей, а граф называется графом с петлями (или псевдографом).
6. Если V является мультимножеством (т.е. множеством, содержащим
несколько одинаковых элементов), то эти элементы называются кратными
ребрами, а граф называется мулътиграфом.
7. Если
элементами
множества
Е
являются
не
обязательно
двухэлементные, а любые подмножества множества V, то такие
элементы множества Е называются гипердугами, а граф называется
гиперграфом.
21
8. Если задана функция F: V→М и/или F: Е→М, то множество М
называется множеством пометок, а граф называется помеченным (или
нагруженным). В качестве множества пометок обычно используются
буквы или целые числа.
9. Если множество U разбито на два непересекающихся подмножества U1 и U2,
причем каждое ребро из V инцидентно вершине из U1 и вершине из U2 ( т.е.
соединяет вершину из U1 с вершиной из U2 ) то граф называется двудольным.
Подмножества U1 и U2 называются долями двудольного графа.
10. Граф, в котором каждая пара вершин смежна, называется полным и обозначается
Кn. Он имеет максимально возможное число ребер:
m=
.
Способы задания графа.
1. описание множеств U и V (такое описание графа будем называть
аналитическим),
2. изображение графа с помощью диаграммы.
3.Пусть G= (М, R) - граф, в котором множество вершин имеет n элементов: М
= {a1, a2, ... ,an}. Матрицей смежности A= (Aij) графа G называется матрица
порядка n, определенная следующим образом:
1, если (аi , a j )  R
Aij  
0, если (аi , a j )  R
если G — неорграф, то матрица смежности А симметрична, т. е. не меняется
при транспонировании: АT = А.
Если Aij = 1, то вершина aj называется последователем вершины ai, a aiпредшественником aj. Вершины ai и aj называются смежными, если Aij = 1
или А ji=1.
Если G — мулътиграф, то в матрице смежности a элемент Aij по
определению равен числу дуг, исходящих из вершины ai и заходящих в
вершину aj .
4.Если число вершин графа G равно n, а число ребер – m, то матрицей
инцидентности В= (Bij) мультиграфа G называется матрица размера m x n:
{
если
если в
й вершине
я дуга образует петлю
.
5.Информацию о весах дуг во взвешенном графе можно представлять в виде
матрицы весов W = (wij), где wij — вес дуги (ai,aj), если дуга (ai,aj)
существует, а для несуществующих дуг веса обычно помечают нулем или
знаком ∞, в зависимости от приложений.
6.Если граф G = (М, R) является разреженным, т. е. число дуг |R|
достаточно мало по сравнению с числом вершин |М|, то более
22
эффективным, чем с помощью матрицы смежности, является
представление дуг графа посредством списка дуг. Этот список задается
двумя наборами т = (m1,m2,... ,m) и п = (n1, n2,…,n|), где (am.,an.) — i- я дуга
графа G.
7.Другим представлением графа, удобным при работе с графами, в
которых удаляются или добавляются вершины, является структура
смежности, получаемая составлением для каждой вершины а списка
номеров ее последователей, т. е. номеров вершин b, для которых имеется
дуга (а,.b).
Операции над графами.
Операцией добавления к графу G = (М,R) вершины a образуется граф (M
{a},R}.
Операция добавления дуги (а,b) к графу G состоит в образовании графа (M
{a, b}, R {(а, b)}).
Под операцией удаления дуги (а, b) из графа G понимается операция,
заключающаяся в удалении пары (а, b) из множества дуг R, в результате
получается граф (M,R\{( а, b)}}.
Операция удаления вершины а из графа G заключается в удалении вершины
а вместе с инцидентными ей дугами.
Изоморфизм графов.
Говорят,
что два графа
G1(V1,E1)
и
G2(V2,E2)
изоморфны
(обозначается G1 ~ G2), если существует биекция h: V1 → V2, сохраняющая
смежность:
e1 = (u,v) ∊ Е1<=>e2 = (h(u),h(v)) ∊ E2,
Изоморфизм графов есть отношение эквивалентности. Действительно,
изоморфизм обладает всеми необходимыми свойствами:
рефлексивность: G ~ G, где требуемая биекция суть тождественная функция;
симметричность: если G1 ~ G2 с биекцией h, то G2 ~ G1 с биекцией h-1;
транзитивность: если g1 ~ G2 с биекцией h и G2 ~ G3 с биекцией g, то
g1 ~ G3 с биекцией g∙h.
Графы рассматриваются с точностью до изоморфизма, то есть
рассматриваются классы эквивалентности по отношению изоморфизма .
Валентность.
Количество ребер, инцидентных вершине v, называется степенью (или
валентностью) вершины v и обозначается d(v):
 ∊ V
0≤d()≤p - l,
d() = Г+().
Обозначим минимальную степень вершины графа G через δ(G), а
максимальную — через ∆(G)
Тема 2. Связность.
Маршруты, цепи, циклы.
Маршрутом в графе называется чередующаяся последовательность вершин
и ребер v0,e1,v1,e2,v2,...,ek,vk, в которой любые два соседних элемента
инцидентны.
Это определение подходит также для псевдо-, мульти- и орграфов. Для
23
«обычного» графа достаточно указать только последовательность вершин
или только последовательность ребер.
Если 0 = k, то маршрут замкнут, иначе открыт.
Если все ребра различны, то маршрут называется цепью. Если все вершины
различны, то маршрут называется простой цепью.
Цепь, соединяющая вершины u и v, обозначается
(u, v). Очевидно, что если есть цепь, соединяющая вершины и и v, то есть и
простая цепь, соединяющая эти вершины.
Замкнутая цепь называется циклом; замкнутая простая цепь называется
простым циклом. Число циклов в графе G обозначается z(G). Граф без
циклов называется ациклическим.
Для орграфов цепь называется путем, а цикл — контуром.
Связность.
Важным понятием теории графов является связность. Граф называется
сязным, если любые две его несовпадающие вершины соединены
маршрутом. Для орграфа существует еще понятие сильной связности, Для
этого определим понятие пути, Путь- это ориентированный маршрут,
Поэтому если для установления простой (или слабой) связности графа
ориентацию его дуг принимать в расчет не следует, то для установления
сильной связности это необходимо. Орграф называется сильно связным, если
для любых двух вершин xi, xj найдется путь с началом в xi и концом в xj . Для
неориентированного графа понятие пути и маршрута совпадают.
Метрические характеристики графа.
Рассмотрим связный граф G = (S,U), пусть xi и хj — две его вершины. Длина
кратчайшего маршрута называется расстоянием между вершинами
обозначается через d(xi, xj). Очевидно, что расстояние между вершинами
является простой цепью и d(xi, xj)=0. Для любой вершины х величина
e(x)=max d(xi, xj) называется эксцентриситетом вершины х. Максимальный
из всех эксцентриситетов вершин называется диаметром графа и
обозначается d(G). Минимальный из эксцентриситетов вершин графа
называется его радиусом и обозначается через r(G). Вершина к называется
периферийной, если ее эксцентриситет равен диаметру графа, т. е. е(х)= d(G).
Простая цепь, расстояние между концами которой равно d(G), называется
диаметральной цепью.
Теорема.Для любого связного графа G справедливо неравенство d(G) rankG.
Эйлеровы и Гамильтоновы графы.
Эйлеровой цепью называется цепь, проходящая по всем ребрам графа.
Эйлеровым циклом называется эйлеровая цепь, начинающаяся и
заканчивающаяся в одной вершине.
Эйлеровым графом называется граф, содержащий Эйлеров цикл.
Теорема: Для того чтобы связанный граф был Эйлеровым, необходимо и
достаточно, чтобы степени всех вершин были четны
Данная теорема позволяет решить задачу о Кенигсбергских мостах.
24
Следствие: Для того чтобы граф содержал Эйлеровую цепь, необходимо и
достаточно, чтобы две вершины имели нечетную степень. При этом в одной
из вершин цепь будет начинаться, в другой – заканчиваться.
Граф называется гамильтоновым, если в нем имеется простой цикл,
содержащий каждую вершину этого графа.
Сам такой цикл также называется гамильтоновым.
Гамильтоновой называется и простая цепь, содержащая все вершины графа.
Очевидно, что любой граф, ребра которого образуют простой цикл, является
гамильтоновым.
Несмотря на схожесть задач о нахождении эйлеровых и гамильтоновых
циклов, решение последней значительно сложнее.
Известны следующие достаточные условия существования гамильтоновых
циклов в связном неорграфе G без петель, имеющем больше 3 вершин:
Теорема. Если для любых двух различных несмежных вершин а, и b графа G
выполняется условие d(а) a + d(b) b >n, то существует гамильmонов цикл.
Следствие. Если для любой вершины а графа G выполнено условие d(а) >n /2;
то существует гамильтонов цикл.
С задачей нахождения гамильтонова цикла связана задача коммивояжера.
Математическая постановка задачи выглядит так: требуется найти
гамильтонов цикл минимального веса
Тема 3. Деревья.
Лес. Деревья.
Граф без циклов называется ациклическим, или лесом. Связный
циклический граф называется (свободным) деревом.
Таким образом, компонентами связности леса являются деревья.
В связном графе G выполняется неравенство q(G)  p(G) — 1.
Граф G, в котором q(G)=p(G)-1, называется древовидным.
В ациклическом графе G z(G) = 0.
Пусть u, v — несмежные вершины графа G,
х = (u, v)  Е.
Если граф G + х имеет только один простой цикл,
z(G + х) = 1, то граф G называется субциклическим.
Теорема. Для неoрграфа G без петель содержащего n вершин следующие
условия эквивалентны:
G — дерево;
G — связный .граф, содержащий n - 1 ребро;
3)G — ациклический граф, содержащий n - 1 ребро;
4)любые две несовпадающие вершины графа G соединяет единственная
простая цепь;
5)G — ациклический граф, такой, что если какую-либо пару егo несмежных
вершин соединить ребром, то полученный граф будет содержать ровно
один цикл
Обходы графа по глубине и ширине.
25
При решении прикладных задач часто возникает необходимость обхода
вершин графа,
связанная с поиском вершин, удовлетворяющих
определенным свойствам.
Пусть G = (М, R) — связный неориентированный граф,
Т — некоторый остов графа G,
a — некоторая фиксированная вершина, называемая корнем дерева Т.
Разместим вершины из М по этажам таким образом, чтобы корень а
находился в верхнем этаже, смежные с ним вершины занимали этаж на
единицу ниже, смежные с отмеченными вершинами — еще на единицу ниже
и т. д. . Таким образом, получаем е(а) + 1 этажей, где е(а) — эксцентриситет
вершины а.
При таком обходе после очередной рассмотренной вершины выбирается
смежная с ней вершина следующего этажа;
Если очередная, рассмотренная вершина висячая и ее достижение не дает
желаемого решения задачи, то возвращаемся до ближайшей вершины
степени > 3 и просматриваем вершины другого, еще, не пройденного
маршрута в таком же порядке и т. д
Очевидно, что при обходе всех вершин оба подхода: поиск в глубину и поиск
по ширине — эквивалентны.
Если же достаточно найти одну вершину с определенным свойством, то
целесообразность применения поиска решения по глубине или по ширине
определяется структурой дерева.
Если дерево является достаточно широким, а висячие вершины расположены
на сравнительно близких этажах, то целесообразно вести поиск по глубине.
Для глубоких узких деревьев, когда висячие вершины могут встретиться на
различных этажах и их разброс по этажам достаточно велик, предпочтение
отдается поиску по ширине.
Отметим, что при компьютерной реализации обходов по глубине и ширине
целесообразно использовать задание дерева структурой смежности вершин.
Фундаментальные циклы. Разрезы.
Пусть G = (M,R) — неорграф, имеющий n вершин, m ребер и с компонент
связности, Т — остов графа G.
Ранее отмечалось, что Т имеет v*(G) = n - с ребер u1,…,un-c , которые будем
называть ветвями остова Т.
Оставшиеся m - n + с ребер v1,v2,…,vm-n+c, не входящие в Т, будем называть
хордами остова Т.
если к лесу Т добавить произвольную хорду vi, то в полученном графе
найдется ровно один цикл, который обозначим через Ci.
Цикл Ci состоит из хорды vi и некоторых ветвей остова Т, которые
принадлежат единственной простой цепи, соединяющей вершины хорды vi.
Цикл Ci называется фундаментальным циклом графа G относительно хорды
vi остова Т.
Множество {C1,…,Cm-n+c } всех фундаментальных циклов относительно хорд
остова Т называется фундаментальным множеством циклов графа G
относительно остова Г.
26
Отметим, что мощность фундаментального множества циклов равна
цикломатическому числу v(G) = m - n + с.
Обозначим через (w1,…,wm) последовательность (v1,…,vm-n+c,u1,…,un-c) всех
ребер графа G. Тогда фундаментальному циклу Ci соответствует вектор а =
(ai1,…,aim ) определенный по следующему правилу:
Теперь фундаментальное множество циклов можно задать с помощью
матрицы фундаментальных циклов, строки которой являются векторами
a1,…,av(G):
Так как каждый фундаментальный цикл Ci содержит ровно одну хорду, а
именно vi, то матрица С имеет вид
Понятие разреза играет важную роль при изучении вопросов, связанных с
отделением одного множества вершин графа от другого. Такие задачи
возникают, например, при изучении потоков в сетях
Сетью называется связный орграф G = (M,R) без петель; потоком в сети G
называется функция : R —> Z, которая ставит в соответствие дуге некоторое
число — вес дуги
В этих задачах фундаментальную роль играет изучение поперечных сечений
сети
(т.е, множеств дуг, которые соединяют вершины двух непересекающихся
множеств вершин)
и нахождение ограниченного поперечного сечения, которое является самым
узким местом.
Эти узкие места определяют пропускную способность системы в целом.
Пусть G = (М,R). - неорграф, M = {М1,М2} - разбиение множества М.
Разрезом графа G (по разбиению M ) называется множество всех ребер,
соединяющих вершины из M1 с вершинами из M2 .
Отметим, что в связном графе любой разрез непуст
Непустой разрез К неорграфа G называется простым разрезом или коциклом,
если любое непустое собственное подмножество К' множества К не
является разрезом ни по какому разбиению.
Другими словами, из К нельзя удалить ни одно ребро с тем, чтобы
полученное множество было непустым разрезом.
27
Теорема. В конечном неорграфе G = (М,R), имеющем с компонент,
связности, множество ребер К тогда и только тогда является коциклом,
когда граф (M,R\K) имеет (с + 1) компонент связности.
Понятия остова и коцикла являются противоположными в том смысле, что
остову соответствует минимальное множество ребер, которые связывают
посредством маршрутов все вершины связного графа, а коцикл состоит из
минимального множества ребер, отделяющих некоторые вершины связного
графа от остальных
Тема 4. Планарность графов.
Ранее уже отмечалось, что возможно несколько изображений одного графа,
поскольку все изоморфные графы несут одну и ту же информацию.
На практике при изготовлении микросхем необходимо выяснить, можно ли
схему радиоэлектронного устройства, которая представляет собой граф,
изобразить на плоскости без пересечений проводников.
Аналогичная задача возникает при проектировании железнодорожных и
других путей, где нежелательны переезды.
Таким образом, возникает задача построения и исследования плоского графа.
Плоским называется граф, вершины которого являются точками
плоскости, а ребра— непрерывными плоскими линиями без самопересечений,
причем никакие два ребра не имеют общих точек, кроме инцидентной им
обоим вершины.
Любой граф, изоморфный плоскому графу, называется планарным.
Все планарные графы укладываются на плоскости (имеют плоскую укладку).
Очевидно, что
 всякий подграф планарного графа планарен,
 граф планарен тогда и только тогда, когда каждая связная
компонента этого графа — планарный граф.
Гранью планарного графа называется множество точек плоскости, каждая
пара которых может быть соединена плоской кривой, не пересекающей ребер
этого графа.
Границей грани называется множество вершин и ребер, принадлежащих этой
грани.
Например, граф G на рис. имеет восемь граней: Г1,Г2,...,Г8. Неограниченная
грань Г называется внешней, а остальные грани Г2,Г3,...,Г8 —внутренними.
Пусть n,m,f — соответственно число вершин, ребер и граней планарного
графа.
Теорема (теорема Эйлера). Для всякого связного планарного графа верно
равенство n-m +f = 2.
Два графа называются гомеоморфными, если они оба могут быть получены
из одного и того же графа подразбиением его ребер. На рис. Изображены
исходный граф G и два гомеоморфных графа G1 и G2.
28
Рис. Гомеоморфизм графов.
Теорема. (теорема Понтрягина —Куратовского). Граф планарен тогда и
только тогда, когда он не содержит подграфов, гомеоморфных К5или К3 3.
Эквивалентная форма критерия планарности описана в следующей теореме.
Теорема. Граф планарен тогда и только тогда, когда в нем нет подграфов,
стягиваемых (т. е. получаемых последовательностью отождествлений
вершин, связанных ребрами) к графам К5 или К3 3.
Для непланарных графов вводятся характеристики, представляющие ту или
иную меру непланарности.
Если граф непланарен, то для его геометрической реализации удаляют
отдельные ребра (переносят их на другую плоскость).
Наименьшее число ребер, удаление которых приводит к планарному графу,
называется числом планарности или искаженностъю sk(G) графа G.
Для числа планарности полного графа справедлива следующая формула:
Важнейшая характеристика непланарного графа— его толщина t(G) —
наименьшее число планарных подграфов графа G, объединение которых дает
сам граф.
Толщина графа равна минимальному числу плоскостей t, при котором граф G
разбивается на плоские части Gl,G2,...,Gl.
Очевидно, что толщина планарного графа равна единице.
для толщины связного (n,т) графа справедливы такие оценки
где [...] — Целая часть числа, а ]..[= [...]+1.
Тема 5. Раскраска графов.
Задачи раскраски вершин и ребер графа занимают важное место в истории
развития теории и в самой теории графов. К построению раскрасок сводится
целый ряд практических задач, например, задачи составления расписаний,
распределения оборудования, проектирования некоторых технических
изделий.
Задача раскрашивания графов, имеет также неожиданно широкое
применение в программировании, особенно при решении фундаментальных
теоретических проблем
Пусть G = (S,U) — неориентированный граф.
Раскраской графа называется такое приписывание цветов его вершинам,
что никакие две смежные вершины не получают одинакового цвета.
Таким образом, множество вершин одного цвета является независимым
множеством.
Хроматическим числом
графа G называется минимальное число цветов,
требующееся для раскраски G . Если = k , то граф называется k хроматическим.
29
В теории хроматических графов существует так называемая гипотеза
четырех красок, которую некоторые авторы с полным основанием называют
«болезнью четырех красок».
Попытки обосновать эту гипотезу привели к ряду интересных результатов не
только
по раскраске графов, но и по ряду других разделов теории графов.

Легко найти хроматические числа некоторых известных графов, например,
Обозначим через P(G) наибольшую из степеней вершин графа G
Теорема Для любого неориентированного графа G выполняется неравенство
 (G) P(G) +1.
Следующая теорема связывает хроматическое число графа с количеством его
вершин и ребер.
Теорема Для любого связного (n,т)- графа G верны неравенства
где [...] — целая часть, а {..} — дробная часть числа.
Теорема. Для любого n -вершинного графа G верно неравенство
Проблема раскраски планарных графов является одной из самых знаменитых
проблем теории графов. Она возникла из задачи раскраски географической
карты, при которой любые две соседние страны должны быть окрашены в
различные цвета. Эта задача легко сводится к задаче раскраски планарного
графа.
В 1879 г. английский математик Кэли четко сформулировал гипотезу
четырех красок, которую некоторые авторы с полным основанием называют
«болезнью четырех красок».
Попытки обосновать эту гипотезу привели к ряду интересных результатов не
только по раскраске графов, но и по ряду других разделов теории графов.
Гипотеза четырех красок. Всякий планарный граф 4-раскрашиваем.
Попытки доказать эту гипотезу привели в 1890г. к появлению теоремы
Хивуда.
Теорема. Всякий планарный граф 5-раскрашиваем
Трудность проблемы четырех красок привела к появлению большого числа
равносильных ей формулировок.
В конце 60-х гг. прошлого века эта проблема была сведена к исследованию
большого, но конечного множества так называемых неустранимых
конфигураций, число которых оказалось равно 1482
В 1976 г. научному коллективу под руководством К. Аппеля и В. Хейкена
удалось с использованием ЭВМ правильно раскрасить все графы из
30
множества неустранимых конфигураций, затратив на это около 2000 часов
машинного времени.
Таким образом, хотя такое доказательство очень сложно повторить, можно
считать, что формально гипотеза четырех красок доказана.
В заключение рассмотрим очень простой алгоритм последовательной
раскраски графа.
Этот алгоритм в общем случае не приводит к минимальной раскраске.
Только для некоторых классов графов, например полных k -дольных,
последовательная раскраска минимальна.
Алгоритм последовательной раскраски содержит два правила:
1) Произвольной вершине х графа G присваивается цвет 1.
2) Если вершины x1,x2,…,xi раскрашены k цветами 1,2,…,k , k<i, то новой
произвольно взятой вершине хi+1 приписывается минимальный цвет, не
использованный при раскраске вершин из ее окружения.
Теорема (теорема Кенига). Граф двуцветен тогда и только тогда, когда он
не содержит нечетных простых циклов.
Заключение.
5.3. Краткое описание лабораторных работ
Учебным планом не предусмотрены
5.4. Краткое описание практических занятий
5.4.1.Перечень практических занятий
Все занятия способствуют достижению освоения ОК-12.
Все практические занятия проводятся с элементами интерактивных
занятий, которые можно разделить на два типа.
1.Занятие, как правило, начинается с устного теоретического опроса, в
котором принимают участие все студенты. Далее следует групповое
решение задач (групповая дискуссия): один студент решает у доски,
остальные контролируют и обсуждают.
В конце занятия подводится итог. Обсуждаются рассмотренные на
занятии задачи. Выставляются оценки (совместно со студентами).
2.Группа разбивается на подгруппы(2-3). Каждой группе выдаются задания.
Для выполнения заданий выделяется время (45-60мин.). Далее проверяется
выполнение заданий у нескольких человек из группы (как правило «слабых»
студентов) с подробными объяснениями. За положительный ответ
выставляются баллы. В подгруппе, получившей определенное количество
баллов, все студенты получают зачет по этой теме
Занятие 1. Основные понятия. Операции над множествами. Булева алгебра
подмножеств. ( Раздел 1. Тема 1.) (интерактив. 1)
Занятие 2. Бинарные отношения. ( Раздел 1. Тема 2.) (интерактив. 1)
Занятие 3. Функции. ( Раздел 1. Тема 2.) (интерактив. 1)
Занятие 4. Отношения эквивалентности и порядка. ( Раздел 1. Тема 2.)
(интерактив. 1)
31
Занятие 5. Мощность множества. ( Раздел 1. Тема 3.) (интерактив. 1)
Занятие 6. Контрольная работа
Занятие 7. Правила суммы и произведения. Перестановки, размещения и
сочетания. ( Раздел 2. Тема 1.) (интерактив.2)
Занятие 8. Разбиения ( Раздел 2. Тема 1.) (интерактив.2)
Занятие 9. Бином Ньютона. Полиномиальная формула. Метод включений
и исключений. ( Раздел 3. Тема1 ,2,3.) (интерактив. 1)
Занятие 10. Производящие функции и рекуррентные соотношения. ( Раздел
3. Тема1 ,2,3.) (интерактив. 1)
Занятие 11. Контрольная работа
Занятие 12. Графы. Виды графов. Способы задания. (Раздел 3. Тема 1.)
(интерактив. 1)
Занятие 13. Операции над графами(Раздел 3. Тема 1.) (интерактив. 1)
Занятие14. Метрические характеристики графов. Упорядочивание
элементов орграфов. ( Раздел 3. Тема 2.) (интерактив.2)
Занятие 15. Эйлеровы и Гамильтоновы графы. ( Раздел 4. Тема 2,.)
(интерактив. 1)
Занятие 16. Планарные графы. ( Раздел 3. Тема 4.) (интерактив. 2)
Занятие17. хроматические графы ( Раздел 3. Тема 5.) (интерактив.2)
Занятие 18. Контрольная работа
5.4.2Методические указания по выполнению заданий на практических занятиях
Цель занятия: Усвоение математической символики, диаграмм Венна,
использование
операций над множествами. Доказательство известных
тождеств алгебры множеств.
Задания на занятия:
1. Описать методом перечисления элементов - множества букв фамилии
и имени студента; получить результаты применения операций над этими
множествами.
2. Используя предикатный метод описать множества: четных, нечетных
чисел, чисел, имеющих одинаковые остатки при делении на заданную
величину.
3. Используя диаграммы Венна, решить задачу:
опрос 100 студентов выявил следующие данные о числе студентов,
изучающих различные иностранные языки: только немецкий — 18;
немецкий, но не испанский — 23; немецкий и французский — 8; немецкий —
26; французский — 48; французский и испанский — 8; никакого языка — 24.
а) Сколько студентов изучают испанский язык?
б) Сколько студентов изучают немецкий и испанский языки?
в) Сколько студентов изучают французский язык, в том и только в том
случае, если они не изучают испанский?
г) Сколько студентов не изучают ни одного языка?
4. Доказать основные тождества алгебры множеств, используя
диаграммы Венна.
32
5. Упростить предложенные выражения над множествами.
6. Описать для предложенных множеств покрытия и разбиения.
7. Выписать множество всех подмножеств предложенного множества.
8. Считая универсальным множество всех четырехугольников на
плоскости, рассмотреть результаты операций над подмножествами этого
множества (параллелограммы, прямоугольники, квадраты, ромбы).
9. Проверить выполнение основных алгебраических тождеств для
прямого (декартова) произведения множеств.
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Следует уделить внимание
использованию нотации теории множеств, четкому и однозначному
использованию знаков и формул. При решении задач указать на
использование разных подходов для получения решения.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 2. Бинарные отношения.
Цель занятия: Использование понятия отношения и его свойств для
анализа моделей и процессов различных объектов.
Задания на занятия:
1. Отношение R на множестве всех книг библиотеки определили
следующим образом. Пара книг а и b принадлежат R, если и только если в
этих книгах есть ссылка на одни и те же литературные источники. Является
ли R
а)
рефлексивным отношением;
б)
симметричным отношением;
в)
транзитивным отношением?
2. Саша дружит с Олей, Коля и Юра дружат с Машей. Саша учится с
Олей в одной группе, а Коля учится в одной группе с Викой. Вика учится
вместе с Юрой и дружит с ним. Ввести бинарное отношение U "учиться
вместе", а также L "быть другом". Построить матрицы смежности для U и L.
Определить свойства этих бинарных отношений, отобразить их в форме
графа.
3. А={a,b,c}, B={1,2,3,4}, P AxB, Q  B2. Изобразить Р и Q
графически. Записать матрицы этих отношений. Найти ( Ро Q.) -1. Проверьте
с помощью матрицы является ли отношение Q рефлексивным,
симметричным, антисимметричным, транзитивным.
Вар
Р
иан
т
1. {(a,1),(a,2),(b,3),(c,2),(c,3),(c,4)}
2. {(a,1),(a,2),(a,4),(c,3),(c,2),(c,4)}
33
Q
{(1,1),(2,1),(2,2),(2,3),(2,4),(3,3),(4,4)}
{(2,1),(3,1),(3,2),(4,1),(4,3)}
3.
4.
5.
6.
7.
8.
{(a,1),(a,2),(a,3),(a,4),(b,3),(c,2)}
{(a,1),(a,2),(b,4),(c,3),(c,2)}
{(a,1),(a,2),(b,2),(b,4),(c,3),(c,2)}
{(a,1),(a,2),(a,4),(b,1),(b,4),(c,3)}
{(a,1),(b,3),(b,1),(b,4),(c,3),(c,2)}
{(a,1),(b,3),(c,1),(c,4),(c,3),(c,2)}
9. {(a,1),(a,2),(a,4),(b,3),(c,1),(c,4)}
10.{(a,3),(a,2),(b,2),(b,3),(c,1),(c,4)}
{(1,1),(1,4),(2,2),(3,3),(4,1),(4,4)}
{(1,1),(1,2),(2,2),(3,3),(4,3),(4,4)}
{(1,1),(1,2),(2,2),(3,3),(4,3),(4,4)}
{(1,1),(2,4),(2,1),(3,3),(4,2),(4,1)}
{(1,3),(1,4),(2,2),(3,3),(4,3),(4,4)}
{(1,1),(1,2),(1,4),(2,1),(2,2),(2,3),(3,3),
( 3,2),(3,4),(4,3),(4,4)}
{(1,3),(1,2),(2,3),(3,2),(3,4),(4.1)}
{(1,1),(1,2),(2,2),(3,3),(4,1),(4,4)}
4. Найти область определения и область значений для отношения Р.
Проверить, является ли отношение Р рефлексивным, симметричным,
антисимметричным, транзитивным:
№
Отношения
1
P = {(x,y)| x,y  N и x делит y}
2
P = {(x,y)| x,y  N и y делит x}
3
P = {(x,y)| x,y  R и x + y  0}
4
P = {(x,y)| x,y  R и x = y2}
5
P = {(x,y)| x,y  R и x2 = y}
6
P = {(x,y)| x,y  R и x2+y 2=1}
7
P = {(x,y)| x,y  Z и x-y кратно 2}
8
P = {(x,y)| x,y  Z и 2x=3y }
9
P = {(x,y)| x,y  Z и x+y нечетно}
10
P = {(x,y)| x,y  Z и x-y четно}
5. Пусть однородное отношение α A×A, где A={1, 2, … , 10 }, задано
условием α={(m,n)/ (m,n)  A×A & m-n без остатка делится на 4 }.
Построить фактор-множество множества A.
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: При выполнении заданий
следует использовать вариантность однотипных заданий и пояснить
методику решения на 2-3 решенных разными студентами заданиях.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 3. Функции.
Цель занятия: Освоение понятий функция,
инъективность,
сюръективность, биективность. Выработка навыков решения задач по теме.
Задания на занятия:
1. Дайте определение функции (отображения).
34
2. Какие функции называются инъективными, сюръективными,
биективными?
3. Являются ли функциями следующие отношения?
Р={(1,2),(2,3),(3,2)};
Q={(1,2),(1,3),(2,3)};
S={(x, x2+2x-3/ x  R }.
4. Проверить, являются ли следующие отображения а) инъекцией; б)
сюръекцией; с) биекцией.
F: R  R, F(x) = ex + 1;
F: R  R, F(x) = xsinx;
F: N  N, F(x) = 2x + 1/
5. Пусть X = {x1, … , xn}, Y = {y1, … , ym} – конечные множества. Показать,
что число всех отображений множества X в Y равно mn.
6. Чему равно число всех s-местных функций типа Xs  Y, где X = {x1, … ,
xn}, Y = {y1, … , ym}?
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 4. Отношения эквивалентности и порядка.
Цель занятия: Освоение понятий «Отношения эквивалентности и
порядка». Выработка навыков решения задач по теме.
1.
2.
3.
4.
5.
6.
Задания на занятия:
Какое бинарное отношение называется отношением эквивалентности?
Что называется разбиением множества А?
Что называется смежным классом множества А? Сформулируйте теорему
о разбиении множества отношением эквивалентности.
Что называется фактор-множеством множества А?
Какое бинарное отношение называется отношением порядка? Дайте
определение нестрого, строгого, частичного, полного порядка.
Дайте определение минимального элемента.
1. На множестве N и N×N определены следующие отношения:
Р={(a,b)/(a-b) делится на 3};
Q={(a,b),(c,d)/ad=bc},
35
Доказать, что P и Q отношения эквивалентности.
2. На множестве N×N определено отношение S следующим образом:
{(a,b),(c,d)} S  [((ad = bc) и b  0 ,d  0 ) или (а = с, b = 0,d=0)].
Доказать, что S - отношение эквивалентности.
3. Привести пример частично упорядоченного множества, и показать,
что оно является частично упорядоченным.
4. Доказать, что всякое частично упорядоченное множество содержит не
более одного наибольшего (наименьшего) элемента.
5. Построить пример частично упорядоченного множества, имеющего
точно один минимальный элемент, но не имеющего наименьшего
элемента.
6. Показать, что существует 2n(n+1)/2 симметричных бинарных отношений
на множестве А = {a1, … , an}.
7. Показать, что существует 2n(n-1) рефлексивных бинарных отношений на
множестве А = {a1, … , an}.
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 5. Мощность множества.
Цель занятия: Освоение понятия «мощность множества». Выработка
навыков решения задач по теме.
Задания на занятия:
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 6. Контрольная работа
Цель занятия: Промежуточный контроль знаний.
Задания на занятия:
1. Изобразить множество D с помощью кругов Эйлера.
36
(А  B)  C
2. Записать булеан множества А.
{{1,2},{3},1,3}
3. Известно, что из n учеников спортом увлекаются a учеников,
программированием b, математикой c, спортом и программированием d,
спортом и математикой e, программированием и математикой f , спортом,
математикой и программированием g учеников. Сколько учеников
увлекается только программированием? Сколько учеников увлекается
только математикой? Сколько учеников ничем не увлекается?
Ход занятия. На контрольную работу отводится 2 часа.
Основные рекомендации по выполнению заданий. Первыми решаются
задачи, кажущиеся простыми.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 7. Правила суммы и произведения. Перестановки, размещения и
сочетания. ( Раздел 3. Тема 1.) (интерактив.2)
Цель занятия: Освоение методов решения задач комбинаторики.
Задания на занятия:
1.
Сколькими способами можно распределить 3 билета среди 10
студентов, если
а) Распределяются билеты в разные кинотеатры на одно и то же время,
то есть каждый студент может получить не более одного билета.
б) Распределяются билеты на разные сеансы в различное время, то есть
каждый студент может получить любое число билетов.
в) Распределяются равноценные билеты на один и тот же сеанс.
2.
Сколькими способами можно расставить 10 человек в колонну,
так чтобы для
каждого человека, кроме первого и последнего, перед ним и позади него
был человек либо большего роста, либо меньшего роста.
3.
Сколько существует различных матриц из n строк и m столбцов
состоящих из нулей и единиц.
4.
Сколько существует различных матриц из n строк и m столбцов
состоящих из нулей и единиц в которых все строки различны.
5.
Сколькими способами можно построить девять человек в три
колонны по три
человека, если в каждой колонне люди стоят по росту и нет двух человек
одинакового роста.
6.
Сколько строк из нулей и единиц длины n можно записать при
условии что никакие две единицы не стоят рядом.
7.
Найти количество перестановок всех чисел от 1 до 9, таких что,
соседние числа отличаются более чем на 1.
8.
Найти количество перестановок всех чисел от 1 до 9, таких что
37
никакое число не стоит на своем месте.
9.
На 8 столах стоит 6 ваз с цветами и 5 свечей. Ни на одном столе
нет двух ваз
или двух свечей. • Сколько существует способов расставить вазы и
свечи.
10.
Сколько способов расставить вазы и свечи так, чтобы на каждом
столе был хотя бы один предмет.
11.
Сколько существует способов расставить вазы и свечи так,
чтобы ровно два стола были пустыми.
12.
Бросают две игральные кости. Сколько возможных комбинаций
в сумме дают нечетные числа.
13.
Бросают три игральные кости. Сколько возможных комбинаций
в сумме дают четные числа.
14.
В IT-компании работает 15 человек. Из них 10 человек знают
язык С++, 8 человек знают PHP, 7 человек в совершенстве разбираются в
технологиях баз данных. При этом 5 человек знают С++ и базы данных, 3
человека С++ и PHP, и 4 человека PHP и базы данных. Определите
1.
• Сколько человек знают С++, PHP и базы данных.
2.
• Сколько человек знают только С++
3.
• Сколько человек знают только PHP
4.
• Сколько человек знают только базы данных
При этом известно, что людей не знающих ни одну из этих технологий,
компания не берет на работу.
15.
Найти
количество
целых
положительных
чисел
не
превосходящих 1000 взаимно простых с числом 105. (Два числа называются
взаимно простыми, если их наибольший общий делитель равен единице).
Ход занятия: Группа разбивается на подгруппы(2-3). Каждой группе
выдаются задания. Для выполнения заданий выделяется время (45-60мин.).
Далее проверяется выполнение заданий у нескольких человек из группы (как
правило «слабых» студентов) с подробными объяснениями. За
положительный ответ выставляются баллы. В подгруппе, получившей
определенное количество баллов, все студенты получают зачет по этой теме
Рекомендации по выполнению заданий: При решении задач указать
на использование разных подходов для получения решения, например
основного закона комбинаторики или одной или нескольких
комбинаторных схем перестановок, размещений или сочетаний.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 9. Бином Ньютона. Полиномиальная формула. Метод включений
и исключений.
Цель занятия: Освоение методов решения задач комбинаторики.
Задания:
1. Определить, сколько рациональных членов содержится в разложении:
a) ( 2  3 3) 20 ;
38
b)
2.
a)
b)
3.
4.
a)
b)
c)
(3 6  4 2 )100.
Найти коэффициент при tk в разложении:
(2+ t4 + t7 )15, k = 17;
(2 + t – 2t3)20, k = 10.
Какое число больше: 9950+10050 или 10150?
Пусть n и m - целые положительные числа. Доказать
∑
∑
∑
5. Доказать, что для любого m = 0,1,2,...,п справедливо тождество
∑
6. Доказать, что ∑[ ]
7. Доказать тождества:
∑
a)
∑
b)
8. Доказать, что ∑
9.
Найти производящие функции следующих последовательностей:
a) an  n n , n  0,1,2,...;
0, n  0,

b) a n   n
 , n  1,2,....
 n!
10. Найти общий член an последовательности, для которой функция fa(t)
является производящей:
f a (t )  (q  pt ) m ;
a)
m
b)
 t2 
f a (t )  1   .
2

11. Сколькими способами можно разменять 10-копеечную монету
монетами 1, 2, 3 и 5 копеек при условии, что каждая из разменных монет
присутствует в двух экземплярах?
12.
Четыре человека сдают свои шляпы в гардероб. В предположении,
что шляпы возвращаются наугад, найти вероятность того, что в точности k
человек получат свои шляпы назад. Рассмотреть все значения k (0≤k≤4).
13.
При обследовании читательских вкусов оказалось, что 60%
студентов читают журнал А, 50% - журнал В, 50% - журнал С, 30% журналы А и В, 20% - журналы В и С, 40% - журналы А и С, 10% - журналы
А, В и С. Сколько процентов студентов:
a)
не читает ни одного журнала;
b)
читает в точности два журнала;
c)
читает не менее двух журналов.
14.
Найти число целых положительных чисел, не превосходящих 100 и
не делящихся ни на одно из чисел 3, 5 и 7.
39
15.
Показать, что если n=30m, то количество целых положительных
чисел, не превосходящих n и не делящихся ни на одно из чисел 6, 10, 15,
равно 22m.
16.
Сколькими способами можно расположить за круглым столом n
супружеских пар так, чтобы мужчины и женщины чередовались и никакие
двое супругов не сидели рядом?
17.
В букинистическом магазине лежит 6 экземпляров романа
И.С.Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4
экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих
романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы
«Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать
покупку, содержащую не менее, чем по одному экземпляру каждого из этих
романов?
Ход занятия: Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Основные рекомендации по выполнению заданий: Использовать
конспекты лекций и другие теоретические источники, образцы решения
задач, объяснения преподавателя.
Требования к отчѐтным материалам: Правильно (с комментариями)
оформленные решения задач.
Занятие 10. Производящие функции и рекуррентные соотношения.
Цель занятия: Выработка навыков решения задач по теме.
Задания на занятия:
18. Сколькими способами выпуклый (n+2)–угольник можно разбить на
треугольники диагоналями, не пересекающимися внутри (n+2)-угольника?
Вывести рекуррентное соотношение для {an}, где an - число способов
разбиения (n+2)–угольника, и разрешить это соотношение.
19. Решить рекуррентные соотношения:
a)
an+3 = 3an+2 - an+1 3 an, a0 = 1, a1 = 3, a2 = 8;
b)
an+3 + an+2 - an+1 - an = 0, a0 = 1, a1 = 2, a2 = 3;
c)
an+2 ± 9an = 0, a0 = 1, a1 = 0.
20. Решить неоднородные рекуррентные соотношения:
a)
an+1 = an + n, a0 = 1;
b)
an+2 = an+1 – 1/4an + 2-n , a0 = 1, a1 = 3/2.
21. Найти общее решение рекуррентных соотношений:
a)
an+2 - an+1 - an = 0;
b)
an+2 = an+1 – 1/4an.
22. Из урны, содержащей m различных шаров, одновременно извлекают s
(1≤s≤m) шаров, записывают их номера, а затем шары возвращаются обратно
в урну. Можно составить (C ms ) d различных наборов, получающихся в
результате d извлечений. Найти число наборов, в которых
a)
встречаются все шары;
40
b)
23.
ровно r (0≤r≤m) шаров не встречается.
Вычислить
S 
k
2
,
2 k
где суммирование проводится по всем
натуральным k’, не кратным 2, 3 и 5.
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 11. Контрольная работа
Цель занятия: Промежуточный контроль знаний.
Задания на занятия: Пример задания:
1. Сколькими способами можно расставить на полке 7 книг, если а) 2
определенные книги должны стоять рядом б) эти 2 книги не должны
стоять рядом.
2. В течение 10 недель студенты сдают 10 экзаменов в том числе два по
математике. Сколькими способами можно распределить экзамены по
неделям так, чтобы экзамены по математике не следовали один за
другим?
3. Город имеет вид прямоугольника, разделенного улицами на квадраты.
Таких квадратов в направлении с севера на юг "n", с востока на запад
"k".Сколько имеется кратчайших дорог от одной из вершин
прямоугольника до противоположной ?
Имеется колода из 36 карт 4-х мастей, занумерованных в каждой масти
1,2,3,4,5,6,7,8,9. Подсчитать, сколькими способами можно выбрать 5 карт,
что среди них окажутся 3 карты из 5 с одним и тем же номером.
Ход занятия. На контрольную работу отводится 2 часа.
Основные рекомендации по выполнению заданий. Первыми решаются
задачи, кажущиеся простыми.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 12. Графы. Виды графов. Способы задания.
Цель занятия: Использование основных понятий теории графов при
освоении различных моделей на графах (деревья, сети).
Задания на занятия:
1. Привести примеры графов:
а. Полный граф с 3, 4, 5 вершинами.
б. Связный планарный граф с 6 вершинами и 17 ребрами.
в. Связный не планарный граф с 6 вершинами и 9 ребрами.
41
г. Связный планарный граф с 10 вершинами 30 ребрами.
д. Связный не планарный граф с 5 вершинами.
е. Двудольный граф.
2. Нарисовать графы:
а. С одним перешейком.
б. С двумя перешейками.
в. Все ребра – перешейки.
3. Привести примеры графов
а. С 8 вершинами и 14 ребрами. Граф должен иметь Эйлеров цикл.
б. С 8 вершинами и 14 ребрами. Граф должен иметь Эйлеров путь и
не иметь Эйлерова цикла.
в. Связный граф с 8 вершинами и 14 ребрами. Граф не должен иметь
Эйлеров путь.
г. С 8 вершинами и 14 ребрами. Граф должен иметь Гамильтонов
цикл и не иметь Эйлерова цикла.
д. С 8 вершинами и 14 ребрами. Граф должен иметь Эйлеров цикл и
не иметь Гамильтонова цикла.
4. Привести примеры деревьев:
а. Пример бинарного дерева с 8 вершинами и глубиной 5.
б. Пример бинарного дерева с 8 вершинами и глубиной 4.
в. Пример бинарного дерева с 9 ребрами и глубиной 5
г. Пример бинарного дерева с 7 ребрами и глубиной 4
5. Для заданных графов выписать матрицы смежности, инцидентности,
достижимости, выполнить основные операции над графами. Определить
характеристические числа графа.
6. Рассмотреть алгоритмы обхода деревьев для задачи 4.
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач. Занятие проводится по сценарию типа 1 (типа 2).
Рекомендации по выполнению заданий: Рассмотреть способы
представления графов в памяти компьютера для решения различных задач и
алгоритмов. Осуществить подготовку данных для лабораторной работе по
алгоритмам.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 13. Операции над графами
Цель занятия: Выработка навыков решения задач по теме.
Задания на занятия:
1. Какие операции над графами можно выполнять? Дайте определения
этих операций.
2. На рис.2 приведены графы G1 и G2. Найти G1  G2 и G1×G2.
x1
x2
G 1:
x1
x1
x4
x3
G2:
G 1:
42
G2:
x3
x2
x1
x2
x4
x3
x3
x2
а
б
Рис. 2
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие14. Метрические
Фундаментальные циклы.
характеристики
графов.
Остовы
графов.
Цель занятия: Выработка навыков решения задач по теме.
Задание:
1. Найти матрицы расстояний, радиусы и диаметры графов, изображенных на
рис.
x1
x2
x3
x4
x1
x2
x3
x8
x7
x6
x5
x8
x7
x6
x1
x2
x3
x4
x1
x2
x3
x4
x5
x4
2. Найти эксцентриситеты вершин, радиусы и диаметры графов,
периферийные, центральные вершины и диаметральные цепи графов,
x8
x7
x6 1. x5
x8
x7
x6
x5
приведенных
на рис.
x1
x2
x3
x4
x1
x2
x3
x8
x7
x6
x5
x8
x7
x6
x4
x5
Рис. 1
3. Упорядочить вершины и дуги орграфов, изображенных на рис.2,
графическим и матричным способом (дуги – только графическим).
x2
u1
x1
u2
u10
u11
43
u5
u7
x1
u2
u7
u4
x3
u8
u1
x6
u4
u3
u6
x2
x3
u9
u5
u6
u3
x6
Рис. 2
4. Доказать, что два графа, изображенных на рис.3, изоморфны, а графы на
рис.4 неизоморфны.
x1
x2
x3
x2
x3
x1
x6
x5
x4
x4
x6
x5
Рис. 3
x2
x3
x2
x1
x4
x6
x3
x1
x5
x4
x6
x5
Рис. 4
1. Для графа G , заданного матрицей весов, построить минимальный по весу
остов G' и найти его вес ω(G').
1)
2)
(
)
(
)
2. Используя матричную теорему Кирхгофа, найти число остовных деревьев в
полном двудольном графе Km,n
3. Найти матрицы фундаментальных циклов, радиусы и диаметры графов,
44
изображенных на рис.
Ход занятия: Группа разбивается на подгруппы(2-3). Каждой группе
выдаются задания.Для выполнения заданий выделяется время (45-60мин.).
Далее проверяется выполнение заданий у нескольких человек из группы (как
правило «слабых» студентов) с подробными объяснениями. За
положительный ответ выставляются баллы. В подгруппе, получившей
определенное количество баллов, все студенты получают зачет по этой теме
Основные рекомендации по выполнению заданий: Использовать
конспекты лекций и другие теоретические источники, образцы решения
задач, объяснения преподавателя.
Требования к отчѐтным материалам:
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 15. Эйлеровы и Гамильтоновы графы. ( Раздел 4. Тема 2,3,4.)
Цель занятия: Выработка навыков решения задач по теме.
Задание:
1. Являются ли изображенные графы эйлеровыми или гамильтоновыми?
5. 2. Доказать, что если для любых двух несмежных вершин x и y
связного п -вершинного графа выполняется условие P(x)+P(y)≥n, то
граф имеет гамильтонов цикл.
2. По алгоритму Флери найти эйлеров цикл в графах, изображенных на
рис.
4. Найти наибольшее независимое множество вершин в графе Петерсена.
6. Показать, что граф Петерсена не гамильтонов.
7. Найти число доминирования δ(G) и наименьшее доминирующее
множество графов, представленных на рис.
8. Построить дерево поиска клик, матрицу клик и найти наибольшие
клики графов, изображенных на рисунках 3.44, а, 3.45 и 3.46, б, в.
9. Приведите пример графа, в котором наименьшее доминирующее
множество не является независимым.
10. Доказать, что если для любых двух несмежных вершин x и y связного
п -вершинного графа выполняется условие P(x)+P(y)≥n, то граф
имеет гамильтонов цикл.
11.По алгоритму Флери найти эйлеров цикл в графах, изображенных на
рис.
12.Найти наибольшее независимое множество вершин в графе Петерсена
13. Показать, что граф Петерсена не гамильтонов.
14. Найти число доминирования δ(G) и наименьшее доминирующее
множество графов, представленных на рис.
15.Построить дерево поиска клик, матрицу клик и найти наибольшие
45
клики графов, изображенных на рисунках 3.44, а, 3.45 и 3.46, б, в.
16. Приведите пример графа, в котором наименьшее доминирующее
множество не является независимым.
Ход занятия: Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Основные рекомендации по выполнению заданий: Использовать
конспекты лекций и другие теоретические источники, образцы решения
задач, объяснения преподавателя.
Требования к отчѐтным материалам:
Правильно (с комментариями) оформленные решения задач.
Занятие 16. Планарные графы.
Цель занятия: Выработка навыков решения задач по теме.
1.
2.
3.
4.
5.
Задания на занятия:
Какой граф называется планарным?
Какое изображение графа называется плоским?
Сформулируйте теорему Понтрягина-Куратовского.
Сформулируйте теоремы о пяти и четырех красках.
Найти хроматическое число заданных графов
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
.Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие17. хроматические графы ( Раздел 5. Тема 1.) (интерактив.2)
Цель занятия: Выработка навыков решения задач по теме.
Задания на занятия:
6. Сформулируйте задачу о раскраске графа. Что называется хроматическим
числом графа?
7. Существует ли алгоритм нахождения раскраски графа?
8. Сформулируйте теоремы о раскрасках графов.
9. Приведите алгоритм последовательной раскраски графа.
10.Сформулируйте теоремы о пяти и четырех красках.
11.Найти хроматическое число заданных графов
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач. Занятие проводится по сценарию типа 1 (типа 2).
46
Рекомендации по выполнению заданий: Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 18. Контрольная работа
Цель занятия: Промежуточный контроль знаний.
Задания на занятия: Пример задания:
1. Даны графы G1 и G2. Найдите G1  G2 , G1  G2 , G1  G2 , G1  G2. Для графа
G1  G2 найдите матрицы смежности, инцидентности, сильных
компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из
вершины 1.
2. Найдите радиус и диаметр, минимальное множество покрывающих цепей
графа G . Является ли изображенный граф эйлеровым? Является ли
изображенный граф планарным? Найдите матрицы фундаментальных
циклов, фундаментальных разрезов. Найти хроматическое число графа.
3. Для графа G , заданного матрицей весов, построить минимальный по весу
остов G' и найти его вес ω(G').
Ход занятия. На контрольную работу отводится 2 часа.
Основные рекомендации по выполнению заданий. Первыми решаются
задачи, кажущиеся простыми.
Требования к отчѐтным материалам. Правильно (с комментариями)
оформленные решения задач.
5.5. Краткое описание видов самостоятельной работы
5.5.1.Общий перечень видов самостоятельной работы
1. Подготовка к практическим занятиям.
2. Домашние контрольные работы по темам «Теория множеств»,
«Комбинаторика» и «Теория графов». Индивидуальные задания
соответствуют задачам к практическим занятиям.
3. Обзор
(доклад,
реферат,
презентация)
по
информации
специализированных сайтов разделов дискретной математики.
4. Подготовка к зачету.
5.5.2 Методические рекомендации по выполнению каждого вида
самостоятельной работы
1.Подготовка к практическим занятиям.
Цель. Для продуктивной работы на занятиях необходимо проработать
теоретический материал.
47
Задание на СРС. Ответить на вопросы, приведенные в методических
указаниях к каждому занятию.
Требования к форме и содержанию отчетных материалов. Устный или
письменный ответ на поставленные вопросы.
Рекомендации по выполнению задания. Использовать лекционный материал
и рекомендованную литературу.
Рекомендуемый график выполнения отдельных этапов СРС. Расписание
занятий.
2. Домашние контрольные работы по темам «Теория множеств»,
«Комбинаторика» и «Теория графов».
Цель работы: Закрепление и использование основных понятий, обозначений
соответствующего раздела дискретной математики при выполнении
индивидуальных заданий.
Содержание заданий: индивидуальные задания соответствуют задачам к
практическим занятиям.
1 Теория множеств
1.1 Нарисовать на диаграмме Венна следующие множества
1. A (B \ C)
2. A ∩ (B  C)
3. (A∩ B) \ C
4. (A B C) \ (A∩ B ∩ C)
5. (A B) ∩ (A C)
6. A \ (B∩ C)
7. (A B) ∩(C \ B)
8. (A∩ B ∩ C)  (A \ B)
9. (A ∩ B) \ (A \ C) ∩ (B \ C)
10. (A B) \ (A \ C)  (B \ C)
1.2 Проверить с помощью диаграмм Венна и тождественными
преобразованиями эквивалентность множеств
1. (A  B) ∩ (A  C) и A  (B∩C)
2. (A∩ B)  (B∩ C) и B ∩ ( A  C)
3. A \ (B C) и (A \ B) ∩ (A \ C)
4. A \ (B \ C) и (A \ B)  (A ∩ C)
5. A \ (B ∩C) и (A \ B)  (A \ C)
6. (A B) \ C и (A \ C)  (B \ C)
7. (A ∩ B) \ C и (A \ C) ∩ (B \ C)
8. А  (ВС) и (А  В)  (А  С)
9. (АВ)  С и (А  С)  (В  С)
10. А  (В\С) и (А  В) \ (А  С)
1.3 Задать следующие ниже отношения. Определить какие из них
являются
транзитивными, симметричными, антисимметричными, рефлексивными.
48
Какие
из
отношений
являются
отношениями
порядка
и
эквивалентности?
Отношение ‖учит‖ на множестве из двух преподавателей кафедры и
четырех студентов.
2. Отношение ‖сумма равна 10‖ на множестве чисел [1 . . . 10]. Два
числа находятся в отношении, если их сумма равна 10.
3. Отношение ‖взаимно простые‖ на множестве чисел [2 . . . 10]. Два
числа являются взаимно простыми, если их наибольший общий делитель
равен 1.
4. Отношение ‖является делителем‖ на множестве чисел [1 . . . 16].
Два числа находятся в отношении, если первое число является делителем
второго числа.
5. Отношение ‖застрелил‖ на множестве {Пушкин, Онегин, Ленский,
Дантес}.
1.4 Какие из указанных множеств равномощны?
• Множество натуральных чисел
• Множество всех цифр, изображение которых содержит кружок.
• Множество всевозможных последовательностей из нулей и единиц
произвольной конечной длины.
• Множество простых чисел
• Множество всех натуральных чисел, являющихся остатками от
деления на 4.
• Множество всех натуральных чисел, делящихся без остатка на 4.
• Множество времен года.
• Множество всевозможных последовательностей из нулей и единиц
бесконечной длины.
1.5 Привести пример двух множеств, таких чтобы в каждом множестве
содержалось по 6 элементов, а в их пересечении было 3 элемента.
1.6 Привести пример двух множеств, таких чтобы в каждом множестве
со держалось по 6 элементов, а в разности множеств было по 4 элемента.
Привести пример двух множеств, таких чтобы в каждом множестве
содержалось по 6 элементов, а в их объединении было 8 элементов.
2 Комбинаторика.
2.1 Музыкальный концерт состоит из 3-х песен и 2-х скрипичных
пьес. Сколькими способами можно составить программу концерта
так, чтобы он начинался и оканчивался исполнением песни и
чтобы скрипичные пьесы не исполнялись одна за другой.
2.2 Пассажирский поезд состоит из 2-х багажных вагонов, 4-х
плацкартных и 3-х купированных. Сколькими способами можно
сформировать состав, если багажные вагоны должны находиться в его
начале, а купированные в его конце.
2.3 Сколькими способами можно расставить на полке 7 книг, если
а) 2 определенные книги должны стоять рядом
б) эти 2 книги не должны стоять рядом.
49
2.4 Сколько различных 3-х буквенных слов можно образовать, используя
буквы составляющие вашу фамилию, причем эти слова должны начинаться
и оканчиваться согласными, а в середине должна стоять гласная буква.
2.5 Сколько различных 3-х буквенных слов можно образовать, используя
буквы составляющие вашу фамилию, причем эти слова должны начинаться
и оканчиваться согласными, а в середине должна стоять гласная буква.
2.6 Сколькими способами можно образовать разные комбинации букв
из слова "перестановка". Сколько из них начинается с буквы "п" и
оканчивается буквой "а".
2.7 Найти число способов, которыми можно выписать в один ряд 9
троек и 6 пятерок так, чтобы никакие 2 пятерки не стояли рядом.
2.8 Сколько различных чисел можно получить, переставляя цифры
123456789 при условии, что в каждой такой перестановке как все
четные цифры, так и все нечетные будут идти в возрастающем порядке.
2.9 В распоряжении агрохимика есть 6 различных типов минеральных
удобрений. Ему необходимо провести несколько
экспериментов по
изучению совместного влияния любой тройки минеральных удобрений.
Сколько всего экспериментов ему надо провести в том случае, если
исключить из рассмотрения такие тройки, куда входит одновременно
удобрения.
2.10 Городской совет состоит из мэра и 6 старейшин. Сколько различных
комиссий можно сформировать из членов совета, если каждая комиссия
состоит из 4-х человек и
а) мэр города входит в каждую комиссию,
б) мэр не входит ни в одну комиссию.
2.11 Некто имеет 8 различных пар перчаток. Сколькими способами он может
отобрать одну перчатку для правой руки и одну для левой так, чтобы они не
принадлежали одной паре
2.12 Предприятие может представить работу по одной специальности
4-м женщинам, по другой - 5 мужчинам и по 3-ей - 3-ем работникам любого
пола. Сколькими способами можно заполнить эти места, если имеются 10
мужчин и 8 женщин?
2.13 В течение 10 недель студенты сдают 10 экзаменов в том числе два
по математике. Сколькими способами можно распределить экзамены по
неделям так, чтобы экзамены по математике не следовали один за другим.
2.14 Сколькими способами из 5 супружеских пар можно отобрать 4-х
человек, если
а) в число отобранных должны входить 2 мужчин и 2 женщины;
б) никакая супружеская пара не должна входить в это число?
2.15 В предвыборной борьбе за 2 одинаковые должности выступают 6
кандидатов. Каждый избиратель может занести в свой бюллетень либо
одного кандидата, либо двух. Сколькими способами могут быть заполнены
бюллетени?
2.16
На железнодорожной дороге 50 станций. На каждом билете
печатаются названия станций отправления и прибытия. Сколько различных
50
билетов можно напечатать? Тот же вопрос, если каждый билет можно
использовать в любом направлении, т.е. безразлично, с какой из двух
станций Вы отправляетесь?
2.17 Каково число матриц из "n" строк и "m" столбцов с элементами из
{0,1} ? И при дополнительном условии, что строки матрицы попарно
различны?
2.18 8 человек должны расположиться в 2-ух комнатах, причем в
каждой должно быть по крайней мере 3 человека. Сколькими способами
это можно сделать?
2.19 Сколькими способами можно расположить в один ряд 5 красных
мячей, 4 черных и 5 белых мячей так, чтобы мячи, лежащие на краях, были
одного цвета?
2.20
Колода игральных карт насчитывает 52 различных карты.
Сколькими способами можно сдать 13 карт на руки одному игроку так,
чтобы у него оказалось ровно 2 туза ?
Теория графов
Для заданного графа выполнить следующие действия:
1. Заполнить матрицу смежности
2. Уложить на плоскости
3. Определить характеристические числа
4. Указать самый большой цикл
5 Определить является ли он эйлеровым и/или гамильтоновым.
51
Требования к отчетным материалам и документам. Контрольные работы
выполняются в отдельной тетради или сброшюрованных листах.
52
Указывается номер варианта и текст задания. Приводятся используемые
формулы для вычислений и список использованной литературы.
4.
Обзор
(доклад,
реферат,
презентация)
по
информации
специализированных сайтов разделов дискретной математики и
программного обеспечения.
Цель работы. Поиск и анализ информации в электронных источниках.
Получение возможности использования доступного программного
обеспечения для решения задач дискретной математики.
Содержание заданий. Индивидуальные задания соответствуют разделам,
изучаемым в курсе, и являются подготовкой к выполнению лабораторных
работ.
Требования к отчетным материалам и документам. Текст работы
представляется в электронной форме в формате, позволяющем возможность
редактирования содержания. Доклад готовится с использованием слайдов
или других мультимедийных средств.
4. Подготовка к зачету
Цель работы: Системное представление знаний, полученных во время
лекционных и практических
занятий, а также при выполнении
индивидуальных заданий и контрольных работ.
Содержание задания: 1) Повторить способы решения задач по всем темам.
2) подготовить ответы на вопросы лекционного материала, которые
приведены в 7.3 – Контрольно-измерительные материалы для итоговой
аттестации по дисциплине.
Основные рекомендации по выполнению задания:
Использовать лекционный материал и рекомендованную литературу.
5.5.3 Описание курсового проекта (курсовой работы)
Учебным планом не предусмотрены.
6. Применяемые образовательные технологии
При реализации данной программы применяются инновационные
технологии обучения, активные и интерактивные формы проведения занятий,
указанные в таблице 2.
Таблица 2 - Применяемые образовательные технологии
Технологии
Виды занятий
Лекции Лаб.
раб.
Интерактивные лекции
работа в команде
Групповая дискуссия
Практ./
СРС
Сем. зан.
4
8
53
Курсовой
проект
7. Методы и технологии контроля уровня подготовки по
дисциплине
7.1. Виды контрольных мероприятий, применяемых
контрольно-измерительных технологий и средств.
1.Промежуточное тестирование с использованием программной системы
тестирования.
2.Демонстрация
и
тестирование
работоспособности
алгоритмов,
выполненных в ходе лабораторных занятий.
3.Экспресс-тестирование на лекции.
4. Оценка выполнения домашних контрольных работ.
6. Зачет в конце семестра.
7.2. Критерии оценки уровня освоения учебной программы (рейтинг).
Текущий контроль успеваемости оценивается преподавателем и
заносится в журнал успеваемости.
По основным разделам дисциплины проводится промежуточное
тестирование с использованием программной системы тестирования,
проверка решения контрольных задач на практических заданий, домашних
контрольных работ.
До зачета по дисциплине (семестр №4) допускаются студенты, сдавшие
все индивидуальные контрольные работы, предусмотренные планом. При
наличии сданных в срок индивидуальных заданий, активной работе на
лекциях и практических занятиях, выполнении всех видов СРС, возможно
выставление зачета автоматически.
7.3.Контрольно-измерительные материалы и другие оценочные средства
для итоговой аттестации по дисциплине.
Пример тестовых заданий:
Тест А. Какой тип мощности имеет множество натуральных чисел?
Варианты ответов:
1) конечный
2) счетный
3) континуальный
Тест В. Укажите комбинаторную схему для задачи: Сколько
вариантов чисел, больших 3 000 000, можно записать, используя цифры 1,
1, 2, 2, 2, 3, 3?
Варианты ответов:
1) сочетания 2) размещения 3) перестановки 4) перестановки с
повторениями
Примеры билетов к зачету:
Билет А.
1) Упорядоченные выборки. Размещения. Перестановки. Число
упорядоченных выборок. Число размещений, перестановок.
Свойства размещений.
2) Графы. Способы задания графов. Маршруты, цепи, циклы.
Кратчайшие пути.
3) Отношение R на множестве всех книг библиотеки определили
54
следующим образом. Пара книг а и b принадлежат R, если и только если
в этих книгах есть ссылка на одни и те же литературные источники.
Является ли R
а) рефлексивным отношением;
б) симметричным отношением;
в) транзитивным отношением?
Билет Б.
1) Бином Ньютона. Свойства биномиальных коэффициентов.
2) Неупорядоченные выборки. Сочетания без повторений.
Сочетания с повторениями. Число сочетаний.
3) Определить характеристические числа графа
Вопросы к экзамену
Теория множеств
1. Множества. Основные понятия.
2. Операции над множествами. Диаграммы Венна (круги Эйлера).
3. Булева алгебра подмножеств.
4. Декартово произведение множеств.
5. Бинарные отношения.
6. N-арные отношения.
7. Операции над бинарными отношениями.
8. Функции.
9. Отношение эквивалентности. Разбиения множества.
10.Отношения порядка.
11.Мощность множества.
12.Минимизация представления множеств
13.Аксиомы теории множеств.
Комбинаторика
14.Общие правила комбинаторики
15.Перестановки и подстановки
16.Размещения и сочетания
17.Размещения и сочетания с повторением
18.Разбиения
19.Метод включений и исключений
20.Бином Ньютона и полиномиальная формула
21.Рекуррентные соотношения.
22.Возвратные последовательности
23.Метод производящих функций
Графы
24.Графы. Основные понятия и определения.
25.Способы задания графов.
26.Виды графов и операции над ними.
55
27.Маршруты. Циклы. Связность графов.
28.Эйлеровы графы
29.Гамильтоновы графы
30.Деревья
31.Остовы графов
32.Обходы графов по ширине и глубине
33.Упорядоченные и бинарные деревья
34.Фундаментальные циклы
35.Фундаментальные разрезы
36.Планарные графы
37.Раскраска графов
8. Рекомендуемое информационное обеспечение дисциплины
8.1. Основная учебная литература
1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер,
2009. –304 с.: ил.
2. Новиков Ф.А. Дискретная математика. Для магистров и бакалавров.
Учебник для вузов. Стандарт третьего поколения Гриф УМО МО РФ
Питер.- 2011 384с
3. Кузнецов O.П., Дискретная математика для инженера. М.: Лань, , 2009.400с.
4. Куликов В.В. Дискретная математика. Гриф УМО МО РФ.- Издательство:
РИОР Серия: Высшее образование, 2010 г.- 174 стр.
8.2. Дополнительная учебная и справочная литература.
1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы,
матроиды, алгоритмы: Учебное пособие. 2-е изд.- Лань, 2010. - 368 c.
2. Судоплатов С.В., Овчинников Е.В. Элементы дискретной математики:
Учебник. – М.: ИНФРА-М, Новосибирск : Изд-во НГТУ, 2002.-280 с.(Серия «Высшее образование».
3. Шапорев С.Д. Курс лекций и практических занятий.- СПб.: БХВПетербург,2006 – 400 с.: ил.
4. Горбатов В.А. Фундаментальные основы дискретной математики.
Информационная математика: Учебник для втузов.- М.: Наука.
Физматлит, 2000.-544с.
8.3. Электронные образовательные ресурсы:
8.3.1.Ресурсы ИрГТУ, доступные в библиотеке университета или в локальной сети
университета.
1.
2.
3.
4.
5.
http://www.intuit.ru/
http://www.edu.ru/
http://www.i-exam.ru/
http://gen.lib.rus.ec/
http://vuz.exponenta.ru
56
8.3.2.Ресурсы сети Интернет
1. http://www.intuit.ru/
2. http://www.edu.ru/
9.Рекомендуемые специализированные программные средства
1. Free Pascal (свободно-распространяемый продукт)
2. Delphi 10
3. C++ Builder
4. MicroSoft Office
10.Материально-техническое обеспечение дисциплины
Лекции по дисциплине проводятся в мультимедийном классе,
оборудованном проектором и экраном.
Лабораторные работы по дисциплине проводятся в компьютерном
классе ИрГТУ (24 ПК).
Промежуточное тестирование проводится с помощью разработанной на
кафедре вычислительной техники программной системы тестирования.
57
Программу составила: Носырева Л.Л., доцент кафедры автоматизированных
систем, к.т.н.
_________________________ ―____‖_________ 20__ г.
(подпись)
Программа одобрена на заседании кафедры «квантовой физики и нанотехнологий»
Протокол № ___ от ―___‖ _________________ 20__ г.
Зав. кафедрой ____________________ / Афанасьев А.Д. / ―____‖_________ 20__ г.
(подпись)
Программа одобрена на заседании Методической комиссии
Физико-технического института
Протокол № _____ от ―___‖ _________________ 20__г.
Декан ____________________ / Афанасьев А.Д. / ―____‖_________ 20__ г.
Руководитель ООП __________________ /Иванов Н.А. / ―____‖_________
58