3.2. Методическое обеспечение дисциплины

№	Название	Местонахождение (кафедра, электронная библиотека)
1.	учебно-методический комплекс дисциплины «Дискретная математика»	электронная библиотека, кафедра математики
2.	литература по дисциплине «Дискретная математика» (в электронном виде)	электронная библиотека, кафедра математики

4. Методические рекомендации по дисциплине

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

5. Лекционный комплекс

ЛЗ 1-4. Множество и способы его задания. Операции над множествами. Бинарные отношения. Отображения.

1-2. Множество. Подмножество. Способы задания множеств. Отношения между множествами. Операции над множествами

Определение 1. Множество – это совокупность определённых различаемых объектов, собранных по какому-либо общему признаку.

Определение 2. Объекты, из которых составлено множество, называются элементами множества.

Множества принять обозначать прописными (большими) латинскими буквами А, В, С, …; элементы множества - строчными (малыми) латинскими буквами а, в, с, ….

Утверждение “Объект а принадлежит множеству А” обозначается: ; утверждение “Объект а не принадлежит множеству А” обозначается: .

Определение 3. Множество, не содержащее ни одного элемента, называется пустым и обозначается .

Существует два основных способа задания множеств:

1) перечислением элементов;

2) характеристическим свойством.

Определение 4. Характеристическое свойство – это свойство, которым обладают все элементы данного множества и не обладает ни один объект, не являющийся его элементом.

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

Определение 5. Два множества и называются равными, если каждый элемент множества является элементом множества , и наоборот, каждый элемент множества является элементом множества . Обозначение: .

Определение 6. Множество называется подмножеством множества , если каждый элемент множества является элементом множества .

Обозначение: . Символ обозначает отношение нестрогого включения. Или обозначение: . Символ обозначает отношение строгого включения.

Примечание. Множества на плоскости изображают с помощью диаграмм Эйлера-Венна.

Определение 7. Булеаном множества называется множество всех подмножеств данного множества , включая Æ и . Обозначение: .

Определение 8. Объединением двух множеств и называется новое множество , состоящее из всех тех и только тех элементов, которые принадлежат множеству или множеству (хотя бы одному из множеств ).

Определение 9. Пересечением множеств и называется множество , состоящее из всех тех и только тех элементов, которые принадлежат и множеству и множеству В.

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

Примечание. Разность множеств определяется аналогично.

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

.

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

.

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

Определение 12. Универсальное множество – множество, в котором все рассматриваемые множества содержаться как подмножества. Обозначение: .

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

Примечание. Дополнение также обозначается: или .

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

1⁰. , (коммутативность);

2⁰. , (ассоциативность);

3⁰. (дистрибутивность относительно );

(дистрибутивность относительно );

4⁰. (идемпотентность);

5⁰. ;

6⁰. ;

7⁰. , (законы де Моргана);

8⁰. ;

9⁰. , ;

10⁰. ;

11⁰. .

3-4. Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений. Их свойства и виды. Отображения. Виды отображений

Определение 1. Упорядоченной парой называется такое множество элементов , где а считается первым элементом, а b – вторым элементом. Обозначение: .

Определение 2. Прямым произведением множеств А и В называется множество всех упорядоченных пар, первые элементы которых принадлежат А, а вторые В.

Примечание. Если А=В, то принято также обозначение .

Утверждение. Если число элементов во множестве А равно n, а во множестве В равно m, то прямое произведение этих множеств состоит из элементов.

Определение 3. Бинарным соответствием между элементами множеств и называется любое подмножество прямого произведения множеств и .

- бинарное соответствие Û .

Определение 4. Бинарным отношением между элементами множества называется любое подмножество множества ².

- бинарное отношение Û Í ²

Примечание. Пусть упорядоченная пара (a,b) является элементом отношения (соответствия) , т.е. . Тогда говорят, что элемент а находится в отношении (соответствии) с элементом b.

Обозначение: ; (читается ”a ро b”).

Примечание. Соответствия и отношения могут быть как математическими, так и не математическими.

Определение 5. Бинарное соответствие , такое, что (a,b)Î в том и только в том случае, когда (a,b)Ï , называется противоположным к соответствию .

Определение 6. Бинарное соответствие , такое, что в том и только в том случае, когда , называется обратным к соответствию .

Способы задания бинарных отношений и соответствий:

1. перечислением элементов;

2. с помощью графика: в системе координат на оси Ох следует изобразить элементы множества А, на оси Оу – элементы множества В и тогда элементы бинарного соответствия (отношения) можно изобразить точками с соответствующими координатами;

3. с помощью графа: элементы множеств А и В являются вершинами графа, которые соединяются дугой, если , причем а - начало дуги, b – конец дуги;

4. с помощью характеристического свойства.

Определение 7. Характеристическое свойство - свойство, которым обладают все пары, входящие в , и не обладает ни одна пара, не входящая в .

Пусть - некоторое бинарное соответствие (отношение); ( ).

Определение 8. Областью определения бинарного соответствия (отношения) называется подмножество множества А, состоящее из всех первых элементов пар, входящих в . Обозначение: .

Определение 9. Областью значений бинарного соответствия (отношения) называется подмножество множества В, состоящее из всех вторых элементов пар, входящих в . Обозначение: .

Свойства бинарных отношений.

1⁰. Рефлексивность.

- рефлексивно

2⁰. Антирефлексивность.

- антирефлексивно

3⁰. Симметричность.

- симметрично

4⁰. Асимметричность.

- асимметрично Û

5⁰. Антисимметричность.

- антисимметрично Û

6⁰. Транзитивность.

- транзитивно Û

7⁰. Антитранзитивность.

