Методические указания к выполнению внеаудиторной работы по дисциплине « Дискретная математика»

Методические указания
самостоятельной внеаудиторной работе
по дисциплине
« Дискретная математика»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКАДисциплина «Дискретная математика» является общепрофессиональной дисциплиной, формирующей базовый уровень знаний для освоения специальных дисциплин. Преподавание дисциплины имеет практическую направленность.
В рабочей программе учебной дисциплины предусмотрена самостоятельная внеаудиторная работа с целью:
систематизации и закрепления, полученных теоретических знаний и практических умений;
углубления и расширения теоретических знаний;
формирования умений использовать специальную литературу;
развития познавательных способностей и активности студентов;
творческой инициативы, самостоятельности, ответственности и организованности;
формирования самостоятельности мышления, способностей к саморазвитию, самосовершенствованию и самореализации;
развития исследовательских умений.
Согласно учебному плану данная дисциплина проводится в 3 и 4 семестрах (II курс)). По итогам изученной дисциплины сдается экзамен. На изучение данной дисциплины отводится 121 час, из которых на самостоятельную внеаудиторную работу отводится 29 часов.
Самостоятельная внеаудиторная работа для студентов проводится в виде заданий:
для овладения знаниями:
чтение текста и выписки из текста (учебника, дополнительной литературы);
учебно-исследовательская работа;
для закрепления и систематизации знаний:
работа с конспектом лекции (обработка текста);
для формирования умений:
решение дополнительных задач.
Перечень заданий к самостоятельной внеаудиторной работе.
Раздел 1. « Основы теории множеств» (4 часа)
Решить задачи по данной теме.
Раздел 3. «Булевы функции». (8 часов).
Решить предложенные задачи.
Раздел 6. «Некоторые элементы теории и практики шифрования» (4 часа).
Найти ответы на вопросы.
Раздел 7. «Метод математической индукции» (3 часа).
Решить предложенные задачи.
Раздел 10. «Основы теории графов» (5 часов).
Решить предложенные задачи.
Раздел №11 « Элементы теории автоматов». (5 часов).
Решить предложенные задачи.
Итого 29 часов.
Раздел №1. Основы теории множеств.
Задание: изучить теоретический материал по данной теме и решить следующие задачи.
Цель: выработать умения решать задачи по данной теме.
Рекомендуемая литература:
лекционный материал
методические указания, в которых представлены примеры решения задач.
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. / М. С. Спирина, П. А. Спирин. – М.: Издательский центр Академия, 2004. – 368 с.
Алгоритм действий:
Прочитать лекционный материал
Рассмотреть примеры решения задач в данном пособии, записать их.
Самостоятельно решить предложенные задачи.
Оформить решения задач в соответствии с примерами.
Примеры решения задач.
Пример №1 «Вычисление множеств».
Пусть U={1, 2, 3, 4, 5, 6, 7, 8}, A={1, 2, 3, 4, 5}, B={2, 4, 6, 8}, C={1, 3, 5, 7}, D={1, 2, 4, 5, 7, 8}.
Найти (D \ A)(BC)(C∸D).
Решение
D \ A ={7, 8},
BC={1, 2, 3, 4, 5, 6, 7, 8},
(D \ A)(BC)={7, 8}{1, 2, 3, 4, 5, 6, 7, 8}={7, 8},
C ∸ D={2, 3, 4, 8},
(D \ A)(BC)(C∸D)={7, 8}{2, 3, 4, 8}={2, 3, 4, 7, 8}.
Пример №2 «Выражение множеств»:
Пусть U={1, 2, 3, 4, 5, 6, 7, 8}, A={1, 2, 3, 4, 5}, B={2, 4, 6, 8}, C={1, 3, 5, 7}, D={1, 2, 4, 5, 7, 8}.
Выразить через известные множества A, B, C, D множество {1, 5}.
Решение
AC={1, 3, 5},
C \ D={3},
(AC) \ (C \ D)={1, 3, 5}\{3}={1, 5}.
Пример №3 «Круги Эйлера (диаграммы Венна)».
а) Выразить через множества A, B, C множество Е, которому соответствует заштрихованная область.
B
A
C
Решение:
B
C
A
Так как заштрихованное множество на рис. 1 соответствует множеству AB, а множество на рис. 2 соответствует множеству BC, то множество Е есть объединение этих множеств.
Рис. 1
B
A
C
Рис. 2
То есть Е=(A B)(BC).
б) Выразить через множества A, B, C, D множество Е, которому соответствует заштрихованная область.
B
D
А
A
C

