A U B = B U A - коммутативность

A n B = B n A

(A U B) U C = A U (B U C), A n (B n C) = (A n B) n C - ассоциативность.

(A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) - дистрибутивность.

Поглощение A U A = A, A n A = A.

Существование универсальных границ.

А U 0 = A

A n 0 = 0

A u U = U

A n U = A

6. Двойное дополнение



Рисунок 2.1. Основные операции над множествами

A = A

7. A U A = U

A n A = 0

8. Законы двойственности или закон Де - Моргана

(AUB) = A n B

(AnB) = A U B

2.2.4 Теория булевых функций. Булева алгебра

Определение.

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры). Названия операций пока не введены.

X & Y = Y&X, X V Y = Y V X - коммутативность.

(X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) - ассоциативность.

(X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) - дистрибутивность.

Поглощение - X & X = X, X V X = X.

Свойства констант

X & 0 = 0

X & I = X, где I - аналог универсального множества.

Инвальтивность (X*)* = X

Дополнимость X V X* = I, X & X* = 0.

Законы двойственности - (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an)

[U] = N

[P(U)] = 2n

Свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.

Oбъединение эквивалентно V, пересечение - &, дополнение - *, пустое множество - 0, а универсальное - I.

Все аксиомы булевой алгебры справедливы в операциях над множествами.

2.2.4.1 Булева алгебра характеристических векторов

Пусть A <= U, A <- P(U) a?- характеристический вектор этого подмножества.

A = {a?, a2 ..an)

n = [P(U)]

ai = 1, если ai <- A (принадлежит).

ai = 0, если ai не принадлежит A.

U = {1 2 3 4 5 6 7 8 9}

A = {2 4 6 8}

B = {1 2 7}

aA = {0 1 0 1 0 1 0 1 0}

aB = {1 1 0 0 0 0 1 0 0}

или

aA = 010101010 - скобки не нужны

aA= 110000100

Характеристические векторы размерностью n называются булевыми векторами.

Они располагаются в вершинах n - мерного булева куба.

Номером булевого вектора является число в двоичном представлении, которым он является

1101 - номер.

Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (если они отличаются только одной координатой).

Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.

Булев куб размерности 1

Булев куб размерности 2

Булев куб размерности 3

0 - нулевой вектор.

I - вектор из одних единиц.

X	Y	X&Y	X V Y
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

Отрицание

X = 0 Y = 0

_ _

Х = 1 Y= 1

Для размерности n операции над векторами производятся покоординатно.

Логическая сумма двух векторов - вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Утверждение

Между множеством всех подмножеств множества U и булевым кубом Bn, где n= =[U] можно установить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения - операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному - единичный.

Следствие

Множество всех характеристических векторов является булевой алгеброй.

2.2.4.2 Булева алгебра высказываний (алгебра логики)

Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно.

U = {1 2 3 4 5 6 7 8 9}

A = «число четное»

B = «число, меньшее пяти»

Множеством истинности высказывания называется совокупность всех элементов, для которых это высказывание истинно.

SA = {2 4 6 8}

SB = {1 2 3 4}

Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.

Высказывания, для которых множества истинности совпадают, называются тождественными или равносильными.

Равносильные высказывания объединим в один класс Р.В. и не будем их разделять, т.к. все они имеют одно и то же множество истинности.

2.2.4.3 Операции над высказываниями

Дизъюнкция высказываний (V, ИЛИ, OR)

Дизъюнкция высказываний - высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.

Конъюнкция высказываний (&, И, AND).

Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.

Отрицание высказываний (- над буквой, НЕ, NOT).

A B	A & B	A V B	Not A
Л Л	Л	Л	И
Л И	Л	И	И
И Л	Л	И	Л
И И	И	И	Л

Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.

Л - ложно.

И - истинно.

Утверждение (основа всей алгебры логики)

Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.

Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.

Теорема

Существуют 3 булевых алгебры:

P(U) Bn

2.2.4.4 Множество классов эквивалентных высказываний

Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются.

Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел).

2.2.4.5 Определение и способ задания булевых функций

Булевой функцией от n аргументов называется однозначное отображение n - мерного булева куба на одномерный булев куб.

Способы задания функций

Табличный

X1 X2 X3 … XN	F(X)
0 0 0 0 0 0 0 0 0	g?
…	gi
1 1 1 1 1 1 1 1 1	gn

gi???значение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

Векторный

F = (g????gn)

3. Геометрический

Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1.

Носителем данной функции - совокупность всех единичных векторов этой функции (Nf - носитель функции f)

На векторах, помеченных звездочкой, функция обращается в 1.



Nf = {001, 011, 100, 110} = [1,3,4,6] [] - указаны номера векторов.

В виде формулы.

Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают.

Будем говорить, что f зависит от переменной xi существенно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно.

Фиктивные переменные у функции можно добавлять и исключать.

Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных.

Таблица функций при n = 1.

X	0	X	_ X	1
0	0	0	1	1
1	0	1	0	1

Таблица всех элементарных булевых функций, применяемых в записи формул

X	Y	0	&	_____ Y®X	X	___ X®Y	Y	+	V	Ї	~	_ Y	X ®Y	_X	Y®X	/	1
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Все эти функции от двух аргументов называются элементарными булевыми функциями.

Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание.

Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры.

Суперпозиции булевых функций

Ф = {ф1…фk}

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

Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента).

В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы.

Ф1 = {Y…xn}

Фi = (x1 … фj(x1…xn) … xn)

Ф(1) - множество всех элементарных суперпозиций из системы Ф.

Ф(k+1) - множество всех элементарных суперпозиций из систему Фk.