- антитранзитивно Û

8⁰. Связность.

- связное Û

Определение 10. Бинарное отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Определение 11. Говорят, что множество М разбито на классы , если выполнены следующие условия:

1) эти классы не пусты;

2) различные классы не пересекаются;

3) объединение всех классов дает множество М.

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

Определение 12. Пусть - отношение эквивалентности. Классом эквивалентности, порожденным элементом а, называется множество всех элементов из А, находящихся с а в отношении . Обозначение: .

Свойства классов эквивалентности.

1⁰. Класс эквивалентности может порождаться любым своим элементом.

2⁰. Классы эквивалентности либо не пересекаются, либо совпадают.

3⁰. Любые два элемента одного класса эквивалентности находятся в отношении , а любые два элемента из разных классов не находятся в отношении .

Определение 13. Множество всех классов эквивалентности по данному отношению называется фактор – множеством множества А по отношению эквивалентности и обозначается .

Определение 14. Бинарное отношение , определенное на множестве А, называется отношением строгого порядка, если оно обладает свойствами антирефлексивности, асимметричности и транзитивности.

Определение 15. Бинарное отношение , определенное на множестве А, называется отношением нестрогого порядка, если оно обладает свойствами рефлексивности, антисимметричности и транзитивности.

Определение 16. Бинарное соответствие между элементами множеств А и В ( ) называется отображением множества А во множество В, если выполнены условия:

1) – всюду определено ( );

2) – определено однозначно.

Пусть - отображение А в В.

Определение 17. Отображение называется инъективным, если для любого элемента из множества существует не более одного прообраза.

Определение 18. Отображение называется сюръективным (отображением «на»), если у любого элемента множества В есть хотя бы один прообраз.

Определение 19. Отображение называется биективным (взаимно однозначным), если оно инъективно и сюръективно одновременно.

Определение 20. Отображение называется тождественным (единичным) отображением.

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

Примечание. Композиция двух отображений f и j существует тогда и только тогда, когда множество значений отображения f является подмножеством области определения отображения j.

ЛЗ 5-8. Основные комбинаторные конфигурации. Формулы комбинаторики.

Определение 1. Упорядоченное - элементное подмножество - элементного множества называют размещением (без повторений) из элементов по ( ).

Число размещений из элементов по обозначают .

Определение 2. - элементное подмножество (неупорядоченное) - элементного множества называют сочетанием (без повторений) из элементов по ( ).

Число сочетаний из элементов по обозначают .

Определение 3. Размещение из элементов по называют перестановкой.

Число перестановок из элементов обозначают .

Определение 4. Размещение из элементов по , в котором один и тот же элемент может повторяться любое число раз (не более ), называется размещением из элементов по с повторениями.

Число размещений из элементов по с повторениями обозначают .

Определение 5. Сочетание из элементов по , в котором один и тот же элемент может повторяться любое число раз (не более ), называется сочетанием из элементов по с повторениями.

Число сочетаний из элементов по с повторениями обозначают .

Определение 6. Перестановки из элементов, в каждую из которых входит элементов вида , элементов вида и т.д. элементов вида , где , называют перестановками из элементов с повторениями.

Число перестановок из элементов с повторениями обозначают .

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

1) Правило суммы. Если объект может быть выбран способами, а объект - способами, то выбор «либо , либо » может быть осуществлен способами.

2) Правило произведения. Если объект может быть выбран способами и после каждого из таких выборов объект может быть выбран способами, то выбор « и » в указанном порядке может быть осуществлен способами.

Бином Ньютона

Формула

( )

называется биномом Ньютона.

Любой член бинома определяется по формуле .

Коэффициенты называются биномиальными.

Свойства биномиальных коэффициентов

1⁰. Коэффициенты членов, равноудалённых от начал и от конца разложения бинома, равны между собой.

2⁰. Сумма всех биномиальных коэффициентов равна .

3⁰. Сумма биномиальных коэффициентов, стоящих на чётных местах, равна сумме биномиальных коэффициентов, стоящих на нечётных местах.

Формула включений и исключений

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

Обозначим - число предметов, обладающих свойствами ; - число предметов, не обладающих ни одним из указанных свойств . Тогда

Эта формула называется формулой включений и исключений.

ЛЗ 9-10. Элементарные булевы функции. Способы задания. Суперпозиция булевых функций. Свойства.

Определение 1. Булевой функцией от переменных называется произвольное отображение вида

.

Областью определения булевой функции от переменных является множество – множество n-мерных векторов, компоненты которых принимают значения 0,1.

Утверждение 1. Число элементов во множестве равно .

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

Утверждение 2. Число булевых функций от переменных равно .

Геометрическая интерпретация булевой функции: множеству можно поставить в соответствие вершины n-мерного единичного куба, определяемого неравенствами .

Элементарные булевы функции от одной переменной

	Обозначение функции
	Название функции	Тождественная	Отрицание	Константа «ноль»	Константа «один»
	0	0	1	0	1
	1	1	0	0	1

Элементарные булевы функции от двух переменных

0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1
0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1

- константа «0»

- конъюнкция

- сумма по модулю два

- дизъюнкция

- стрелка Пирса

- эквиваленция

- импликация

- штрих Шеффера

- константа «1»

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

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

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

Определение 2. Пусть функция определена на , а функции - соответственно на . Тогда функция называется суперпозицией функций и .

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

Для упрощения записи формул (сокращения числа скобок) вводят приоритетность операций: .

Определение 3. Булевы функции и называются равными, если одинаковым наборам значений их переменных соответствуют одинаковые значения функций. Обозначение:

Свойства элементарных булевых функций

Обозначим операции: .

1. Коммутативность:

2. Ассоциативность:

3. Дистрибутивность:

4. Закон двойного отрицания:

5. Законы конъюнкции и дизъюнкции:

6. Законы де Моргана:

7. Законы отрицания:

8. Законы исключения импликации и эквиваленции:

Применяя эти свойства можно упрощать формулы.

Определение 4. Пусть - произвольная булева функция. Функция называется двойственной к функции .

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

Теорема (закон двойственности) Если булевы функции равны, то двойственные к ним функции так же равны:

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

1) Вербальный (словесный);

2) Аналитический (в виде формулы);

3) Табличный (в виде таблицы истинности);

4) Вектором значений;

5) Графический (релейно-контактные схемы и схемы из функциональных элементов).

ЛЗ 11-14. Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ. Полиномы по модулю два. Контактные схемы. Сокращение ДНФ.

Определение 1. Конъюнкцией переменных (конъюнктивным одночленом (КО)) называется конъюнкция некоторого конечного набора переменных и/или их отрицаний.

Определение 2. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция КО-в.

Теорема 1. Для любой булевой функции существует хотя бы одна её ДНФ.

Определение 3. Конъюнктивный одночлен называется совершенным (СКО), если он содержит все переменные, причём либо переменную, либо её отрицание, и не содержит повторяющихся переменных.

Определение 4. Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая ДНФ в которой:

1) каждый конъюнктивный одночлен является совершенным;

2) нет повторяющихся слагаемых (КО-в).

Определение 5. Дизъюнкцией переменных (дизъюнктивным одночленом (ДО)) называется дизъюнкция некоторого конечного набора переменных и/или их отрицаний.

Определение 6. Конъюнктивной нормальной формой (КНФ) называется конъюнкция ДО-в.

Теорема 2. Для любой булевой функции существует хотя бы одна её КНФ.

Определение 7. Дизъюнктивный одночлен называется совершенным (СДО), если он содержит все переменные, причём либо переменную либо её отрицание, и не содержит повторяющихся переменных.

Определение 8. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ в которой:

1) каждый дизъюнктивный одночлен является совершенным;

2) нет повторяющихся множителей (ДО-в).

Теорема 3. (о СДНФ) Любую булеву функцию, не равную тождественно нулю, можно представить СДНФ (причём единственным образом с точностью до порядка следования слагаемых и порядка следования множителей в каждом слагаемом).

Алгоритм перехода от табличного способа задания булевой функции, не равной «0», к аналитическому в виде СДНФ:

1) считаем, сколько раз булева функция принимает значение «1» - ;

2) делаем вывод о том, что в СДНФ будет ровно СКО;

3) составляем «каркас» СДНФ

;

4) если переменная принимает значение «0», то включаем её в соответствующий КО со знаком отрицания. В противном случае - без знака отрицания;

5) получена СДНФ данной булевой функции.

Теорема 4. (О СКНФ) Любая булева функция, не равная тождественно единице, представима в виде СКНФ (причём единственным образом с точностью до порядка следования множителей и порядка следования слагаемых в каждом множителе).

Алгоритм перехода от табличного способа задания булевой функции, не равной «1», к аналитическому в виде

СКНФ:

1) считаем, сколько раз булева функция принимает значение «0» - ;

2) делаем вывод о том, что в СКНФ будет ровно СДО;

3) составляем «каркас» СКНФ

;

4) если переменная принимает значение «1», то включаем её в соответствующий ДО со знаком отрицания. В противном случае - без знака отрицания;

5) получена СКНФ данной булевой функции.

Алгоритм перехода от ДНФ к СДНФ (для булевой функции не равной «0»):

1) проверяем, является ли каждый КО, входящий в ДНФ, совершенным. Если да, то данная ДНФ является СДНФ. Если нет, то переходим к шагу 2;

2) приводим КО, не являющиеся совершенными, к совершенному виду, добавляя недостающие переменные по правилам: ; ;

3) проверяем, имеются ли среди слагаемых полученной ДНФ одинаковые КО. Если нет, то полученная ДНФ является СДНФ. Если да, то из каждой серии одинаковых КО-в оставляем по одному. В итоге получим СДНФ.

Алгоритм перехода от КНФ к СКНФ (для булевой функции не равной «1»):

1) проверяем, является ли каждый ДО, входящий в КНФ, совершенным. Если да, то данная КНФ является СКНФ. Если нет, то переходим к шагу 2;

2) приводим ДО, не являющиеся совершенными, к совершенному виду, добавляя недостающие переменные по правилам: ; ;

3) проверяем, имеются ли среди множителей полученной КНФ одинаковые ДО. Если нет, то полученная КНФ является СКНФ. Если да, то из каждой серии одинаковых ДО-в оставляем по одному. В итоге получим СКНФ.

Алгоритм перехода от СКНФ к СДНФ (для булевой функции не равной «0»):

1) находим СКНФ по правилу:

отрицание формулы равно конъюнкции тех и только тех СДО от тех же самых переменных, которые не входят в СКНФ ;

2) находим по правилу:

отрицание формулы , записанной в базисе , может быть получено из заменой

- всех вхождений » на « », и « » на « »;

- каждой переменной на и на ;

3) получили СДНФ

Алгоритм перехода от СДНФ к СКНФ (для булевой функции не равной «1»):

1) находим СДНФ по правилу:

отрицание формулы равно дизъюнкции тех и только тех СКО от тех же самых переменных, которые не входят в СДНФ ;

2) находим по правилу:

отрицание формулы , записанной в базисе , может быть получено из заменой

- всех вхождений » на « », и « » на « »;

- каждой переменной на и на ;

3) получили СКНФ = .

