WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Pages:   || 2 |

«1. Информация из ФГОС, относящаяся к дисциплине 1.1. Вид деятельности выпускника Дисциплина охватывает круг вопросов относящиеся к виду деятельности выпускника: ЭВМ, ...»

-- [ Страница 1 ] --

1. Информация из ФГОС, относящаяся к дисциплине

1.1. Вид деятельности выпускника

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

1.2. Задачи профессиональной деятельности выпускника

В дисциплине рассматриваются указанные в ФГОС задачи профессиональной деятельности выпускника:

Проектирование программных и аппаратных средств;

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

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

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

- владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК-1);

- умеет логически верно, аргументировано и ясно строить устную и письменную речь (ОК-2);

- готов к кооперации с коллегами, работе в коллективе (ОК-3);

- стремится к саморазвитию, повышению своей квалификации и мастерства (ОК-6);

- способен анализировать социально-значимые проблем и процесс (ОК-9);

- использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);

- осознает сущность и значение информации в развитии современного общества; владеет основными методами, способами и средствами получения, хранения, переработки информации (ОК-11);

- имеет навыки работы с компьютером как средством управления информацией (ОК-12);

- способен работать с информацией в глобальных компьютерных сетях (ОК-13);

- осваивать методики использования программных средств для решения практических задач (ПК-2);

- разрабатывать интерфейсы «человек – электронно-вычислительная машина» (ПК-3);

- разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технологии программирования (ПК-5);

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

1.4. Перечень умений и знаний, установленных ФГОС Студент после освоения программы настоящей дисциплины должен:

знать: основные положения теории графов.

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

Владеть методами теории графов.

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

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

- изучение основ теории множеств; спецификации и свойства множеств, отношений, функций и отображений;

- освоение основных понятий комбинаторики, методов решения комбинаторных задач;

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

- приобретение навыков осуществления операций над графами и выполнения количественных оценок их характеристик;

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

3. Место дисциплины в структуре ООП Для изучения дисциплины, необходимо освоения содержания дисциплин:

- Математика. Алгебра, аналитическая геометрия и математический анализ;

- Информатика;

- Программирование.

Знания и умения, приобретаемые студентами после освоения содержания дисциплины, будут использоваться в:

- Теория вероятностей и математическая статистика;

- Моделирование;

- Теория автоматов;

- Проектирование цифровых систем;

- Технологии программирования.

В результате освоения программы дисциплины обучающийся должен:

уметь:

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

- иметь опыт использования символики дискретной математики для выражения количественных и качественных отношений объектов;

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

знать:

- основы теории множеств; спецификации и свойства множеств, отношений, функций и отображений;

- базовые понятия комбинаторики, методов решения комбинаторных задач;

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

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

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

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

уметь:

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

- иметь опыт использования символики дискретной математики для выражения количественных и качественных отношений объектов;

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

знать:

- основы теории множеств; спецификации и свойства множеств, отношений, функций и отображений;

- базовые понятия комбинаторики, методов решения комбинаторных задач;

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

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

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

владеть:

понятиями, методами и алгоритмами дискретной математики для решения практических задач.

5. Основная структура дисциплины.

Таблица 1 – Структура дисциплины Самостоятельная работа (в том числе кур- 32 совое проектирование) Вид промежуточной аттестации (итогово- Экз. 40 го контроля по дисциплине), в том числе курсовое проектирование 6. Содержание дисциплины 6.1. Перечень основных разделов и тем дисциплины 1. Множества и их спецификации.

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

Прямые произведения множеств. Определение прямого произведения.

Примеры. Теорема о мощности множества, образованного декартовым произведением n множеств.

2. Отношения, свойства отношений.

Обратное отношение. Образ и прообраз множества. Область определения и область значения бинарного отношения. Композиция отношений.

Определение функции и отображения. Понятие обратной функции.

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

Специальные бинарные отношения, свойства бинарных отношений:

рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, антитранзитивность. Отношение эквивалентности.

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

3. Алгебра логики, логические функции.

Алгебра логики, логические функции (или переключательные функции (ПФ) и способы их задания.). Синтез релейных схем. Представление логических функций различными формулами. Эквивалентные (равносильные) функции. Существенные и фиктивные переменные. Двойственные функции. Булева алгебра функций и эквивалентные преобразования в ней.

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

для перехода от ДНФ к СДНФ. Приведение к СКНФ. Понятие КНФ. Построение КНФ с помощью эквивалентных преобразований, переход от ДНФ к КНФ. Правило «расщепления» для перехода от КНФ к СКНФ.

Минимизация логических (переключательных) функций. Теорема о возможности и однозначности представления логических функций в виде сокращенной дизъюнктивной (конъюнктивной) нормальной формы. Понятие импликанты. Тупиковые ДНФ. Понятие минимальной ДНФ (МДНФ). Графический способ построение МДНФ.

Полнота системы логических функций. Понятие полной системы логических функций. Теорема о функциональной полноте.

Определение базиса. Примеры функционально-полных базисов.

4. Основы комбинаторики.

Общие правила комбинаторики. Формула включений и выключений.

Правила суммы и произведения. Примеры решения задач. Круги Эйлера.

Типы расстановок.

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

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

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

5. Основные понятия теории графов.

Элементы теории графов. Основные определения, типы графов.

Определение графа, вершины, ребра (дуги, петли, звена), отношение инцидентности, степень вершины. Основные типы графов (орграф, неорграф, униграф, мультиграф, полный граф). Маршруты, цепи, циклы.

Связность. Граф типа «дерево», остов, разрез.

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

Определение путей и кратчайших путей в графах. Потоки в сетях.

Элементы сетевого планирования. Сетевые графики. Критический путь. Критическое время. Резервы времени.

6.2. Краткое описание содержания теоретической части разделов и тем дисциплины Тема 1. Теория множеств.

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

Множеством S называется объединение в одно целое объектов, хорошо различимых нашей мыслью или интуицией. Эти объекты называется элементами множества S. Такое интуитивное определение дал немецкий математик Г. Кантор. В данном определении важны следующие два момента:

- Множество - это нечто, состоящее из хорошо различимых объектов.

-Это нечто мыслится как единое целое.

Множества бывают конечными и бесконечными, Количество элементов в конечном множестве называется мощностью множества. Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается. Множество, включающее в себя все рассматриваемые множества, называется универсальным множеством или универсумом и обозначается U. Символом обозначается отношение принадлежности. Запись x означает, что элемент х принадлежит множеству Х.

Если элемент х не принадлежит множеству Х, то пишут хХ.

Множества могут быть заданы следующими способами:

- перечислением (списком своих элементов);

- описанием свойств, которыми должны обладать его элементы;

- порождающей процедурой.

Например:

Множество экзаменационных оценок может быть задано:

- перечислением А={2; 3; 4; 5};

- описанием свойств А={a a- экзаменационная оценка;

- порождающей процедурой А=а а=2+i, i= 0,3.

Подмножеством множества А называется множество В, если любой элемент множества В принадлежит множеству А:

Символом обозначается отношение включения. Запись АВ означает множество А является подмножеством множества В.

Не следует смешивать отношение принадлежности и отношение включения. Отношение принадлежности применяется к элементам множества, а отношение включения к множествам. Хотя }, однако не верно, что 1, так как единственным элементом множества 1 является 1.

Если А и, то, то есть множество А строго включено в множество В. Символ называется строгим включением.

Свойства подмножеств Рефлексивность. Множество А является подмножеством множества Транзитивность. Если множество А является подмножеством множества В, а множество В является подмножеством множества С, то множество А является подмножеством множества С:

Принцип объемности. Если множество А является подмножеством множества В, а множество В является подмножеством множество А, то множество А равно множеству В:

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

Объединением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В:

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

Разностью множества А и В называется множество всех тех элементов, которые принадлежат множеству А и не принадлежат множеству В:

Симметричной разностью множеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В, и элементов множества В, не принадлежащих множеству А:

Дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А:

Для наглядного представления операций над множествами используют диаграммы Эйлера-Венна.

Диаграмма отражает результаты выполнения операций, где A B - это области 1, 2, 3;

A - это область 1, 3;

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

Для любых множеств А, В и С выполнимы следующие тождества:

Коммутативный закон

A B B A A B B A

Ассоциативный закон Дистрибутивный закон Закон поглощения Закон идемпотентности

A A A A A A

Закон де Моргана

A B A B A B A B

Закон исключенного третьего Закон противоречия Операции с универсумом:

A U U A U A

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

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

Кортеж - это упорядоченный набор элементов. Кортеж характеризуется элементами и их порядком расположения. Элементы кортежа называются компонентами. Компоненты нумеруют слева направо. Число компонент определяет длину кортежа. Кортеж обозначается а1, а2,..., аn.

Кортеж длиной в две компоненты называется парой, кортеж длиной в три компоненты - тройка, длиной в n - n-ка.

Проекцией кортежа на i-тую ось называется его i-тая компонента.

Проекцией кортежа на оси i1, i2,..., iq оси называется кортеж, состоящий из i1, i2,..., iq компонент.

Проекцией кортежа на пустое множество осей является пустой кортеж.

Например:

Пусть дан кортеж А=,,,. Найти проекции на 1 ось, 3 ось, 5 ось, 1 и 4 оси, 4 и 2 оси.

Пр А5 не определена Пр А4,2 не определена.

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

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

Проекцией множества называется множество проекций соответствующих кортежей.