Функция g называется суперпозицией функций из системы, если ????? g??? Фn

Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции.

Конкретное выражение суперпозиции будем называть формулой над системой Ф.

G = Fф

Суперпозиция элементарных булевых функций - формула.

Для удобства записи договоримся, что отрицание - самая сильная операция. Следующая - конъюнкция, а остальные - равносильны.

_ _

X+Y = XY V XY

_ _

X ~ Y = XY V XY

__

X ®? Y = X V Y

_ _

X Ї? Y = X Y

2.3 Графы

Графом (G) называется тройку объектов (V, X, q?)

V - множество n вершин.

X - конечное множество ребер.

q--- функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.

q ?задана на множестве X.

Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф).

Vj - начало ребра

Vk - его конец

q?xi) = (Vj, Vk) - ребро инцидентно в вершине Vj и в вершине Vk.

Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными.

Если на ребре xi0

q?(x0) = (Vj0, Vj0),

то ребро называется петлей.

2.3.1 Способы задания графов

2.3.1.1 Аналитический

Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.

Выписываются все ребра и пишутся напротив две пары вершин, которым они инцидентны.

В конце выписываются все изолированные вершины.

2.3.1.2 Геометрический

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин - кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

2.3.1.3 С помощью матрицы инцидентности

A(m*n)

m = [V] - число вершин

n = [X}- число ребер

а) Неориентированные графы

Aij = {0, если Vi не инцидентно xj, 1, если Vi инцидентно xj)

б) Орграфы

Aij = {0, если Vi не инцидентно xj, -1, если Vi - начало xj, 1, если Vi - конец xj)

Для петель нужны дополнительные предположения.

Матрица смежности (задается одинаково для всех графов)

B(m*m) m = [V]

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична. Граф, в котором нет кратных ребер и петель, называется простым. Простой граф называется полным, если любой паре его вершин инцидентно одно ребро.

Все о неориентированных графах.

K1 - полный граф с одной вершиной

K2 - с двумя

K3 - с тремя

K4 - полный граф с четырьмя вершинами

K5 - полный пятивершинник

Граф называется двудольным, если множество вершин разбивается на 2 непересекающихся подмножества, такие, что ребра соединяют вершины из разных подмножеств.

Двудольный граф называется полным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.

Полный двудольный граф.

2.3.2 Маршруты, циклы, связности

Маршрутом в графе называется чередующаяся последовательность вершин и ребер, начинающаяся и заканчивающаяся вершинами, такую, что каждое ребро в нем соединяет только те вершины, между которыми оно стоит.

Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если существует маршрут, то последняя вершина называется достижимой из первой вершины.

Маршрут, в котором нет повторяющихся ребер, называется цепью.

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.

Если в простой цепи первая и последняя вершины совпадают, то она называется циклом.

Граф называется связным, если любая вершина достижима из любой другой вершины. В противном случае граф называется несвязным. Несвязный граф распадается на несколько частей, каждая из которых является связным графом.

Эти части называются компонентами связности.

Ребро называется циклическим, если оно входит хотя бы в один цикл графа. В противном случае ребро называется ациклическим.

Утверждение.

Если из связного графа удалить циклическое ребро, то вновь полученный граф останется связным, а если удалить ациклическое ребро, то граф распадется на два компонента связности.

Связный граф, у которого все ребра ациклические, называется деревом.

Несвязный граф, компонентами связности которого являются деревья, лесом.

Свойства деревьев.

Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

Эйлеровы графы

Дан граф. Требуется найти в нем маршрут, проходящий по каждому ребру ровно один раз. Начало и конец - в одной вершине.

Такой маршрут называется Эйлеровым циклом, а граф, в котором он существует, называется Эйлеровым графом.

Степень вершины в графе - это число ребер, инцидентных этой вершине.

Для того, чтобы связный граф без петель был Эйлеровым, необходимо и достаточно, чтобы степень его вершины была четным числом.

Планарные графы.

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

Сама же укладка графа без пересечения ребер называется плоским графом.

Любой граф можно изобразить в трехмерном пространстве без пересечения ребер.

Для любого графа xi, соединяющего 2 вершины проводим новую плоскость, содержащую эту прямую, а ребро рисуем на плоскости.

Граф будет планарным, если существует его укладка на сфере.

Доказательство следует из взаимно однозначного соответствия точек на сфере с точками плоскости из стереографических проекций.

Следствие. Граф любого выпуклого многогранника планарен.

Ребра плоского графа разбивают плоскость на несколько частей, одна из которых бесконечна. Эти части и являются гранями плоского графа.

Теорема Эйлера о плоских графах.

Формула Эйлера.

Для плоского графа справедливо соотношение.

M - N + P = 2.

Докажем индукцией по числу граней

P = 1

Если P = 1, то граф - дерево. В нем нет ни одного цикла. У дерева число вершин больше числа ребер на 1.

M = N + 1

N + 1 - N + 1 = 2 - справедливо.

Пусть p = k, и утверждение верно.

Тогда оно верно и при P= k+1

Берем ребро графа, отделяющее бесконечную грань от внутренних и удаляем это ребро из графа. Т.к. оно циклическое, то в новом графе g1 (он также будет связным) число вершин M останется прежним.

N1 = N - 1

P1 = P - 1

M = M

k + 1-1 = k

Для g1 справедливо предположение индукции.

M1 + N1 + P1 = 2

M - N - 1 + K = 2

M - N + K - 1 = 2

M - N + P = 2

Что и требовалось доказать.

Следствие 1.

Для плоского связного простого графа справедливо соотношение

n <= 3*(m-2)

Следствие 2.