Алгоритм перехода от ДНФ к КНФ:

1) ;

2) ;

3) .

Алгоритм перехода от КНФ к ДНФ:

1) ;

2) ;

3) .

Правила сокращения ДНФ

Пусть К – элементарная конъюнкция.

1) ;

2) склеивание: ;

3) поглощение: или .

Определение 9. Назовем полиномом Жегалкина (по модулю два) сумму по модулю два конъюнкций переменных без отрицаний и двоичной константы (0 или 1).

Теорема 5. (о полиноме по модулю два) Любая булева функция может быть представлена полиномом Жегалкина и это представление единственно.

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

Утверждение. Если в СДНФ произвести замену всех знаков дизъюнкции « » знаками суммы по модулю два « », а все «отрицаемые» переменные заменить согласно тождеству , то после преобразований (раскрытие скобок, приведение подобных) будет получен полином Жегалкина, представляющий данную булеву функцию.

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

Чтобы построить релейно-контактную схему для любой булевой функции, нужно сначала найти равную её функцию, представляющую собой результат суперпозиции функций: «отрицание», «конъюнкция» и «дизъюнкция».

Простейшие контактные схемы:

	Функция	Контактная схема
1
2
3

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

Определение 1. Контактная схема - это граф с полюсами А, В. Ребро – это контакт, который замкнут, если соответствующая ему переменная принимает значение 1, разомкнут, - если 0.

ДНФ и КНФ – аналитические способы задания функций, представляющие собой результат суперпозиции функций: «отрицание», «конъюнкция» и «дизъюнкция». Для ДНФ и КНФ контактная схема строится на основании правил построения 3-х простейших контактных схем.

Примечание. Если булева функция не является ни ДНФ, ни КНФ, но представляет собой результат суперпозиции функций: «отрицание», «конъюнкция» и «дизъюнкция», то контактная схема строится также на основании правил построения 3-х простейших контактных схем. Иначе для булевой функции сначала нужно найти равную ей функцию, представляющую собой результат суперпозиции функций: «отрицание», «конъюнкция» и «дизъюнкция».

В технических реализациях ДНФ желательно сократить число контактов (или параллельных ветвей). Эта задача сводится к задаче сокращения ДНФ.

Правила сокращения ДНФ

Пусть К – элементарная конъюнкция.

1) ;

2) склеивание: ;

3) поглощение: или .

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

Определение 2. Пусть фиксированы множества: F (элементарных булевых функций) и X (булевых переменных). Схемой из функциональных элементов над базисом (СФЭ), или просто схемой над базисом , также -cxeмой, называют бесконтурный ориентированный граф (т.е. сеть), каждая вершина которого помечена одним из элементов множества так, что выполняются следующие требования:

1) каждый вход сети помечен либо некоторым переменным из X, либо некоторой константой из ;

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

При изображении схем входы обозначаются кружочками, а вершины, не являющиеся входами, - треугольниками, внутри которых записано обозначе­ние функции, помечающей данную вершину. Выходы отмечаются „выходными" стрелками (или закрашенным кружочком, или кружочком с точкой в центре).

Определение 3. Глубина СФЭ над базисом - максимальное число внутренних вершин в ориентированных цепях, соединяющих вход с выходом.

ЛЗ 15-16. Полные системы булевых функций. Теорема Поста

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

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

Функционально замкнутые классы булевых функций

1. - класс булевых функций сохраняющих «0»

Определение 3. Булева функция называется функцией сохраняющей «0», если .

2. - класс булевых функций сохраняющих «1»

Определение 4. Булева функция называется функцией сохраняющей «1», если .

3. - класс самодвойственных булевых функций

Определение 5. Булева функция называется самодвойственной, если , где - функция двойственная к .

4. - класс линейных булевых функций

Определение 6. Булева функция называется линейной, если её полином по модулю два имеет линейных вид, т.е.

, .

5. - класс монотонных булевых функций.

Определение 7. Набор предшествует набору , если .

Обозначение:

Определение 8. Булева функция называется монотонной, если .

Теорема 1. Классы , , , , булевых функций являются функционально замкнутыми.

Утверждение. Классы попарно различные.

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

	+	-	-	+	+
	-	+	-	+	+
	+	+	+	+	+
	-	-	+	+	-
	+	+	-	-	+
	+	+	-	-	+
	+	-	-	+	-
	-	+	-	-	-
	-	+	-	+	-
	-	-	-	-	-
	-	-	-	-	-

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

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

Определение 10. Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным).

Теоремы о полноте

Теорема 2. Пусть даны две системы булевых функций:

и .

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

Теорема 3. Если система булевых функций полна, то система двойственных функций также полна.

Теорема 4. (Теорема Поста) Для того, чтобы система булевых функций была полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию:

1. не сохраняющую единицу;

2. не сохраняющую ноль;

3. не самодвойственную;

4. не линейную;

не монотонную.

ЛЗ 17-18. Основные понятия теории кодирования. Корректирующие коды

- множество двоичных кодовых слов длины .

Определение 1. Любое подмножество множества называют двоичным кодом (равномерным) длины .

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

Определение 3. Расстоянием Хэмминга кода называется число

.

Определение. 4 Двоичный код с расстоянием Хэмминга называют корректирующим - кодом.

Теорема 1. Корректирующий - код позволяет обнаруживать ошибки, возникающие в позициях, и исправлять ошибки в позициях кодового слова.

Определение 5. Двоичный код с расстоянием Хэмминга , построенный по алгоритму Хэмминга, называют кодом Хэмминга.

Алгоритм построения кода Хэмминга на примере (2,6,3)-кода Хэмминга.