Решение:
Е=(A∸C) \ D. (По определению, напомним, X∸Y==)
Пример №4. Доказать следующее тождество
Доказательство: с помощью диаграмм Эйлера построим левую и правую части данного тождества:
1382395359410Левая часть:
1459865241935Правая часть:
Так как получили и слева, и справа одно и тоже, то тождество верно. Что требовалось доказать.
Задачи для самостоятельного решения:
Пусть U={1;2;3;4;5;6;7;8;9;10;11;12;13;14}, A={1;2;3;4;7;9}, B={3;4;5;6;11;12;13}, C={2;3;4;7;8;12;13;14}, D={1;7;14}.
Вычислить
А) \;
Б) ;
С)
2. Пусть U={1, 2, 3, 4, 5, 6, 7, 8, 9}, A={1, 2, 3, 4, 5, 9}, B={2, 4, 6, 8}, C={1, 3, 5, 7}, D={1, 2, 4, 5, 7, 8, 9}. Выразить через известные множества A, B, C, D следующие множества или доказать, что это сделать невозможно.
А) {7; 1; 4; 3; 8; 5; 9; 6};
Б) {1; 2; 6};
С) {5; 7; 1; 6};
3. Выразить через данные множества закрашенную область:
А)
Б)
Критерии оценки:
«5» - если решены все задачи (3)
«4» - если решены 2 задачи.
«3» - если решена одна задача.
Раздел 3. Булевы функции.
Задание: изучить теоретический материал по данной теме и решить следующие задачи.
Цель: выработать умения решать задачи по данной теме.
Рекомендуемая литература:
лекционный материал.
Методические указания, в котором представлены примеры решения задач.
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. / М. С. Спирина, П. А. Спирин. – М.: Издательский центр « Академия», 2004. – 368 с.
Алгоритм действий:
Прочитать лекционный материал. Выписать законы логики в тетрадь.
Рассмотреть примеры решения задач в данных методических указаниях, записать их. В примере №3 записать какие законы логики применялись при его решении.
Записать теоретические сведения в тетрадь, разобрать предложенные примеры по теоретическому материалу.
Самостоятельно решить предложенные задачи.
Оформить решения задач в соответствии с примерами.
Пример№1. Запишите символически следующие сложные предложения, употребляя буквы для обозначения простых компонентов предложения.
а) Если посылка истинна, а заключение ложно, то импликация ложна.
Решение:
Пусть А="посылка истинна", В="заключение ложно", С="импликация ложна". Тогда данное предложение символически можно записать в виде .
b) Если цепь С состоит из двух параллельно подключенных переключателей А и В, то по С идет ток в том и только в том случае, когда включен переключатель А или включен переключатель В.
Решение:
Пусть X="цепь С состоит из двух параллельно подключенных переключателей А и В", Y="по С идет ток", Z="включен А", V="включен B". Тогда данное предложение символически можно записать в виде .
Пример №2.
Построить таблицу истинности для высказывания .
Решение:
Пусть .
Заполним столбец таблицы, соответствующий , пользуясь тем, что=1,=0.
A B C F
0 0 0 1 1 1 0 0
0 0 1 0 0 1 0 1
0 1 0 1 1 0 1 1
0 1 1 0 0 0 1 1
1 0 0 1 1 0 1 1
1 0 1 0 1 0 1 1
1 1 0 1 1 1 0 0
1 1 1 0 1 1 0 0
Затем, на основе столбцов A и заполним столбец A, пользуясь тем, что 01=1, 00=0, 11=1, 10=1. На основе столбцов B и A заполним столбец , используя правило: 00=1, 01=0, 10=1, 11=1. Заполним столбец , причем будем ставить в некоторой строке 1, если в той же строке столбца BA стоит 0, и наоборот. Наконец, заполним последний столбец, используя данные столбцов A и и зная, что 10=0, а в остальных случаях импликация истинна.
Пример №3.
Привести к ДНФ высказывание .
Решение:
Высказывание приведено к ДНФ.
Пример №4.
Привести к СДНФ высказывание . По возможности упростить ее.
Решение:
Построим таблицу истинности высказывания F.
A B C AC F
0 0 0 0 0 1 0
0 0 1 0 0 1 0
0 1 0 1 0 0 1
0 1 1 1 0 0 1
1 0 0 1 0 0 1
1 0 1 1 1 1 0
1 1 0 1 0 0 1
1 1 1 1 1 1 0
F=A0B1C0A0B1C1A1B0C0A1B1C0=
Высказывание приведено к СДНФ. Полученную СДНФ можно упростить, приведя ее к более простой ДНФ.
.
Пример №5.
Привести данное высказывание к СДНФ, по возможности упростить:
xyF(x,y)
0
0
1
1 0
1
0
1 0
1
1
1
Решение:
xyF(x,y) элементарные произведения
0
0
1
1 0
1
0
1 0
1
1
1


