WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«ДИСКРЕТНАЯ МАТЕМАТИКА Учебно-методическое пособие Челябинск УДК 519.2 ББК 22.17 А-47 Алексеева О.А. Дискретная математика: учебно-методическое пособие. – ...»

Алексеева О.А.

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебно-методическое пособие

Челябинск

УДК 519.2

ББК 22.17

А-47

Алексеева О.А. Дискретная математика: учебно-методическое

пособие. – Челябинск: НОУВПО РБИУ, 2014. – 56 с.

В учебно-методическом пособии приводятся теоретические

сведения, задачи и задания, необходимые для самостоятельной работы студентов по дисциплине «Дискретная математика». Учебнометодическое пособие содержит достаточное количество разнообразных заданий по предусмотренным темам курса, решение которых способствует пониманию предмета. Предназначается для студентов II курса, обучающихся по направлениям: 230700.62 Прикладная информатика, 080500.62 Бизнес-информатика.

Рецензенты:

Чеботарев С.С. – кандидат физ.-мат. наук, заведующий кафедрой математики и информатики, НОУВПО РБИУ.

Турлакова С.У. – кандидат физ-.мат. наук, доцент кафедры Прикладная математика ФГБОУ ВПО «ЮУрГУ» (НИУ) УДК 519.2 ББК 22.17 © Алексеева О.А., 2014 © НОУВПО РБИУ, 2014 Содержание Введение

1. Множества и отношения

1.1. Из истории вопроса

1.2. Доказательство тождеств

1.3. Задачи о множествах

1.4. Отношения

2. Методы комбинаторного анализа

2.1. Комбинаторные объекты

2.2. Свойства комбинаторных объектов

2.3. Рекуррентные уравнения



3. Графы

3.1. Понятия теории графов. Маршруты в графе

3.2. Изоморфизм плоских графов

4. Задачи о маршрутах. Алгоритм Дейкстры

5. Применение методов теории графов в практических задачах..36

5.1. Задача о раскрасках. Проблема четырех красок

5.2. Анализ алгоритмов на графах

6. Анализ и синтез комбинационных схем автоматов

6.1. Минимизация ФАЛ от большого числа переменных.................45

6.2. Основные автоматные узлы комбинационного типа..................47 Заключение

Библиографический список

Введение Учебно-методическое пособие для самостоятельной работы студентов являются частью учебно-методического комплекса дисциплины по дискретной математике, рассчитанного на студентов II курса по направлениям: 230700.62 Прикладная информатика, 080500.62 Бизнес-информатика. Место дисциплины в структуре программы: математический и естественнонаучный цикл, базовая часть.

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

В первом разделе «Множества и отношения» в подразделах 1.1 и 1.2 приводятся необходимые для самостоятельной работы сведения и пример доказательства тождества, в следующих подразделах даны задачи для самостоятельной работы.

Во втором разделе «Методы комбинаторного анализа» предлагаются комплекты задач по следующим темам: комбинаторные объекты, свойства комбинаторных объектов. В подразделе «Рекуррентные уравнения» рассматриваются подробные решения типовых задач дискретной математики и особое внимание уделено теме «Производящие функции».

В третьем разделе Даны задачи по темам «Понятия теории графов» и «Маршруты в графах». Особое внимание и подробная теория излагается по теме «Изоморфизм графов».

В разделах 4 и 5 рассмотрены основные алгоритмы классических задач теории графов: Алгоритм Дейкстры и Задача о раскрасках.

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

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

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

–  –  –

Основы теории множеств созданы математиками XIX века.

Начало заложил немецкий математик Георг Кантор, ему принадлежит высказывание, которое можно рассматривать как интуитивное определение множества: «Множество есть многое, мыслимое как единое».

Опыт развития показал, что интуитивное определение понятия множества не является состоятельным, поскольку приводит к парадоксам – например, парадокс Рассела о парикмахере: парикмахер, проживающий в деревне, бреет всех жителей деревни, которые не бреются сами. Вопрос: бреет ли он самого себя? Этот и другие парадоксы показали, что интуитивные определения в математике не могут рассматриваться как основополагающие. Выход был найден в построении системы аксиом, которые не допускали бы применения интуитивного понятия при доказательствах теорем или в определениях. К настоящему времени сложилось несколько аксиоматических систем теории множества. По оценкам экспертов, наиболее базовой из всех существующих является система Цермело (Z – система). Она состоит из семи аксиом: Z1– аксиома объемности; Z2 – аксиома пары; Z3 – аксиома суммы; Z4 – аксиома степени; Z5 – аксиома выделения; Z6 – аксиома бесконечности; Z7 – аксиома выбора. На основе понятия принадлежности элемента множеству и аксиом Z1, Z2, Z3 получены понятие подмножества и арсенал основных операций теории множеств – объединение, пересечение, разность и симметрическая разность. Аксиома выделения дает метод построения множеств, аксиома степени касается вопроса множества всех подмножеств конечного множества и его мощности. Аксиома бесконечности касается мер мощности множеств. Аксиома выбора дает возможность их упорядочения и сравнения.

Множества и отношения на них являются предметом изучения любой математической дисциплины. Исследования дискретной математики проводятся на конечных или счетных множествах; основные сведения о них и приведены в первом разделе учебного пособия в составе УМК, а также в многочисленных литературных источниках.

1.2. Доказательство тождеств Тождеством в теории множеств называется запись следующего вида:

A(В C) = (A B) (A C).

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

Доказательство справедливости такого рода тождеств основывается на определении равенства множеств, базирующегося на понятии «подмножество», т. е. если А В и В А, то А = В. Из этого следует, что доказательство проводится в обе стороны – в прямую и обратную. В первом случае доказывается, что любой элемент множества, стоящего в левой части равенства, является элементом множества, стоящего справа. Затем наоборот, что любой элемент множества, стоящий в правой части равенства, является элементом множества, стоящего слева. И из этого следует, что равенство (тождество) доказано.