Для плоского связного простого графа без треугольных граней справедливо соотношение

n <= 2*(m-2)

Следствие 3.

Граф K5 - непланарен.

m > 2

И если бы он был плоским, то для него было бы справедливо следствие 1.

N <= 3*(m-2)

10 <= 9 - неверно.

Противоречие. Значит, он не может быть нарисован плоским.

Следствие 4.

Нет треугольных граней.

Если бы он был плоским, то для него было бы справедливо следствие 2.

9 <= 2*(6-2)

9 <= 8 - неверно.

Противоречие из предположения, что он не может быть плоским.

Операцией разбиения ребра графа называется следующая процедура:

Ребро удаляется из графа, и в граф добавляется новая вершина, соединенная новыми ребрами с концами данного ребра.

Два графа называются гомеоморфными, если каждый из них может быть получен из одного и того же графа путем применения конечного числа раз операции разбиения ребер.

2.3.3 Сети. Пути в орграфах. Остовы минимальной длины

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

Двуполюсная сеть называется сильно связанной (связной), если через любое ребро проходит простая цепь, соединяющая полюса. В ней нет повторяющихся вершин.

Параллельная сеть - сеть вида

Последовательная сеть - сеть вида

П (пи) сети - последовательно-параллельные сети

Примеры П-сетей

Такая сеть называется мостиковой.

Контактными схемами называются сильносвязные двуполюсные сети, каждому ребру которой поставлено в соответствие x или NOT(x).

X Not Y

Z Not X

Любой контактной схеме (КС) можно поставить в соответствие булеву функцию (функцию проводимости) по правилу:

Для любой простой цепи, соединяющей полюса, записываем ЭК тех переменных, которыми помечены ребра этой цепи.

Затем берем дизъюнкцию всех ЭК. Получим искомую функцию проводимости.

Если в контактной схеме будут стоять переключатели (релейные контакты), которые будем считать замкнутыми, если выражение, стоящее у ребра равно 1 или в противном случае разомкнутыми, то при подаче на полюса разности потенциалов (электрического тока) контактная схема будет проводить ток при таких и только при таких состояниях контактов, при которых значение функции равно 1.

Минимальной контактной схемой для функции называется контактная схема, для которой эта функция является функцией проводимости. Эта схема содержит наименьшее число ребер.

2.3.4 Минимальные пути в графах

Путем в графе (в орграфе) называется маршрут, движение по которому любого ребра проходит в соответствии с направлением этого ребра.

Контуром в орграфе называется замкнутый путь, в котором вершины не повторяются (кроме первой и последней).

Орграф, в котором нет ни одного контура, называется бесконтурным.

Первая задача о минимальном пути.

Дан граф. Выделено две вершины. Найти путь из одной вершины в другую, состоящий из наименьшего числа ребер.

Обозначения

Г(V) - множество вершин, в которые можно попасть из вершины V, пройдя только по одному ребру в его направлении.

Г-1(V) - множество вершин, из которых можно попасть в вершину V, пройдя только по одному ребру.

Алгоритм.

Исходной вершине A присваиваем метку 0.

Любому Г(А), которые еще не имели меток, присваиваем метку М = 1.

Для любой V, принадлежащей Г(А) находим Г(V) и любой V, принадлежащему Г(V), если она не имела метку, даем метку 2.

И так далее до тех пор, пока конечная вершина не получит метку.

Выбираем путь по Г-1(V).

Может произойти такое, что пути из А в В нет вообще.

Тогда на некотором шаге при обратном ходе нужной вершины нет.

Вторая задача.

Если каждому ребру поставить в соответствие некоторое целое положительное число, называемое его длиной и требуется найти путь из А в В, такой, что i = minimum. (r или l - длина ребра)

Алгоритм будет следующий.

Метка для ребра А l??=??

Для Vi li = +(бесконечность) - очень большое число, большее суммы всех длин ребер всего графа.

L(Vi, Vj) - длина ребра, идущего из вершины Vi в Vj. Направление важно.

Для любого ребра из графа проверяем выполнение неравенства.

lj - li > L(Vi, Vj) *

Если это неравенство выполняется, то меняем метку ?j на новую.

lj = li + L(Vi, Vj) и так до тех пор, пока выполняется *.

Если * нигде не выполняется, то та метка, которая будет стоять у вершины В и будет равна длине минимального пути из А в В, а сам путь строится движением назад из В в А.

Г-1(В) Существует такое ребро Vi1, для которого выполнено равенство.

lb - li1 = L(Vi1,B)

Затем Г-1(V1) Существует V2, где l?V1) - l?V2) = L(V1, V2) и т.д. пока не вернемся в вершину А.

Путь минимальной длины найден.

Остов графа минимальной длины.

Остов - дерево, содержащее все вершины графа и какие-то из его ребер.

Если каждому ребру графа поставлена в соответствие его длина, то требуется найти такой остов, сумма длин ребер которого минимальна.

Алгоритм

Перенумеруем все ребра графа в порядке возрастания их длин.

Просматриваем ребра, начиная с первого. Если x1 не является петлей, включаем в остов и переходим к следующему ребру. Если оно не является петлей и не образует с уже имеющимися ребрами цикла, мы его включаем в остов. И так до тех пор, пока не рассмотрим все ребра.

Остов минимальной длины найден.

2.3.5 Парное сочетание (паросочетание) двудольных графов

Двудольным графом называется граф, у которого множество вершин можно разбить на два непересекающихся подмножества так, что ребра соединяют вершины из разных подмножеств.

Паросочетанием в двудольном графе называется любое множество попарно несмежных ребер (у них нет общих вершин).