1. В основной таблице последовательно заполняются все позиции кодовых слов. Позиции с номерами (т.е. 1, 2, 4, 8, ...) называются контрольными, остальные – информационными (в таблице контрольные позиции помечены *).

2. Затем заполняются информационные позиции в порядке возрастания кодовых слов как двоичных чисел. Мощность кода Хэмминга равна , где - число информационных позиций.

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

		0		0	0
		0		0	1
		0		1	0
		0		1	1
		1		0	0
		1		0	1
		1		1	0
		1		1	1
Основная таблица

3	0	1	1
5	1	0	1
6	1	1	0
Вспомогательная таблица

4. Находим выражения для расчёта контрольных позиций:

; ; .

5. В основной таблице заполняются контрольные позиции на основании формул из п.4.

0	0	0	0	0	0
0	1	0	1	0	1
1	0	0	1	1	0
1	1	0	0	1	1
1	1	1	0	0	0
1	0	1	1	0	1
0	1	1	1	1	0
0	0	1	0	1	1
Основная таблица

6. В результате получим код Хэмминга длины 6.

Примечание. Точно так же строятся коды Хэмминга любой длины.

Рассмотрим метод обнаружения и исправления ошибок для кода Хэмминга на примере (2,6,3)-кода Хэмминга.

Предположим, что получено кодовое слово .

В правильном кодовом слове суммы

равны 0 (так как в этом случае и т.д.).

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

А теперь рассмотрим, каким образом можно исправлять ошибочное кодовое слово при условии, что ошибка произошла в одной позиции. Из формул для можно усмотреть, что двоичное число в десятичной системе определяет номер ошибочной позиции.

Например, получено кодовое слово

1	0	0	1	0	0

Определяем , , : (в 5-й позиции ошибка).

Примечание. Точно так же обнаруживаются ошибки в одной или двух позициях и исправляются в одной и в кодах Хэмминга произвольной длины. Следует помнить, что если ошибки произошли в 3-х или более позициях, то нельзя гарантировать их обнаружение, а также нельзя исправить ошибки, если они произошли в 2-х или более позициях.

Основная задача теории кодирования (равномерного)

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

Формальная поставка задачи:

. (1)

Обратной является задача минимизации длины кода при ограничении на мощность кода с заданным расстоянием Хэмминга:

. (2)

Смысл задач (1), (2) состоит в сокращении информационной избыточности и, следовательно, в сокращении затрат на обработку и передачу информации.

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

Теорема 2. Код Хэмминга длины , где имеет максимальную мощность.

ЛЗ 19-20. Некоторые свойства кодов. Эффективное кодирование. Коды Фано, Шеннона, Хаффмена

Некоторые свойства кодов

Определение 1. Код назовем разделимым, если из каждого равенства в алфавите вида следует, что l=k и , t=1,2,…,k.

То есть любое сообщение, составленное из кодовых слов, единственным образом разлагается на кодовые слова.

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

Теорема 1 (критерий разделимости). Код с длинами кодовых слов является разделимым тогда и только тогда, когда выполняется неравенство Крафта-Макмиллана

.

Определение 2. Конкатенацией слов и называется слово , полученное выписыванием подряд сначала всех символов слова , а потом всех символов слова .

Определение 3. Слово называют началом (префиксом) слова , если существует слово такое, что = ; при этом слово называют собственным началом слова , если ( - пустое кодовое слово).

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

Замечание. Префиксный код является разделимым.

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

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

Теорема 2 (критерий префиксности). Для префиксных кодов и только для них множество кодовых слов совпадает с множеством концевых вершин кодового дерева (т.е. вершин, из которых не исходит ребер).

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

Теорема 3 (критерий полноты). Разделимый код является полным тогда и только тогда, когда он является префиксным и выполнено равенство .

Теорема 4 (критерий полноты). Разделимый код является полным тогда и только тогда, когда он префиксный и из каждой внутренней вершины кодового дерева исходит ровно два ребра.

Эффективное кодирование (кодирование с минимальной информационной избыточностью)

Определение 8. Стоимостью (средней длиной) кода V при распределении P называют величину , где - вероятность появления буквы ; - длина кодового слова , соответствующего букве .

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

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

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

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

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

Алгоритм построения кода Фано:

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

2) Буквам из первой части приписывается символ 0, а буквам из второй части – символ 1.

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

4) Процесс продолжается до тех пор, пока весь список не будет разбит на части, содержащие по одной букве.

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

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

Примечание. Метод Шеннона применим лишь в случае, когда все вероятности положительны.

Алгоритм построения оптимального кода Хаффмена:

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

2) Эта процедура проделывается со списком из вероятностей и так далее до тех пор, пока не получится список из двух вероятностей.

3) После получения списка из двух вероятностей первой из них приписывается символ 0, а второй – символ 1 (оптимальный код для двух букв при произвольном распределении вероятностей).

4) Согласно теореме 5 (приведённой ниже) из оптимального кода для двух букв строится оптимальный код для трех букв при соответствующем списке вероятностей и так далее до тех пор, пока не получится оптимальный код при исходном списке вероятностей.

Теорема 5 (Хаффмена).

Если оптимальный код при распределении и ,

то код

является оптимальным при распределении

ЛЗ 21-22. Основные понятия теории графов

Основные понятия теории графов. Виды графов. Способы задания графов. Планарные графы. Группы автоморфизмов графов

Определение 1. Неориентированным графом называют пару множеств , где - множество вершин, - множество ребер (неупорядоченных пар ). Обозначение:

Определение 2. Ориентированным графом называют пару множеств , где - множество вершин, - множество дуг (упорядоченных пар ).

Определение 3. Смешанным графом называют пару множеств , где - множество вершин, - множество ребер и дуг.

