close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
1.Информация из ФГОС, относящаяся к дисциплине
1.1 Вид деятельности выпускника
Дисциплина охватывает круг вопросов относящиеся к виду
деятельности выпускника: расчетно- проектная деятельность;
1.2 Задачи профессиональной деятельности выпускника
В дисциплине рассматриваются указанные в ФГОС задачи
профессиональной деятельности выпускника:
 изучение научно-технической информации, отечественного и
зарубежного опыта по тематике проекта;
 контроль соответствия разрабатываемых проектов и технической
документации техническим регламентам, национальным стандартам,
стандартам связи, техническим условиям и другим нормативным
документам;
 проведение предварительного технико-экономического обоснования
проектных расчетов;
 разработка проектной и рабочей технической документации,
оформление законченных проектно-конструкторских работ;
1.3 Перечень компетенций, установленных ФГОС
Освоение программы настоящей дисциплины позволит сформировать у
обучающегося следующие компетенции:
 использовать основные законы естественнонаучных дисциплин в
профессиональной деятельности, применять методы математического
анализа и моделирования, теоретического и экспериментального
исследования (ОК-9);
 иметь навыки самостоятельной работы на компьютере и в компьютерных
сетях; быть способным к компьютерному моделированию устройств,
систем и процессов с использованием универсальных пакетов
прикладных компьютерных программ (ПК-2);
 уметь организовать доведение услуг до пользователей услугами связи;
быть способным провести работы по управлению потоками трафика на
сети (ПК-11);
1.4.Перечень умений и знаний, установленных ФГОС
Студент после освоения программы настоящей дисциплины должен:
Уметь:

использовать математические методы в технических приложениях;
строить вероятностные модели для конкретных процессов, проводить
необходимые расчеты в рамках построенной модели; использовать
возможности вычислительной техники и программного обеспечения;
Знать:

основные понятия и методы математического анализа, теории
вероятностей и математической статистикой, основы математического
аппарата, применяемого для решения задач управления и алгоритмизации
процессов обработки информации, элементы теории множеств,
логические функции, графы и конечные автоматы; математические
2
программы для использования возможностей компьютеров для
качественного исследования свойств различных математических моделей;
законы и методы накопления, передачи и обработки информации с
помощью компьютера;
Владеть:

методами математического анализа и теории вероятностей;
основными методами работы на компьютере с использованием
универсальных прикладных программ; иметь опыт аналитического и
численного решения вероятностных и статистических задач, навыками
использования основных приемов обработки экспериментальных данных,
в том числе с использованием стандартного программного обеспечения,
пакетов программ общего и специального назначения; навыками
экологического обеспечения производства и инженерной защиты
окружающей среды
2. Цели и задачи освоения программы дисциплины
Целью данной дисциплины является формирование у обучающихся
базовых знаний по дискретной математике, умений и навыков поприменению
методов
дискретной
математики,
необходимых для
построения
математических моделей и разработки алгоритмов, применяемых для анализа
различных процессов и явлений, а также при проектировании
вычислительных машин, комплексов, систем и сетей. Формирование
практических навыков разработки и анализа алгоритмов над объектами
дискретной математики.
Задачи
преподавания
дискретной
математики
определяются
спецификой ее предмета и метода. Конкретно, для избранного профиля в
более детальном плане задачами являются:
- изучение студентами основ теории множеств;
-освоение основных понятий комбинаторики, методов решения
комбинаторных задач;
- приобретение навыков осуществления операций над графами и
выполнения количественных оценок их характеристик;
3. Место дисциплины в структуре ООП
Для изучения дисциплины, необходимо освоения содержания
дисциплин:
- Математика
- Информатика
Знания и умения, приобретаемые студентами после освоения
содержания дисциплины, будут использоваться в:
- Вычислительная техника и информационные технологии
- Многоканальные телекоммуникационные системы
4. Основная структура дисциплины.
Таблица 1 – Структура дисциплины
Вид учебной работы
3
Трудоемкость, часов
Всего
Общая трудоемкость дисциплины
Аудиторные занятия, в том числе:
лекции
лабораторные работы
практические/семинарские занятия
Самостоятельная работа (в том числе
курсовое проектирование)
Вид промежуточной аттестации
(итогового контроля по дисциплине), в
том числе курсовое проектирование
5.
5.1.
108
54
36
18
54
Семестр
№4
108
54
36
18
54
Зачет
Зачет
Содержание дисциплины
Перечень основных разделов и тем дисциплины
Раздел 1. Теория множеств
Тема 1. Множества.
Основные понятия и определения. Операции над множествами. Диаграммы
Венна. Алгебра подмножеств. Декартово произведение множеств. Мощность
множества.
Тема 2. Отношения.
Бинарные отношения. N-арные отношения.Специальные бинарные
отношения. Операции над бинарными отношениями. Матрица бинарного
отношения. Функции. Инъективные и сюръективные функции. Отношения
эквивалентности. Отношения порядка.
Тема 3. Мощность множеств.
Эквивалентность множеств. Понятие мощности множества.
Раздел 2. Комбинаторика.
Тема 1. Комбинаторные конфигурации.
Основные правила комбинаторики. Перестановки и подстановки.
Размещения и сочетания. Размещения и сочетания с повторением. Разбиения.
Бином Ньютона. Полиномиальная формула. Метод включений и
исключений.
Тема 2. Рекуррентные соотношения. Возвратные последовательности.
Рекуррентные соотношения. Возвратные последовательности.
Тема 3. Производящие функции.
Производящие функции.
Раздел 3. Графы.
Тема 1. Основные определения.
Основные понятия и определения. Виды графов. Способы задания графа.
Операции над графами. Изоморфизм графов. Валентность.
Тема 2. Связность.
Маршруты, цепи, циклы. Связность. Метрические характеристики графа.
Эйлеровы и Гамильтоновы графы. Определение путей и кратчайших путей в
4
графах. Потоки в сетях.
Тема 3. Деревья.
Лес. Деревья. Обходы графа по глубине и ширине. Остов графа.
Фундаментальные циклы. Разрезы.
Тема 4. Планарность графов.
Основные определения. Теорема Эйлера. Теорема Понтрягина —
Куратовского. Искаженность. Толщина.
Тема 5. Раскраска графов.
Хроматическое число графа. Алгоритмы раскраски. Теоремы о пяти и
четырех красках.
Все лекции читаются с элементами интерактивных занятий. Лекция, как
правило, начинается с того, что студентам формулируются задачи,
которые будут рассматриваться на лекции и предлагается обсудить
подходы к решению этих задач. Обсуждение проходит в форме групповой
дискуссии и может продолжаться по ходу лекции.
В конце лекции подводится итог. Обсуждаются рассмотренные на лекции
темы и задачи. Дается оценка дискуссии, проходившей в начале лекции.
5.2. Краткое описание содержания теоретической части разделов и тем
дисциплины
Раздел 1.
Тема 1. Множества.
Понятие «множество» относится к исходным
понятиям
математической теории и не является строго определяемым. Его синонимами
являются «совокупность», «семейство», «класс», «система», «собрание» и др.
Георг Кантор (1845–1918), немецкий математик, создатель теории
множеств, дал такое определение: «под множеством понимают объединение
в одно общее объектов, хорошо различаемых нашей интуицией или нашей
мыслью».
Объекты, составляющие данное множество, называют его
элементами. При этом никаких ограничений на природу элементов
множества не накладывается. Предполагается только, что для любых двух
элементов данного множества имеется возможность выяснить, различны они
или одинаковы.
Тот факт, что элемент x принадлежит множеству А(x является
элементом множества А), записывается так: x  A (x не принадлежит
множеству А x  A ).
Существенным в понятии «множество» является то, что мы
объединяем некоторые предметы в одно целое.
Понятие множества — одно из основных понятий современной
математики. Понятия и теоремы теории множеств обладают большой
общностью, так как элементы множеств могут быть различной природы, а
потому одни и те же утверждения, касающиеся множеств, можно
истолковать как утверждения о точках, натуральных числах, молекулах и т.д.
Множество называется конечным, если оно состоит из конечного
числа элементов, и бесконечным — в противоположном случае.
5
Возможны различные способы задания множеств.
Множества могут быть заданы следующими способами:
- перечислением (списком своих элементов);
- описанием свойств, которыми должны обладать его элементы;
- порождающей процедурой.
Например:
Множество экзаменационных оценок может быть задано:
- перечислением А={2; 3; 4; 5};
- описанием свойствА={aa- экзаменационная оценка;
- порождающей процедуройА=а а=2+i, i= 0,3 .
Множество, не содержащее ни одного элемента называетсяпустым и
обозначается  .
О п р е д е л е н и е 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 и состоящее из всех тех и только тех
элементов, которые принадлежат как множеству А, таки множеству В.
6
A B  x x  A & x  B.
О п р е д е л е н и е 2 . 2 .Объединением множеств Аи В называется
множество, обозначаемое A B и состоящее из всех тех и только тех
элементов, которые принадлежат хотя бы одному из множеств А, В.
A B  x x  A x  B.
О п р е д е л е н и е 2 . 3 . Разностью множествА и В называют
множество, обозначаемое А\В и состоящее из элементов, принадлежащих
множеству А и не принадлежащих множеству В.
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. Изображение операций с помощью кругов Эйлера
Пусть Б(Е) - совокупность всех подмножеств множества Е. Б(Е) замкнуто
относительно операций объединения, пересечения и дополнения множеств,
т.е. производя эти операции над элементами множества Б(Е), получаем
элементы, принадлежащие Б(Е). Множество Б(Е) с введенными операциями
объединения, пересечения и дополнения называют булевой алгеброй
подмножеств множества Е.
Основные законы, которым подчиняются эти операции:
7
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;
10) A  A  A;