В прямую сторону.

Пусть xA (B C) xA и x(B C) xA и (xB или xС) (xA и xB) или (xA и xC) x(A B) или x(A C) x(A B) (A C).

В обратную сторону.

Пусть x(A B)(A C) x(A B) или x(A C) (xA и xB) или (xA и xC) xA и (xB или xС) xA и x(B C) xA(B C).

Для закрепления изложенного материала предлагается выполнить 5 примеров из задания 1.10, приведенного ниже.

1.3. Задачи о множествах

Задание 1

Задание 1.1. Множества А и В заданы перечислением:

А = {a, b, c, d, e}, B = {d, e, f}. Так же перечислением задать множества, являющиеся объединением, пересечением, разностью, симметрической разностью и декартовым произведением этих множеств.

Задание 1.2.

Проиллюстрируйте известные вам операции (,, \, ) с помощью диаграмм Эйлера – Венна для следующих вариантов взаимного расположения множеств А и В на плоскости (рис. 1).





Рис. 1. Варианты взаимного расположения множеств А и В на плоскости Задание 1.3. Пусть X – множество {1, 2}, а Y – множество {x: x = y + z; y, z X}. Определить в явном виде (списком) множество Y.

Задание 1.4. Выразить операции,, \ через две другие:

а), ;

б), ;

в) \,.

Задание 1.5.

Доказать, что если А есть множество корней уравнения x2 – 7x + 6 = 0, а В = {1, 6}, то А = В.

Задание 1.6.

Проиллюстрировать на конкретных множествах и/или с помощью диаграмм Эйлера – Венна справедливость следующих соотношений:

а) А (В С) = (А В) (А С);

б) А (А В) = А;

в) А ( A В) = А В;

г) А (В С) = (А В) (А С).

Задание 1.7.

Каждый студент группы обладает хотя бы одним из признаков: юноша, волосы крашеные, получает стипендию. Юношей в группе 12, из них 3 покрасили волосы, а 8 получают стипендию.

Всего в группе 6 студентов с крашеными волосами, из них 2 получают стипендию и 1 из двоих – юноша. Стипендию получают 14 человек, из них 8 – юношей. Сколько студентов в группе?

Задание 1.8.

В дискоклубе собрались представители двух молодежных организаций: “Комсомол” и “Яблоко”. Комсомольцев было

24. Юношей – 16. Причем юношей-комсомольцев было столько же, сколько девушек-яблочниц. Сколько человек было на встрече?

Задание 1.9. Доказать тождества теории множеств (5 на выбор):

1. А (В С) = (А В) (А С);

2. ( A B) = A B ;

3. ( A B) = A B ;

4. А \ (В С) = (А \ В) (А \ С);

5. А \ (В С) = (А \ В) (А \ С);

6. (А В) С = (А С) (В С);

7. (А \ В) С = (А С) \ (В С);

8. А (В \ С) = (А В) \ (А С);

9. А В (А \ В) (В \ С);

10. А В (С \ В) (С \ А);

11. А В С A С и С В;

12. А (В С) А В и А С.

Задание 1.10. Даны множества: А = {1, 2, 3}, B = {2, 7}. Требуется задать множества:

1. A В, В А, 2. (А В) (В А), 3. (А В) (В А).

–  –  –

Задание 3 Задача 3.1.

Сколько четырёхзначных чисел можно составить из цифр {0, 1, 2, 3, 4, 5} если:

а) ни одна цифра в числе не повторяется;

б) цифры в числе могут повторяться;

в) число должно быть нечётным (цифры могут повторяться)?

Задача 3.2.

На вершину горы ведёт 7 дорог.

Сколькими способами турист может подняться на гору и спуститься с неё, если подъём и спуск осуществляются:

а) одной и той же дорогой;

б) любой дорогой;

в) другой дорогой?

Задача 3.3. Сколькими способами можно упорядочить последовательность из n элементов так, чтобы:

а) два данных элемента стояли рядом в одном и том же порядке;

б) два данных элемента не стояли рядом;

в) два данных элемента стояли рядом в любом порядке?

Задача 3.4.

В турнире принимают участие m шахматистов, причём каждые два шахматиста сыграют по одной партии. Сколько всего партий будет сыграно?

Задача 3.5.

Группа из 15 студентов должна выбрать трех делегатов на конференцию. Сколько всего вариантов решения было у группы?

Задача 3.6.

Собрание группы из 15 студентов выбрало трёх человек в актив: одного старостой группы, второго профоргом, а третьего – членом студсовета факультета. Сколько было возможных вариантов выбора?

Задача 3.7.

В школу бальных танцев пришли 7 девочек и 5 мальчиков. Сколько вариантов составить танцевальные пары было у тренера?

Задача 3.8.

На научном семинаре планируется заслушать работы четырех авторов : А, B, С и D. Сколько существует вариантов расположить их в повестке семинара, если С не может выступить прежде, чем выступит B?

Задача 3.9.

Сколько существует способов рассадить n гостей за круглым столом?

Задача 3.10.

Сколько различных 5-буквенных слов можно составить из символов алфавита {а, b, с} при условии, что буква а встречается в слове не более трех раз, буква b – не более двух раз, буква с – не более одного раза?

Задача 3.11.

Сколько разных четырёхзначных чисел можно составить из цифр числа 3344477?

Задача 3.12.

В кафе продаются 6 сортов мороженого. Сколько существует вариантов заказать три порции мороженого?

Задача 3.13.

Сколько существует вариантов разложить n одинаковых шаров по m урнам?

Задача 3.14.

На конечной остановке в автобус сели 20 пассажиров. По пути следования автобус делает 5 остановок. Сколько вариантов высадки этих пассажиров может быть?

Задача 3.15.

Сколько способов разделить 15 разных конфет между тремя детьми трех, пяти и семи лет так, чтобы каждому досталось столько конфет, сколько ему лет?

–  –  –