Паросочетание называется максимальным для данного графа, если оно содержит наибольшее число ребер для всех возможных паросочетаний.

Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.

Для любого подмножества S через ф(S) обозначим те вершины из множества w, которые соединяются ребрами с вершинами подмножества S.

Теорема Холла (без доказательства)

Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)].

Венгерский алгоритм нахождения максимального паросочетания.

Дан двудольный граф. Все определения для графа справедливы.

Полным паросочетанием называется паросочетание (ПС), к которому нельзя добавить ни одного ребра графа, не нарушив условие несмежности ребер.

Перебираем все ребра в любом порядке. Все несмежные ребра включаем в паросочетание.

Ребра, входящие в полное паросочетание, будем называть толстыми. Остальные ребра считаем тонкими.

Вершины, которые соединены толстыми ребрами - насыщенные. Остальные - ненасыщенные.

Чередующейся цепью называется цепь, в которой тонкие и толстые ребра чередуются.

Тонкой чередующейся цепью называется чередующаяся цепь, соединяющая 2 ненасыщенные вершины (В ней тонких ребер на 1 больше, чем толстых).

Находим полное паросочетание.

Для этого паросочетания ищем тонкую цепь. Если ее нет, то данное паросочетание максимально и алгоритм закончен.

Если же она существует, то проводим перекраску ребер.

Толстые ребра тонкой цепи делаем тонкими, а тонкие - толстыми.

Получаем новое паросочетание, т.е. из исходного паросочетания удаляем те толстые ребра, которые входили в тонкую цепь и вместо них добавляем тонкие ребра из этой цепи.

Переходим на шаг 2.

Количество ребер в новом паросочетании увеличится на 1.

Максимальное паросочетание (МПС) найдено.

Совершенное ПС - МПС обязательно.

Матрицы смежности двудольных графов.

A(M,N)

[V] = M

[W] = N

Aij = 1, если есть ребро ViWj

Если его нет, то Aij = 0.

Чтобы найти полное паросочетание, нужно найти единицы, которые находятся в разных строках и разных столбцах.

Алгоритм - тот же самый.

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

Алгоритм оптимального назначения

Есть m работников и m работ.

Каждый из работников выполняет каждую работу с определенной эффективностью.

Требуется распределить работы таким образом, чтобы каждый работник выполнял только одну работу, выполнялись все работы и суммарная эффективность была максимальна среди всех возможных таких распределений.

A = (aij) - матрица эффективности.

А(М*М)

А =

В терминах матрицы эффективности задача состоит в нахождении М элементов, расположенных в разных строках и разных столбцах, чтобы их сумма была максимальной.

Дан двудольный полный граф с V = M, W = M

Даны длины ребер.

Задача состоит в нахождении совершенного паросочетания, сумма длин всех ребер которого максимальна.

Алгоритм. Всем вершинам Vi даем метку аi = max по всем элементам нужной строки.

По всем j присваиваем метку 0.

Ищем ребра, для которых выполняется условие

Ai + Bj = Aij

Строим граф, в который входит все вершины исходного графа и найденные ребра.



	0	0	0	0
4	1	2	3	4
4	1	4	4	2
6	2	5	6	3
6	1	6	4	4

В построенном графе ищем максимальное паросочетание. Если найденное паросочетание совершенно, то алгоритм закончен. Если нет, то переходим дальше.

Из теоремы Холла существует подмножество S из V, [S] > ф(S).

Ищем это подмножество.

Для каждой вершины Vi из S метку Ai уменьшают на 1, а для wj из ф(s) метку Vj увеличивают на 1.

5. Переходим на начало шага 2 с новыми значениями меток.

Потоки в транспортных сетях

Введем обозначения

V - вершина орграфа

M-(V) - множество ребер, для которых вершина V является концом.

M+(V) - множество ребер, для которых вершина V является началом.

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

Существует только одна вершина A, для которой M-(А) - пустое множество. А - исток.

Имеется только одна вершина B, для которой M+(B) - пустое множество. В - сток.

Каждому ребру графа поставлено в соответствие целое неотрицательное число, называемое пропускной способностью данного ребра.



2(1) 3(1) 1(1)

6(0)

5(5)

1(1) 4(1) 2(1)

Потоком в транспортной сети (ТС) называется целочисленная функция, определенная на любых ребрах ТС и удовлетворяющая следующим свойствам

ф(X) <= C(X),

где С(X) - пропускная способность ребра.

На всех ребрах значение функции потока не превосходит значения пропускной способности ребра. Значение функции потока ставим рядом со значением пропускной способности ребра в скобках.

2. Для каждой внутренней вершины V транспортной сети, не равной A или B выполняется следующее условие: суммарная функция потока по ребрам, входящим в вершину, равна суммарной функции потока по ребрам, исходящим из вершины (сколько втекает, столько и вытекает).

Величиной потока [ф] = val(ф) называется число, равное сумме функций потока по всем ребрам, выходящим из вершины А или сумма всех функций потока по всем ребрам, входящим в вершину В.

Выбор потока.

Берем путь из А в В.

Выбираем минимальную пропускную способность и ставим ее в соответствие каждому ребру из пути.

Просматриваем все остальные ребра. Если они не пересекаются, то проделываем для них то же самое, начиная с п1. Всем остальным ребрам ставим в соответствие значение функции потока, равное 0.

Поток в транспортной сети называется максимальным, если выполнено условие

Val(ф) ? Val(Ф*)

Ф* = maximum

Любое подмножество S транспортных вершин, содержащих исток и не содержащих сток, определяет разрез, отделяющий исток от стока (разрез).