Замечание. В дальнейшем будем рассматривать неориентированные графы.

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

1. графический;

2. с помощью матрицы смежности.

Матрица смежности графа – таблица размера , где на пересечении -й строки и -го столбца ставится 1, если ; 0 – в противном случае;

3. формальный.

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

Определение 5. Ребро называется инцидентным вершине и вершине .

Определение 6. Два ребра называются смежными, если существует вершина, им инцидентная.

Определение 7. Степенью вершины называют число инцидентных этой вершине ребер.

Определение 8. Цепь – это последовательность смежных ребер.

Определение 9. Цикл – замкнутая цепь.

Определение 10. Гамильтонов цикл – это цикл, проходящий через все вершины ровно один раз.

Определение 11. Эйлеров цикл – цикл, содержащий все ребра ровно по одному разу

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

Определение 12. Длина цепи – это число ребер в цепи.

Определение 13. Расстояние между вершинами – это длина кратчайшей цепи, связывающей вершины.

Определение 14. Диаметр графа – это расстояние между двумя наиболее удаленными вершинами.

Определение 15. Граф называют подграфом графа , если , .

Определение 16. Остовным называют подграф графа , содержащий все вершины графа .

Определение 17. При удалении вершины в графе удаляются все инцидентные ей ребра.

Определение 18. При удалении ребра остаются инцидентные вершины.

Определение 19. Граф - дополнение графа , если , , - полный граф.

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

Определение 20. Регулярный граф - граф, в котором все вершины имеют одну и ту же степень.

Определение 21. Паросочетание - регулярный граф со степенями вершин, равными 1.

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

Определение 23. Полный граф - граф, содержащий все возможные ребра.

Определение 24. Дерево – связный граф без циклов.

Определение 25. Граф - двудольный, если , , и .

Теорема 2 (Кёнига). Граф является двудольным тогда и только тогда, когда в нём нет циклов нечётной длины.

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

Определение 26. Граф называется планарным, если его можно так «нарисовать» на плоскости, чтобы никакие два ребра не пересекались во «внутренних» точках. В этом случае укладка графа на плоскости называется плоским графом.

Примечание. Всякий плоский граф делит множество точек плоскости на части – грани.

Теорема 3. ,

где - число вершин, - число рёбер, - число граней.

Утверждение 1. Граф (полный граф на 5 вершинах) не планарен.

Утверждение 2. Граф (полный двудольный граф с 3 вершинами в каждой доле) не планарен.

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

Теорема 4 (Понтрягина-Куратовского). Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам и .

Группы автоморфизмов графов

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

, где

; , если .

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

Утверждение 3. Если - автоморфизм, то .

То есть автоморфизм – перестановка на множестве вершин графа , сохраняющая множество рёбер .

Теорема 5. Множество всех автоморфизмов графа является группой, которую называют группой автоморфизмов графа .

Утверждение 4. Если - автоморфизм, то степени вершин совпадают.

ЛЗ 23-24. Задачи на графах: задача о независимом множестве вершин, задача о клике, задача о покрывающем множестве вершин

Независимое множество вершин

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

Примечание. НМВ также называют внутренне устойчивым множеством вершин.

Определение 2. НМВ называется максимальным по включению, если оно не является подмножеством никакого другого НМВ, т.е. если его нельзя «расширить».

Определение 3. НМВ с наибольшим числом вершин называется наибольшим по мощности НМВ.

Определение 4. Число вершин в наибольшем НМВ называется числом вершинной независимости графа и обозначается .

Теорема 1. ,

где - число вершин графа ,

- наибольшая степень вершины.

Задача о НМВ может быть сформулирована в виде задачи распознавания или задачи оптимизации.

Задача распознавания: в заданном графе для заданного числа найти такое НМВ , что .

Задача оптимизации: в заданном графе найти НМВ наибольшей мощности.

Клика

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

Примечание. Клику также называют полностью зависимым множеством.

Определение 6. Клика называется максимальной по включению, если она не является подмножеством никакой другой клики, т.е. если её нельзя «расширить».

Определение 7. Клика с наибольшим числом вершин называется наибольшей по мощности кликой.

Определение 8. Число вершин в наибольшей клике называется кликовым числом (плотностью) графа и обозначается .

Теорема 2. ,

где - число вершин графа ,

- наименьшая степень вершины.

Примечание. Задача о клике может быть сформулирована в виде задачи распознавания или задачи оптимизации (аналогично задаче о НМВ).

Теорема 3. Пусть - дополнение графа . Тогда - клика в графе тогда и только тогда, когда - НМВ в графе .

Следствие. Таким образом, задачи о клике (распознавания и оптимизации) сводятся к задачам о НМВ.

Покрывающее множество вершин

Определение 9. Подмножество множества вершин графа называют покрывающим множеством вершин (ПМВ), если любое ребро графа инцидентно, по крайней мере, одной вершине этого множества.

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

Определение 11. ПМВ с наименьшим числом вершин называется наименьшим по мощности ПМВ.

Определение 12. Число вершин в наименьшем ПМВ называется числом вершинного покрытия графа и обозначается .

Теорема 4. ,

где - число вершин графа .

Следствие. - наибольшее НМВ графа тогда и только тогда, когда - наименьшее ПМВ.

Задача о ПМВ может быть сформулирована в виде задачи распознавания или задачи оптимизации.

Задача распознавания: в заданном графе для заданного числа найти такое ПМВ , что .

Задача оптимизации: в заданном графе найти ПМВ наименьшей мощности.

Задачи на графах: задача о доминирующем множестве вершин, задача о вершинной раскраске, задача коммивояжера