2.3.1. Задача о размене монеты Сколькими способами можно разменять гривенник (монету копеек) на монеты,, и копеек (монеты такого достоинства были в обращении в России до года)?

Решение. Пусть – число способов размена монеты достоинством копеек на монеты,, и копеек.

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

–  –  –

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

Первоначальное рекуррентное уравнение для такой задачи имеет вид:

.

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

Рассмотрим еще одну задачу — в ней рекуррентные уравнения использованы для нахождения числа элементарных действий рекурсивно описанного алгоритма.

2.3.2. Задача о «ханойской башне»

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

Решение. Определим алгоритм индуктивно по возрастанию числа колец. Обозначим – количество перекладываний при переносе пирамиды высоты.

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

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

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

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

2) перенесем оставшееся самое большое кольцо на свободный стержень за действие;

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

Суммируя количество перекладываний на каждом шаге, получаем рекуррентное уравнение для определения с начальным условием :

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

Для нахождения решения этого уравнения в явном виде выполним преобразования, выражая через, — через и т.

д., пока не дойдем до значение которого можно подставить в явном виде:

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

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

Получим:

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

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

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

Числовые ряды. Ряд – это бесконечная сумма слагаемых вида Если все образуют некоторую числовую последовательность, то ряд называется числовым.

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

, то соответствующий ряд (2.1) называется сходящимся, а число – суммой этого ряда.

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

Рассмотрим примеры сходящихся и расходящихся числовых рядов.

Пример 2.1.

Исследуем на сходимость ряд

Вычислим частичные суммы:

Ясно, что, следовательно, рассматриваемый ряд сходится, и можно записать Пример 2.2. Рассмотрим ряд

Находим частичные суммы:

Так как при, то ряд является расходящимся.

Пример 2.3. Теперь рассмотрим пример ограниченного расходящегося ряда:

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

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

Важным частным случаем переменных рядов являются степенные ряды, которые имеют вид:

Пример 2.4.

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

–  –  –

В остальных случаях ряд (4) расходится:

при при и, при получаем ряд, рассматривавшийся в примере 2.2, следовательно, не существует.

Таким образом, область сходимости ряда (4) есть.

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

Свойство 2.1. Область сходимости произвольного степенного ряда имеет вид где — некоторая константа, причем точки в ряде случаев могут принадлежать области сходимости (обе или одна из них).

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

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

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

Пример 2.5. В качестве примера выведем следующую полезную формулу:

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

При формула (6) вырождается в (4).

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

Запишем (6) для и применим (4) с учетом области сходимости :

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

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

что и доказывает формулу (6).

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

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

Пример 2.6.

Пусть имеется бесконечная геометрическая прогрессия с общим членом.

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

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

Ньютона:

–  –  –

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

Свойство 2.4. Если производящие функции и соответствуют последовательностям и, то производящая функция соответствует последовательности, являющейся их суммой:. Другими словами, производящая функция суммы равна сумме производящих функций.

Справедливость этого свойства следует из правила почленного сложения многочленов и рядов.

На основе последовательностей и определим последовательность с общим членом Последовательность называется сверткой и Свойство 5.

(Теорема о свертке) Производящая функция свертки двух последовательностей и равна произведению производящих функций и этих последовательностей:

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

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

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

Пример 2.10.

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

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

–  –  –

Пример 2.11. Выведем с использованием производящей функции формулу числа сочетаний с повторениями на основе доказанного в ранее рекуррентного соотношения:

Начальные условия для него и.

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

Умножим почленно обе части (2.8) на при и сложим почленно все полученные равенства. Будем иметь:

С учетом (8) входящие в (9) суммы можно записать в виде:

Подставляя эти выражения в (9), получаем Решаем это линейное рекуррентное уравнение первой степени относительно для.

–  –  –

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

–  –  –

3.1. Понятия теории графов. Маршруты в графе Задание 5 Задание 5.1.Сколько рёбер в полном графе?

Задание 5.2.

Какое наименьшее число рёбер должно быть в графе, чтобы он был связным?

Задание 5.3.

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

Задание 5.4.

Задать граф, изображённый на рис. 2, матрицей смежности и матрицей инцидентности.

Задание 5.5.

Построить матрицу смежности и инцидентности для графов, изображённых на рис. 4-6.

–  –  –

Задача 5.12.

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

Задание 5.13.

Пронумеровать каждое дерево в прямом обратном и внутреннем порядке.

Рис. 10.

Задание 5.14.

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

–  –  –

Задание 5.15.

Построить корневое дерево, соответствующее следующим выражениям:

а) –+ a b + c ** d 2;

б) (((x * y) + ( z * v)) ** 2) – ((a + b) + c);

в) (X OR Y) AND (( NOT (A)) OR B) OR ( NOT (X)).

–  –  –

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

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

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

Графы G(V,U) и G' (V', U') называются изоморфными, если существует биекция между множествами вершин V и V', а также между множествами ребер U и U', сохраняющая отношение инцидентности: если v V, v'V ', u U, u'U ', то вершина v' инцидентна ребру U' тогда и только тогда, когда вершина v инцидентна ребру U.

Рассмотрим два графа, изображенные на рис. 12 G1 ( A1, B1 ) и G2 ( A2, B2 )

–  –  –

получаем граф G1' ( A1, B1 ), у которого A1 A2, B1 B2, т.е. изоморфный граф.

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

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

Задача укладки имеет применение, например, при разработках информационных, транспортных, энергетических сетей и т. д.

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

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

Теорема 3.1.

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

Построим для задачи о трех соседях и трех колодцах граф, соответствующий взаимному расположению домов и колодцев. Этот граф изображен на рис. 13, а. На рис. 13, б изображен граф, изоморфный исходному. Из теоремы Жордана следует, что соединение вершин vd3 и vk2 ребром без пересечения с замкнутой кривой L не представляется возможным.

–  –  –

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

Граф, изображенный на рис. 13, а, получил специальное обозначение А33.

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