Разрез состоит из всех вершит тех ребер, которые имеют свои начала в вершинах множества S, а концы - из дополнения к множеству S.

Пропускной способностью разреза K называется сумма значений пропускных способностей всех ребер этого разреза.

Разрез K** называется минимальным, если для любого другого разреза выполнено условие C(K**)??? C(K).

Теорема Форда - Фалькерсона (без доказательства).

В транспортной сети величина максимального потока равна пропускной способности минимального разреза.

Алгоритм нахождения максимального потока (Алгоритм Форда - Фалькерсона).

Берем любой поток в транспортной сети.

Строим граф перестроек g* по следующему правилу:

В него входят все вершины исходного графа g.

Те ребра, на которых значение функции потока в исходном графе g были равны 0, входят в новый граф без изменений со своими пропускными способностями.

Все ребра, на которых ф(x) > 0 в новом графе g* заменяются двумя ребрами x* и x**. Ребро x* направлено в ту же сторону, что и x, и пропускная способность c(x*) = c(x) - ф(x).

Ребро x** направлено в противоположную сторону ребру x, и пропускная способность c(x**) = ф(x).

Ребра с нулевой пропускной способностью можно не рисовать.

В графе g* ищем путь из А в В по ребрам с ненулевой пропускной способностью. Если его нет, то имеющийся поток является максимальным и алгоритм закончен. Иначе переходим к пункту 4.

(Этот путь называется увеличенной цепью. D--=?min(c(x)) - минимальное значение пропускной способности этой цепи).

Меняем значение функции потока в графе g для тех ребер, которые соответствуют найденному пути в графе перестроек по следующему правилу:

Если направление ребра x в графе g совпадает с направлением пути, то новое ф(x) = ф(x) + D

Если же направление противоположно направлению пути, то ф(x) = ф(x) - D

5. Переходим на шаг 2 с новым потоком.

2.4 Комбинаторика

I-ое рекуррентное соотношение:

II-ое рекуррентное соотношение:

2.4.1 Перестановки с повторениями.

В

B=

элементов

если .

Т.е. множество выбираемых элементов ( элементов), которое разбито на классов , причем i-ый класс содержит ni элементов.

Перестановки из элементов данной спецификации называют перестановками с повторениями.

Оценим число перестановок с повторениями

Если переставлять буквы слова «мама», то поменяв местами буквы «м» и «а» мы ничего не изменим.

мама

Для вычисления заменим в множестве B элементы класса на элементы, которые различны между собой между всеми элементами множества B. Тогда число возрастает в раз (по правилу умножения)

Проделаем эту процедуру для

,

т. к. после замены все элементы в B стали различные и их можно переставить способами.

2.4.2 Перестановки с неограниченными повторениями

Имеем n различных элементов. После выбора элемента на его место становится точно такой же элемент из запаса, т.е. после выбора каждого элемента ситуация полностью восстанавливается.

Перестановки при спецификации элементов называются перестановки с неограниченными повторениями.

r раз

Пусть имеем n различных элементов. Чем сочетания отличаются от перестановок? Перестановки - упорядоченная выборка.

Сочетания - неупорядоченная выборка.

r!=

Неупорядоченную г-выборку можно упорядочить r! способами.

! Договариваемся

Комбинаторного смысла это не несет.

Рассмотрим

2.4.3 Рекуррентные соотношения для сочетаний

(o o … o ) B

Сочетания разбиваем на два типа: сочетания, содержащие элемент

элемент в выборку входит,

и сочетания, не содержащие элемент

из B надо взять r элементов

элемент взяли из B

Т.к. разбили число сочетаний на два класса (т.е. на два непересекающихся множества), то

при n>r

2.4.4 Рекуррентное соотношение для числа сочетаний

Формула

Свойства числа

Таблица

n\r	0	1	2	3	4
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1

Из таблицы следует, что:

Число сочетаний в каждой строке таблицы совпадают с коэффициентами разложения выражения (1+t)n по биному Ньютона

Число сочетаний имеют свойство симметрии

2.4.5 Сочетания с повторениями

Имеем n классов (или видов) элементов. Из них осуществляется r-выборка (r>n). В выборке элементы будут повторяться (это очевидно).

В этом случае сочетания называются сочетаниями с повторениями.

эклеры песочные слоеные наполеон

Т.е. 4 вида. Из них выбирают 7 предметов для покупки. Это не задача на перестановки: порядок выбора элементов не важен. Это не задача на сочетания: в комбинацию могут входить повторяющиеся элементы.

Закодируем покупку

111 о 111 о о 1

3 эклера 3 песочных 0 слоеных 1 наполеон

Пишем столько единиц, сколько куплено предметов 1-го класса. Затем пишем разделительный ноль, и т.д.

Очевидно, что предложенный способ кодирования покупки позволяет поставить взаимооднозначно

и обратно!

Число покупок равно числу различных вариантов комбинаций, которые можно составить из 7 единиц и 3-х нулей.

В общем случае:

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

где k - число предметов,

r - число предметов, которые выбираем.

Выводы:

Числа сочетаний и перестановок существенно зависят от спецификации элементов, из которых осуществляется комбинация.

2.4.6 Производящие функции для сочетаний

Изучая свойства сочетаний (на таблице) было показано, что числа сочетаний совпадают с биномиальными коэффициентами, т.е.

функцию называют перечисляющей производящей функцией для сочетаний из n различных элементов или энумератором.

Пример.

а). t=1

б). t=-1

Рассмотрим а) + б).

Пусть i - четное. Тогда



…………………………….

Пусть i - нечетное.

…………………………….

Тогда а) + б) даст

Вычтем из а) б). Тогда:

а) Пусть i - четное, тогда

……………

……………………………….

б). Пусть i - нечетное, тогда

…………………

………………………………

перемножим и суммируем члены при t.

…………………………………………….

Вывод:

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

2.4.7 Производящие функции при одинаковых элементах в комбинациях сочетания

n штук

o o o o ……… o

(1+t) (1+t) (1+t) (1+t) (1+t)

o o o ….……. o

(1+x1t) (1+x2t) (1+x3t) (1+xnt)

идентифицирующие элементы

Тогда для 3-х элементов с учетом идентифицирующих элементов

1 + 3 + 3 + 1

! Все , , - симметричные функции переменных , , .

! Число слагаемых каждого коэффициента равно числу сочетаний:

Это справедливо для случая из n элементов.



если , то получаем

! Коэффициенты по своей сути являются r-сочетаниями. При этом каждый элемент в сочетании появится не более 1 раза.

Зачем ввели новый вид записи производящих функций?

Это основа для обобщений.

если заменить на , то элемент будет входить в сочетание i раз.

если входит в сочетание четное число раз, но не более чем j раз

если входит хотя бы один раз в сочетание (но не более i раз)

! Таким образом, производящая функция способна описывать не только виды элементов, но и виды искомых сочетаний.

Примеры.

Задача про магазин.

Пусть имеем n видов элементов, и нет ограничений на число повторений элемента в сочетании. Запишем производящую функцию.



Введем еще одно условие для задачи из примера 1:

В каждое сочетание непременно должен входить по крайней мере один элемент каждого вида.

В этом случае будем иметь:

(сменим индексацию )

Пусть имеем 3 класса предметов. Сколько из них моно составить комбинаций, содержащих 5 предметов? Условие: в комбинацию входят предметы каждого класса. Классы предметов - a, b, c.

1). aaabc 2). abbbc 3). abccc 4). aabbc 5). aabcc 6). abbcc

2.4.8 Производящие функции для перестановок

Воспользуемся связью

Тогда производящая функция для перестановок имеет вид:

Числа перестановки появляются в форме коэффициентов при

Воспользуемся производящими функциями для подтверждения ранее полученных результатов.

Перестановки с повторениями.

n элементов

n1 n2 nl

В этом случае производящая функция имеет вид:

А если надо найти число перестановок из r элементов? (r<n)

Тогда надо найти коэффициенты при и т.д.

Рассмотрим r перестановок из n различных элементов с неограниченными повторениями.

искомое число перестановок

Производящие функции, возникающие при изучении перестановок называют экспоненциальной производящей функцией, т.к.

3. Реализация электронного учебника по дискретной математике

3.1 Постановка задачи

Компьютерная проектная среда, ориентированная на изучение движения в гравитационном, электростатическом, магнитном или в любых других полях, а также движения, вызванного всевозможными видами взаимодействия объектов. Работа программы основана на численном интегрировании уравнений движения.

В ней легко и быстро «создаются» схемы экспериментов, модели физических объектов, силовые поля. Способы представления результатов (мультипликация, график, таблица, диаграмма, вектор) задаются самим пользователем в удобном редакторе среды. Программа позволяет «оживить» эксперименты и иллюстрации К задачам курса дискретной математики, разработать новый методический материал, помогает ученикам лучше понять теорию, решить задачу, осмыслить лабораторную работу. Она может использоваться для сопровождения как школьного, так вузовского курса дискретной математики. Методическое сопровождение программы содержит несколько десятков готовых физических задач и моделей экспериментальных установок.

Основным ориентиром при создании электронных учебников должен быть конечный пользователь. И в зависимости от того, является ли он преподавателем или учащимся, учебник должен быть по-разному построен. Отличаться они должны так же как, например, методические рекомендации к учебнику и сам учебник. Основная роль заказчика не просто распорядиться, а свести все требования к электронному учебнику, который должен входить, как весомый элемент в методику преподавания какого-либо предмета. Подход к созданию электронного учебника в первую очередь зависит от возраста обучаемых (младший, средний, старший школьный возраст, студент профессионального училища, техникума или вуза, аспирант и т.д.); во-вторых, от того, для какой из форм преподавания (контроль, освоение нового материала, самостоятельное закрепление усвоенного, повторение, тренаж в закреплении с элементом проблемного изучения и т.д.) предназначен программный продукт. В зависимости от этого электронный учебник должен быть по-разному реализован. К сожалению, большинство программных продуктов, называемых электронными учебниками, являются лишь электронной версией книги, в лучшем случае учебника или методического пособия. На наш взгляд, электронная книга может стать электронным учебником, если она удовлетворяет требованиям, предъявляемым к учебникам и является неотъемлемой частью методики преподавания соответствующего предмета.