Пример:

А=1,2,3;4,5,6;3,3, Пр А1,3=,3,6, Пр А3,1 не определена.

Тема 2. Отношения.

Отношением называется пара вида, M такая, что Ф (M2=MM),где Ф - график отношения, М - это множество, между элементами которого существует данное отношение.

Например:

Пусть дано, M, где M {x | x N }, а график отношения определяется как { x, y | x y}. Это отношение ”X больше Y” на множестве натуральных чисел. Данное отношение задано описанием свойств. Перечислением данное отношение может быть задано следующим образом:

Отношение называется полным, если 2.

{x,xy,y.

Отношение называется отношением неравенства, если 2\.

Запись xy означает, что между x и y существует отношение.

Операции над отношениями.

Пусть даны два отношения и r=R,M. Над данными отношениями могут быть выполнены следующие операции:

объединение r=R,M;

разность \r=Ф\R,M;

композиция r=ФR,M;

инверсия -1=Ф-1,M.

Основные свойства отношений.

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

Отношение называется рефлексивным, если для всех x выполняется условие: xx или.

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

Отношение называется антирефлексивным, если для всех x выполняется условие: xx (символ ““ означает “не выполняется”) или Симметричность.

Отношение называется симметричным, если для всех x выполняется условие: xy yx или Ф=Ф-1.

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

Отношение называется антисимметричным, если для всех x выполняется условие: xy и xy yx или 1.

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

Отношение называется асимметричным, если для всех x выполняется условие: xy yx или 1 =.

Связность (полнота).

Отношение называется связным (полным), если для всех x выполняется условие: xy xy или yx или М2\.

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

Отношение называется транзитивным, если для всех x выполняется условие: xy и yz xz или ФФФ.

Например:

Какими свойствами обладает отношение =Ф,X, где X={1; 2; а}, Ф={1,1;a,a;a,2;2,2}.

Определим Ф-1, X:

Ф-1={1,1;a,a;2,a;2,2} X={1,1;2,2;a,a}.

Отношение является:

- рефлексивным, так как XФ;

- антисимметричным, так как X;

- транзитивным, так как ФФ={1,1;a,a;a,2;2,2}Ф;

- несвязное, так как X2\X={1,2;1,a;2,1;2,a;a,1;a,2} ФФ-1={1,1;a,a;a,2;2,2;2,a}.

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

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

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

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

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

ТЕМА 4. Комбинаторные объекты и комбинаторные числа В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества A, а также числовые характеристики этих объектов.

При подсчете числа объектов с наперед заданными свойствами используются следующие два правила:

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

- Правило произведения. Если объект U может быть выбран m способами и после каждого из таких выборов объект V в свою очередь может быть выбран k способами, то выбор « U и V » в указанном порядке может быть осуществлен mk способами.

Набор элементов ai, ai,..., ai из множества A a1, a2,..., an называется выборкой объема k из n элементов или ( n, k ) -выборкой.

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

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

Рассмотрим некоторые комбинаторные объекты и их комбинаторные числа.

Размещения. Размещением элементов из A по k (или размещением из n элементов по k) называется упорядоченная ( n, k ) -выборка, в которой элементы попарно различны.

Обозначим число размещений из n по k через n k. Для подсчета числа n k используем правило произведения. При построении конкретного размещения первым элементом в нем можно взять любой из n элементов множества A, вторым элементом – любой из n 1 оставшихся в A элементов и т.д. Поэтому При k n не существует размещений из n по k, следовательно, n k Упражнение 1. Показать, что для чисел n k выполняются тождества:

Перестановки. Перестановками элементов множества A (или перестановками из n элементов) называются упорядоченная (n, n) -выборка, в которой элементы попарно различны A.

Пример 2. Пусть жества:

Очевидно, что перестановки из n элементов – частный случай размещений из n элементов по k, когда k n. Поэтому их число равно Сочетания. Сочетанием элементов из A по k (или сочетанием из n элементов по k) неупорядоченная ( n, k ) -выборка, в которой элементы попарно различны.

Пример 3. Пусть множества по два:

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

Формулу (1) несложно доказать, используя метод математической индукции. Советуем провести доказательства в качестве упражнения.

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

В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число Размещения с повторениями. Размещением с повторениями элементов из A по k (или размещением с повторением из n элементов по k) упорядоченная ( n, k ) -выборка, в которой элементы могут повторяться.

Пример 4. Пусть вторениями из этого множества по два:

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

Таким образом, число размещений из n элементов по k равно В частности, если в качестве множества A взято множество 0,1, то совокупность всех размещений с повторениями из A по k называется едиB k 2k ничным k -мерным кубом и обозначают B.

Пример 5. 3-х мерный куб размера 2 состоит из следующих элементов: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

Сочетания с повторениями. Сочетанием с повторениями элементов из A по k (или сочетанием с повторением из n элементов по k) неупорядоченная ( n, k ) -выборка, в которой элементы могут повторяться.

Пример 5. Пусть рениями из этого множества по два:

Можно показать, что число сочетаний с повторениями из n элементов по k равно Булеан множества A. Множество всех подмножеств называется буA леаном множества A и обозначается как 2.

Мощность булеана множества A равна 2. Докажем это. Пусть A a1, a2,..., an. Возьмем произвольное множество M 2 A и сопоставим ему взаимнооднозначным образом двоичный набор 1, 2,..., n :

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

Покрытие множества A. Семейство подмножеств A1, A2,..., Ar мноr 8. Разбиение множества A. Покрытие, образованное семейством A1, A2,..., Ar непустых, попарно непересекающихся подмножеств множества A, называют разбиением A. Множества A1, A2,..., Ar называют блоками разбиения.

Пример 7. Пусть является как разбиением, так и покрытием. В то время как семейство a, b, b, c является покрытием, но не является разбиением.

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

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

довательность функций. Этой последовательности сопоставим форa k k ( x) мальный ряд k 0 (для конечных последовательностей этот ряд превращается в многочлен). В ряде случаев, например, при определенных ограничениях, данный ряд может оказаться сходящимся и задавать некоa В качестве k В качестве примера применения производящих функций установим с их использованием следующее комбинаторное тождество:

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

Сравнивая коэффициенты при в левой и правой частях последнего тождества, получаем ТЕМА 3. ПЕРЕКЛЮЧАТЕЛЬНЫЕ (Булевы) ФУНКЦИИ 1. Свойства переключательных функций Рассмотрим множество из двух элементов B(2) = {0,1} и определим совокупность переменных ( x1, x2,......, x n ), таких, что каждая переменная может принимать значения только из B(2). Совокупность таких переменных назовем вектором двоичных переменных и обозначим символом чающуюся из ~ после замены переменных их значениями, двоичным набором. Любой такой набор можно рассматривать как целое двоичное число. Условимся называть десятичный эквивалент этого числа номером набора. Если обозначить произвольный двоичный набор символом ( 1, 2,.... n ), а номер этого набора j( ), то для заданного его ноn мер вычисляется следующим образом: j( )= i 2 n - i.

Например, номер набора j(0, 1, 0, 1, 0, 1) = 24 + 22 + 20 = 21. Наборы из n компонентов нумеруются числами от 0 до 2n - 1. Следовательно, всего имеется 2n различных двоичных наборов.

Двоичный набор ( j ) полностью определяется своим номером j и числом компонентов n. Например, для j = 12 и n= 6 имеем (12) = (0,0,1,1,0,0).

Далее, введем функции, зависящие от вектора аргументов ~, кото- x гут принимать значения только из множества B(2) и называются переключательными (булевыми) функциями. Областью определения переключательной функции от n переменных является множество из 2n двоичных наборов. Для того чтобы задать переключательную функцию, нужно указать соответствие между этими наборами и значениями функции. Такое соответствие проще всего описать с помощью таблицы истинности, число строк в которой определяется числом наборов, а число столбцов на единицу больше числа переменных. Пример такой формы задания функции приведен в табл. 1.1. Обозначим множество переключательных функций, зависящих от n аргументов: Р (n) = { ( x1, x 2,......x n ) }, и найдем число элементов этого множества |Р (n)|, т. е. число различных переключательных функций от n аргументов. В случае табличного задания столбцы значений различных функций должны иметь различие хотя бы в одной строке. Следовательно, для того чтобы найти число различных функций n переменных, нужно подсчитать, какое количество различных столбцов значений может быть в таблице, имеющей 2n строк. Если каждую позицию в столбце считать двоичной переменной, то задача сводится к определению числа наборов для 2n переменных. Исходя из этого, получаем, что |Р (n)| = 2 2.

1.1. Алгебра переключательных функций Перейдем к рассмотрению свойств множества функций Р (n). Прежде всего отметим, что это множество является частично упорядоченным, поскольку для некоторых пар функций i ( ~ ) и j ( ~ ) можно установить отx x ношение частичного порядка i ( ~ ) j ( ~ ), если в векторе значений функции j ( ~ ), вычисленном для всех возможных наборов, единицы стоят на всех тех местах, на которых они стоят в векторе значений функции i ( ~ ), и может быть, еще на некоторых.

Определим на этом множестве операции нахождения наибольшей нижней и наименьшей верхней граней. Согласно определению, каждая переключательная функция из множества Р(n) может принимать только значения из множества В (2). Если определить операции конъюнкции, дизъюнкции и отрицания с помощью таблиц истинности, то путем подстановки нетрудно убедиться, что все аксиомы булевой алгебры, оказываются справедливыми для этих операций. Например, подставляя вместо х вначале 0, а затем 1 в выражение 1 x x, убеждаемся, что это равенство справедливо для любого х В(2).

Используя введенные операции, можно выполнять операции над значениями различных функций, соответствующих одному и тому же набору аргументов. Следовательно, на множестве Р(n) можно определить операции конъюнкции и дизъюнкции, соответствующие нахождению наибольшей нижней и наименьшей верхней граней, следующим образом. Результатом конъюнкции функций 1 ( ~ ) и 2 ( ~ ) является функция 3 ( ~ ), знаx x x чения которой получаются путем вычисления конъюнкции значений 1 ( ) 2 ( ) на всех наборах. Результатом дизъюнкции функций 1 ( ~ ) и 2 ( ~ ) является функция 4 ( ~ ), значения которой получаются путем вычисления дизъюнкции значений 1 ( ) 2 ( ) на всех наборах Таким образом, можно сделать вывод, что частично упорядоченное множество Р(n) с определенными на нем операциями конъюнкции и дизъюнкции представляет собой алгебраическую решетку. Далее, можно утверждать, что при таком определении операций функция, принимающая значение 1 на всех наборах значений переменных, представляет собой наибольший элемент решетки - (1 ), а функция, принимающая значение на всех наборах, - наименьший элемент решетки - ( 0 ).

Более того, для каждой функции ( ~ ) в множестве Р (n) существует инверсный элемент ( ~ ), который вычисляется путем инвертирования каждого из значений функции ( ~ ).

Примеры выполнения операций, а также элементы (1 ) и ( 0 ) приведены в табл. 1.5.

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

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

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

несущественной, ( x1,..., xi 1,1, xi 1,..., xn ) ( x1,..., xi 1,0, xi 1,..., xn ) при любых значениях остальных переменных. Это означает, что изменение значения переменной x i не изменяет значения функции, поэтому эту переменную можно исключить из числа аргументов и рассматривать заданную функцию как функцию, зависящую от n-1 переменной. Несущественные переменные можно не только удалять, но и добавлять к аргументам функции. Следовательно, если заданы две функции ( x1,....., x k ) и ( x1,....., x l ), зависящие от разного числа переменных и k I, то, добавляя к функции с меньшим числом аргументов (I – k) несущественных переменных, можно получить функции с одинаковым количеством аргументов k. Описанный прием позволяет рассматривать операции конъюнкции и дизъюнкции как операции, определенные на множестве переключательных функций, зависящих от различного числа аргументов.

С ростом числа переменных таблица истинности, задающая переключательную функцию, сильно усложняется. Чтобы избежать усложнения таблицы, в некоторых случаях функцию задают множеством номеров двоичных наборов, на которых она равна единице. Например, функция, приведенная в табл. 1.1., может быть задана в виде следующей совокупности двоичных наборов: ( x1, x 2, x 3 ) { 010,011,101,111 } или их десятичных эквивалентов: ( x1, x 2, x 3 ) { 2,3,5,7 }.

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

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

ет, какие переменные образуют конъюнкцию, а набор задает порядок~ расстановки знаков инверсии над ними. Например: К(0,1,0,1) (x1,х2,х3,х4) = Разобьем вектор переменных ~ ( x1, x 2,..., x n ) на два подвектора ~ и ~ таким образом, чтобы подвектор ~ состоял из k, а подвектор ~ разбиению вектора переменных соответствует разбиение вектора значений ( 1, 2,.... n ) также на два подвектора: 1 ( 1, 2,.... k ) и Любую переключательную функцию, зависящую от n переменных, можно представить в виде дизъюнктивного разложения по k n переменным:

или в развернутом виде Следствие. Любую переключательную функцию можно представить в виде дизъюнктивного разложения по k = n переменным:

или в развернутом виде Выражение вида x1 1 x2 2... x l называют дизъюнкцией / пеl ременных и обозначают: D ( ~ ) x1 1 x2 2... x l.

Любую переключательную функцию, зависящую от n переменных, можно представить в виде конъюнктивного разложения по k n переменным:

или в развернутом виде Cледствие. Любую переключательную функцию можно представить в виде конъюнктивного разложения по k = n переменным:

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

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

Элементарной конъюнкцией n переменных или конституентой единицы называется выражение, представляющее собой конъюнкцию всех n переменных, причем каждая переменная может входить либо в прямом, либо в инверсном виде. Согласно принятым обозначениям элементарную конъюнкцию можно записать так: K ( ~ ) x1 1 x2 2... xn n. Из этой заx писи следует, что существует всего 2n различных элементарных конъюнкций n переменных, поскольку каждая конъюнкция определяется одним двоичным набором, состоящим из n компонентов.

В дальнейшем нам потребуется следующее свойство функции (1.1):

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

Рассмотрим теперь два свойства элементарных конъюнкций. Элементарная конъюнкция K ( ~ ) равна единице только в том случае, когда набор совпадает с набором значений переменных ~. В таблице истинx ности, задающей элементарную конъюнкцию, должна быть всего одна единица в столбце значений функции. Эта единица расположена в строке, отмеченной двоичным набором, совпадающим с набором. Таким образом, каждому набору в таблице соответствует единственная элементарная конъюнкция, равная единице на этом наборе. Для того чтобы построить эту элементарную конъюнкцию, нужно расставить инверсии над переменными согласно заданному набору. Например, конъюнкция, равная единице на наборе (0,1,1,1,0), имеет вид: x1 x2 x3 x4 x5.

Конъюнкция двух различных элементарных конъюнкций n переменных равна нулю: K ( ~ ) K ( ~ ) 0.

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

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

Два набора называются противоположными, если все компоненты одного из них можно получить с помощью инверсии компонентов другого набора. Например, наборы 1=(1,2,3,4,5) и 2=(1,2,3,4,5) противоположны. Элементарная дизъюнкция D ( ~ ) равна нулю только в том случае, когда набор является противоположным набору значений переменных.

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

Например, дизъюнкция, равная нулю на наборе (0, 1, 1, 1, 0), имеет вид:

Дизъюнкция двух различных элементарных дизъюнкций n переменных равна единице:

Любую переключательную функцию на основании (1.2) можно представить в совершенной дизъюнктивной нормальной форме (СДНФ), и притом, единственным образом, в следующем виде:

Покажем единственность СДНФ. Каждому набору, для которого ( ) = 1, соответствует единственная элементарная конъюнкция. Следовательно, совокупности наборов, на которых функция равна единице, соответствует единственная совокупность элементарных конъюнкций, являющаяся СДНФ заданной функции.

Любую переключательную функцию можно представить в совершенной конъюнктивной нормальной форме (СКНФ), и притом, единственным образом. Поскольку инверсия функции ( ~ ) равна единице на писать следующим образом:

Найдем инверсию правой и левой части выражения (1. 5):

Применяя дважды к полученному выражению правила де Моргана, получаем:

Последнее выражение и является СКНФ. Единственность СКНФ следует из единственности СДНФ.

ПРИМЕЧАНИЕ. СКНФ по аналогии с СДНФ можно получить также на основании разложения (1.3).

Пример 1.1. Построить СДНФ и СКНФ для функции из табл. 1.6:

Для построения СДНФ выпишем все наборы, на которых функция y равна 1: 000, 010, 101, 110. Для каждого набора построим элементарную конъюнкцию, равную единице на этом наборе: x1 x 2 x 3, x1 x 2 x 3, x1 x 2 x 3, x1 x 2 x 3. Соединяя эти конъюнкции знаками дизъюнкции, получаем СДНФ заданной функции:

Для построения СКНФ выписываем все наборы, на которых функция y равна нулю: 001,011,100,111. Для каждого набора построим элементарную дизъюнкцию, равную нулю на этом наборе: x1 x 2 x 3, x1 x 2 x 3, x1 x 2 x 3, x1 x 2 x 3. Объединяя с помощью конъюнкции все элементарные дизъюнкции, получаем СКНФ заданной функции:

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

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

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

Вектор аргументов x1,...,xn разбивают на две части x1,...,xk и xk+1,...,xn. Строкам таблицы приписывают значения первой группы аргументов 1,...,k, а столбцам таблицы - значения второй группы аргументов k+1,...,n. При таком расположении значений аргументов каждому набору (1,...,n) соответствует одна клетка таблицы, в которую может быть записано значение функции. Двухмерные таблицы для переключательных функций, которые называют диаграммами Вейча или картами Карно, обычно строят, приписывая значения аргументов строкам и столбцам таблицы таким образом, чтобы наборы аргументов, отличающиеся значением только одной переменной, располагались симметрично относительно какой-либо оси симметрии таблицы. Для построения карт, обладающих свойством симметрии, значения переменных приписывают строкам и столбцам таблицы в порядке, соответствующем зеркальному коду (цикличному коду, коду Грея).

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

1. Коды единичной длины (n=1) являются зеркальными.

2. Если построен код длины (n-1), то нужно построить новую ось симметрии и отобразить зеркально коды длины (n-1) относительно этой оси, а затем приписать слева всем кодам, расположенным выше оси, цифру 0, а кодам, расположенным ниже оси, цифру 1. В результате получаем зеркальные коды длины n.

Процесс построения зеркальных кодов для n=1,2,3 показан на рис.

1.1, а карты, построенные с использованием этих кодов, на рис. 1.2.

Для удобства построения и использования карт коды строк и столбцов опущены. Вместо них на картах строки и столбцы, соответствующие единичным значениям переменных xi, i=1,n, отмечены чертой с обозначеРис. 1. нием переменной xi. Таким образом, клетки, расположенные в строке или столбце, отмеченными чертой с переменной xi, соответствуют наборам, в которых xi =1. На картах, приведенных на рис. 1.2, жирными линиями показаны оси симметрии, которые соответствуют границам изменения значений переменных. Нетрудно проверить, что коды клеток, расположенных симметрично относительно оси с номером k, отличаются только значением одной переменной xk. Свойство симметрии карт является основой визуальных методов минимизации переключательных функций, которые будут рассмотрены в следующей главе.

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

2. МИНИМАЛЬНЫЕ ФОРМЫ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ

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

Построение упрощенных представлений основано на возможности эквивалентного преобразования членов СДНФ заданной функции. Например, если в СДНФ входят элементарные конъюнкции x 1 x 2 x 3 x 4 и x 1 x x 3 x 4, то, вынеся за скобки общий множитель, получаем:

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

В общем случае можно определить операцию склеивания для 2L различных элементарных конъюнкций, имеющих общий множитель из (n - L) букв, где n - число переменных, из которых состоит элементарная конъюнкция. Например, после вынесения общего множителя за скобки в СДНФ имеем x 2 x 3( x 1 x 4 x 1 x4 x1 x 4 x 1 x 4) = x2 x 3, поскольку выражение в скобках представляет собой дизъюнкцию всех элементарных конъюнкций двух переменных, которая тождественно равна единице.

Заметим, что по результату склеивания можно всегда восстановить исходную совокупность элементарных конъюнкций. Восстановление выполняется с использованием последовательных действий, которые назовем операцией расширения. Эта операция выполняется путем умножения конъюнкции, полученной в результате склеивания, на дизъюнкцию каждой отсутствующей буквы и ее отрицания. Например, чтобы восстановить заданную ДНФ по конъюнкции x2 x 3, полученной в предыдущем примере, необходимо домножить ее на произведение ( x x )( x 4 x4). В результате получаем x2 x3( x x ) ( x 4 x4) = x2 x3( x x 4 x x4 x x 4 x x4). После раскрытия скобок по закону дистрибутивности вновь приходим к (2.1).

Назовем число букв, образующих конъюнкцию, рангом конъюнкции. Для обозначения ранга конъюнкции K условимся использовать выражение r(K). Отметим, что склеиваться могут только конъюнкции одинакового ранга. Между конъюнкциями различных рангов может существовать отношение покрытия. Если r(Ki)r(Kj) и если Ki Kj=Ki, то говорят, что конъюнкция Ki покрывает конъюнкцию Kj Например, всякая конъюнкция, получающаяся в результате склеивания, покрывает все элементарные конъюнкции, используемые для ее построения.

Назовем сумму рангов конъюнкций, входящих в ДНФ заданной функции, рангом дизъюнктивной нормальной формы. Тогда ранг ДНФ, состоящей из m дизъюнктивных членов, определяется выражением где ri - ранг конъюнкции с порядковым номером i. Более точной по сравнению с рангом ДНФ мерой сложности ДНФ является так называемая цена по Квайну – общее число всех входов логических элементов в канонической двухярусной логической схеме, построенной на основании ДНФ. При построении такой схемы предполагается так называемая парафазное представление аргументов функции, т.е. наличие одновременно переменных x i и их дополнений x i, и не учитываются ограничения на число входов логических элементов.

Цена по Квайну определяется как сумма ранга ДНФ и числа конъюктивных членов ДНФ:

где r j – число входов логических элементов конъюнкции на 1-м ярусе схемы; m – число входов элемента дизъюнкции на 2-м ярусе схемы.

ПРИМЕЧАНИЕ:

- в первом слагаемом () учитываются только ранги конъюнкций - второе слагаемое (m) учитывается только в случае m 2.

Аналогично можно определить цену по Квайну КНФ. Отличием будет то, что соответствует числу входов логических элементов дизъюнкции на 1-м ярусе схемы, а m – числу входов элемента конъюнкции на 2-м ярусе схемы. Прежде чем перейти к дальнейшему изложению, рассмотрим следующий пример.

Пример 2.1. Пусть переключательная функция ( x 1, x 2, x 3, x 4) задана совокупностью своих элементарных конъюнкций: R4() = { x 1 x 2 x 3 x 4, x 1 x 2 x 3 x 4}, которая соответствует СДНФ. Найдем в множестве R4() все склеивающиеся пары конъюнкций и выпишем результаты операции склеивания. Обозначим полученное множество конъюнкций третьего ранга:

x 2 x 3 x 4, x 1 x 2 x 3}. Отыскивая склеивающиеся конъюнкции в множестве R3() и выполняя операцию склеивания, находим множество конъюнкций второго ранга: R2() = { x 1 x 4}. Поскольку последнее множество состоит из одной конъюнкции, то R1() =. Объединим полученные множества конъюнкций различных рангов в одно множество R() и назовем его комплексом конъюнкций заданной функции : R() = R4() R3() R2(). Любое подмножество Т R(), конъюнкции которого покрывают все элементарные конъюнкции множества R4(), назовем покрытием заданной функции. Например, следующие три подмножества являются покрытиями заданной функции: Т1 = { x 1 x 3 x 4, x 1 x 2 x 3 x 4, x 1 x 2 x 3 x 4, x 1 x 3 x 4, x 2 x 3 x 4}. Каждое покрытие соответствует ДНФ заданной переключательной функции. Таким образом, множество различных покрытий определяет множество эквивалентных дизъюнктивных нормальных форм переключательной функции.