v1

–  –  –

То, что граф U55 не плоский, доказывается точно также как и для графа А33. В теории плоских графов один из фундаментальных результатов принадлежит Понтрягину и Куратовскому. Ими доказана следующая теорема.

Теорема 3.2.

(Понтрягин и Куратовский) Для того чтобы граф G был плоским, необходимо и достаточно, чтобы он не содержал частичного графа, изоморфного А33 или U55.

Доказательство этой теоремы здесь не приводим ввиду его громоздкости.

4. Задачи о маршрутах. Алгоритм Дейкстры

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

Требованием неотрицательности весов мы достигаем того что, циклы отрицательной длины автоматически исключаются и задача всегда будет иметь решение. Кроме того, это условие позволяет на порядок уменьшить трудоемкость алгоритма по сравнению с алгоритмом Форда-Беллмана.

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

Обозначим W – множество вершин, кратчайшее расстояние до которых уже найдено, и назовем его множеством обработанных вершин.

Инициализация:

ЦИКЛ ПО i от 1 до n D(i) = P(s; i) Здесь в качестве начальных значений пометок берутся веса ребер, соединяющих начальную вершину s с остальными (при отсутствии таких ребер пометка берется равной бесконечности).

Основной алгоритм: W = {S } ЦИКЛ-ПОКА V \ W (есть необработанные вершины) найти вершину w V / W с наименьшей пометкой D(w) перенести найденную вершину во множество обработанных:

W W w модифицировать пометки необработанных вершин через w :

ЦИКЛ ПО всем вершинам u V / W, смежным с w D(u) = min{D(u); D(w) + P(w; u)} Доказательство корректности алгоритма. Для доказательства выясним смысл пометок вершин.

Лемма 4.1.

Пометка D(w) каждой обработанной вершины – кратчайшее расстояние от источника до вершины w. Пометка D(u) каждой необработанной вершины – кратчайшее расстояние от источника до этой вершины на множестве путей, у которых все вершины, кроме последней, обработаны.

Доказательство. Докажем лемму по индукции. База индукции обеспечена инициализацией: источник – обработанная вершина, и расстояние до нее (равное 0) найдено, пометки других вершин определяются длинами ребер из источника в эти вершины, их можно рассматривать как пути из одного ребра, начальная вершина которого обработана, а конец нет.

Рис. 15.

Индукционный переход. Предположим, утверждение леммы верно для m=k, докажем, что после выполнения одного шага внешнего цикла оно будет верно для m = k + 1. Сначала докажем, что значение пометки необработанной вершины w с минимальной пометкой – это расстояние до нее. Докажем от противного. Пусть существует более короткий путь до w. Тогда часть его вершин обработана (по крайней мере, первая вершина), а часть – нет (по крайней мере, последняя). Рассмотрим первую необработанную вершину u (рис. 15). Длина пути от источника до этой вершины должна быть не больше, чем длина пути от источника до вершины w (в силу неотрицательности ребер), но тогда пометка вершины u будет меньше пометки вершины w, что противоречит правилу выбора вершины w! Противоречие доказывает утверждение. Теперь докажем справедливость утверждения леммы для необработанных вершин. Но оно следует непосредственно из алгоритма модификации – новая пометка строится так, чтобы она была минимальным расстоянием на множестве путей, у которых всевершины, кроме последней, обработаны. Лемма доказана Теорема 4.1. Алгоритм Дейкстры корректно решает задачу о нахождении кратчайших длин путей от источника до всех вершин графа.

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

Рассмотрим пример протокола работы алгоритма Дейкстры.

–  –  –

Пример 6.12.

Найдем кратчайшие расстояния от вершины Е (источника) связного неориентированного графа до остальных его вершин Граф задан матрицей весов (таблица 1) и изображен на рис. 16.

Первая строка протокола (таблица 1) – строка Е матрицы весов, показывающая длины ребер, выходящих из Е. (Вершина Е уже «обработана», поэтому ее пометка не пересчитывается, что обозначено заливкой клетки в серый цвет).

А В СDЕF

Е 10 5 0 2 Минимальная из этих пометок длин – пометка вершины F – есть длина кратчайшего пути от Е до F. Переведем эту вершину в разряд обработанных (что в протоколе отмечаем заливкой клетки, соответствующей вершине F ) и пересчитаем пометки вершин, смежных вершине F.

–  –  –

теории графов в практических задачах

5.1. Задача о раскрасках. Проблема четырех красок Удивительный факт: любую политическую карту можно раскрасить всего четырьмя красками, причем так, что соседние страны на ней не будут окрашены в один цвет. Пронумеруем краски: 1 – красная, 2– зеленая, 3 – синяя и 4 – желтая. Пусть рис. 17 изображает гипотетический континент, омываемый со всех сторон океаном и разделенный прямолинейными границами на суверенные государства. Единственное условие этой карты такое: все страны должны иметь друг с другом протяженные границы, т.е. они не могут соприкасаться в единственной точке, что представляется вполне разумным. Действительно, так не бывает, чтобы реальные страны соприкасались в одной-единственной идеально геометрической точке. Ведь нужно же куда-то вкопать пограничный столб, поставить шлагбаум, определить местоположение будки для пограничника.

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

Рис. 17. Гипотетический континент

Нашу гипотетическую карту начнем раскрашивать следующим образом. Океан можно принять за некую «страну рыб и водорослей», которую закрасим в синий цвет (3). Поэтому все прибрежные страны уже нельзя будет закрашивать этой краской, в противном случае нарушится принцип запрета на соседство двух одинаковых красок. Далее выберем любую, первую попавшуюся страну и назначим ей цвет 1 (на рис. 17 эта страна обозначена серым цветом).

Две ее соседки с выходом к морю окрасим в зеленый цвет 2. Далее идем по часовой стрелке и окрашиваем подряд все прибрежные страны так, что у нас получится цепочка: 1 – 2 – 1 – 2 – 4 – 1 – 2 – 1