11) A  A  A;
12) A  E  A;
13) A    A;
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
8
(согласно определению), либо R(а, b), либо aRb. Обозначение aRb исходит
из обозначений видаа = b,а<b, A  B и др.
Если R  A  B — бинарное отношение и А=В, то R называют
бинарным отношением, определенным на множестве А (вместо того, чтобы
говорить, что R — бинарное отношение, определенное на паре множеств А,
А).
Бинарные отношения иногда удобно изображать графически. Один
способ состоит в том, что элементы х Аи у В, связанные отношением
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 определенное на паре
непустых множеств А и В, называется функцией, определенной на
множестве А со значениями в В (или отображением из А в В) , если для
любого элементах А существует один и только один элемент у В,
удовлетворяющий условию xfy.
О п р е д е л е н и е 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→
10
Y(или: если каждый элемент множестваY имеет хотя бы один прообраз в
множестве Х при отображенииF).
Другое название сюръективного отображенияF: X→ Y —
отображение множества Х на множество Y.
Определение11.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 (транзитивность);
3) из хρу и уρх следует х = у для любых x, y  A (антисимметричность).
МножествоА, на котором задан какой-нибудь частичный порядок,
называется частично упорядоченным.
11
О п р е д е л е н и е 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. Конечные и бесконечные множества. Рассматривая различные
множества, мы замечаем, что иногда можно, если не фактически, то хотя бы
примерно, указать число элементов в данном множестве. Посмотрим, как мы
сравниваем между собой два конечных множества. Можно, например,
сосчитать число элементов в каждом из них и, таким образом, эти два
множества сравнить. Но можно поступить и иначе, именно, попытаться
установить биекцию, т. е. взаимно однозначное соответствие между
элементами этих множеств, иначе говоря, такое соответствие, при котором
каждому элементу одного множества отвечает один и только один элемент
другого, и наоборот. Заметим теперь, что если первый способ (подсчет числа
элементов) годится лишь для сравнения конечных множеств, второй
(установление взаимно однозначного соответствия) пригоден и для
бесконечных.
2. Счетные множества. Простейшим среди бесконечных множеств
является множество натуральных чисел. Назовем счетным множеством
12
всякое множество, элементы которого можно биективно сопоставить со
всеми натуральными числами. Иначе говоря, счетное множество — это такое
множество, элементы которого можно занумеровать в бесконечную
последовательность: а1, а2…, аn, … . Приведем примеры счетных множеств.
Бесконечное множество, не являющееся счетным, называется
несчетныммножеством.
Установим некоторые общие свойства счетных множеств.
1.Всякое подмножество счетного множества конечно или счетно.
2.Сумма любого конечного или счетного множества счетных
множеств есть снова счетное множество.
3.Всякое бесконечное множество содержит счетное подмножество.
3. Эквивалентность множеств.
О п р е д е л е н и е . Два множества, М и N, называются эквивалентными (обозначение М ~ N), если между их элементами можно
установить взаимно однозначное соответствие.
Всякое бесконечное множество эквивалентно некоторому своему
собственному подмножеству.
Это свойство можно принять за определение бесконечного множества.
4.Несчетность множества действительных чисел.
Т е о р е м а 1 .Множество действительных чисел, заключенных
между нулем и единицей, несчетно.
5.Теорема Кантора—Бернштейна. Следующая теорема является
одной из основных в теории множеств.
Т е о р е м а 2 (Кантор-Бернштейн). ПустьАи В— два произвольных
множества. Если существуют взаимно однозначное отображение f
множестваА на подмножество В1 множества В и взаимно однозначное
отображение g множества В на подмножество А1 множества А, то А и В
эквивалентны.
6.Понятие мощности множества.Если эквивалентны два конечных
множества, то они состоят из одного и того же числа элементов. Если же
эквивалентные между собой множества МиN произвольны, то говорят, что
М иN имеют одинаковую мощность. Про множества, эквивалентные множеству всех действительных чисел отрезка [0, 1], говорят, что они имеют
мощность континуума. Эта мощность обозначается символом с (или
символом ).
Раздел 2. Комбинаторика.
Тема 1.Комбинаторные конфигурации.
Комбинаторика – раздел математики, посвященный решению задач выбора
и расположения элементов некоторого, обычно конечного, множества в
соответствии с заданными правилами. Каждое такое правило определяет
способ построения некоторой конструкции из элементов исходного
множества, называемой комбинаторной конфигурацией. Поэтому целями
комбинаторного анализа являются изучение комбинаторных конфигураций,
алгоритмов их построения, оптимизация таких алгоритмов, а также решение
13
задач
перечисления.
Простейшими
примерами
комбинаторных
конфигураций являются перестановки, размещения, сочетания и разбиения.
При подсчете комбинаторных конфигураций используются правила суммы,
произведения и степени.
При подсчете числа объектов с наперед заданными свойствами
используются следующие два правила.
Правило суммы. Если объект U может быть выбран m способами, а объект
V k способами, то выбор «либо U , либо V » может быть осуществлен m  k
способами.
Правило произведения. Если объект U может быть выбран m способами и
после каждого из таких выборов объект V в свою очередь может быть
выбран k способами, то выбор « U и V » в указанном порядке может быть
осуществлен mk способами.
i
Набор элементов i i
из множества A  a1 , a2 ,..., an  называется
выборкой объема k из n элементов или ( n, k ) -выборкой.
Выборка называется упорядоченной, если порядок следования элементов
в ней задан. Две упорядоченные выборки, различающиеся лишь порядком
следования элементов, считаются различными. Если порядок следования
элементов не является существенным, то выборка называется
неупорядоченной.
В выборках могут допускаться или не допускаться повторения
элементов.
Рассмотрим некоторые комбинаторные объекты и их комбинаторные
числа.
Размещения.Размещением элементов из A по k (или размещением из n
элементов по k) называется упорядоченная ( n, k ) -выборка, в которой
элементы попарно различны.
A  a, b, c k  2
Пример 1. Пусть
и
. Выпишем все размещения из этого
множества по два:
a, b , b, a  , a, c  , c, a  , b, c  , c, b .
a 1 , a 2 ,..., a k
Обозначим число размещений из n по kчерез n k . Для подсчета числа n k
используем правило произведения. При построении конкретного размещения
первым элементом в нем можно взять любой из 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 .
14

 . Выпишем все перестановки этого