Подробно и удачно изложены основные понятия, регламентирующие материалы, основные этапы разработки электронных учебников в статье Зиминой О.В., Кириллова А.И. Рекомендации по созданию электронного учебника (http://www.academiaxxi.ru/Meth_Papers/AO_recom_t.htm). Перед тем как приступать к разработке собственного электронного учебника очень полезно прочитать указанную статью.

Суммируя изложенное можно сказать, что наиболее эффективными станут разработки электронных учебников, если «три подхода» будут объединены. Заказчик должен в первую очередь обратиться к конечному пользователю и предъявить связный список требований разработчику. Программисты должны реализовать продукт в той среде программирования, которая оптимально позволяет выдержать требования заказчика. После реализации начальной версии, продукт должен пройти тестовое использование, а уже затем выставляться на рынок вместе с методическими рекомендациями по применению электронного учебника в системе образования.



Рисунок 3.1. Внешний вид главной страницы электронного учебника

Платформа: Windows.

Носитель: CD-ROM.

3.2 Выбор платформы реализации

Для работы над учебником использовался редактор языка MS FrontPage как наиболее распространенный редактор для работы в формате HTML. Такой выбор подтверждается общей практикой применения электронных учебников. Перспективой такого подхода является отображение в различных операционных системах и браузерах на их базе.

Таким образом, возникает необходимая кроссплатформенность учебника.

Не секрет, что в последнее время возникают всевозможные попытки перевести компьютерные классы образовательных учреждений с операционной системы MS Windows на операционные системы серии Linux.

А язык HTML как гипертекстовый кроссплатформенный язык программирования позволяет оставаться независимым в этом смысле.

3.3 Структурная матрица электронного учебника по дискретной математике

Основным документом, подтверждающим и позволяющим подтвердить оригинальность разработки является матрица электронного учебника. При разработке она позволяет структурно рассмотреть учебник и отслеживать замечания пользователей, студентов и развивать сам учебник.

Таблица 3.1. Структурная схема учебника

	Аннотация	Глава	Выводы	Примеры и детали
Раздел 1 Введение
Подраздел 1 Что изучает Дискретная математика?
Подраздел 2 Становление и развитие дискретной математики
Подраздел 3 Теория множеств
Раздел 2 Теория множеств
Подраздел 1
Подраздел 2
Подраздел 3
Подраздел 4
Подраздел 5
Подраздел 6
Подраздел 7
Раздел 3 Теория графов
Подраздел 1
Подраздел 2
Подраздел 3
Подраздел 4
Подраздел 5
Подраздел 6
Раздел 4 Комбинаторика
Подраздел 1
Подраздел 2
Подраздел 3
Подраздел 4
Подраздел 5
Раздел 5 Глава 5
Заключение

3.4 Состав основных глав электронного учебника

Комплекты компьютерных экспериментов и учебных пособий -- цельная методическая система, предусматривающая как демонстрации и лабораторные работы, так и самостоятельное проектное творчество. Они особенно важны на первых порах знакомства учителя с программой, помогая быстрее её освоить и вводить в учебный процесс не эпизодически, а как продуманную систему.

3.4.1 Главы посвященные теории множеств

Исходным понятием теории множеств является само понятие множество, под которым принято понимать некоторую совокупность объектов, хорошо различимых нашей мыслью или интуицией. При этом не делается никаких предположений ни о природе этих объектов, ни о способе их включения в данную совокупность. Отдельные объекты, составляющие то или иное множество, называют элементами данного множества. Вопрос "Почему мы рассматриваем ту или иную совокупность элементов как множество?" не требует ответа, поскольку в общее определение множества не входят никакие дополнительные условия на включение отдельных элементов в множество. Если нам хочется, например, рассмотреть множество, состоящее из трех элементов: "солнце, море, апельсин", то никто не сможет запретить это сделать.



Рисунок 3.2. Внешний вид главы, посвященной исторической справке по теории множеств.

3.3.1.1Состав раздела теории множеств

Историческая справка

Множество. Алгебра множеств

Основное правило комбинаторики (показано на примере)

Основные операции над множествами

Свойства операций над множествами

Теория булевых функций. Булева алгебра.

Булева алгебра характеристических векторов

Булева алгебра высказываний (алгебра логики

Операции над высказываниями

Множество классов эквивалентных высказываний

Определение и способ задания булевых функций

3.3.1.2 Графы

Структура раздела позволяет рассмотреть общие методы построения излагаемого материала предлагается.

Способы задания графов

Аналитический

Геометрический

С помощью матрицы инцидентности

Маршруты, циклы, связности

Сети. Пути в орграфах. Остовы минимальной длины

Минимальные пути в графах

Парное сочетание (паросочетание) двудольных графов

В результате получаем внешний вид раздела, посвященного теории графов

Рисунок 3.3. Внешний вид главы, посвященной теории графов

3.3.1.3 Комбинаторика

Особенностью современного подхода к изложению комбинаторики являются межпредметные связи этой дисциплины с широким спектром задач и дисциплин

Перестановки с повторениями

Перестановки с неограниченными повторениями

Рекуррентные соотношения для сочетаний

Рекуррентное соотношение для числа сочетаний

Сочетания с повторениями

Производящие функции для сочетаний

Производящие функции при одинаковых элементах в комбинациях сочетания

Производящие функции для перестановок

Компакт-диск, содержащий фильмы и упражнения .

3.4 Разработка систем тестирования и контроля знаний учащихся

Интерес к системам тестирования и контроля знаний учащихся, представленным на рынке специализированного программного обеспечения (ПО), постоянно повышается. Современное ПО рассматриваемого класса, как правило, поддерживает четыре вида тестов:

1. Выбор правильного ответа на вопрос из множества имеющихся (одиночный выбор и/или множественный выбор).

2. Правильная установка соответствия между элементами.

3. Поддержка последовательности действий.

4. Возможность ответа на вопрос, вводом произвольного (по синтаксисту) текста ответа на вопрос в специальном окне ввода

Перспективно использование адаптивных методик тестирования с целью сокращения общего времени тестирования, однако введение этих методик осложнено трудностями оценки сложности задаваемых вопросов [1]. Актуальные проблемы виртуальной образовательной системы (ВОС): создание надежного инструмента дистанционного on-line тестирования и оценки знаний пользователей, организация on-line базы данных контрольных вопросов, организация средств самотестирования и самоконтроля студентов и моментального оценивания их знаний. Отмечу некоторые перспективные разработки, представленные на рынке современного специализированного ПО. Это система дистанционного обучения WebTutor (Компания Вэбсофт - разработчик сложных информационных систем и программных комплексов. http://www.websoft.ru/) готовое решение для создания системы дистанционного обучения и корпоративного учебного портала. STELLUS (http://www.stel.ru/do/frameabout.htm) - полнофункциональный, построенный на web-технологии, модульный комплекс программного обеспечения для поддержки открытого образования. Система организации и проведение тестирования SunRav TestOfficePro http://www.sunrav.ru/srtop/index.shtml. Несмотря на наличие этих известных разработок и нескольких десятков не названных мною менее известных, разработка систем тестирования и контроля знаний учащихся остается по прежнему актуальной. Это объясняется как достаточно высокой стоимостью представленных разработок для потребителя, так и тем, что не все разработки позволяют создавать высокоэффективные тесты контроля знаний учащихся по некоторым специальным дисциплинам. Например, системы тестирования, ориентированные на контроль знаний в области органической химии, должны обеспечивать возможность легкого построения сложных химических формул [2].

Коллективом кафедры информационных систем Санкт-Петербургского государственного технологического института (технического университета) выполнена разработка ПО “Система контроля знаний (система тестирования) IS-Test”. ПО позволяет загрузить информацию, предназначенную для тестирования, после чего можно разорвать on-line соединение и выполнить прохождение теста в автономном режиме (off-line). После сдачи теста можно отослать информацию с зашифрованными ответами на вопросы, непосредственно подключившись к серверу или выполнив отправку информации по электронной почте. Разработанное ПО, зарегистрированное в ОФАП (код программы по ЕСПД .03524577.00658-01, срок окончания разработки 28.04.2004), используется в учебном процессе. Подготовлены базы данных с тестами к курсам: "Алгоритмические языки и программирование", "Программирование на языках высокого уровня", "Теория информационных систем", "Системный анализ химических технологий", "Работа с базами данных сети STN International”.

Программный комплекс тестирования предназначен для проверки знаний в форме теста. Состоит из 3-х частей, которые могут находиться на разных компьютерах. Связь между компьютерами может осуществляться при помощи локальной сети (LAN), e-mail или с использованием внешнего носителя информации.

3.5 Варианты построения уроков с использованием электронного учебника

1. Электронный учебник используется при изучении нового материала и его закреплении (20 мин. работы за компьютером). Учащихся сначала опрашивают по традиционной методике или с помощью печатных текстов. При переходе к изучению нового материала ученики парами садятся у компьютера, включают его и начинают работать со структурной формулой и структурными единицами параграфа под руководством и по плану учителя.

2. Электронная модель учебника может использоваться на этапе закрепления материала. На данном уроке новый материал изучается обычным способом, а при закреплении все учащиеся 5-7 мин. под руководством учителя соотносят полученные знания с формулой параграфа.

3. В рамках комбинированного урока с помощью электронного учебника осуществляется повторение и обобщение изученного материала (15-17мин.). Такой вариант предпочтительнее для уроков итогового повторения, когда по ходу урока требуется «пролистать» содержание нескольких параграфов, выявить родословную понятий, повторить наиболее важные факты и события, определить причинно следственные связи. На таком уровне учащиеся должны иметь возможность поработать сначала сообща (по ходу объяснения учителя), затем в парах (по заданию учителя), наконец, индивидуально (по очереди).

4. Отдельные уроки могут быть посвящены самостоятельному изучению нового материала и составлению по его итогам своей структурной формулы параграфа. Такая работа проводится в группах учащихся (3-4 человека). В заключении урока (10 мин.) учащиеся обращаются к электронной формуле параграфа, сравнивая её со своим вариантом. Тем самым происходит приобщение учащихся к исследовательской работе на уроке, начиная с младшего школьного возраста.

5. ЭУ используется как средство контроля усвоения учащимися понятий. Тогда в состав электронного учебника входит система мониторинга. Результаты тестирования учащихся по каждому предмету фиксируются и обрабатываются компьютером. Данные мониторинга могут использоваться учеником, учителем, методическими службами и администрацией. Процент правильно решённых задач даёт ученику представление о том, как он усвоил учебный материал, при этом он может посмотреть, какие структурные единицы им усвоены не в полной мере, и впоследствии дорабатывать этот материал. Таким образом, ученик в какой-то мере может управлять процессом учения.

Учитель, в свою очередь на основе полученной информации также имеет возможность управлять процессом обучения. Результаты класса по содержанию в целом позволяю учителю увидеть необходимость организации повторения по этой или иной структурной единице для достижения максимального уровня обученности. Рассматривая результаты отдельных учащихся по структурным единицам, можно сделать аналогичные выводы по каждому отдельному учащемуся и принять соответствующие методические решения в плане индивидуальной работы. Наконец, Можно проследить динамику обучения ученика по предмету. Стабильно высокие результаты некоторых учеников даёт учителю возможность выстроить для них индивидуальную предметную траекторию.

Методическим объединениям и кафедрам учителей чаще интересны результаты мониторинга по содержанию. Они получают полную информацию об усвоении каждой структурной единицы учениками всей параллели. На основе таких данных выявляется материал, который вызвал затруднения у учащихся, что позволяет на заседаниях кафедр и в рамках творческих групп разрабатывать методические рекомендации по преодолению этих трудностей. Администрации школы система педагогического мониторинга позволяет отслеживать уровень знаний учеников по предметам, видеть его динамику, активизировать методическую работу педагогов по конкретным проблемам содержания образования, контролировать оптимальность учебного плана и на основе данных педагогического мониторинга осуществлять его корректировку.