– 2. Желтый (4) цвет здесь появился потому, что красным цветом (1) мы не имели права пользоваться в силу ограничивающего условия. Затем начинаем раскрашивать четыре внутриконтинентальные страны, которые имеют огромные города-столицы (они обозначены белыми кружками) с отходящими от них во все страны-соседки шоссейными магистралями (они обозначены пунктирными прямыми). Пусть цвет страны совпадает с названием страны и названием столицы, т.е. в центральной части континента располагаются Красная (1), Зеленая (2), Синяя (3) и Желтая страны и, соответственно, столицы.

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

Чтобы не нарушать исходного условия, нам придется взяться за перекраску однажды уже окрашенных стран; в этом как раз и состоит проблема четырех красок. Дело в том, что процедура перекраски может затянуться и мы вынуждены будем перекрашивать еще одну страну, потом еще и т.д. Однако геометрам всегда удавалось за конечное число перекрасок прийти в полное согласие с условием. Им не попадалось такой карты, сколько бы в ней ни было стран, чтобы ее нельзя было покрасить четырьмя красками. Это выглядит несколько странно, что привело к формулировке задачи, которая, наподобие Великой теоремы Ферма, не была решена на протяжении столетия.

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

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

Этой проблемой был озабочен немецкий математик Август Фердинанд Мёбиус (1790–1868) – родоначальник науки топологии. Известно, что около 1840 г. он размышлял над задачей о четырех красках, о которой он говорил как об известном любопытном факте.

Дальнейшая судьба этой задачи такова. В первом томе Трудов Лондонского географического общества 1879 г. известный британский алгебраист Артур Кэли (1821–1895) поместил статью, где отчетливо сформулировал задачу о четырех красках, которая до этого была известна как занятная головоломка. В то время он занимался метрической геометрией и теорией инвариантов непрерывных точечных преобразований, которые входили тогда в качестве раздела в молодую науку топологию. Уже через год ее решение представил А. Кемпе, но, как потом оказалось, он поспешил. Его доказательство раскритиковал Р. Хивуд, который в 1890 г. в работе «Теоремы о раскраске карты» показал, что задачу можно решить точно, если иметь в своем распоряжении не четыре, а пять красок. После этих попыток задачу надолго отложили и только в 1969 г. к ней вернулся математик Х. Хееш, показавший, что она сводится к проблеме неприводимых конфигураций.

Рассмотрим суть подхода, используемого при доказательстве проблемы четырех красок. Прежде всего, при работе с граф-картой, как мы уже говорили, будем считать, что каждой его вершине инцидентно не более трех ребер (т.е. граница состоит более чем из одной точки). Чтобы этого добиться, всякая вершина х, в которой пересекаются более трех границ, «размазывается» и образует дополнительную область. В результате в преобразованной граф-карте исходная вершина отсутствует, а вместо неё появляется к новых вершин: х1, х2,... хn (рис. 18). Каждая из этих n вершин, имеет три инцидентных ребра: два из них инцидентны двум другим вершинам из этого же множества новых вершин, а третье ребро соответствует одному из ребер «размазанной» вершины х. Ребра, соединяющие между собой новые вершины, ограничивают ту дополнительную область, которая образовалась вместо х.

–  –  –

Для преобразованной таким путем граф-карты G строится двойственный граф D – граф дорог: вершины двойственного графа соответствуют областям, а ребра соединяют вершины, соответствующие смежным областям. Внешней для граф-карты области также сопоставляется вершина в двойственном графе. Ясно, что задача раскрашивания областей исходного графа эквивалентна задаче раскрашивания вершин для двойственного графа.

При графическом изображении ребра двойственного графа D окружают вершины исходного графа G. Поскольку степени всех вершин в G равны 3, то двойственный граф D разбивает плоскость на треугольники (в общем случае криволинейные, что не принципиально) или, как говорят, задает триангуляцию плоскости (рис. 19).

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

Рис. 19. Пример раскрашенной граф-карты и двойственного графа дорог Назовем конфигурацией связный подграф плоского графа, порожденный некоторым подмножеством (обычно небольшим) его вершин. Остальные вершины и ребра составляют так называемую внешнюю часть конфигурации.

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

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

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

Было доказано, что все конфигурации, в которых степени вершин не превосходят 5, являются редуцируемыми. При исследовании структуры и способов порождения плоских графов с достаточно большим количеством вершин было установлено, что существует так называемый неизбегаемый набор конфигураций. Для каждой конфигурации из этого набора нужно было доказать ее редуцируемость. В процессе формирования неизбегаемых конфигураций и проверки их на редуцируемость и потребовалось прибегнуть к переборным методам, что невозможно сделать вручную. С помощью ЭВМ Хееш построил набор из 1932 конфигураций, к которым можно свести всякий двойственный к карте граф, и которые уже нельзя более упростить. (для этого потребовалось около 150 часов машинного времени). К. Аппель и В. Хейкен в 1976 г., заинтересовавшись решением Хееша, составили компьютерную программу для перебора всевозможных раскрасок неприводимых конфигураций, фактически осуществили их раскраску и, таким образом, доказали разрешимость вековой проблемы.

5.2. Анализ алгоритмов на графах

Графы встречаются в сотнях разных задач, и алгоритмы обработки графов очень важны. При анализе алгоритма будем оценивать время обработки заданного графа G(V, E) в зависимости от числа его вершин - |V| и рёбер |Е|. Для краткости обычно пишут V и Е вместо |V| и |Е|.

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

Для заданного графа G(V, E) и фиксированной начальной вершины s алгоритм поиска в ширину перечисляет все достижимые из s (если идти по рёбрам) вершины в порядке возрастания расстояния от s. Расстоянием считается длина (число рёбер) кратчайшего пути.

В процессе поиска из графа выделяется часть, называемая «деревом поиска в ширину» с корнем s. Она содержит все достижимые из s вершины (и только их). Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Алгоритм применим и к ориентированным и к неориентированным графам.