Выберем те строки, в которых значение функции равно 1. В нашем случае это вторая, третья и четвертая строки. Для каждой строки запишем элементарные произведения следующим образом: если в этой строке значение переменной 0, то её запишем с отрицанием, в противном случае без отрицания. Запишем дизъюнкцию данных элементарных произведений. Полученное выражение и есть СДНФ

Упростим данное выражение:
СДНФ=xy+xy+xy=xy+xy+xy+xy=xy+x+xy=xy+xy+x=yy+y+x=x+yИтак. получим СДНФ=xy+xy+xy, ДНФ = x + yПриложение алгебры высказываний к исследованию электрических двухполюсников (теоретические сведения).
Приложение логики к электрическим схемам основано на нескольких простых соглашениях:
1. Если по цепи С идет ток, то мы будем писать С=1; если же по С ток не идет, то С=0.
2. Если цепь С состоит из двух последовательно подключенных переключателей А и В, то по С идет ток в том и только в том случае, когда включены А и В, то есть С=1 тогда и только тогда, когда А=1 и В=1:

Но теми же свойствами обладает конъюнкция, поэтому говорят, что последовательное соединение переключателей описывается конъюнкцией:
\* MERGEFORMAT
.
3. Аналогично параллельное соединение переключателей моделируется дизъюнкцией:


4. Через обозначается переключатель, который включен в том и только в том случае, когда переключатель А выключен.
1143635657860Не давая строгого определения, что такое параллельно-последовательный двухполюсник, приведем пример такого объекта:
Опишем данный двухполюсник формулой алгебры высказываний:

Упростив высказывание F, мы построим схему, соответствующую этому более простому высказыванию. Построенная схема будет функционировать так же, как и исходная, но будет устроена, как мы увидим, более просто:

Таким образом, исходная схема равносильна схеме:

Как видите – эффективный пример, показывающий возможные аспекты приложения алгебры высказываний. Оказывается, полученные результаты позволяют исследовать и упрощать не только параллельно-последовательные, но и произвольные двухполюсники.
Пример №6.
Дан двухполюсник.
\* MERGEFORMAT
Обозначим предложенную сеть символом S(A, B, C).
1. Положим, A=0, B=0, C=0. Непосредственно видно, что нет пути из М в N, проходящего по ребрам , поэтому S(0,0,0)=0.
2. Положим, A=0, B=0, C=1. Проверка показывает, что нет пути из М в N по ребрам , поэтому S(0,0,1)=0.
3. A=0, B=1, C=0. Есть путь из М в N. Условно его можно обозначить так: . Поэтому S(0,1,0)=1.
4. A=0, B=1, C=1. Есть путь из М в N: . Поэтому S(0,1,1)=1.
5. A=1, B=0, C=0. Нет пути из М в N, то есть S (1, 0, 0)=0.
6. A=1, B=0, C=1. S(1, 0, 1)=0.
7. A=1, B=1, C=0. S (1, 1, 0)=0.
8. A=1, B=1, C=1. S (1, 1, 1)=0.
Сети S соответствует таблица истинности:
A B C S
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 0
. То есть исходная сеть S равносильна следующей:
\* MERGEFORMAT
Пример на голосование.
Имеется комиссия, состоящая из четырех человек a, b, c, d (а– председатель комиссии). Предложение считается принятым, если за него проголосовало большинство, но председатель обладает следующим преимуществом – правом "вето": если он проголосовал "против", то предложение не принимается, если проголосовал "за", то достаточно, чтобы еще кто-то один поддержал это предложение. Сконструировать схему, в которой сигнал бы зажигался, если предложение принято, и не зажигался в противном случае. Обозначим эту схему через F(a, b, c, d) и построим для нее таблицу истинности:
abcdF
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
Значит,
.
Строим схему голосования:
\* MERGEFORMAT
Задачи для самостоятельного решения:
Запишите символически следующие сложные предложения, употребляя буквы для обозначения простых компонентов предложения.
Есть простое число и 4 есть составное число.
Идет дождь или кто-то не выключил душ.
Если идет дождь, то улицы мокрые.
Иван сядет, и он или Сергей будут ждать.
Иван сядет и будет ждать или Сергей будет ждать.
Я поеду на автобусе или на такси.
Ни Север, ни Юг не победили в гражданской войне.
Человека не подкупит лесть, если ум у человека есть.
Если учитель ест стоя, то ученики едят на ходу.
Если не можешь признать похвал заслуженными, то считай их лестью.
Если будет хорошая погода, то я позвоню друзьям, и мы поедем к морю.
Если я устал или голоден, я не могу заниматься.
Натуральное число n делится на 3 тогда и только тогда, когда сумма цифр числа n делится на 3.
Если Смит победит на выборах, он будет доволен, а если он будет доволен, то он плохой борец в предвыборной кампании, но если он провалится на выборах, то потеряет доверие партии; он плохой борец в предвыборной кампании, если он потеряет доверие партии, и, если он плохой борец в предвыборной кампании, ему следует выйти из партии; Смит или победит на выборах, или провалится, следовательно, ему нужно выйти из партии.
Контракт будет выполнен тогда и только тогда, когда дом будет закончен в феврале, если дом будет закончен в феврале, то мы можем переезжать 1-го марта, если мы не сможем переехать 1-го марта, то мы должны внести квартирную плату за март; если контракт не будет выполнен, то мы должны внести квартирную плату за март, но мы не будем вносить квартирную плату за март.
Построить таблицы истинности для следующих высказываний.
1.; 10.;
2.; 11.;
3.; 12.;
4.; 13.;
5.; 14.;
6.; 15.;
7.; 16.;
8.; 17.;
9.; 18.;
Привести данные высказывания к ДНФ:










Привести данные высказывания к СДНФ, по возможности упростить:










Привести данные высказывания к СДНФ, по возможности упростить.
xyF(x,y)
0
0
1
1 0
1
0
1 0
1
0
0
xyF(x,y)
0
0
1
1 0
1
0
1 1
0
0
0
xyF(x,y)
0
0
1
1 0
1
0
1 0
1
0
1

Упростить следующие последовательно-параллельные двухполюсники:



Упростить следующие произвольные двухполюсники:


Составить схемы результатов голосования для следующих задач.
1. Голосуют три человека A, B, C. Предложение принимается большинством голосов, причём выполняются следующие условия:
а) если C голосует "за", то B голосует "против";
б) C голосует "против" тогда и только тогда, когда B голосует "за";
в) если C голосует "за" или B голосует "за", то A голосует "против";
г) A и B – коалиция, т. е. голосуют одинаково, а C им противоречит;
д) C подозревает A и B в коалиции, т. е. если A и B голосуют одинаково, то C им противоречит;
е) если C голосует "за", то A голосует "за" тогда и только тогда, когда B голосует "против";
ж) если B голосует "за", то C голосует "против" тогда и только тогда, когда A голосует "против";
з) A или B голосуют "против" тогда и только тогда, когда C голосует "за";
и) C и A голосуют "за" тогда и только тогда, когда B голосует "против";
к) если A голосует "за" или B голосует "против", то C голосует "за".
2. Голосуют три человека A, B, C. Предложение принимается большинством голосов, причём A обладает правом вето. Кроме того, выполняются следующие условия:
а) если B голосует "за", то C голосует "против";
б) B голосует "против" тогда и только тогда, когда C голосует "за";
в) если C голосует "за" или A голосует "за", то B голосует "против";
г) A и C – коалиция, т. е. голосуют одинаково, а B им противоречит;
д) A подозревает C и B в коалиции, т. е. если C и B голосуют одинаково, то A им противоречит;
е) если A голосует "за", то C голосует "за" тогда и только тогда, когда B голосует "против";
ж) если C голосует "за", то A голосует "против" тогда и только тогда, когда B голосует "против";
з) B или C голосуют "против" тогда и только тогда, когда A голосует "за";
и) C и B голосуют "за" тогда и только тогда, когда A голосует "против";
к) если B голосует "за" или C голосует "против", то A голосует "за".
3.  Голосуют четыре человека A, B, C, D. Предложение принимается большинством голосов. Если голоса разделились поровну, то предложение принимается, если A голосует "за".
4. Голосуют четыре человека A, B, C, D. Предложение принимается большинством голосов. Если голоса разделились поровну, то предложение принимается, если B голосует "за".
Критерии оценки:
При оценивании будет учитываться:
«5» если решены 7-8 задач.
«4» - если решены 5-6 задач.
«3» - если решены 4 задачи.
«2» - если решено менее 4 задач.

Раздел 6. Некоторые элементы теории и практики шифрования.
Задание: изучить теоретический материал по данной теме и письменно ответить на вопросы.
Цель: отработать умения систематизировать материал, находить ответы на поставленные вопросы.
Рекомендуемая литература:
Романец Ю. В., Тимофеев П. А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях./ Ю. В Романец, П. А. Тимофеев, В.Ф. Шаньгин. М.: Радио и связь, 2005. – 376 с.
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. / М. С. Спирина, П. А. Спирин. – М.: Издательский центр Академия, 2004. – 368 с.
Алгоритм действий:
Прочитать следующие разделы в книге №1
Шифры простой замены ( стр 48 – 60)
Шифры сложной замены ( стр. 60 – 68)
Шифрование гаммированием ( стр. 69 – 76).
Ответить письменно на следующие вопросы:
В чем заключается шифрование шифром простой замены?
Перечислите основные модификации шифра Цезаря.
Приведите пример шифрования Цезарем с ключевым словом.
В чем смыл шифрования таблицей Трисемуса. Приведите пример.
Сформулируйте процедуру шифрования Плейфера. Приведите пример.
В чем заключается шифрование шифром сложной замены?
В чем смысл шифрования «двойным квадратом» Уитстона?
В чем смысл шифрования Вернама?
Что такое гаммирование?
Приведите примеры шифрования гаммированием.
Критерии оценки:
При оценивании будет учитываться:
«5» - если верно ответили на все вопросы (10 вопросов)
«4» - если верно ответили на 8 вопросов.
«3» - если верно ответили на 6 вопросов.
«2» - если ответили менее чем на 6 вопросов.