Дизъюнктивную нормальную форму, обладающую наименьшим рангом из всех ДНФ заданной переключательной функции, назовем минимальной дизъюнктивной нормальной формой (МДНФ). В рассматриваемом примере МДНФ соответствует покрытию Т3 и имеет вид x 1 x 4 x 1 x 2 x 3 x 2 x 3 x 4. Ранг этой ДНФ равен 8, цена по Квайну Анализируя элементы комплекса R(), можно заметить, что некоторые из них покрываются конъюнкциями меньшего ранга и что имеются элементы, которые не покрываются другими конъюнкциями. Это наблюдение позволяет нам сформулировать следующее определение. Конъюнкция K называется минималью или простым импликантом, если в комплексе R() не существует другой конъюнкции K меньшего ранга, которая покрывает конъюнкцию K. Например, множество минималей P функции, приведенной в примере 2.1, имеет вид: P = { x 1 x 4, x 1 x 2 x 3, x 2 x 3 x 4, Дизъюнктивная форма, соответствующая множеству минималей, называется сокращенной дизъюнктивной нормальной формой (СкДНФ). Любая минимальная дизъюнктивная нормальная форма состоит из минималей. Это дает нам основание при построении МДНФ работать с множеством минималей P вместо того, чтобы выполнять это построение, пользуясь элементами комплекса R(), который содержит, как правило, значительно большее число элементов, чем P. Необходимо отметить, что ранг СкДНФ может намного превышать ранг МДНФ, поэтому построение СкДНФ следует рассматривать как первый этап процедуры нахождения МДНФ заданной функции. Задачей второго этапа этой процедуры обычно является упрощение полученной СкДНФ, которое достигается за счет удаления избыточных конъюнкций из СкДНФ.

Алгоритм построения множества минималей, или СкДНФ, зависит от того, в какой дизъюнктивной форме задана функция. Как правило, функцию задают либо в СДНФ, либо в произвольной ДНФ. Построение множества минималей несколько упрощается при задании функции в виде СДНФ.

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

2.2. Табличный метод построения множества минималей Квайна Мак-Класки Метод Квайна - Мак-Класки предназначен для нахождения множества минималей (простых импликант) для функций, заданных совокупностью наборов, на которых функция равна единице, или дизъюнктивной совершенной нормальной формой. Если Cn() - множество кодов, определяющих функцию, то наборы и, отличающиеся значением только одного компонента i, можно склеить и получить набор ~ ранга n-1. ВыполCn(), можно построить мноняя все возможные склеивания наборов жество наборов Cn-1() для заданной функции. Если операцию склеивания повторить для кодов Cn-1(), то можно получить множество кодов CnПовторяя подобным образом операции склеивания, можно последовательно получить множества Cn-1(), Cn-2(),..., C1(), если, конечно, они существуют. При этом коды, которые не были использованы для получения кодов меньшего ранга, т.е. коды, которые не покрываются кодами меньшего ранга, образуют искомое множество минималей.

Чтобы упростить процедуру поиска склеивающихся кодов, используют таблицу, состоящую из n столбцов. В первый столбец таблицы заносят коды множества Cn(). Склеивание кодов этого множества возможно лишь в том случае, если коды отличаются значением только одного компонента. Поэтому коды в этом столбце можно разместить, разделяя их на группы так, чтобы в каждую группу входили коды, имеющие одинаковое число единиц. Группы целесообразно расположить таким образом, чтобы число единиц в кодах каждой последующей группы было на единицу больше, чем в предыдущей. При таком размещении склеивание возможно только между кодами, расположенными в соседних группах. В результате склеивания кодов соседних групп может быть получено множество кодов ранга n-1, которые будут иметь одинаковое число единиц. Полученные коды расположим в столбце n-1, сохраняя разбиение по группам с одинаковым числом единиц и располагая группы в порядке возрастания числа единиц. Для кодов в полученном столбце можно повторить операцию склеивания для соседних групп и построить множество кодов ранга n-2. Сохраняя разбиение на группы и упорядочение групп, в каждом из последующих столбцов можем найти множества Cn-3(), Cn-4(),..., C1().

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

В качестве иллюстрации описанного способа рассмотрим следующий пример.

Пример 2.2. Требуется найти множество минималей для функции ( x 1, x 2, x 3, x 4 ) = {0000, 0001, 1000, 0011, 0101, 0111, 1100, 1101} из примера 2.1.

Построим таблицу из четырех столбцов и поместим в первый столбец таблицы заданные коды, предварительно разбив их на группы по числу единиц, как это показано в табл. 2.1. Выполняя операцию склеивания смежных кодов, расположенных в соседних группах, и помечая коды, использованные для склеивания, получаем коды ранга три, которые записаны во второй столбец табл. 2.1. В этом столбце коды также разделены на группы с одинаковым числом единиц. Выполняя операцию склеивания для смежных кодов в соседних группах, получаем коды ранга два, которые запишем в третий столбец. Поскольку в рассматриваемом примере получается всего один код ранга два, то процесс заканчивается, и множество кодов, не имеющих отметок в таблице, представляет собой множество минималей P = {000z, z000, 1z00, 110z, z101, 0zz1}.

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

Пример 2.3. Рассмотрим образование неизбыточных покрытий функции, приведенной в примере 2.1. Согласно примеру 2.2, множество минималей этой функции имеет вид P = {0zz1, 110z, 1z00, z101, z000, 000z}. Выбирая различные способы покрытия наборов, определяющих заданную функцию, нетрудно найти все ее неизбыточные покрытия:

H2 = {0zz1, 1z00, z101, z000}, H4 = {0zz1, 1z00, z101, 000z}, из которых покрытие H1 является минимальным.

Сравнивая неизбыточные покрытия, построенные в примере, нетрудно заметить, что код 0zz1 обязательно входит в каждое такое покрытие. Последнее обстоятельство объясняется тем, что наборы 0011 и 0111 покрываются только этим кодом 0zz1, и поэтому его удаление из любой совокупности кодов Hj привело бы к появлению непокрытых наборов из Cn().

Назовем набор Cn() существенным, если он покрывается только одним кодом “е” из множества минималей Р, а код “е”, покрывающий хотя бы один существенный набор, назовем экстремалью. В приведенном примере код 0zz1 является экстремалью, а наборы 0011 и 0111 являются существенными наборами. Все экстремали входят в любое неизбыточное покрытие заданной функции, поскольку каждая экстремаль покрывает хотя бы один набор Cn(), который не покрывается никаким другим кодом из Р.

Из сказанного вытекают два важных следствия.

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

Следствие 2. Если минимальное покрытие состоит из экстремалей, то такое покрытие является единственным.

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

3. РЕАЛИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ В

УНИВЕРСАЛЬНЫХ БАЗИСАХ

Логические или комбинационные схемы, являющиеся основой для построения различных вычислительных устройств и компьютеров, обычно строят из логических элементов (ЛЭ), каждый из которых реализует определенную переключательную функцию. При изготовлении ЛЭ, а также при построении БИС выгодно иметь один тип элементов, которые могут быть использованы для построения любой логической схемы. Такой логический элемент должен быть универсальным. Он должен обеспечивать возможность построения схемы для любой переключательной функции.

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

Для упрощения перехода от переключательной функции к реализующей ее логической схеме переключательную функцию удобно записывать в так называемой операторной форме, в которой каждый использованный оператор F(x1,…, x k ) реализует функцию (x 1,…, x k ) и однозначно соответствует некоторому ЛЭ с k входами и одним выходом в логической схеме.

Совокупность функций B { y1, y 2,..., y m } образует полный функциональный базис если любая переключательная функция произвольного числа аргументов может быть представлена суперпозицией функций из этого базиса. Соответственно, совокупность логических элементов {ЛЭ1,ЛЭ2,...,ЛЭm}, реализующих функции из полного функционального базиса B, образует полный структурный базис и позволяет построить логическую схему произвольной сложности.

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

3.1. Реализация переключательных функций в универсальном базисе Шеффера В качестве первого такого базиса рассмотрим универсальный базис В={/} – “Штрих Шеффера” (отрицание конъюнкции):

Для перехода к логической схеме введем оператор S(x1 x2) = x1/x2, которому соответствует универсальный элемент Шеффера ( рис. 3.1 ):

Рассмотрим свойства операции "/".

1. Операция не идемпотентна, так как х/х = x x = x.

2. Операция коммутативна, так как 3.Операция не ассоциативна, так как Выразим теперь функции базиса {,, } через функцию " / ".

Инверсия:x = x x = x/x = x 1 = x/1. Условимся в дальнейшем использовать второй из рассмотренных способов инвертирования, заменяя все неиспользуемые аргументы константой 1.

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

Конъюнкция:

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

x1 x2 = (x1 / x2)/ 1=S (S(x1,x2), 1) = S2 (x1,x2) ПРИМЕЧАНИЕ: S (x1, x2) = S (S2 (x1, x2),1) = S (x1, x2).

Аналогично можно определить оператор произвольной степени:

Дизъюнкция:

Перейдем теперь к операторному представлению и построим соответствующие фрагменты логических схем для исходного базиса и базиса Шеффера (рис. 3.4) x1 x2 = (x1/1)/(x2/1) = S (S(x 1,1),S (x2,1)) По аналогии с операциями конъюнкции и дизъюнкции можно рассматривать как обобщение двуместной операции "/" многоместную операцию "Штрих Шеффера" и многоместный оператор Шеффера:

x1/x2/..../xt = x1 x2... xt = S (x1, x2,..., xt), где t – местность оператора и соответственно число входов многовходового универсального логического элемента Шеффера. Следует, однако, соблюдать осторожность при попытке представить многоместную операцию "Штрих Шеффера" в виде суперпозиции операций Шеффера меньшей местности. Следует помнить, что операция "/" не ассоциативна, поэтому, например, не справедливы равенства:

Эквивалентное преобразование имеет вид:

В операторной форме это преобразование имеет вид:

S (x1, x2, x3) = S (S 2 (x1, x2), x3) = S (x1, S 2 (x2, x3)) и может быть проиллюстрировано фрагментами логических схем (рис. 3.5):

Рассмотрим два способа построения формул над базисом {/}, перехода к операторному представлению и построению логических схем.

Примем два допущения:

- исходной формулой является произвольная формула над базисом - местность оператора Шеффера и соответственно число входов универсального логического элемента Шеффера фиксированы (t = const);

- допускаются инверсии элементарных переменных.

Способ 1.

ШАГ 1. Произвольную формулу с помощью эквивалентных преобразований по законам булевой алгебры вначале привести к ДНФ. Затем к ДНФ применить закон двойного отрицания и закон де Моргана для перехода в базис Шеффера:

Шаг 2. Если какие-либо операции Шеффера k (отрицание конъюнкции) в полученной записи имеют местность больше t, необходимо выразить их через операции местности t. Операции с местностью меньше t следует привести к необходимой местности, заменяя отсутствующие переменные константой 1.

Шаг 3. Заменить каждую операцию Шеффера местностью t соответствующим оператором Шеффера, построить логическую схему.

ПРИМЕЧАНИЕ: вырожденной (однобуквенной) конъюнкции вида в ДНФ в новой формуле соответствует вырожденная (однобуквенная) операция Шеффера вида x i l.

Пример 3.1. Пусть исходной является формула в ДНФ.

=S (S (S2 (x1, x2, x3),x4, 1), S (x1,x2, 1), x3).

По операторному представлению легко построить логическую схему (рис 3.6).

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

ПРИМЕЧАНИЕ: Вначале следует использовать операторы Шеффера произвольной местности, а затем привести их к необходимому значению t.

Пример 3.2. Пусть исходной является формула в ДНФ, y = S2 (x1, x2, x3,x4) S2 (x1,x2) x3 = S (S3 (x1, x2, x3,x4), S3 (x1,x2), x3) = = S (S (x1, x2, x3,x4), S (x1,x2), x3) = S (S (S2 (x1, x2, x3),x4,1), S (x1,x,1), x3).

Соответствующая логическая схема аналогична приведенной на рис.

3.6.

ТЕМА 4. КОМБИНАТОРИКА

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

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

Правило суммы. Если объект U может быть выбран m способами, а объект V k способами, то выбор «либо U, либо V » может быть осуществлен m k способами.

Правило произведения. Если объект U может быть выбран m способами и после каждого из таких выборов объект V в свою очередь может быть выбран k способами, то выбор « U и V » в указанном порядке может быть осуществлен mk способами.

Набор элементов ai, ai,..., ai из множества A a1, a2,..., an называется выборкой объема k из n элементов или ( n, k ) -выборкой.

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

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

Рассмотрим некоторые комбинаторные объекты и их комбинаторные числа.

1. Размещения. Размещением элементов из A по k (или размещением из n элементов по k) называется упорядоченная ( n, k ) -выборка, в которой элементы попарно различны.

го множества по два:

Обозначим число размещений из n по k через n k. Для подсчета числа n k используем правило произведения. При построении конкретного размещения первым элементом в нем можно взять любой из n элементов множества A, вторым элементом – любой из n 1 оставшихся в A элементов и т.д. Поэтому При k n не существует размещений из n по k, следовательно, n k Упражнение 1. Показать, что для чисел n k выполняются тождества 2. Перестановки. Перестановками элементов множества A (или перестановками из n элементов) называются упорядоченная (n, n) -выборка, в которой элементы попарно различны A.

Очевидно, что перестановки из n элементов – частный случай размещений из n элементов по k, когда k n. Поэтому их число равно 3. Сочетания. Сочетанием элементов из A по k (или сочетанием из n элементов по k) неупорядоченная ( n, k ) -выборка, в которой элементы попарно различны.

Пример 3. Пусть множества по два:

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

Формулу (1) несложно доказать, используя метод математической индукции. Советуем провести доказательства в качестве упражнения.

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

В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число 4. Размещения с повторениями. Размещением с повторениями элементов из A по k (или размещением с повторением из n элементов по k) упорядоченная ( n, k ) -выборка, в которой элементы могут повторяться.

Пример 4. Пусть вторениями из этого множества по два:

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

Таким образом, число размещений из n элементов по k равно В частности, если в качестве множества A взято множество 0,1, то совокупность всех размещений с повторениями из A по k называется едиB k 2k ничным k -мерным кубом и обозначают B.

Пример 5. 3-х мерный куб размера 2 состоит из следующих элементов: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

5. Сочетания с повторениями. Сочетанием с повторениями элементов из A по k (или сочетанием с повторением из n элементов по k) неупорядоченная ( n, k ) -выборка, в которой элементы могут повторяться.

Пример 5. Пусть рениями из этого множества по два:

Можно показать, что число сочетаний с повторениями из n элементов по k равно 6. Булеан множества A. Множество всех подмножеств называется булеаном множества A и обозначается как 2.

Мощность булеана множества A равна 2. Докажем это. Пусть A a1, a2,..., an. Возьмем произвольное множество M 2 A и сопоставим ему взаимнооднозначным образом двоичный набор 1, 2,..., n :

Отсюда получаем, что мощность булеана совпадает с мощностью множества, образованного всеми двоичными наборами, т.е. с мощностью 7. Покрытие множества A. Семейство подмножеств A1, A2,..., Ar 8. Разбиение множества A. Покрытие, образованное семейством A1, A2,..., Ar непустых, попарно непересекающихся подмножеств множества A, называют разбиением A. Множества A1, A2,..., Ar называют блоками разбиения.

Пример 7. Пусть является как разбиением, так и покрытием. В то время как семейство a, b, b, c является покрытием, но не является разбиением.

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

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

Пусть имеется последовательность чисел a0, a1, a2,..., ak,... и последовательность функций k (x). Этой последовательности сопоставим формальa k k ( x) ный ряд k 0 (для конечных последовательностей этот ряд превращается в многочлен). В ряде случаев, например, при определенных ограничениях, данный ряд может оказаться сходящимся и задавать некоторую функцию F (x ) :. Эта функция называется производящей для поk следовательности В качестве k (x) обычно используют x и x / k!.

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

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

тождества, получаем

ТЕМА 5. ТЕОРИЯ ГРАФОВ

Начало теории графов как математической дисциплине было положено Леонардом Эйлером в его знаменитом решении задачи о Кенигсбергских мостах в 1736 году. План города Кенигсберга представлен на рис. 5.1.

Задача о Кенигсбергских мостах сводилась к тому, чтобы построить маршрут своей воскресной прогулки так, чтобы, начиная в любой точке суши (A, B, C или D) пройти по всем мостам строго по одному разу и вернуться в исходную точку (начало маршрута).

Рис. 5.1. Иллюстрация к задаче о Кенигсбергских мостах.

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

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

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

Иными словами, граф представляет совокупность множества вершин Граф, представленный на рис. 3. 2, состоит из множества вершин Графическое изображение графа является самым наглядным, но не единственным способом задания графа. Кроме того граф может быть задан:

1. перечислением:

где Г - образ вершины x - множество вершин, в которые исходят дуги из данной вершины.

3. матрицей инцидентности Матрица инцидентности - это матрица вершин и инцидентных им дуг.

Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вершину.

Вершина инцидентна дуге, если в эту вершину заходит или исходит данная дуга.

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

1, если из i-той вершины исходит j-тая дуга:

1, если в i-той вершину заходит j-тая дуга;

0, если i-тая вершина не инцидента j-той дуге;

2, если из i-той вершины исходит j-тая дуга и в нее же заходит, т.е. в i-той вершине j-тая дуга образует петлю.

Для графа, представленного на рис. 5.2 матрица инцидентности имеет вид:

На практике в матрице инцидентности иногда нули не проставляются для наглядности.

Свойство матрицы инцидентности – сумма элементов по столбцам равна 0 или 2.

4. матрицей смежности Смежные дуги – это дуги инцидентные одной вершине.

Смежные вершины – вершины, инцидентные одной дуге.

Матрица смежности - это матрица смежных вершин.

Матрица смежности заполняется по следующему правилу: 1, если из i-той вершины исходит дуга в j – тую вершину; во всех остальных случаях 0 (для удобства и наглядности на практике в матрице смежности нули не проставляются).

Для графа, представленного на рис. 3.2 матрица смежности имеет вид:

Полустепенью захода ( x ) i–той вершины называется число дуг, заходящих в данную вершину.

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

Степенью i-той вершины исхода ( x ) называется сумма полустепеi ней захода и исхода:

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

1. Сумма единиц по строке определяет полустепень исхода;

2. Сумма единиц по столбцу определяет полустепень захода;

3. Сумма единиц по строкам и по столбцам определяет степень вершин.

Основное свойство графа:

В любых графах число вершин с нечетной степенью четно.

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

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

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

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

Контур – путь, начинающийся и заканчивающийся в одной точке.

Петля – контур длиной в одну единицу.

Графы бывают двух видов:

ориентированный граф (орграф) - это граф, состоящий из вершин и дуг.

неориентированный граф – это граф, состоящий из вершин и ребер.

Ребро – это дуга, не имеющая направление.

В неориентированном графе путь называется цепью; контур – циклом.

Неориентированный граф также может быть задан с помощью матриц инцидентности и смежности.

Матрица инцидентности для неориентированного графа составляется по правилу:

1, если i-тая вершина инцидентна j-тому ребру;

0, если i-тая вершина не инцидента j-тому ребру;

2, если. в i-той вершине j-тое ребро образует петлю.

Для графа, представленного на рис. 5.3, матрица инцидентности имеет вид:

I II III IV V VI VII

Матрица смежности для неориентированного графа составляется по правилу: 1, если из i-тая и j – тая вершины смежные.

Для графа, представленного на рис. 5.3, матрица смежности имеет вид:

Матрица смежности для неориентированного графа симметрична относительно главной диагонали. Степень i- той вершины равна сумме элементов по строке или по столбцу матрицы смежности.

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

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

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

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

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

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

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

ТЕОРЕМА: Для того чтобы связанный граф был Эйлеровым, необходимо и достаточно, чтобы степени всех вершин были четны Данная теорема позволяет решить задачу о Кенигсбергских мостах.

Граф, соответствующий данной задаче, имеет вид Вершины графа (A, B, C, D) имеют степени:

Тогда в соответствии с теоремой Эйлера данный граф не является Эйлеровым. А это означает, что нельзя обойти все мосты г. Кенигсберга строго по одному разу, начав и закончив путь в одной точке суши.

Следствие из ТЕОРЕМЫ: Для того чтобы граф содержал Эйлеровую цепь, необходимо и достаточно, чтобы две вершины имели нечетную степень. При этом в одной из вершин цепь будет начинаться, в другой – заканчиваться.

Множество внутренней устойчивости графа Множество внутренней устойчивости графа – это множество несмежных вершин.

Пусть дан граф G Г, X. Тогда для множества внутренней устойчивости X ' справедливо следующее:

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

ПРИМЕР

Данный граф имеет следующие множества внутренней устойчивости.

{ A, E}, {B, D}, {B, E}, {C, D}, {C, E} Рассмотрим множество { A, E}. Добавляя к нему любую вершину, получаем множества внутренне неустойчивые: { A, E, B}, { A, E, C}, { A, E, D}.

Следовательно, множество { A, E} является максимальным множеством внутренней устойчивости.

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

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

Алгоритм Магу для определения множества внутренней устойчивости графа Пусть дан граф G Г, X. Для данного графа существует множество внутренней устойчивости X '.

Введем булевую переменную x, которая определяется следующим образом:

вости x X ' ;

чивости x X ' ;

Введем булевую переменную :

1, если между i-той и j-той вершиной есть дуга;

0, если между i-той и j-той вершиной нет дуги.

Тогда определение внутренней устойчивости (3.4) может быть представлено в следующем виде:

Или используя булевую алгебру:

Применяя формулы равносильности, преобразуем:

Рассмотрим выражение:

Если 0, то данное равенство является тавтологией.

Если 1, то равенство имеет вид:

Данное уравнение лежит в основе алгоритма Магу Алгоритм Магу состоит из следующих этапов:

1. Для графа составляется матрица смежности.

2. По таблице смежности выписываются все парные дизъюнкции.

3. Выражение приводится к ДНФ.

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

ПРИМЕР

Матрица смежности имеет вид:

Для всех единиц выписываются парные дизъюнкции:

Приведем выражение к ДНФ:

Множества внутренней устойчивости:

Числом внутренней устойчивости = 2.

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

1). Любая вершина входит в это множество 2) Либо вершина не входит в это множество, но из этой вершины есть дуга в данное множество.