Приведенная ниже реализация алгоритма под названием BFS (breath-first search) использует представление графа G(V, E) списками смежных вершин.

Вторым базовым алгоритмом для графов является поиск в глубину (DFS, depth-first search). Алгоритм поиска в глубину перечисляет вершины начиная от начальной и уходя по рёбрам «вглубь»

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

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

Граф будет задаваться списком смежности – одномерный массив размером N, содержащий список вершин смежных с данной:

Type TAdjacencyList = array [1..N] of record Count: Integer; {число элементов в списке} List: array[1..N] of record {список} Node, {номер смежной вершины} Weight: Integer; {вес ребра} end;

end;

Var Graph: TAdjacencyList;

Способ хранения графа списком смежности позволяет наиболее эффективно производить поиск, но требует порядка O(N2) памяти под хранение.

Кратко алгоритм поиска в глубину описывается следующей последовательностью шагов:

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

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

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

В булевском массиве Visited будем помечать уже посещенные вершины. Первоначально массив должен быть заполнен значениями false (ни одна из вершин не была посещена).

Теперь реализуем рекурсивную логику алгоритма в рекурсивной программе (v – номер вершины):

procedure DepthSearch(v: Integer);

Var j: Integer;

begin Visited[v] := True;

Write(‘Вершина ’, v, ‘посещена.’);

for j := 1 to Graph[v].Count do if not Visited[Graph[v].List[j].Node] then DepthSearch(Graph[v].List[j].Node);

end;

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

procedure DepthSearch2(v: Integer);

Var Way: array[1..N] of record {содержимое стека возврата} Node, {номер вершины} Number: Integer; {число рассмотренных элементов списка смежности} end;

Count: Integer; {размер (вершина) стека возврата} Current, j: Integer;

Found: Boolean;

begin Count := 1; Way[Count].Node := v; Way[Count].Number := 0;

Visited[v] := True;

Write(‘Вершина ’, v, ‘посещена.’);

repeat Current := Way[Count].Node;

Found := False;

for j := Way[Count].Number+1 to Graph[Current].Count do begin if not Visited[Graph[Current].List[j]] then begin Inc(Count);

Way[Count].Node := Graph[Current].List[j];

Way[Count].Number := 0;

Visited[Graph[Current].List[j]] := True;

Write(‘Вершина ’, Graph[Current].List[j], ‘посещена.’);

Found := True;

Break;

end;

end;

if not Found then Dec(Count);

until Count = 0;

end;

Оценим общее число операций при выполнении алгоритма DFS. Каждая вершина просматривается один раз (после этого она становится серой), на это уходит O(V) операций. По каждому ребру мы проходим один раз – это добавляет O(E) операций. Оценка вычислительной сложности – O(V+E).

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

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

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

procedure WidthSearch(v: Integer);

Var Delayed: array[1..N] of Integer; {очередь} Count, {хвост очереди} Head: Integer; {голова очереди} Current, j: Integer;

begin Count := 1; Head := 0; Delayed[Count] := v;

Visited[v] := True;

Write(‘Вершина ’, v, ‘посещена.’);

repeat Inc(Head); Current := Delayed[Head];

for j := 1 to Graph[Current].Count do if not Visited[Graph[Current].List[j]] then begin Inc(Count);

Delayed[Count] := Graph[Current].List[j];

Visited[Graph[Current].List[j]] := True;

Write(‘Вершина ’, Graph[Current].List[j], ‘посещена.’);

end;

until Count = Head;

end;

Оценим время работы алгоритма. Каждая вершина просматривается только один раз. Следовательно, на все вершины будет затрачено O(V) операций. Сумма длин списков смежности равна |Е| (2|Е| для неориентированного графа) и всего на его обработку уйдёт О(Е) операций. В результате получаем оценку вычислительной сложности – O(V+E).

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

–  –  –

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

6.1. Минимизация ФАЛ от большого числа переменных Если требуется вручную минимизировать ФАЛ от большого числа переменных (5 и более), то использование любого из трех рассмотренных в основном учебном пособии методов минимизации становится довольно неудобным. Это происходит по следующим причинам:

при аналитическом методе минимизации ФАЛ число термов, которые могут склеиваться между собой, возрастает в геометрической прогрессии;

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

Например, для функции от 6 переменных таблица будет содержать 64 строки и 63 столбца;

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

Поэтому для минимизации ФАЛ от большого числа переменных используют метод декомпозиции функции.

В этом методе исходная таблично заданная ФАЛ разбивается на несколько равных частей, число строк в которых кратно 2 n, например по 16 строк. В каждой из выделенных групп одни переменные имеют постоянные значения (для данной группы), другие – меняются. Строя, например, карты Карно по меняющимся переменным, получим минимальные формы записи для каждой части. Эти минимальные формы необходимо домножить на значения переменных, постоянные для этих частей, и просуммировать получившиеся выражения.

–  –  –

6.2. Основные автоматные узлы комбинационного типа Рассмотрим основные комбинационные узлы ЭВМ. К ним относятся дешифраторы, шифраторы, мультиплексоры, демультиплексоры, одноразрядные сумматоры, полусумматоры, комбинационные счетчики, формирователи и сдвигатели [14; 23; 24].

В основе синтеза всех комбинационных схем лежит канонический метод синтеза. Все логические схемы являются комбинационными; основные их характеристики – сложность и быстродействие.

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

Рассмотрим дешифраторы, шифраторы, мультиплексоры и демультиплексоры, сумматоры и полусумматоры.

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

В общем случае дешифратор с n входами имеет 2n различных значений и каждому из этих значений соответствует сигнал 1 на одном из выходов дешифратора; 3-входовый дешифратор (рис. 20) функционирует в соответствии с таблицей истинности (таблица 4).

–  –  –

По таблице истинности дешифратора (таблица 4), представляющей собой систему из восьми ФАЛ, легко построить логическую схему дешифратора в любом из базисов.