Раздел 7. Метод математической индукции.
Задание: изучить теоретический материал по данной теме и решить предложенные задачи.
Цель: выработать умения решать задачи по данной теме.
Рекомендуемая литература:
лекционный материал.
Методические указания, в которых представлены примеры решения задач.
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. / М. С. Спирина, П. А. Спирин. – М.: Издательский центр « Академия», 2004. – 368 с.
Алгоритм действий:
Прочитать лекционный материал
Рассмотреть примеры решения задач в данном пособии, записать их.
Самостоятельно решить предложенные задачи.
Оформить решения задач в соответствии с примерами.
Пример №1
Доказать, что
.(1)
Доказательство
1. Базис индукции: проверим равенство при . Левая часть (ЛЧ)=1, правая часть (ПЧ)=. Равенство при , то есть базис индукции, выполняется.2. Индуктивное предположение: допустим, равенство (1) верно при , то есть допустим, что
.(2)
3. Индуктивный переход: докажем равенство (1) при , то есть докажем, что . В самом деле, . Здесь мы применили индуктивное предположение. Далее , что и требовалось доказать.
На основании ММИ равенство (1) верно при любом .
Символом обозначается произведение , где . Например, . По определению полагают .
Пример №2
Доказать, что для любого
.(3)
Доказательство
1. Базис индукции: проверим утверждение (3) при . ЛЧ=, ПЧ=. Базис индукции доказан.
2. Индуктивное утверждение: допустим, (3) верно при , то есть допустим:
.(4)
3. Индуктивный переход: докажем (3) при , используя (4), то есть докажем, что
.
В самом деле,
Пример №3
Доказать, что для любого делится на 9.(5)
Доказательство:
1. Базис индукции: проверим (5) при . ЛЧ=4+15-1=18 делится на 9.
2. Индуктивное предположение: допустим, (5) выполняется при , то есть делится на 9.(6)
3. Индуктивный переход: докажем (5) при , используя (6), то есть докажем, что делится на 9.
.
Первая скобка делится на 9 по индуктивному предположению. Осталось доказать, что второй слагаемый делится на 9, то есть надо доказать, что делится на 3. Это утверждение мы будем доказывать методом математической индукции, то есть нам придется применять "индукцию в индукции". При m=1 4+5=9 делится на 3. Допустим, делится на 3. Докажем, что делится на 3, но . Первый слагаемый делится на три по индуктивному предположению, а второе – очевидно. Таким образом, мы доказали, что делится на 3, а вместе с этим, что делится на 9.
Пример №4
для любого .
Доказательство:
При n=1 неравенство очевидно: 2>1. Допустим, . Докажем, что . В самом деле, , так как по индуктивному предположению и  – очевидное неравенство.
Пример №5
для любого натурального .
Доказательство:
При n=5 получаем верное неравенство 32>25. Допустим, неравенство верно при , то есть . Докажем, что . Это неравенство равносильно . Если мы докажем, что , то будет доказано и исходное неравенство. Неравенство доказываем индукцией (индукция в индукции). При имеем верное неравенство . Допустим, неравенство верно при , то есть . Докажем при то есть докажем, что или . Очевидно, что это неравенство верно в силу индуктивного предположения.
Задачи для самостоятельного решения:
1. Доказать, что для любого
a) ;
б) .
2. Доказать, что сумма кубов первых чисел натурального ряда равна .
3.  Доказать, что при каждом натуральном справедливо равенство .
4.  Доказать, что для любого справедливо равенство .
5. Доказать, что для любого
а) ;
б) .
5. Доказать формулу суммы первых членов арифметической прогрессии .
6. Доказать, что при любом 0 справедливы утверждения:
а) 7n+2 +82n+1 делится на 57;
б) 11n+2+122n+1 делится на 133;
в) 25n+3+5n3n+2 делится на 17;
г) 2n+5 34n +53n+1 делится на 37;
д) 33n+2 +523 n+1 делится на 19;
е) 32n+2 52n 33n+2 22n делится на 1053;
ж) 22n+21 делится на 3;
з) 72n+21 делится на 48
7. Доказать, что при каждом натуральном n справедливо неравенство 1++++.
8. Доказать неравенство 1, .
Критерии оценки:
«5» - если верно решено 8 задач.
«4» - если верно решено 5- 7 задач.
«3» - если верно решено 4 задачи.
«2» - если верно решено менее чем 4 задачи.