Доминирующее множество вершин

Определение 1. Подмножество множества вершин графа называют доминирующим множеством вершин (ДМВ), если любая вершина графа, не принадлежащая , смежна, по крайней мере, с одной вершиной из .

Примечание. ДМВ также называют внешне устойчивым множеством вершин или всесмежным множеством вершин.

Определение 2. ДМВ называется минимальным по включению, если оно перестаёт быть доминирующим при удалении любой вершины из этого множества.

Определение 3. ДМВ с наименьшим числом вершин называется наименьшим по мощности ДМВ.

Определение 4. Число вершин в наименьшем ДМВ называется числом доминирования (внешней устойчивости) графа и обозначается .

Теорема 1. .

Задача о ДМВ может быть сформулирована в виде задачи распознавания или задачи оптимизации.

Задача распознавания: в заданном графе для заданного числа найти такое ДМВ , что .

Задача оптимизации: в заданном графе найти ДМВ наименьшей мощности.

Ядро

Определение 5. Подмножество множества вершин графа называют ядром, если оно является одновременно независимым и доминирующим множеством вершин.

Теорема 2. НМВ является ДМВ тогда и только тогда, когда оно является максимальным по включению НМВ.

Вершинная раскраска графа

Определение 6. Вершинной раскраской графа называется приписывание каждой вершине графа определённого цвета (номера).

Определение 7. Вершинная раскраска графа называется правильной, если никакие две смежные вершины графа не окрашены в один цвет.

Определение 8. Наименьшее число цветов, необходимых для правильной вершинной раскраски графа, называется хроматическим числом этого графа и обозначается .

Теорема 3. .

Теорема 4. ,

где - наибольшая степень вершины.

Теорема 5. ,

где - число вершин графа,

- число вершинной независимости.

Гипотеза 4-х красок. .

Ориентированные графы

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

Примечание. Матрица смежности в общем случае не симметрическая.

Определение 9. Полустепень исхода вершины – это число дуг, исходящих из вершины, полустепень захода - число дуг, заходящих в вершину.

Определение 10. Дуги смежные, если конец одной совпадает с началом другой.

Определение 11. Путь – последовательность смежных дуг.

Определение 12. Контур – замкнутый путь.

Определение 13. Петля – это дуга ­ .

Определение 14. Орграф направленный, если из следует (нет петель).

Определение 15. Турнир – любые две вершины соединены одной и только одной дугой (нет петель).

Задача коммивояжера

Пусть - орграф с вершинами и всеми дугами. Каждой дуге поставлено в соответствие число (длина дуги или расстояние от вершины ­ до вершины ­ ).

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

Определение 16. Длиной гамильтонова контура называется сумма длин дуг, составляющих этот контур:

.

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

Задача полностью определяется матрицей расстояний: на пересечении -й строки и -го столбца находится число . На главной диагонали обычно ставят знаки бесконечности ( - переходов в контуре быть не должно).

Задача циклически симметрична: контуры, получаемые один из другого циклической перестановкой вершин эквивалентны (имеют равную длину). Поэтому можно ограничиться контурами, начинающимися с первой вершины. Число контуров равно .

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

ЛЗ 25-26. Задача о последовательных станках. Задача о 2-х последовательных станках. Задача о параллельных (идентичных) станках

Задача о последовательных станках

Постановка задачи: Имеется n станков и m видов деталей. Последовательность обработки каждого вида деталей на станках одна и та же, начиная с 1-го станка до последнего:

1 2 n

…………….

Заданы числа - время обработки партии деталей -го вида на станке .

Ограничения на порядок обработки деталей:

1) обработка партии одного вида на станке происходит без прерываний от начала до конца обработки;

2) каждый станок в любой момент времени может обрабатывать партию деталей только одного вида или простаивать;

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

Общее время обработки – это интервал времени между началом обработки на первом станке и завершением обработки последней партии на последнем станке.

Необходимо найти оптимальный график обработки, то есть график, которому соответствует минимальное общее время обработки.

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

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

Задача о двух станках (частный случай задачи о последовательных станках)

Для такой задачи существует простой точный алгоритм решения.

Пусть - время обработки партии деталей вида на 1-м и 2-м станках соответственно.

Описание алгоритма:

1) положим ;

2) пусть ;

3) если , то деталь (партия деталей вида k) обрабатывается первой; если , то последней;

4) этот же расчет повторяется для оставшихся (m-1) деталей при уже определенном месте детали k. В итоге за (m-1) шагов будет получена оптимальная очередность обработки деталей.

Примечание. Из-за неопределенности выбора по алгоритму можно получить несколько расписаний, но все они будут оптимальными.

Задача о n параллельных станках

Постановка задачи: Имеется n идентичных станков, на которых может обрабатываться любая из m деталей, . Известно время обработки детали ­ . Необходимо распределить детали по станкам так, чтобы общее время обработки было минимальным.

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

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

ЛЗ 27-28. Периодические однопроцессорные расписания (в дискретном времени). Задача сетевого планирования

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

Рассмотрим процесс передачи дискретной информации по каналу связи. Шкала времени разделена на единичные интервалы , . Имеется n абонентов.

Условия:

1) в течение одного единичного интервала (кванта времени) передаётся один и только один сигнал от какого-либо абонента;

2) сигналы -го абонента повторяются через равные интервалы времени периодически с периодом .

Определение 1. Расписания, удовлетворяющие сформулированным двум условиям, назовем допустимыми.

Определение 2. Вектор , соответствующий допустимому расписанию, назовем допустимым набором периодов, если .

Обозначим - множество допустимых наборов периодов размерности .

Пусть , .