Пусть дан граф G Г, X. Тогда для множества внешней устойчивости X ' справедливо следующее:

Число внешней устойчивости () – это наименьшая мощность из всех множеств внешней устойчивости.

Алгоритм Магу для определения множества внешней устойчивости.

Пусть дан граф G Г, X. Для данного графа существует множество внешней устойчивости X ".

Вводятся булевые переменные x и по тому же правилу, что и для алгоритма Магу для определения множества внутренней устойчивости.

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

Для 1 справедливо следующее Данное уравнение лежит в основе алгоритма Магу Алгоритм Магу состоит из следующих этапов:

1. Для графа составляется матрица смежности 2. Матрица смежности дополняется единицами (1) по главной диагонали.

3. Для каждой строки выписываются дизъюнкции.

4. Выражение приводится к ДНФ.

5. Все вершины, входящие в элементарную конъюнкцию, образуют множество внешней устойчивости

ПРИМЕР

Определить множество внешней устойчивости для графа, представленного на рис. 5.7.

Матрица смежности имеет вид:

Дополним матрицу смежности единицами по главной диагонали Для каждой строки выписываются дизъюнкции:

Приведем выражение к ДНФ:

Множества внутренней устойчивости:

Числом внешней устойчивости = 2.

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

Граф, представленный на рис. 5.7. имеет ядро {x, x } Множество путей в графе По матрице смежности можно определить, сколько различных путей существует между i-той и j- той вершинами длиной в к единиц. Для этого необходимо определить матрицу M k, где M - матрица смежности.