Раздел 10.«Основы теории графов» (5 часов).
Задание: изучить теоретический материал по данной теме и решить предложенные задачи.
Цель: выработать умения решать задачи по данной теме.
Рекомендуемая литература:
данные методические указания..лекционный материал
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. / М. С. Спирина, П. А. Спирин. – М.: Издательский центр Академия, 2004. – 368 с.
Алгоритм действий:
Прочитать лекционный материал. Рассмотреть решения задач в лекции.
Рассмотреть примеры решения задач в данном пособии, записать их.
Самостоятельно решить предложенные задачи.
Оформить решения задач в соответствии с примерами.
Пример №1.
Пусть дан ориентированный граф (рис.1) , причем ребра a,b,h являются ориентированными (их направление указано стрелками), а остальные ребра не ориентированы.
Требуется методами булевой алгебры найти пути и сечения между вершинами 2 и 4.

Решение:

Рисунок 1Составляем структурную матрицу S, затем вычеркиваем из нее 4-ю строчку и 2-й столбец (тем самым получаем минор М(4,2)):
.
Получаем

Искомые пути, расположенные в порядке прохождения ребер:
П 24 =d hf ce hgbe.
Сечения же получатся отрицанием этих путей. Применяя правила де Моргана (заменяя конъюнкцию на дизъюнкцию и наоборот), затем раскрывая скобки, получаем: (знаки отрицания опущены во всех равенствах, кроме 1-го):
=  d (h f)(c e)(h g b e)
S24= d(h f)(e ch cg cb) = d(he ch cgh сbhfe fchfcg fcb),
или, применяя в скобках правило поглощения, получаем
S24 = d(he ch fe fcg fcb),
S24=dhedch dfе dfcg dfcb.
Пример №2.
Требуется, расставляя пометки в графе с заданным потоком с помощью алгоритма, описанного в теореме Форда – Фалкерсона, найти максимальный поток между вершиной с номером 1 и вершиной с максимальным номером. При этом если улучшенный поток окажется максимальным, то нужно указать то минимальное сечение, которому равен наш поток (если же улучшенный поток не окажется максимальным, то нужно снова его улучшать до тех пор, пока он не окажется максимальным).
Решение:
На рис.2 а изображен граф с данными пропускными способностями ребер, при этом вершина номер 1 является “источником”, а вершина 6 – стоком. На рис. 2 б изображен тот же граф, но на ребрах его задан поток, удовлетворяющий свойствам 1–4, который надо либо увеличить, либо доказать, что он является максимальным.

Рисунок 2Начинаем расставлять пометки во втором графе (там дан поток). 1-я вершина (источник) всегда имеет пометку ( ) (это означает, что второе число как угодно большое). Далее вторую вершину пометить пока нельзя, зато можно пометить вершину 4 и ее пометка будет (+1,25). Это означает, что дуга (1,4) прямая, ненасыщенная и по ней можно “перевезти” дополнительно 25 единиц “груза”. Далее вершину 5 пометить пока нельзя, но теперь можно пометить вершину 2 и ее пометка будет (–4,20).