В некоторых случаях функция дешифратора ограничивается выделением только m 2n входных наборов из общего числа М = 2n. При этом предполагается, что М – m входных наборов не существует. Дешифраторы с числом выходов m 2n называются неполными.

–  –  –

6.2.3. Мультиплексор Мультиплексором называется комбинационная схема, имеющая n + 2n входов и один выход, где n – число адресных входов, а 2n

– число информационных входов мультиплексора. Адреса представляются в двоичном коде и им присваивается номер i. Каждому адресу с номером i соответствует свой информационный вход Аi, сигнал с которого при данном адресе проходит на выход. Основным назначением мультиплексора является коммутация 2n входных сигналов на один выход. На рис. 22 представлено обозначение мультиплексора, имеющего 4 информационных входа. Таблица истинности этого мультиплексора представлена в таблице 6.

Логическая схема мультиплексора состоит из дешифратора и вентильной части (рис. 22).

Кроме основного назначения (коммутации сигналов) мультиплексоры могут быть использованы, например, для синтеза схем, выполняющих любую ФАЛ [24; 25; 26; 27]. В этом случае на информационные входы подаются не изменяющиеся во времени сигналы 0 и

1. Считывание данных сигналов производится подачей соответствующих сигналов на адресные входы. На рис. 23 приведена реализация ФАЛ, заданной в таблице 5 основного учебного пособия.

–  –  –

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

6.2.4. Демультиплексор

–  –  –

Логическая схема, реализующая функцию демультиплексора, представлена на рис. 26.

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

Полусумматор представляет собой комбинационную схему, имеющую два входа и два выхода. Условное графическое обозначение полусумматора приведено на рис. 27, а, где А и В – слагаемые двоичные цифры, каждая из которых может принимать значение 0 или 1; S и P – выводы, на которых появляется результат сложения. Вывод S предназначен для выдачи суммы слагаемых А и В, а вывод Р – для выдачи переноса в следующий (i+1)-й разряд. Полусумматор функционирует в соответствии с таблицей истинности (таблица 7).

–  –  –

Полный одноразрядный двоичный сумматор предназначен для построения многоразрядных сумматоров и имеет три входа и, следовательно, предназначен для сложения трёх двоичных цифр. Условное графическое обозначение полного одноразрядного двоичного сумматора приведено на рис. 27, б, а таблица истинности, в соответствии с которой функционирует сумматор, – в таблице 8. А и В – двоичные разряды чисел; С – входной перенос в данный разряд из предыдущего разряда. Это разделение входов сумматора условно, так как все три входа (А, В и С) имеют одинаковый вес. На выходе S появляется разряд суммы, а на выходе Р – разряд переноса в следующий разряд.

Функциональная схема полного одноразрядного двоичного сумматора строится на основе функций суммы S и переноса Р, составляемых по таблице истинности (таблица 8):

Р = А В + А С + В С;

–  –  –

Наиболее удачные схемы одноразрядных сумматоров, содержащих наименьшее количество элементов и наименьшее количество входов у элементов, получены эмпирическим путём [18]. Одна из таких функциональных схем приведена на рис. 28.

Логические уравнения для значений суммы и переноса в этой схеме следующие:

Р = А В + А С + В С;

–  –  –

Как видно из рис. 28, схема состоит из 9 логических элементов.

Общее число входов – 20.

Если для реализации сумматора использовать соотношения Р = А В + (А + В) С;

–  –  –

Рис. 29. Функциональная схема одноразрядного сумматора, состоящего из двух полусумматоров и схемы «2ИЛИ»

Если в полусумматоре HS1 сигнал переноса не возник, то он может возникнуть в полусумматоре HS2 при условии поступления на вход сумматора сигнала переноса из младшего разряда и значения «1» одного из слагаемых. Если же сигнал переноса появился в полусумматоре HS1, то сигнал переноса р1 из полусумматора HS2 не появится. Общий сигнал переноса сумматора равен логической сумме переносов обоих полусумматоров. Сигнал суммы S вырабатывается на выходе полусумматора HS2.

Если реализовать схему, изображённую на рис. 29, на логических элементах И, ИЛИ, НЕ, то общее число элементов будет равно

9. Общее число входов такой схемы равно 16. Таким образом, схема полного одноразрядного двоичного сумматора, состоящего из двух полусумматоров, является наиболее экономичной.

Заключение

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

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

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

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

Библиографический список

Андерсон Д. Дискретная математика и комбинаторика. – М.:

1.

Вильямс, 2004. – 960 с.

2. Новиков Ф.А. Дискретная математика для программистов:

Учебник для вузов. – СПб.: Питер, 2009. – 384 с.

3. Хаггарти Р. Дискретная математика для программистов. – М.:

Техносфера, 2005. – 400 с.

4. Грэй П. Логика, алгебра и базы данных / пер. с англ. Х.И. Килова, Г.Е. Минца; под ред. Орловского, А.О. Слисенко. – М.:

Машиностроение, 1989. – 368 с.

5. Гуц А.К. Математическая логика и теория алгоритмов: учебное пособие. – Омск: Изд-во Наследие. Диалог-Сибирь, 2003. – 108 с.

6. Ежов И.И. Элементы комбинаторики / сост. И.И. Ежов, А.В. Скороход, М.И. Ядренко. – М.: Наука, 1977.

7. Иванов Б.Н. Дискретная математика. Алгоритмы и программы:

учеб. пособие. – М.: Лаборатория Базовых Знаний, 2003. – 288 с.

8. Карпов Ю.Г. Теория автоматов: учебник для студ. вузов, обучающихся по спец. «Вычислительные машины, комплексы, системы и сети». – СПб.: Питер, 2002. – 224 с.

9. Лавров И.А. Задачи по теории множеств, математической логике и теории алгоритмов / сост. И.А. Лавров, М.М. Максимова. – М.: Наука, 1984. – 224 с.

10. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