Пример 2. Пусть
множества:
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
A  a , b, c
элементов по k) неупорядоченная ( n, k ) -выборка, в которой элементы
попарно различны.
Пример 3. Пусть A  a , b, c и k  2 . Выпишем все сочетания из этого
множества по два:
a, b , a, c  , b, c  .
В сочетании, в отличие от размещения, порядок следования элементов
не учитывается. Поэтому из одного сочетания из n элементов по k получается
k! размещений. Отсюда для числа
n
 
k
сочетаний из n элементов по k
получается формула
 n  n k
n!
  

k!
k!n  k ! 0  k  n
k
,
.
Из последней формулы следует
 n
   1  n    n 
  

 n
и k  n  k  .
0  n
      1
k

0
При
полагают  0   0  . При k  n полагают
k  n не
существует сочетаний из
Наряду с обозначением
n
 
k
n
n
   0
k
,
поскольку при
элементов по .
k
k
C
n
часто используется обозначение
.
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
      ...     ...     2 n
 0 1
k
n
;
При
(2)
x  1 получим
n  n
 n
      ...  ( 1) n    0
0 1
 n
.
При четномn из соотношений (2) и (3) следуют тождества
15
(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  1  n  1 
   
  

 k   k   k  1
 n n
 n
      ...     2 n 1
1
3
   
 n
.
n
 
k
выполняется тождество
.
Из последнего тождества вытекает эффективный способ реккурентного
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
, если n нечетно.
Размещения с повторениями.Размещением с повторениями элементов
из A по k (или размещением с повторением из n элементов по k)
упорядоченная ( n, k ) -выборка, в которой элементы могут повторяться.

 и k  2 . Выпишем все размещения с
Пример 4. Пусть
повторениями из этого множества по два:
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 называется
A  a , b, c
B k  2k
k
k
B
единичным -мерным кубом и обозначают .
.
Пример 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).
16
Сочетания с повторениями.Сочетанием с повторениями элементов из
A по k (или сочетанием с повторением из n элементов по k)
неупорядоченная ( n, k ) -выборка, в которой элементы могут повторяться.

 и k  2 . Выпишем все сочетания с