Если элемент a матрицы M k :

a 0 - между i-той и j- той вершины не существует пути длиной в к единиц;

a n - между i-той и j- той вершины существуют n различных путей длиной в к единиц;

Если M k - нулевая матрица, это означает, что графе нет путей в к единиц, а максимальный путь – это путь длиной в (к -1) единиц.

Алгоритм фронта волны. Поиск минимального пути в графе.

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

Рассмотрим некоторые свойства минимальных путей 1. Любой минимальный путь является простым путем.

x (1 i j k ) внутри минимального пути также будут минимальxx ны.

Пусть Г-1х – прообраз вершины xi – это множество вершин, из которых исходят дуги в вершину xi.

Одним из алгоритмов поиска минимального пути в графе является алгоритм фронта волны (FW –Front Wave) Алгоритм фронта волны.

Пусть необходимо найти минимальный путь из вершины x в вершиi ну x.

дексом 0.

2. Находится первый фронт волны FW ( x ) как множество вершин образа вершины x.

3. Все вершины, принадлежащие первому фронту волны, помечаются индексом 1.

4. Вводится счетчик шагов (фронтов волны) k 1.

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

6. Если x FW ( x ), то переходим к пункту 8. В противном случае существует путь из вершины x в вершину x длиной в k единиц, и этот путь минимальный:

7. Находятся промежуточные вершины z, z,, z z по правилу:

где Г 1 - прообраз вершины x - множество вершин, из которых захоx дят дуги в вершину x 8. Определяется k 1 фронт волны как все непомеченные вершины, принадлежащие образу вершин k - го фронта волны. Помечаются индексом k 1 вершины k 1 фронта волны. Далее осуществляется переход к пункту 5.

ПРИМЕР

Пусть задан граф матрицей смежности:

Необходимо найти минимальный путь из вершины x в вершину x (по алгоритму «фронта волны»).

1. Выпишем все вершины. Вершина x помечается индексом «0»

2. Находится первый фронт волны:

3. Все вершины, принадлежащие первому фронту волны, помечаются индексом «1».

5. Все вершины, принадлежащие второму фронту волны, помечаются индексом «2».

определяем третий фронт волны:

7. Так как x FW ( x ), то существует путь из вершины x в вершину x длиной 3 единицы:

8. Находятся промежуточные вершины z, z :

Таким образом, минимальный путь из вершины x в вершину x имеет вид:

Ярусно-параллельная форма графов Граф, не имеющий контуров, может быть представлен в яруснопараллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус помещены вершины, имеющие только исходящие дуги; в нижний ярус помещены вершины, имеющие только входящие дуги. На k-том ярусе помещены вершины, которые имеют входящие дуги из предыдущих ярусов, среди которых хотя бы одна дуга из (kтого яруса.

Количество вершин в ярусе определяет ширину яруса. Наибольшая ширина яруса определяет ширину графа в ярусно-параллельной форме.

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

Алгоритм приведения графа к ярусно-параллельной форме.

1. Составляется матрица смежности графа.

2. Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус.

3. Из матрицы смежности столбцы и строки, соответствующие вершинам нулевого яруса.

4. Повторяется п.2 данного алгоритма до тех пор, пока не будут охвачены все вершины.

5. По исходной матрице смежности восстанавливаются дуги между вершинами.

6.3. Краткое описание лабораторных работ 6.3.1. Перечень рекомендуемых лабораторных работ 1. Использование языковых средств программирования для задач теории множеств.

2 Процедуры генерации комбинаторных схем.

3 Алгоритмы минимизации булевых функций.

4 Программная реализация алгоритмов на графах.

6.3.2. Перечень рекомендуемых практических занятий 1 Множества и их спецификации; диаграммы Венна; алгебра множеств.

2 Отношения, свойства бинарных отношений. Отношения эквивалентности, порядка.

3 Комбинаторика, основное правило комбинаторики, комбинаторные схемы. Биномиальная и полиномиальная теоремы.

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

5 Решение задач и рассмотрение алгоритмов теории графов.

5.1.1. Методические указания по выполнению лабораторных работ Лабораторная работа № 1. Использование языковых средств программирования для задач теории множеств.



Pages:   || 2 |
 


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

«ИНСТИТУТ ЭТНОЛОГИИ И АНТРОПОЛОГИИ РАН ИССЛЕДОВАНИЯ ПО ПРИКЛАДНОЙ И НЕОТЛОЖНОЙ ЭТНОЛОГИИ № 233 В.К. Малькова ПОЛИЭТНИЧНАЯ МОСКВА 2011–2012 гг.: ТРЕВОЖНЫЕ ЗВОНКИ В ИНФОРМАЦИОННОМ ПРОСТРАНСТВЕ Москва ИЭА РАН 2012 ББК 63.5 УДК 008(470.6) Серия: Исследования по прикладной и неотложной этнологии (издается с 1990 г.) Редколлегия: академик РАН В.А. Тишков (отв. ред.), к.и.н. Н.А. Лопуленко, д.и.н. М.Ю. Мартынова. Материалы серии отражают точку зрения авторов и могут не совпадать с позицией редакционной...»

«LCJE Bulletin Лозаннская Консультация по Евангелизации Евреев (ЛКЕЕ) Special Russian Edition 2014 Networking Jewish Evangelism LCJELausanne Consultation on Jewish Evangelism LCJE Networking Jewish Evangelism Lausanne Consultation on Jewish Evangelism LCJE Bulletin Russian Edition - 2014 От Координатора © Lausanne Consultation on Jewish Evangelism Дорогой сотрудник, Editor : Jim Melnick Design : Chris Skjtt Приветствую вас во имя нашего Мессии Иешуа! В данном специальном издании бюллетеня...»

«Свидетельство о регистрации ПИ № ФС 77 18831 выдано Федеральной службой по надзору за соблюдением законодательства в сфере массовых коммуникаций и охране культурного наследия СОДЕРЖАНИЕ Вступая в следующий год......................................... 4 ФИНАНСОВЫЕ РЫНКИ А. Мёрфи, З. А. Сабов Финансовые и валютные кризисы: возможные пути преодоления.............. 5 Ю. Р. Ичкитидзе О рефлексивности финансового рынка.................»

«УДК 1/14 + 29 ББК 86.35 С 89 ПРЕДИСЛОВИЕ С у д з у к и Д. Т. Дзэн и японская культура. — СПб.: Наука, 2003. — 522 с. ISBN 5-02-026193-9 Известный японский буддолог Дайсэцу Тэйтаро Судзуки (1870 — 1966) приглашает читателя погрузиться в мир при­ чудливой японской культуры. Своеобразие этой культуры во многом связано с долгим и плодотворным влиянием на нее Эт а книга под заголовком Д зэн -будди зм и его дзэн-буддизма. Излагая тему одновременно и в качестве влияние на японскую к у л ь т у р у (...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное образовательное учреждение высшего профессионального образования КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ УТВЕРЖДАЮ Декан факультета ветеринарной медицины профессор Лысенко А.А. _ 2009 г. РАБОЧАЯ ПРОГРАММА дисциплины: Культурология для специальности 111900 Ветеринарно-санитарная экспертиза квалификация бакалавр Факультет Ветеринарной медицины Ведущая кафедра социологии и культурологии Дневная форма обучения...»

«Министерство культуры, по делам национальностей, информационной политики и архивного дела Чувашской Республики Национальная библиотека Чувашской Республики Центр формирования фондов и каталогизации документов ИЗДАНО В ЧУВАШИИ бюллетень новых поступлений обязательного экземпляра документов февраль 2009 г. Чебоксары 2009 PDF created with pdfFactory Pro trial version www.pdffactory.com Издано в Чувашии - бюллетень поступлений обязательного экземпляра документов, включает издания за 2001-2009 гг.,...»

«РеаСпоМед 2006 СПЕЦИАЛИЗИРОВАННАЯ ВЫСТАВКА И НАУЧНЫЙ ФОРУМ 1 ОРГАНИЗАТОРЫ: КОМПАНИЯ МЕДИ ЭКСПО РОССИЙСКАЯ АССОЦИАЦИЯ ПО СПОРТИВНОЙ МЕДИЦИНЕ И РЕАБИЛИТАЦИИ БОЛЬНЫХ И ИНВАЛИДОВ ПРИ ПОДДЕРЖКЕ И УЧАСТИИ: СОВЕТА ФЕДЕРАЦИИ ФЕДЕРАЛЬНОГО СОБРАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЙ ДУМЫ ФЕДЕРАЛЬНОГО СОБРАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ МИНИСТЕРСТВА ЗДРАВООХРАНЕНИЯ И СОЦИАЛЬНОГО РАЗВИТИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОГО АГЕНТСТВА ПО ФИЗИЧЕСКОЙ КУЛЬТУРЕ И СПОРТУ ВСЕРОССИЙСКИЙ...»

«Габитов Т. Х. КУЛЬТУРОЛОГИЯ Учебник Алматы 2006 Введение 1 – РАЗДЕЛ: Теория культуры 1.1.Формирование предмета культурологии. 1.2. Культура и цивилизация. 1.3. Этнокультуры и мировая цивилизация 1.4.Современные западные теории культуры и цивилизаций. 1.5. Модернизм и постмодернизм 1.6. Диалог культур 1.7. Культура и религия в гражданском обществе 1.8.Устойчивое развитие как ценность современной культуры 1.9.Культура, демократия, рынок. 1.10. Гражданское общество и религия 2 - РАЗДЕЛ. Мировые...»

«Таллиннская палата обществ инвалидов Инфосборник В помощь людям с ограниченными возможностями 2010 Обзор государственных и предоставляемых городом Таллинном услуг и пособий, предназначенных людям с ограниченными возможностями. Информация о Таллиннской палате обществ инвалидов и ее 21 членской организации, помогающая найти необходимые контактные данные людям, желающим вступить в какое-либо общество людей с ограниченными возможностями. Euroopa Kolmandate Riikide Kodanike Integreerimise Fond...»

«Антон САлмин СиСтЕмА ФолЬК-РЕлиГии ЧУВАШЕЙ Санкт-Петербург наука 2007 УДК 908 + 29 + 16 ББК 63.5 (2) + 86.31+87.251.24 С16 Работа утверждена к печати Ученым Советом МАЭ РАН 15 июня 2006 г. Ответственный редактор А.И. Терюков Рецензенты М.Ф. Альбедиль, А.Б. Островский Издание осуществлено при финансовой поддержке СанктПетербургского научного центра РАН (грант 2007 г.), а также спонсоров (В.И. Матросов, О.В. Немцева, В.Г. Муравьёв, Д.А. Тукмаков) Салмин А.К. C16 Система фольк-религии чувашей. –...»

«М.ТРУНОВ, Л.КИТАЕВ ЭКОЛОГИЯ МЛАДЕНЧЕСТВА. ПЕРВЫЙ ГОД Серия “Школа сознательного родительства” Дорогие друзья! Перед вами первая книга из серии “Школа сознательного родительства”, рассказывающая о младенчестве с позиции любви, о первом годе жизни ребенка и вашей жизни вместе с ним, а не для него. Эта серия посвящается тем малышам, которые своим здоровьем и радостным отношением к жизни убеждали авторов и нас в естественности и правильности выбранного пути. Создатели этой серии – такие же...»

«АДМИНИСТРАЦИЯ НИЖЕГОРОДСКОЙ ОБЛАСТИ РАСПОРЯЖЕНИЕ от 13 сентября 1996 г. N 1236-р ОБ ОБЪЯВЛЕНИИ ПРИРОДНЫХ ОБЪЕКТОВ ГОСУДАРСТВЕННЫМИ ПАМЯТНИКАМИ ПРИРОДЫ РЕГИОНАЛЬНОГО (ОБЛАСТНОГО) ЗНАЧЕНИЯ В соответствии со ст. 9 и 64 Закона Российской Федерации Об охране окружающей природной среды, ст. 2 и 26 Федерального закона РФ Об особо охраняемых природных территориях, во исполнение решения Нижегородского областного Совета народных депутатов от 22.03.1994 N 57-м Об утверждении Перечня особо охраняемых...»

«БЮЛЛЕТЕНЬ НОВЫХ ПОСТУПЛЕНИЙ 2011 г., 1 КВАРТАЛ 2012 г. Библиотека Иркутской государственной сельскохозяйственной академии Иркутск 2012 Содержание 1. Агрономический факультет...2 2. Инженерный факультет...20 3. Общественные кафедры...31 4. Факультет Биотехнологии и ветеринарной медицины.38 5. Факультет охотоведения...51 6. Экономический факультет...62 7. Энергетический факультет..85 8. Художественная литература..90 2 1. АГРАРНЫЙ ФАКУЛЬТЕТ ББК 75 Агротуризм : проблемы и перспективы развития...»

«Департамент образования города Москвы Государственное образовательное учреждение высшего профессионального образования города Москвы МОСКОВСКИЙ ГОРОДСКОЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ Социальный институт Кафедра социальной педагогики УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС УЧЕБНОЙ ДИСЦИПЛИНЫ Социально-педагогическая поддержка ребенка в образовании 0504000.68 Психолого-педагогическое образование Квалификация (степень) выпускника – магистр Профили подготовки – Социально-педагогическая деятельность в детских и...»

«Евгений Николаевич Лебедев Ломоносов Жизнь замечательных людей – 827 http://zzl.lib.ru Ломоносов: Молодая гвардия; Москва; 1990 Аннотация Книга во многом по-новому излагает обстоятельства жизни и творчества великого русского просветителя, ученого и поэта Михаила Васильевича Ломоносова (1711-1765). Автор показывает гениального сына нашего отечества в неразрывной связи с предыдущей и последующей судьбой российской культуры и просвещения, его глубокую самобытность, всестороннюю блистательную...»

«ВСЕМИРНЫЙ АНТИДОПИНГОВЫЙ КОДЕКС Всемирное антидопинговое агентство 2009 Всемирное антидопинговое агентство Национальная антидопинговая организация РУСАДА ВСЕМИРНЫЙ АНТИДОПИНГОВЫЙ КОДЕКС Москва Издательство 2009 2 УДК ББК В Всемирный антидопинговый кодекс 2009: Всемирное антидопинговое агентство. Пер. с англ. И.И. Гусева, А.А. Деревоедов, Г.М. Родченков / Ред. А.А. Деревоедов.: – М.: Издательство., 2008.–.с. ISBN Всемирный антидопинговый кодекс был впервые принят в 2003 году и начал...»

«ИЗВЕСТИЯ ИНСТИТУТА НАСЛЕДИЯ БРОНИСЛАВА ПИЛСУДСКОГО № 17 Южно-Сахалинск 2013 1 Известия Института наследия БроУДК 390 (Р573) нислава Пилсудского. Институт наследия ББК 63.5 (2Р 55) Бронислава Пилсудского государственного бюджетного учреждения культуры Сахалинский областной краеведческий музей. № 17. Южно-Сахалинск: ГУП Сахалинская областная типография, 2013. 360 с., илл. РЕДАКЦИОННАЯ КОЛЛЕГИЯ: В. М. Латышев, М. М. Прокофьев, Т. П. Роон, А. Кучинский (Польша), А. Маевич (Польша), Б. С. Шостакович...»

«ия и содержание формы 10-апк годового отчета Понятие строение и структура счетов бух Учёта Их взаимосвязь с балансом Постельные принaдлежности-производство и продaжa Понятие организации, её цели и характерные черты Виды организации После 11 и халиса Понятия + и виды социального контроля Понятие и ридмет административного права Порнофото и видео старых учительниц с маленькими мальчиками Последствия для мужа после приворота и отворота от жены и детейПомощь целителя Поправка на контроль и...»

«И. А. Халий О. В. Аксенова В. В. Мельникова Социокультурные основания деятельности современных российских неправительственных организаций Электронный ресурс URL: http://www.civisbook.ru/files/File/inab_2010_01.pdf Перепечатка с сайта Института социологии РАН http://www.isras.ru/ УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ СОЦИОЛОГИИ РАН Информационно-аналитический бюллетень ИНАБ № 1 — 2010 СОЦИОКУЛЬТУРНЫЕ ОСНОВАНИЯ ДЕЯТЕЛЬНОСТИ СОВРЕМЕННЫХ РОССИЙСКИХ НЕПРАВИТЕЛЬСТВЕННЫХ ОРГАНИЗАЦИЙ Москва —...»

«Линь Хоушен, Ло Пэйюй Секреты китайской медицины. 300 вопросов о цигун. Издание второе, переработанное и дополненное. Новосибирск,Наука, Сибирская издательская фирма РАН, 1995. Заказ № 251 Перевод с китайского. ISBN 5-02-030907-9 Отсканировал Владимир Яковенко (2:5020/368.77) Откорректировал Алексей Ширшин (2:5061/101.500) html-верстка: Игорь ig2@tut.by ОГЛАВЛЕНИЕ Исторический очерк и основные понятия. 1Что называется цигуном. 2Как зародился цигун. 3Откуда пришло название цигун. 4Какие записи о...»














 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

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