Это означает, что дуга (4,2) обратная, и, учитывая возможный “разворот” ее, по ней можно дополнительно “перевезти” 20 единиц “груза”. Так как 20 меньше 25, получаем данную пометку. Теперь можно пометить вершину 3 пометкой (+2,15) и, вершину 5, пометка которой будет (–3,15). (Заметим, что по дуге (5,3) с учетом разворота можно дополнительно “перевезти” 25 единиц груза, но так как для вершины 3 второе число было равно 15, то любое следующее число не может быть его больше). Только после этого можем пометить вершину 6 (сток), пометка которой будет (+5,15). Таким образом, наш поток можно увеличить на 15 единиц, прибавляя эти 15 единиц к прямым дугам и вычитая из обратных с учетом возможного “разворота” обратных дуг. Результат всех этих действий изображен на рис.3.
Таким образом, получили новый поток, изображенный на рис.4
После этого для нового потока (рис.4), снова расставляем пометки, которые также изображены на рис.4 Мы видим, что для этого потока (кроме источника) можно пометить только 2 вершины: вершину 4 (ее пометка будет (+1,10)) и (после этого) вершину 2, пометка которой будет (+4,5). Больше ничего пометить нельзя, так как из множества помеченных вершин (Y) в множество непомеченных вершин (Z) идут только прямые, насыщенные дуги (дуги (2–3) и (4–5)). Эти две дуги образуют минимальное сечение, величина которого равна 30 условных единиц, и эта же величина равна величине потока. Заметим, что величина потока также равна “количеству груза”, вывозимого из источника, и равна количеству груза, ввозимого в сток. Таким образом, поток на рис. 4 является максимальным, а дуги (2–3) и (4–5) образуют минимальное сечение, которому равен наш поток.
Задачи для самостоятельного решения:
Требуется составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути Pij из вершины i в вершину j, затем найти все сечения Sij между этими вершинами. В данном задании (чтобы исключить возможные неясности графического рисунка) указываются все ориентированные ребра, причем запись (2–4) означает, что 2 вершина связана с 4-й, а обратной связи нет.
а) Дан орграф. Имеется 2 ориентированных ребра: (2–5) и (3–4); i=3, j=1.

б) Дан орграф. Имеется 2 ориентированных ребра: (2–3) и (2–4); i=4, j=6.

в)Дан орграф. Имеется 1 ориентированное ребро: (4–5); i=3, j=4.

г) Дан орграф. Имеется 2 ориентированных ребра: (6–2) и (5–4); i=3, j=5.
 

Требуется найти в данной сети (т.е. в графе с заданными пропускными способностями ребер) максимальный поток из вершины с номером 1 в вершину с наибольшим номером (в заданиях либо вершину 5, либо 6). В заданиях заданы 2 графа (граф, который находится слева, – это сеть с заданными пропускными способностями ребер, и граф справа с заданным потоком, который необходимо либо улучшить, либо доказать, что он не улучшаем и, значит, является максимальным).




Критерии оценки:
«5» - если решено 2 задачи полностью
«4» - если верно решено 1 задача и 2 задача под буквами а,b.
«»3» если решена полностью задача №1.
«2» - если задача №1 решена под пунктами а-в.

Раздел №11 « Элементы теории автоматов». (5 часов).
Задание: изучить теоретический материал по данной теме и решить предложенные задачи.
Цель: выработать умения решать задачи по данной теме.
Рекомендуемая литература:
лекционный материал
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. / М. С. Спирина, П. А. Спирин. – М.: Издательский центр Академия, 2004. – 368 с.
Алгоритм действий:
Прочитать лекционный материал. Рассмотреть решения задач в лекции.
Самостоятельно решить предложенные задачи.
Оформить решения задач в соответствии с примерами из лекции.
Задачи для самостоятельного решения:
В учебнике №3 решить задачи
7.1- 7.3. на странице 357.
Критерии оценки:
«5» - если решено 3 задачи полностью
«4» - если верно решено 2 задачи и 3 задача под буквами а, b.
«»3» если решены полностью задачи №1 и №2.
«2» - если решена только одна задача..
Рекомендуемая литература
Методические указания, в которых представлены примеры решения задач.
Романец Ю. В., Тимофеев П. А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях./ Ю. В Романец, П. А. Тимофеев, В.Ф. Шаньгин. М.: Радио и связь, 2005. – 376 с.
Спирина М. С., Спирин П. А. Дискретная математика: учебник для студ. учреждений сред. проф. образования. / М. С. Спирина, П. А. Спирин. – М.: Издательский центр Академия, 2004. – 368 с.