11. Рыбин В.В. Основы теории нечтких множеств и нечткой логики: учебное пособие. – М.: Изд-во МАИ, 2007. – 96 с.

12. Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петербург, 2008. – 352 с.

–  –  –



Похожие работы:

«РОССИЙСКАЯ АССОЦИАЦИЯ ЭКСПЕРТНЫХ ОРГАНИЗАЦИЙ ТЕХНОГЕННЫХ ОБЪЕКТОВ ПОВЫШЕННОЙ ОПАСНОСТИ РОСТЕХЭКСПЕРТИЗА СЕРИЯ 03 НОРМАТИВНЫЕ ДОКУМЕНТЫ МЕЖОТРАСЛЕВОГО ПРИМЕНЕНИЯ ПО ВОПРОСАМ ПРОМЫШЛЕННОЙ БЕЗОПАСНОСТИ И ОХРАНЫ НЕДР ИЗМЕНЕНИЯ И ДОПОЛНЕНИЯ ЗА 2010 г. (ИД-2010) К СТАНДАРТУ ОРГАНИЗАЦИИ СТО–СА–03–002–2009 ПРАВИ...»

«912 УДК543+541 ВЭЖХ в исследовании радиационно-химических превращений серотонина адипината Ульянова Е.В.1, Антропова И.Г. 2, Ревина А.А.1, Ларионов О.Г.1, Одинец А.Г.3 Федеральное государственное бюджетное учреждение...»

«0902685 Каталог 2009 y^DISSEO ^ A Bluestar Company Международная химическая производственная компания Адиссео, организующая продажи более, чем в 100 странах, использует уникальную комбинацию исс...»

«А. А. Самарский П. Н. Вабищевич ЧИСЛЕННЫ Е МЕТОДЫ РЕШ ЕНИЯ О БР А ТН Ы Х ЗАДАЧ М АТЕМАТИЧЕСКОЙ ФИЗИКИ Издание третье URSS МОСКВА ББК 22.193 22.311я73 22.161.6 Самарский Александр Андреевич, Вабищевич Петр Николаевич Чис...»

«БЮЛЛЕТЕНЬ для голосования на годовом общем собрании акционеров Полное фирменное наименование: Открытое акционерное общество «Башнефтегеофизика» Место нахождения общества: Российская Федерация,450000, Республика Башкортостан, г. Уфа, ул. Ленина, 13 Место проведения собрания: Российская Федерация, Республ...»

«№13, том 23. 2010 ISSN 2074-0212 O O O O n O O O O 1, 4-dioxane 59-64% H2NHN NHNH2 H H N N 18(19) N N 26(27) 22(23) O O 10(11) 4 O O n 30(31) 14(15) 1 O O ISSN 2074-0948 International Edition in English: Butlerov Communications Полная исследовательская публикация Тематический раздел: Препаративная х...»

«Калмыков Антон Георгиевич КОЛЛОИДНО-ХИМИЧЕСКИЕ ОСНОВЫ ЗОЛЬ-ГЕЛЬ МЕТОДА ПОЛУЧЕНИЯ МЕМБРАН СО СЛОЯМИ CuO И ZnO 02.00.11 – Коллоидная химия АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата химических наук Москва – 2013 Работа выполнена на каф...»

«ВЫБОР КАТАЛИТИЧЕСКОЙ СИСТЕМЫ ДЛЯ ЭЛЕКТРОХИМИЧЕСКОГО ОКИСЛЕНИЯ ХОЛЕСТЕРИНА А.В. Охохонин, А.И. Матерн ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина», г. Екатеринбург Цель и задачи работы Получение ан...»

«ТЕСТ ТЬЮРИНГА И КОМПЬЮТЕРНАЯ ПОДДЕРЖКА МАТЕМАТИЧЕСКОГО ОБРАЗОВАНИЯ В.А. Еровенко, О.В. Тимохович Белорусский государственный университет Успешная компьютеризация математического образования зависит не только от количества компьютерных классов, но и от качест...»

«Содержание Предисловие Глава 1. Теория вероятностей и математическая статистика в MS Excel §1. Встроенные функции дискретных распределений. 9 §2. Макросы для дискретных распределений §3. Встроенные функции не...»

«http://www.izdatgeo.ru Геология и геофизика, 2009, т. 50, № 12, с. 1560—1570 УДК 549.211 MАНГАНОИЛЬМЕНИТ КАК МИНЕРАЛ-СПУТНИК АЛМАЗА В КИМБЕРЛИТАХ Ф.В. Каминский, Е.А. Белоусова* KM Diamond Exploration Ltd., 2446 Shadbolt Lane, West Vanc...»

«УДК 544.6.076.328.2-034.791 АМАЛЬГАМНЫЕ МЕТОДЫ ПОЛУЧЕНИЯ И РАФИНИРОВАНИЯ МЕТАЛЛОВ С ПРИМЕНЕНИЕМ БИПОЛЯРНЫХ ЭЛЕКТРОДОВ. ЧАСТЬ I С.П. Бухман, Б.А. Сотников, Ю.А. Стекольников Кафедра «Химия» ГОУ ВПО «Елецкий государственный университет им. И.А. Бунина»; chimic...»

«С.Л. Василенко Золотые трели Золотая клетка соловью не потеха. Английская пословица Есть среди золотосеченцев один интересный человек – Григорий Мартыненко – профессор кафедры математи...»

«Совык Дмитрий Николаевич Плазмохимический синтез трёхмерных структур из алмаза методом реплики 01.04.07 Физика конденсированного состояния Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель: канд. физ.-мат. наук...»

«Второй съезд аналитиков России http://analystscongress.ru Тезисы докладов 23-27 сентября 2013 г., Москва I ОРГАНИЗАТОРЫ Российская академия наук, Научный совет РАН по аналитической химии Ассоциация «Аналитика» Ассоциация «Экоаналитика» Институт общей и неорганической химии им. Н....»










 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

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