Определение 3. Композицией допустимого набора периодов на допустимый набор периодов по числу назовем допустимый набор периодов , полученный упорядочением по неубыванию чисел

.

Определение 4. Набор , где - простое число, назовем простым.

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

Утверждение. Если n£12, то множество можно получить композицией допустимых наборов периодов меньшей размерности.

В таблице представлены множества :

	(2,2)
	(3,3,3), (2,4,4)
	(4,4,4,4), (2,4,8,8), (2,6,6,6), (3,3,6,6)
	(5,5,5,5,5), (2,4,8,16,16), (2,4,12,12,12), (2,6,6,12,12), (2,8,8,8,8), (3,3,6,12,12), (3,3,9,9,9), (3,6,6,6,6), (4,4,4,8,8), (4,4,6,6,6)

В 23 элемента.

Задачи об определении оптимальных наборов периодов и, соответственно, оптимальных периодических однопроцессорных расписаний.

1) Задача об организации передачи дискретной информации по каналу связи

Пусть t длительность кванта времени. Необходимо организовать процесс передачи дискретной информации по каналу связи от абонентов. Пусть – предельные значения для периодов повторения сигналов от абонентов.

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

Экономический смысл задачи: чем больше длительность кванта времени, в течение которого передается один сигнал, тем слабее требования, предъявляемые к каналу связи.

Задачу можно решить методом полного перебора.

1) Находим множество .

2) Для набора определяем .

3) Определяем оптимальный набор такой, что . Набор - решение задачи.

2) Задача об организации периодической обработки деталей на станке.

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

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

Экономический смысл задачи: снижение пиковой загрузки станка (рабочего места).

Задачу можно решить методом полного перебора.

1) Находим множество .

2) Для набора определяем .

3) Определяем оптимальный набор такой, что . Набор - решение задачи.

Задача сетевого планирования (СП)

Сеть - это орграф без контуров с двумя выделенными вершинами (полюсами). Один полюс – начальный, из него дуги только исходят, другой – конечный, в него дуги только заходят.

Типичная задача сетевого планирования формулируется следующим образом (в дискретном времени):

Имеется n видов работ, которым ставится в соответствие n вершин орграфа. Из вершины i в вершину j проводится дуга, если работа j может быть начата после завершения работы i. Орграф не должен содержать контуров, иначе задача сетевого планирования неразрешима.

Имеется m видов ресурсов (станков, рабочих по профессиям).

При выполнении i–й работы в течение одного единичного интервала времени затрачивается единиц каждого ресурса.

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

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

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

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

ЛЗ 29-30. Формализация понятия «алгоритм». Машина Тьюринга

Определение 1. Алгоритмом называется общий единообразный, точ­но определенный способ решения любой задачи из дан­ной массовой проблемы.

Массовая проблема - класс однотипных задач.

Примечание. Это определение алгоритма называют интуитивным.

Характерные черты алгоритма

1) Дискретность. Алгоритм - это пошаговый процесс. Алгоритм – это дискретная цепочка универсальных действий.

2) Детерминированность. На каждом шаге результат зависит от результата предыдущего шага и определяет следующий шаг.

3) Элементарность шагов. Закон получения последующей системы величин из предшествующей должен быть простым.

4) Массовость. Возможность применения алгоритма к обширному классу данных. Начальная система величин может выбираться из некоторого потенциально бесконечного множества.

5) Результативность. Конечный результат всегда должен быть получен.

В подходах к уточнению (формализации) понятия алгоритма мож­но выделить три основных направления:

1) понятие алгоритма связано с понятием эффективно вычислимой функции. Этим занимались А. Черч, К. Гедель, С. Клини.

2) Сущность понятия алгоритм раскрывается с помощью условной машины, которая в каждый дискретный момент времени выполняет некоторую элементарную операцию из заданного набора таких операций. Это направление развито Тьюрингом и Постом.

3) Связано с понятием нормальных алгоритмов из работ А. А. Маркова.

Машина Тьюринга

Устройство машины Тьюринга включает в себя:

1) внешний алфавит, то есть конечное множество символов . В этом алфавите в виде слова кодируется та информация, которая подается в машину.

2) Внутренний алфавит, то есть конечное множество символов . Символы - состояния машины. Два состояния имеют особое назначение: - начальное состояние ма­шины, - заключительное состояние (стоп-состояние).

3) Бесконечная в обе стороны лента (внешняя память машины). Она разбита на ячейки. В каждую ячейку может быть записана только одна буква. Пустую ячейку будем обозначать символом .

4) Управляющая головка. Она передвигается вдоль ленты и может останавливаться напротив какой-либо ячейки, т.е. воспринимать символ. В одном такте работы машины управляющая головка может сдвигаться только на одну клетку (вправо, влево) или оставаться на месте.

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

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

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

2) Машина никогда не останавливается (не переходит в стоп-состояние). В таком случае говорят, что машина не применима к начальной информации .

В каждом такте работы машина действует по функциональной схеме, которая имеет вид:

Здесь — буквы внешнего алфавита; — состояния машины; — символы сдвига.

В зависимости от того, какая буква на ленте обозревается управляющей головкой (в нашей записи ) и в каком состоянии (в нашей записи ) находится машина, в данном такте вырабатывается команда, состоящая из трех элементов:

1) Буква внешнего алфавита, на которую заменяется обозреваемая буква ( ).

2) Адрес ленты (внешней памяти) для следующего такта

.

3) Следующее состояние машины ( ).

Совокупность всех команд образует программу машины Тьюринга. Программа представляется в виде дву­мерной таблицы и называется Тьюринговой функциональной схемой.

Тезис Тьюринга. Всякий алгоритм может быть реализован в машине Тьюринга.

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