Пример 5. Пусть
повторениями из этого множества по два:
a, b , a, c  , b, c  , a, a  , b, b , c, c  .
Можно показать, что число сочетаний с повторениямииз n элементов по
A  a , b, c
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 = qan определяет геометрическую прогрессию.
3. Формула аn+2 = аn+1 + аn задает последовательность чисел Фибоначчи.
В случае, когда рекуррентное соотношение линейно и однородно, т.е.
выполняется соотношение вида
аn+k + p1an+k-1 + ... + pkan = 0
(5.4)
(p = const), последовательность a0,a1,a2, ... называется возвратной.
Многочлен
Ра ( х )  х k  p1 x k 1  ...  p k
(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  c 2 n2  ...  c k nk , где с1,с2,…,сk – произвольные константы.
3. Если i - корень кратности ri( i = 1,…,s ) характеристического
многочлена (5.5), то общее решение рекуррентного соотношения (5.4) имеет
s
вид a n   (ci1  ci 2 n  ...  cir n r 1 )in , где сij – произвольные константы.
i
i
i 1
Зная общее решение рекуррентного уравнения (5.4), по начальным
условиям а0,а1,…,аk можно найти неопределенные постоянные сij и тем
самым получить решение уравнения (5.4) с данными начальными условиями.
17
П р и м е р 5.6.2. Найти последовательность {аn}, удовлетворяющую
рекуррентному соотношению an  2  4a n1  3a n  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  p1a n  k 1  ...  p k a n  f (n), n  0,1,...
(5.6)
Пусть {bn} – общее решение однородного уравнения (5.4), а {сn} – частное
(конкретное)
решение
неоднородного
уравнения
(5.6).
Тогда
последовательность {bn + сn} образует общее решение уравнения (5.6), и тем
самым справедлива.
Теорема
5.6.2.
Общее
решение
неоднородного
линейного
рекуррентного уравнения представляется в виде суммы общего решения
соответствующего однородного линейного рекуррентного уравнения и
некоторого частного решения неоднородного уравнения.
Таким образом, в силу теоремы 5.6.1. задача нахождения общего
решения рекуррентного уравнения (5.6) сводится к нахождению некоторого
частного решения.
В отдельных случаях имеются общие рецепты нахождения частного
решения.
Если f (n)   n (где  не является характеристическим корнем), то,
подставляя a n  c n в (5.6), получаем c(  k  p1  k 1  ...  p k )   n   n и
отсюда c  Pa (b)  1, т.е. частное решение можно задать формулой a n 
1
  n.
Pa (  )
Пусть f(n) – многочлен степени r от переменной n, и число 1 не
является характеристическим корнем. Тогда Pa (1)  1  p1  ...  p k  0 и частное
r
решение следует искать в виде a n   d i n i . Подставляя многочлены в формулу
i 0
(5.6),
получаем
r
r
 d (n  k )
i
i 0
i
r
r
 p i  d i (n  k  1) i  ...  p k  d i n i   d i ((n  k ) i  p1 (n  k  1) i  ...  p k n i ) 
i 0
i0
i 0
r
  d i ( g 1n i  ...)  f (n).
i 0
Сравнивая коэффициенты в левой и правой частях последнего равенства,
получаем соотношения для чисел di, позволяющих эти числа определить
П р и м е р 5.6.3. Найти решение уравнения
an 1  2a n  n  1
с начальным условием a 0  1.
Рассмотрим характеристический многочлен Ра(х) = х + 2. Так как Ра(х)
= 3  0 и правая часть f(n) уравнения (5.6) равна n + 1, то частное решение
будем искать в виде с n  d 0  d1 n. Подставляя сn в уравнение (5.7), получаем
(d 0  d1 (n  1))  2(d 0  d1n)  = (3d 0  d1 )  3d1  n  1  n . Приравнивая коэффициенты
18
в левой и правой частях последнего равенства, получаем систему
3d 0  d 1  1,

3d 1  1,
2
9
1
3
откуда находим d 0  , d1  . Таким образом, частное решение уравнения
2 1
9 3
уравнения a n 1  2a n  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  . Таким образом, a n   n  (2) n .
9
9
9 3
9
(5.7) имеет вид cn   n. По теореме 5.6.1. общее решение однородного
Тема 3.Производящие функции.
Для решения комбинаторных задач в некоторых случаях можно
использовать методы математического анализа. В качестве примера
рассмотрим основную идею метода производящих функций.
a , a , a ,..., a ,...
0 1 2
k
Пусть имеется последовательность чисел
и
k (x)
последовательность функций
. Этой последовательности сопоставим

 a  ( x)
k k
формальный ряд
(для конечных последовательностей этот ряд
превращается в многочлен). В ряде случаев, например, при определенных
ограничениях, данный ряд может оказаться сходящимся и задавать
k 0

F ( x) 
некоторую
функцию
F (x)
:
 a  ( x)
k k
k 0
.
Эта
функция
называется
a 
k
последовательности
относительно
 (x)
последовательности функций k
.
k
k
 (x)
В качестве k
обычно используют x и x / k! .
В качестве примера применения производящих функций установим с их
использованием следующее комбинаторное тождество:
производящей
для
n
 2n 
 n
  
 
 n  k 0  k 
2

.
Прежде всего, заметим, что из формулы бинома Ньютона
n
n
(1  x ) 
n k
  x
k
k 0  

n
следует, что функция (1  x) является производящей для биномиальных
n
2n
n
коэффициентов. Возьмем тождество (1  x )  (1  x ) 1  x  и разложим
2n
n
функции (1  x) и (1  x) в левой и правых частях этого тождества по формуле
бинома Ньютона:
19
2n
n
n
 2n  i 
 n  k 
 n  k 
  x 
  x
  x


i 
k  
k


i 0
 k 0
 k  0    .


Сравнивая коэффициенты при
тождества, получаем
xn

в левой и правой частях последнего
n
n


 2n 
 n  n 
n
  
 
 
 
 n  k  0  k  n  k  k 0  k 
2
.
Раздел 4. Графы.
Тема 1. Основные определения.
Теория графов,
как раздел дискретной математики, имеет
многочисленные предметные интерпретации. Теория графов применяется
при анализе функционирования сложных систем, таких как сети железных
дорог, телефонные или компьютерные сети, ирригационные системы. Эта
теория традиционно является эффективным аппаратом формализации задач
экономической и планово-производственной практики, применяется в
автоматизации управления производством, в календарном и сетевом
планировании.
Среди дисциплин и методов дискретной математики теория графов и,
особенно алгоритмы на графах, находят наиболее широкое применение в
программировании.
Графом G = (U, V) называется совокупность двух множеств — непустого
множества U и множества V  U2- бинарного отношения, определённого на
множестве 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. Если в графе имеются как ориентированные так и неориентированные
ребра, то граф называется смешанным.
20
5. Если элементом множества V может быть пара одинаковых (не
различных) элементов U, то такой элемент множества V называется
петлей, а граф называется графом с петлями (или псевдографом).
6. Если V является мультимножеством (т.е. множеством, содержащим
несколько одинаковых элементов), то эти элементы называются кратными
ребрами, а граф называется мулътиграфом.
7. Если
элементами
множества
Е
являются
не
обязательно
двухэлементные, а любые подмножества множества V, то такие
элементы множества Е называются гипердугами, а граф называется
гиперграфом.
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, aaiпредшественником aj. Вершины ai и ajназываются смежными, если Aij= 1
или Аji=1.
Если G — мулътиграф, то в матрице смежности aэлемент Aijпо определению
равен числу дуг, исходящих из вершины ai и заходящих в вершину aj .
4.Если число вершин графа G равно n, а число ребер – m, то матрицей
инцидентности В= (Bij) мультиграфаG называется матрица размера mxn:
.
5.Информацию о весах дуг во взвешенном графе можно представлять в виде
матрицы весов W = (wij), где wij — вес дуги (ai,aj), если дуга (ai,aj)
21
существует, а для несуществующих дуг веса обычно помечают нулем или
знаком ∞, в зависимости от приложений.
6.Если граф G = (М, R) является разреженным, т. е. число дуг |R|
достаточно мало по сравнению с числом вершин |М|, то более
эффективным, чем с помощью матрицы смежности, является
представление дуг графа посредством списка дуг. Этот список задается
двумя наборами т = (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() = Г+().
22
Обозначим минимальную степень вершины графа G через δ(G), а
максимальную — через ∆(G)
Тема 2.Связность.
Маршруты, цепи, циклы.
Маршрутом в графе называется чередующаяся последовательность вершин
и ребер v0,e1,v1,e2,v2,...,ek,vk, в которой любые два соседних элемента
инцидентны.
Это определение подходит также для псевдо-, мульти- и орграфов. Для
«обычного» графа достаточно указать только последовательность вершин
или только последовательность ребер.
Если 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)=maxd(xi, xj)называется эксцентриситетом вершины х. Максимальный
из всех эксцентриситетов вершин называется диаметром графа и
обозначается d(G). Минимальный из эксцентриситетов вершин графа
называется его радиусом и обозначается через r(G). Вершина к называется
периферийной, если ее эксцентриситет равен диаметру графа, т. е. е(х)= d(G).
Простая цепь, расстояние между концами которой равно d(G), называется
диаметральной цепью.
Теорема.Длялюбого связного графа G справедливо неравенство d(G) rankG.
Эйлеровы и Гамильтоновы графы.
Эйлеровой цепьюназывается цепь, проходящая по всем ребрам графа.
23
Эйлеровым циклом называется эйлеровая цепь, начинающаяся и
заканчивающаяся в одной вершине.
Эйлеровым графомназывается граф, содержащий Эйлеров цикл.
Теорема: Для того чтобы связанный граф был Эйлеровым, необходимо и
достаточно, чтобы степени всех вершин были четны
Данная теорема позволяет решить задачу о Кенигсбергских мостах.
Следствие: Для того чтобы граф содержал Эйлеровую цепь, необходимо и
достаточно, чтобы две вершины имели нечетную степень. При этом в одной
из вершин цепь будет начинаться, в другой – заканчиваться.
Граф называется гамильтоновым, если в нем имеется простой цикл,
содержащий каждую вершину этого графа.
Сам такой цикл также называется гамильтоновым.
Гамильтоновойназывается и простая цепь, содержащая все вершины графа.
Очевидно, что любой граф, ребра которого образуют простой цикл, является
гамильтоновым.
Несмотря на схожесть задач о нахождении эйлеровых и гамильтоновых
циклов, решение последней значительно сложнее.
Известны следующие достаточные условия существования гамильтоновых
циклов в связном неорграфе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, называется древовидным.
В ациклическом графе Gz(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 соединяет единственная
простая цепь;
24
5)G — ациклический граф, такой, что если какую-либо пару егo несмежных
вершин соединить ребром, то полученный граф будет содержать ровно
один цикл
Обходы графа по глубине и ширине.
При решении прикладных задач часто возникает необходимость обхода
вершин графа,
связанная с поиском вершин, удовлетворяющих
определенным свойствам.
Пусть 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
25
относительно остова Г.
Отметим, что мощность фундаментального множества циклов равна
цикломатическому числу 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 называется простым разрезом или коциклом,
если любое непустое собственное подмножество К' множества К не
является разрезом ни по какому разбиению.
Другими словами, изК нельзя удалить ни одно ребро с тем, чтобы
полученное множество было непустым разрезом.
Теорема.В конечном неорграфе G = (М,R), имеющем с компонент,
связности, множество ребер К тогда и только тогда является коциклом,
26
когда граф (M,R\K) имеет (с + 1) компонент связности.
Понятия остова и коцикла являются противоположными в том смысле, что
остову соответствует минимальное множество ребер, которые связывают
посредством маршрутов все вершины связного графа, а коцикл состоит из
минимального множества ребер, отделяющих некоторые вершины связного
графа от остальных
Тема 4. Планарность графов.
Ранее уже отмечалось, что возможно несколько изображений одного графа,
поскольку все изоморфные графы несут одну и ту же информацию.
На практике при изготовлении микросхем необходимо выяснить, можно ли
схему радиоэлектронного устройства, которая представляет собой граф,
изобразить на плоскости без пересечений проводников.
Аналогичная задача возникает при проектировании железнодорожных и
других путей, где нежелательны переезды.
Таким образом, возникает задача построения и исследования плоского графа.
Плоским называется граф, вершины которого являются точками
плоскости, а ребра— непрерывными плоскими линиями без самопересечений,
причем никакие два ребра не имеют общих точек, кроме инцидентной им
обоим вершины.
Любой граф, изоморфный плоскому графу, называется планарным.
Все планарные графы укладываются на плоскости (имеют плоскую укладку).
Очевидно, что
 всякий подграф планарного графа планарен,
 граф планарен тогда и только тогда, когда каждая связная
компонента этого графа — планарный граф.
Граньюпланарного графа называется множество точек плоскости, каждая
пара которых может быть соединена плоской кривой, не пересекающей ребер
этого графа.
Границейграни называется множество вершин и ребер, принадлежащих этой
грани.
Например, граф G на рис. имеет восемь граней: Г1,Г2,...,Г8. Неограниченная
грань Г называется внешней, а остальные грани Г2,Г3,...,Г8 —внутренними.
Пусть n,m,f — соответственно число вершин, ребер и граней планарного
графа.
Теорема (теорема Эйлера). Для всякого связного планарного графа верно
равенство n-m +f = 2.
Два графа называются гомеоморфными, если они оба могут быть получены
из одного и того же графа подразбиением его ребер. На рис. Изображены
исходный граф G и два гомеоморфных графа G1 и G2.
Рис. Гомеоморфизм графов.
Теорема. (теорема Понтрягина —Куратовского). Граф планарен тогда и
только тогда, когда он не содержит подграфов, гомеоморфных К5или К33.
Эквивалентная форма критерия планарности описана в следующей теореме.
Теорема. Граф планарен тогда и только тогда, когда в нем нет подграфов,
стягиваемых (т. е. получаемых последовательностью отождествлений
27
вершин, связанных ребрами) к графам К5 или К33.
Для непланарных графов вводятся характеристики, представляющие ту или
иную меру непланарности.
Если граф непланарен, то для его геометрической реализации удаляют
отдельные ребра (переносят их на другую плоскость).
Наименьшее число ребер, удаление которых приводит к планарному графу,
называется числом планарности или искаженностъюsk(G) графа G.
Для числа планарности полного графа справедлива следующая формула:
Важнейшая характеристика непланарного графа— его толщинаt(G) —
наименьшее число планарных подграфов графа G, объединение которых дает
сам граф.
Толщина графа равна минимальному числу плоскостей t, при котором граф
Gразбивается на плоские части Gl,G2,...,Gl.
Очевидно, что толщина планарного графа равна единице.
для толщины связного (n,т) графа справедливы такие оценки
где [...] — Целая часть числа, а ]..[= [...]+1.
Тема 5. Раскраска графов.
Задачи раскраски вершин и ребер графа занимают важное место в истории
развития теории и в самой теории графов. К построению раскрасок сводится
целый ряд практических задач, например, задачи составления расписаний,
распределения оборудования, проектирования некоторых технических
изделий.
Задача раскрашивания графов, имеет также неожиданно широкое
применение в программировании, особенно при решении фундаментальных
теоретических проблем
Пусть G = (S,U) — неориентированный граф.
Раскраской графа называется такое приписывание цветов его вершинам,
что никакие две смежные вершины не получают одинакового цвета.
Таким образом, множество вершин одного цвета является независимым
множеством.
Хроматическим числом
графа G называется минимальное число цветов,
требующееся для раскраски G . Если = k, то граф называется kхроматическим.
В теории хроматических графов существует так называемая гипотеза
четырех красок, которую некоторые авторы с полным основанием называют
«болезнью четырех красок».
Попытки обосновать эту гипотезу привели к ряду интересных результатов не
только по раскраске графов, но и по ряду других разделов теории графов.
Легко найти хроматические числа некоторых известных графов, например,
Обозначим через P(G) наибольшую из степеней вершин графа G
ТеоремаДля любого неориентированного графа G выполняется неравенство
28
 (G) P(G) +1.
Следующая теорема связывает хроматическое число графа с количеством его
вершин и ребер.
ТеоремаДля любого связного (n,т)- графа G верны неравенства
где [...] — целая часть, а {..} — дробная часть числа.
Теорема.Для любого n-вершинного графа G верно неравенство
Проблема раскраски планарных графов является одной из самых знаменитых
проблем теории графов. Она возникла из задачи раскраски географической
карты, при которой любые две соседние страны должны быть окрашены в
различные цвета. Эта задача легко сводится к задаче раскраски планарного
графа.
В 1879 г. английский математик Кэли четко сформулировал гипотезу
четырех красок, которую некоторые авторы с полным основанием называют
«болезнью четырех красок».
Попытки обосновать эту гипотезу привели к ряду интересных результатов не
только по раскраске графов, но и по ряду других разделов теории графов.
Гипотеза четырех красок.Всякий планарный граф 4-раскрашиваем.
Попытки доказать эту гипотезу привели в 1890г. к появлению теоремы
Хивуда.
Теорема.Всякий планарный граф 5-раскрашиваем
Трудность проблемы четырех красок привела к появлению большого числа
равносильных ей формулировок.
В конце 60-х гг. прошлого века эта проблема была сведена к исследованию
большого, но конечного множества так называемых неустранимых
конфигураций, число которых оказалось равно 1482
В 1976 г. научному коллективу под руководством К. Аппеля и В. Хейкена
удалось с использованием ЭВМ правильно раскрасить все графы из
множества неустранимых конфигураций, затратив на это около 2000 часов
машинного времени.
Таким образом, хотя такое доказательство очень сложно повторить, можно
считать, что формально гипотеза четырех красок доказана.
В заключение рассмотрим очень простой алгоритм последовательной
раскраски графа.
Этот алгоритм в общем случае не приводит к минимальной раскраске.
Только для некоторых классов графов, например полных k-дольных,
последовательная раскраска минимальна.
Алгоритм последовательной раскраски содержит два правила:
1) Произвольной вершине х графа G присваивается цвет 1.
2) Если вершины x1,x2,…,xiраскрашены kцветами 1,2,…,k , k<i, то новой
29
произвольно взятой вершине хi+1приписывается минимальный цвет, не
использованный при раскраске вершин из ее окружения.
Теорема (теорема Кенига).Граф двуцветен тогда и только тогда, когда он не
содержит нечетных простых циклов.
Заключение.
5.3. Краткое описание лабораторных работ
Учебным планом не предусмотрены
5.4. Краткое описание практических занятий
5.4.1.Перечень практических занятий
Все практические занятия проводятсяс элементами интерактивных
занятий, которые можно разделить на два типа.
1.Занятие, как правило, начинается с устного теоретического опроса, в
котором принимают участие все студенты. Далее следует групповое
решение задач(групповая дискуссия): один студент решает у доски,
остальные контролируют и обсуждают.
В конце занятия подводится итог. Обсуждаются рассмотренные на
занятии задачи. Выставляются оценки (совместно со студентами).
2.Группа разбивается на подгруппы(2-3). Каждой группе выдаются задания.
Для выполнения заданий выделяется время (45-60мин.). Далее проверяется
выполнение заданий у нескольких человек из группы (как правило «слабых»
студентов) с подробными объяснениями. За положительный ответ
выставляются баллы. В подгруппе, получившей определенное количество
баллов, все студенты получают зачет по этой теме
Занятие 1. Основные понятия. Операции над множествами. Булева алгебра
подмножеств.( Раздел 1. Тема 1.) (интерактив. 1)
Занятие 2. Бинарные отношения. ( Раздел 1. Тема 2.)(интерактив. 1)
Занятие 3.Функции.( Раздел 1. Тема 2.)(интерактив. 1)
Занятие 4.Отношения эквивалентности и порядка.( Раздел 1. Тема
2.)(интерактив. 1)
Занятие 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)
30
Занятие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. Доказать основные тождества алгебры множеств, используя
диаграммы Венна.
5. Упростить предложенные выражения над множествами.
6. Описать для предложенных множеств покрытия и разбиения.
7. Выписать множество всех подмножеств предложенного множества.
8. Считая универсальным множество всех четырехугольников на
плоскости, рассмотреть результаты операций над подмножествами этого
множества (параллелограммы, прямоугольники, квадраты, ромбы).
9. Проверить выполнение основных алгебраических тождеств для
прямого (декартова) произведения множеств.
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий: Следует уделить внимание
использованию нотации теории множеств, четкому и однозначному
использованию знаков и формул. При решении задач указать на
31
использование разных подходов для получения решения.
Требования к отчётным материалам.Правильно (с комментариями)
оформленные решения задач.
Занятие 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.
2.
3.
4.
5.
6.
7.
8.
Р
Q
{(a,1),(a,2),(b,3),(c,2),(c,3),(c,4)}
{(a,1),(a,2),(a,4),(c,3),(c,2),(c,4)}
{(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),(2,1),(2,2),(2,3),(2,4),(3,3),(4,4)}
{(2,1),(3,1),(3,2),(4,1),(4,3)}
{(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}
32
3
4
5
6
7
8
9
10
P = {(x,y)| x,yRи x + y 0}
P = {(x,y)| x,yRи x = y2}
P = {(x,y)| x,yRи x2 = y}
P = {(x,y)| x,yRиx2+y 2=1}
P = {(x,y)| x,yZ и x-y кратно 2}
P = {(x,y)| x,y Z и 2x=3y }
P = {(x,y)| x,yZиx+y нечетно}
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. Дайте определение функции (отображения).
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.Самостоятельное
33
решение задач.
Рекомендации по выполнению заданий:Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчётным материалам.Правильно (с комментариями)
оформленные решения задач.
Занятие 4. Отношения эквивалентности и порядка.
Цель занятия: Освоение понятий «Отношения эквивалентности и
порядка». Выработка навыков решения задач по теме.
1.
2.
3.
4.
5.
6.
Задания на занятия:
Какое бинарное отношение называется отношением эквивалентности?
Что называется разбиением множества А?
Что называется смежным классом множества А? Сформулируйте теорему
о разбиении множества отношением эквивалентности.
Что называется фактор-множеством множества А?
Какое бинарное отношение называется отношением порядка? Дайте
определение нестрого, строгого, частичного, полного порядка.
Дайте определение минимального элемента.
1. На множестве N и N×Nопределены следующие отношения:
Р={(a,b)/(a-b) делится на 3};
Q={(a,b),(c,d)/ad=bc},
Доказать, что 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.Самостоятельное
решение задач.
Рекомендации по выполнению заданий:Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
34
Требования к отчётным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 5. Мощность множества.
Цель занятия: Освоение понятия «мощность множества». Выработка
навыков решения задач по теме.
Задания на занятия:
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий:Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
.
Требования к отчётным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 6. Контрольная работа
Цель занятия: Промежуточный контроль знаний.
Задания на занятия:
1. Изобразить множество D с помощью кругов Эйлера.
(А 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
студентов, если
а)Распределяютсябилетывразныекинотеатрынаодноитожевремя,
тоестькаждыйстудентможетполучитьнеболееодногобилета.
б)Распределяютсябилетынаразныесеансывразличноевремя,
тоестькаждыйстудентможетполучитьлюбоечислобилетов.
35
в)Распределяютсяравноценныебилетынаодинитотжесеанс.
2.
Сколькимиспособамиможнорасставить 10 человеквколонну,
такчтобыдля
каждогочеловека,
кромепервогоипоследнего,
переднимипозадинегобылчеловеклибобольшегороста, либоменьшегороста.
3.
Сколькосуществуетразличныхматрициз
n
строки
m
столбцовсостоящихизнулейиединиц.
4.
Сколькосуществуетразличныхматрициз
n
строки
m
столбцовсостоящихизнулейиединицвкоторыхвсестрокиразличны.
5.
Сколькимиспособамиможнопостроитьдевятьчеловеквтриколонны
потри
человека,
есливкаждойколоннелюдистоятпоростуинетдвухчеловекодинаковогороста.
6.
Сколькострокизнулейиединицдлины
n
можнозаписатьприусловиичтоникакиедвеединицынестоятрядом.
7.
Найтиколичествоперестановоквсехчиселот 1 до 9, такихчто,
соседниечислаотличаютсяболеечемна 1.
8.
Найтиколичествоперестановоквсехчиселот
1
до
9,
такихчтоникакоечислонестоитнасвоемместе.
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мин.).
Далее проверяется выполнение заданий у нескольких человек из группы (как
правило «слабых» студентов) с подробными объяснениями. За
36
положительный ответ выставляются баллы. В подгруппе, получившей
определенное количество баллов, все студенты получают зачет по этой теме
Рекомендации по выполнению заданий: При решении задач указать на
использование разных подходов для получения решения, например
основного закона комбинаторики или одной или нескольких
комбинаторных схем перестановок, размещений или сочетаний.
Требования к отчётным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 9.Бином Ньютона. Полиномиальная формула. Метод включений и
исключений.
Цель занятия: Освоение методов решения задач комбинаторики.
Задания:
1. Определить, сколько рациональных членов содержится в разложении:
a)
( 2  3 3 ) 20 ;
b)
(3 6  4 2 )100 .
2. Найти коэффициент при tk в разложении:
a)
(2+t4 +t7 )15, k = 17;
b)
(2 + t – 2t3)20, k = 10.
3. Какое число больше: 9950+10050 или 10150?
4. Пусть nи m - целые положительные числа. Доказать
a)
b)
c)
5. Доказать, что для любого m= 0,1,2,...,псправедливо
тождество
6. Доказать, что
7. Доказать тождества:
a)
b)
8. Доказать, что
9.
Найти производящие функции следующих последовательностей:
37
a) a n  n n , n  0,1,2,...;
0, n  0,

b) an   n
 , n  1,2,....
 n!
10. Найти общий член an последовательности, для которой функция fa(t)
является производящей:
a)
f a (t )  (q  pt ) m ;
b)
 t2
f a (t )  1 
2

m

 .

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.
15.
Показать, что если n=30m, то количество целых положительных
чисел, не превосходящих nи не делящихся ни на одно из чисел 6, 10, 15,
равно 22m.
16.
Сколькими способами можно расположить за круглым столом
nсупружеских пар так, чтобы мужчины и женщины чередовались и никакие
двое супругов не сидели рядом?
17.
В букинистическом магазине лежит 6 экземпляров романа
И.С.Тургенева «Рудин», 3 экземпляра его же романа «Дворянское гнездо» и 4
экземпляра романа «Отцы и дети». Кроме того, есть 5 томов, содержащих
романы «Рудин» и «Дворянское гнездо», и 7 томов, содержащих романы
«Дворянское гнездо» и «Отцы и дети». Сколькими способами можно сделать
покупку, содержащую не менее, чем по одному экземпляру каждого из этих
романов?
Ход занятия:Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Основные рекомендации по выполнению заданий:Использовать
конспекты лекций и другие теоретические источники, образцы решения
задач, объяснения преподавателя.
Требования к отчётным материалам:Правильно (с комментариями)
оформленные решения задач.
38
Занятие 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) шаров, записывают их номера, а затем шары возвращаются обратно
в урну. Можно составить (Cms ) d различных наборов, получающихся в
результате d извлечений. Найти число наборов, в которых
a)
встречаются все шары;
b)
ровно r (0≤r≤m) шаров не встречается.
23.
Вычислить
S 
k
2
,
2 k
где суммирование проводится по всем
натуральным k’, не кратным 2, 3 и 5.
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.
Рекомендации по выполнению заданий:Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчётным материалам.Правильно (с комментариями)
оформленные решения задач.
Занятие 11. Контрольная работа
Цель занятия: Промежуточный контроль знаний.
Задания на занятия:Пример задания:
1. Сколькими способами можно расставить на полке 7 книг, если а) 2
определенные книги должны стоять рядом б) эти 2 книги не должны
стоять рядом.
2. В течение 10 недель студенты сдают 10 экзаменов в том числе два по
математике. Сколькими способами можно распределить экзамены по
неделям так, чтобы экзамены по математике не следовали один за
другим?
39
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 ребрами.
г. Связный планарный граф с 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. Групповое решение
40
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.Занятие проводится по сценарию типа 1 (типа 2).
Рекомендации по выполнению заданий:Рассмотреть способы
представления графов в памяти компьютера для решения различных задач и
алгоритмов. Осуществить подготовку данных для лабораторной работе по
алгоритмам.
Требования к отчётным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 13. Операции над графами
Цель занятия: Выработка навыков решения задач по теме.
Задания на занятия:
1. Какие операции над графами можно выполнять? Дайте определения
этих операций.
2. На рис.2 приведены графы G1и G2. Найти G1  G2и G1×G2.
x1
x2
G 1:
x1
x1
x4
x3
G 2:
G 1:
G 2:
x3
x4
x2
x1
x2
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
x7
x6
x4
x5
x4
41
x8
x7
x6
x5
x8
x5
2. Найти эксцентриситеты вершин, радиусы и диаметры графов,
периферийные, центральные вершины и диаметральные цепи графов,
приведенных на рис. 1.
x1
x2
x3
x4
x1
x8
x7
x6
x5
x8
Рис. 1
x2
x3
x7
x6
x4
x5
3. Упорядочить вершины и дуги орграфов, изображенных на рис.2,
графическим и матричным способом (дуги – только графическим).
x2
u1
x1
u6
u4
u3
x4
x2
x3
u9
u2
u10
u11
u5
u7
u8
u1
x6
x1
u2
u7
u3
x4
x5
u5
u6
u4
u8
x3
x6
x5
Рис. 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').
42
1)
2)
2. Используя матричную теорему Кирхгофа, найти число остовных деревьев в
полном двудольном графе Km,n
3. Найти матрицы фундаментальных циклов, радиусы и диаметры
графов,изображенных на рис.
Ход занятия:Группа разбивается на подгруппы(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, то
43
граф имеет гамильтонов цикл.
11. По алгоритму Флери найти эйлеров цикл в графах, изображенных
на рис.
12.Найти наибольшее независимое множество вершин в графе Петерсена
13. Показать, что граф Петерсена не гамильтонов.
14. Найти число доминирования δ(G) инаименьшее доминирующее
множество графов, представленных на рис.
15. Построить дерево поиска клик, матрицу клик и найти наибольшие
клики графов, изображенных на рисунках 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. Сформулируйте теоремы о пяти и четырех красках.
44
11. Найти хроматическое число заданных графов
Ход занятия: 1. Теоретический опрос студентов. 2. Групповое решение
задач (на доске, с обсуждением всеми студентами). 3.Самостоятельное
решение задач.Занятие проводится по сценарию типа 1 (типа 2).
Рекомендации по выполнению заданий:Использовать конспекты лекций и
другие теоретические источники, образцы решения задач, объяснения
преподавателя.
Требования к отчётным материалам. Правильно (с комментариями)
оформленные решения задач.
Занятие 18. Контрольная работа
Цель занятия: Промежуточный контроль знаний.
Задания на занятия:Пример задания:
1. Даны графы G и G . Найдите G  G , G  G , G  G , G  G . Для графа
1
2
1
2
1
2
1
2
1
2
G1  G2 найдите матрицы смежности, инцидентности, сильных
компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из
вершины 1.
2. Найдите радиус и диаметр, минимальное множество покрывающих цепей
графа G . Является ли изображенный граф эйлеровым? Является ли
изображенный граф планарным? Найдите матрицы фундаментальных
циклов, фундаментальных разрезов. Найти хроматическое число графа.
3. Для графа G, заданного матрицей весов, построить минимальный по весу
остов G' и найти его вес ω(G').
Ход занятия.На контрольную работу отводится 2 часа.
Основные рекомендации по выполнению заданий. Первыми решаются
задачи, кажущиеся простыми.
Требования к отчётным материалам. Правильно (с комментариями)
оформленные решения задач.
5.5. Краткое описание видов самостоятельной работы
5.5.1.Общий перечень видов самостоятельной работы
1.
2.
Подготовка к практическим занятиям.
Домашние контрольные работы по темам «Теория множеств»,
«Комбинаторика» и «Теория графов». Индивидуальные задания
соответствуют задачам к практическим занятиям.
3.
Обзор
(доклад,
реферат,
презентация)
по
информации
специализированных сайтов разделов дискретной математики.
4.
Подготовка к зачету.
5.5.2 Методические рекомендации по выполнению каждого вида
самостоятельной работы
45
1.Подготовка к практическим занятиям.
Цель. Для продуктивной работы на занятиях необходимо проработать
теоретический материал.
Задание на СРС. Ответить на вопросы, приведенные в методических
указаниях к каждому занятию.
Требования к форме и содержанию отчетных материалов. Устный или
письменный ответ на поставленные вопросы.
Рекомендации по выполнению задания. Использовать лекционный материал
и рекомендованную литературу.
Рекомендуемый график выполнения отдельных этапов СРС. Расписание
занятий.
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Задать следующие ниже отношения. Определить какие из них
являются
транзитивными, симметричными, антисимметричными, рефлексивными.
Какие
из
отношений
являются
отношениями
порядка
и
46
эквивалентности?
Отношение ”учит” на множестве из двух преподавателей кафедры и
четырех студентов.
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 книги не должны стоять рядом.
2.4 Сколько различных 3-х буквенных слов можно образовать, используя
буквы составляющие вашу фамилию, причем эти слова должны начинаться
и оканчиваться согласными, а в середине должна стоять гласная буква.
2.5 Сколько различных 3-х буквенных слов можно образовать, используя
47
буквы составляющие вашу фамилию, причем эти слова должны начинаться
и оканчиваться согласными, а в середине должна стоять гласная буква.
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 станций. На каждом билете
печатаются названия станций отправления и прибытия. Сколько различных
билетов можно напечатать? Тот же вопрос, если каждый билет можно
использовать в любом направлении, т.е. безразлично, с какой из двух
станций Вы отправляетесь?
2.17 Каково число матриц из "n" строк и "m" столбцов с элементами из
{0,1} ? И при дополнительном условии, что строки матрицы попарно
различны?
2.18 8 человек должны расположиться в 2-ух комнатах, причем в
48
каждой должно быть по крайней мере 3 человека. Сколькими способами
это можно сделать?
2.19 Сколькими способами можно расположить в один ряд 5 красных
мячей, 4 черных и 5 белых мячей так, чтобы мячи, лежащие на краях, были
одного цвета?
2.20
Колода игральных карт насчитывает 52 различных карты.
Сколькими способами можно сдать 13 карт на руки одному игроку так,
чтобы у него оказалось ровно 2 туза ?
Теория графов
Для заданного графа выполнить следующие действия:
1. Заполнить матрицу смежности
2. Уложить на плоскости
3. Определить характеристические числа
4. Указать самый большой цикл
5 Определить является ли он эйлеровым и/или гамильтоновым.
49
Требования к отчетным материалам и документам.Контрольные работы
выполняются в отдельной тетради или сброшюрованных листах.
Указывается номер варианта и текст задания. Приводятся используемые
формулы для вычислений и список использованной литературы.
4.Обзор
(доклад,
реферат,
презентация)
по
информации
специализированных сайтов разделов дискретной математики и
программного обеспечения.
Цель работы. Поиск и анализ информации в электронных источниках.
Получение возможности использования доступного программного
обеспечения для решения задач дискретной математики.
Содержание заданий. Индивидуальные задания соответствуют разделам,
изучаемым в курсе, и являются подготовкой к выполнению лабораторных
работ.
Требования к отчетным материалам и документам.Текст работы
представляется в электронной форме в формате, позволяющем возможность
редактирования содержания. Доклад готовится с использованием слайдов
или других мультимедийных средств.
4. Подготовка к зачету
Цель работы: Системное представление знаний, полученных во время
лекционных и практических
занятий, а также при выполнении
индивидуальных заданий и контрольных работ.
Содержание задания: 1) Повторить способы решения задач по всем темам.
2) подготовить ответы на вопросы лекционного материала, которые
приведены в 7.3 – Контрольно-измерительные материалы для итоговой
аттестации по дисциплине.
Основные рекомендации по выполнению задания:
Использовать лекционный материал и рекомендованную литературу.
5.5.3 Описание курсового проекта (курсовой работы)
Учебным планом не предусмотрены.
50
6. Применяемые образовательные технологии
При реализации данной программы применяются инновационные
технологии обучения, активные и интерактивные формы проведения занятий,
указанные в таблице 2.
Таблица 2 - Применяемые образовательные технологии
Технологии
Интерактивные лекции
работа в команде
Групповая дискуссия
Виды занятий
Лекции Лаб.
раб.
2
Практ./
СРС
Сем. зан.
Курсовой
проект
2
2
7. Методы и технологии контроля уровня подготовки по дисциплине
7.1. Виды контрольных мероприятий, применяемых контрольноизмерительных технологий и средств.
1.Промежуточное тестирование с использованием программной системы
тестирования.
2.Демонстрация
и
тестирование
работоспособности
алгоритмов,
выполненных в ходе лабораторных занятий.
3.Экспресс-тестирование на лекции.
4. Оценка выполнения домашних контрольных работ.
5. Экзамен.
7.2. Критерии оценки уровня освоения учебной программы (рейтинг).
Текущий контроль успеваемости оценивается преподавателем и
заносится в журнал успеваемости.
По основным разделам дисциплины проводится промежуточное
тестирование с использованием программной системы тестирования,
проверка решения контрольных задач на практических заданий, домашних
контрольных работ.
До экзамена по дисциплине (семестр №2) допускаются студенты,
сдавшие все лабораторные работы и контрольные работы, предусмотренные
планом. При наличии сданных в срок лабораторных работ, активной работе
на лекции и практических занятиях, выполнении всех видов СРС, возможно
выставление
автоматического
экзамена
после
предварительного
собеседования с преподавателем (обычно в форме тестирования).
7.3.Контрольно-измерительные материалы и другие оценочные средства
для итоговой аттестации по дисциплине.
Пример тестовых заданий:
Тест А. Какой тип мощности имеет множество натуральных чисел?
Варианты ответов:
1) конечный
2) счетный
3) континуальный
Тест В. Укажите комбинаторную схему для задачи: Сколько
вариантов чисел, больших 3 000 000, можно записать, используя цифры 1,
1, 2, 2, 2, 3, 3?
51
Варианты ответов:
1) сочетания 2) размещения
повторениями
3) перестановки 4) перестановки с
Примеры билетов к коллоквиуму:
Билет А.
1) Упорядоченные выборки. Размещения. Перестановки. Число
упорядоченных выборок. Число размещений, перестановок.
Свойстваразмещений.
2)Графы. Способы задания графов. Маршруты, цепи, циклы.
Кратчайшиепути.
3) Отношение R на множестве всех книг библиотеки определили
следующим образом. Пара книг а и 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. Разбиения
52
19. Метод включений и исключений
20. Бином Ньютона и полиномиальная формула
21. Рекуррентные соотношения.
22. Возвратные последовательности
23. Метод производящих функций
Графы
24. Графы. Основные понятия и определения.
25. Способы задания графов.
26. Виды графов и операции над ними.
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с.
53
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
8.3.2.Ресурсы сети Интернет
1. http://www.intuit.ru/
2. http://www.edu.ru/
9.Рекомендуемые специализированные программные средства
1. FreePascal (свободно-распространяемый продукт)
2. Delphi 10
3. C++ Builder
4. MicroSoftOffice
10.Материально-техническое обеспечение дисциплины
Лекции по дисциплине проводятся в мультимедийном классе,
оборудованном проектором и экраном.
Лабораторные работы по дисциплине проводятся в компьютерном
классе ИрГТУ (24 ПК).
Промежуточное тестирование проводится с помощью разработанной на
кафедре вычислительной техники программной системы тестирования.
54
1/--страниц
Пожаловаться на содержимое документа