Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1. Методы минимизации булевых функций
Под минимизацией в данном случае понимается такое упрощение формулы, выражающую данную функцию, при котором в нее входит минимальное число литералов, либо ее отрицание.
1) Правило «склеивания»
2) Метод неопределенных коэффициентов
Рассмотрим функцию 3-х переменных:
Рассмотрим конкретную функцию. В данной формуле при всевозможных значениях неопределенных коэффициентов k(каждый из которых сам по себе может принимать значения только 0 или 1) содержится всевозможные функции трех переменных. Задача состоит в том, чтобы выбрать значения коэффициентов k. Чтобы для данной функции получить выражение, содержащее минимальное число литералов.
Получим сначала систему уравнений для определения этих коэффициентов.
Коэффициенты, которые входят в 5,6,7 уравнения все равны 0 по свойству дизъюнкции. Поэтому:
Эти коэффициенты входят также и в другие уравнения, как слагаемые. Поэтому их можно убрать, убрав их получим упрощенную систему:
Решение системы (выкинув все коэффициенты найти максимально входящий во все уравнения):
3) Метод карт Карно.
Один из методов автоматического поиска минитерм, которые можно склеить. Карты Карно – это особым образом зарисованная таблица функции.
Карты Карно функции трех переменных:
|
f . |
|||
|
0 0 0 0 1 1 1 1 |
0 0 1 1 0 0 1 1 |
0 1 0 1 0 1 0 1 |
0 1 0 1 1 0 1 1 |
Карты 4 функции переменных:
Карты Карно для не полностью определенных функций.
В практике использования булевых функций бывает случай, когда некоторые значения аргументов физически не реализуются, такие функции называются не полностью определенными. При их минимизации используется следующий прием: в таблице соотношений на месте не реализуемого набора аргументов ставится специальный символ (*) и при реализации той или иной минимизации, вместо * считается 1 или 0, который выгоден.
4) Метод Квайна
Предполагает, что минимизируемая функция записана в виде СДНФ. Каждую конъюнкцию, которая входит в СДНФ , будем называть минитермой ранга n.
1. Этап. Нахождение первичных импликант.
Сравнивая попарно минитермы четвертого ранга, склеиваем те пары, которые можно склеить. Все первичные импликанты будут со «*».
Отмеченные «*» - минитермы не должны входить в минимальное представление функции, т.к. их вклад в наборы единиц функций учтен минитермами более низкого ранга, полученного в результате склеивания с участием этой минитермы. Те же минитермы, которые не отмечены «*», могут войти в минимальное представление функции. Минитермы, не отмеченные звездочками будут называться первичными импликантами.
Выпишем отдельно эти первичные импликанты.
2. Этап. Составление таблицы и расстановка меток.
|
\конституэнты Минтермы\ |
0011 |
0100 |
0101 |
0111 |
1001 |
1011 |
1100 |
1101 |
|
0*11 |
|
|
||||||
|
*011 |
|
|
||||||
|
01*1 |
|
|
||||||
|
10*1 |
|
|
||||||
|
1*01 |
|
|
||||||
|
*10* |
|
|
|
|
3. Этап. Нахождение существенных импликант.
4. Этап. Вычеркивание столбцов.
После 3 этапа в таблице могут оказаться столбцы, в которых имеются метки в одинаковых строках. Все такие столбцы, кроме одного надо вычеркнуть.
5. Этап. Если после выбрасывания некоторых столбцов в таблице появятся строки, в которых нет ни одной метки, то соответствующие строки этих меток надо вычеркнуть, исключив, таким образом, соответствующие им импликанты из дальнейшего рассмотрения.
6. Этап. Выбор минимального покрытия.
Нужно выбрать строки с минимальным количеством литералов. Исследуя таблицу, выберем совокупность первичных импликант, которая, во-первых, включала метки во всех столбцах и, во-вторых, содержала минимальное число литералов.
В нашем случае это импликанта из 1-й и 4-й строк. На предыдущих этапах выделим одну импликанту.
5) Модификация метода Мак-Класки
Если минитермы записать с помощью 0 и 1, наша задача: 0011,0100,0101,0111,1001,1011,1100,1101.
Склеиваются минитермы, коды которых отличаются на единицу, поэтому перебор упрощается.
1го веса: 0100*;
2го веса: 0011*,0101*,1001*,1100*;
3го веса: 0111*,1011*,1101*.
010*,*100,0*11,*011,01*1,*101,10*1,1*01,110*.
1 вес 010*,*100
2 вес 0*11,*011,01*1,*101,10*1,1*01,110*
*10*
Далее по методу Квайна.
2.Понятие управляющего автомата
Многие дискретные информационные процессы, а также некоторые дискретные системы управления описываются в рамках теории конечных автоматов.
В общем случае выходные переменные какой-либо системы управления могут зависеть от значений входных переменных не только в данный момент времени, но и от их предыдущих значений. Другими словами некоторые системы управления обладают памятью, т.е. их поведение зависит не только от входного воздействия в заданный момент времени, но и от предыдущих значений. Такие системы управления называются динамическими. Для учета предыстории развития системы в текущий момент времени в рассмотрение вводится один или несколько внутренних параметров, называемых состоянием системы или процесса.
Понятие состояния может быть определено из той роли, которую оно играет в определении основной модели конечного автомата, а именно:
-выходной символ конечного автомата в данный момент времени однозначно определяется входным символом и состоянием в данный момент
-состояние в следующий момент времени зависит от входного символа и состояния в настоящий момент времени.
Другими словами, состояние – такая переменная, которая совместно дает возможность описать работу конечного автомата.
Конечный автомат – модель наиболее простой динамической системы устройства работ в дискретном времени. Это система следующего вида.
S={A,Q,V,σ,λ}, где А – алфавит входных сигналов, Q – алфавит состояний, V – выходной алфавит, σ-функция выходов, она определена на QxA→V, т.е. σ(q,a)=v ,λ- функция перехода состояний QxA→Q, т.е. λ(q,a)=q’.
Выше описан автомат Мили.
Для автомата Мура σ(q)=v.
Несмотря на то, что автомат Мура - частный случай автомата Мили их возможности одинаковы.
Наиболее распространенной на практике является модель Мили, так как в модели Мура необходимо прогнозировать поведение входных воздействий и количество различный состояний, необходимых для описания автомата, значительно больше.
Автомат для синхронных автоматов живет в дискретном времени. Т.е. имеют дело с тактами – последовательностью моментов времени, в которые приходят входные сигналы. Происходит мгновенный переход в новое состояние и на выход подается сигнал.
σ(qν,aν)=v, λ(qν,aν)=qν+1, где ν-такт времени.
Реализация автоматов.
Закодируем каждый символ A,q,v двоичными кодами. Это позволит каждую из функций представить как совокупность булевских функций. Для того чтобы учесть новые состояния, которые потребуются на следующем такте необходимо ввести задерживающий элемент Д. Схематически конечный автомат можно представить:
Этапы:
- построить таблицу переходов автомата
- все входные символы и состояния перевести в двоичную систему исчисления
- используя таблицу двоичных значений, записать полиномы булевских функций в совершенно нормальной дизъюнктивной или конъюнктивной форме
- синтезировать модель конечного автомата
3.Способы описания управляющих автоматов
Работа конечного автомата может быть описана различными способами: матричный, графовый, с использованием таблицы переходов.
Наиболее распространенным является способ таблицы переходов.
|
λ |
а1 |
а2 |
а3 |
|
q1 |
q3ν1 |
q3ν2 |
q2ν1 |
|
q2 |
q4ν1 |
q1ν1 |
q1ν1 |
|
q3 |
q2ν1 |
q3ν1 |
q3ν2 |
|
q4 |
q4ν1 |
q2ν1 |
q1ν2 |
Например.
Пусть А={a1,a2}={0,1}
|
λ |
а1 |
а2 |
|
q1 |
q2 |
q3 |
|
q2 |
q3 |
q3 |
|
q3 |
q1 |
q2 |
Q={q1,q2,q3}={00,01,10}
V={v1,v2}={0,1}
Зададим таблицу автомата:
Реализуем две функции для двух разрядов нового состояния: для первого разряда q’ ν+1=f(x1, x2, x3)=f(q’ ν,q’’ ν,a ν).
|
q’ ν |
q’’ ν |
a |
q’ ν+1 |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
* |
|
1 |
1 |
1 |
* |
Заполнение q’ ν+1 : смотрим на по совокупности значений q’ν и q’’ν из Q= {00,01,10} сопоставляем соответствующую пару значений соответствующему состоянию qi . Также сопоставив значение из столбца а алфавиту А={0,1} определяем соответствующий входной символ ai. Определив qi и ai обращаемся к таблице автомата, откуда на пересечении столбца и строки определяем следующее состояние qj. Исходя из этого состояния определяем его представление в булевской кодировке из Q={00,01,10}. Поскольку идет расчет для первого разряда, то в столбец q’ ν+1 записываем только первый символ из двух.
Далее, стараемся минимизировать булевскую функцию из таблицы (q’ ν+1), например, с помощью карт Карно.
Откуда, q’ ν+1= q’’ν v⌐ q’ν a ν .
Аналогичным образом для второго разряда получаем:
|
q’ ν |
q’’ ν |
a |
q’’ ν+1 |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
* |
|
1 |
1 |
1 |
* |
Откуда, q’’ ν+1= q’ν a ν v⌐ q’ν ⌐ q’’ν ⌐ a ν .
4.Основные понятия теории графов
Пусть имеется некоторое множество,и на этом множестве, как на базовом, задано бинарное отношение , V – множество вершин, Г – множество бинарных отношений, G - граф.
Граф – множество вершин и отношения, заданные на нем.
Ориентированный граф
Если имеется пара (дуга) (Vi,Vj), будем говорить, что она исходит из Vi и заходит в Vj.
(Vi, Vi) – петля.
Если бинарное отношение симметрично, то нет смысла рисовать обе дуги, а следует оставить одну, но не ставить стрелки. Такой граф называется не ориентированным, в этом случае вместо «дуги» говорят «ребро». Если две вершины связаны ребром или дугой, то они называются смежными.
Способы задания графов
Поскольку графы соответствуют бинарным отношениям, то способ задания у них аналогичен. Графическое изображение графа естественно. Графический граф представляется только тогда, когда он имеет небольшую размерность, иначе теряется наглядность.
Матричное задание графов
Существует два вида матриц, с помощью которых задаются графы – это матрицы смежности и инцидентности.
Можно задать матрицу смежности относительно дуг, но при этом матрица будет большей размерности. Смежными дуги считаются тогда, когда первая дуга заканчивается на той вершине, где начинается вторая дуга – пара.
Матрица инцидентности – это матрица отношения между вершинами и дугами (-1 – входит дуга в; 1 – выходит дуга из):
Подграфы
В графе необходимо выделить некоторые подграфы. Подграф, порожденный подмножеством вершин – это часть исходного графа, в котором оставлены только те дуги, которые соединяют вершины заданного подмножества вершин. Аналогично можно строить подграфы, порожденные заданным подмножеством дуг.
Назовем направленным путем в графе подмножество дуг
Путем называется направленный путь, в котором нарушена конфигурация.
Направленный путь называется простым, если ни одна вершина в нем не повторяется, т.к. у простого пути не могут повторяться дуги.
Направленный путь называется направленным контуром, если первая и последняя вершины пути совпадают.
Контур называется простым, если в нем нет повторяющихся вершин.
Если граф не ориентированный, то вместо пути говорят цепь, а вместо контура говорят цикл.
Достижимость
Вершина Vj называется достижимой из вершины Vi, если существует направленный путь из вершины Vi в вершину Vj. Вершина Vi называется контрдостижимой из вершины Vj, если существует направленный путь из вершины Vj в вершину Vi.
Обозначим через сам граф.– множество вершин графа, которые достижимы из вершины Vi с помощью путей длиной в одну дугу (это вершины, смежные с вершиной Vi). Тогда через назовем множество дуг, которые достижимы из вершины Vi с помощью путей в две дуги. – множество путей, достижимых путями длинной n. Тогда множество вершин, достижимых из вершины Vi будут являться объединением всех множеств, т.е.:
– множество вершин достижимости из вершины Vi может не совпадать с множеством всех вершин графа, т.е. в графе могут быть такие вершины, которые недостижимы. На практике часто возникает задача определения множества .
Множество (1) называется транзитивным замыканием вершины Vi.
Может быть поставлена задача нахождения множества вершин контрдостижимых из вершины Vi. Это обратное транзитивное замыкание вершины Vi.
– множество вершин контрдостижимых из вершины Vi путями длинны в k дуг. Задачу достижимости можно записать с помощью задачи понятия матрицы смежности. Введем понятие матрицы достижимости R.
Теорема: Матрицы R и Q можно найти по следующей формуле: , где k и l – min степень матрицы А, которая при дальнейшем увеличении степени результат повторяется.
Здесь это m-ная степень матрицы бинарного отношения, соответствующего данному графу (обратного бинарного отношения).
Замечание 1: При возведении матрицу в некоторую степень мы используем умножение по правилу матричного произведения, но арифметическое умножение и сложение заменяем булевым.
Замечание 2: Сформулированная теорема следует из определения и соответствию между графами и бинарными отношениями (изоморфизм).
Замечание 3: Матрица А-1 – транспонированная матрица к смежности А – матрица смежности обратного графа.
Пример
Связность
Ориентированный граф называется связным, если две любые вершины графа Vi и Vj соединены, по крайней мере, одним направленным путем из Vi в Vj и любым направленным путем из Vj в Vi.
Сильносвязный граф – если две вершины графа Vi и Vj соединены по крайней мере одним направленным путем из Vi в Vj и хотя бы 1 направленным путем из Vi в Vj.
Взаимодостижимость
Две вершины Vi и Vj называются взаимодостижимыми, если rij=1 и qij=1, поэтому можно ввести обозначение матрицы взаимодостижимости hij=rij qij.
hij=1, вершины Vi и Vj взаимодостижимы и равняются нулю в противном случае.
Очевидно, мы получаем отношение взаимодостижимости между вершинами графа. Это отношение:
1. Рефлексивно, т.к. каждая вершина взаинодостижима сама с собой.
2. Симметрично – взаимодостижимо
3. Транзитивно:
Если отношение рефлексивно, симметрично и транзитивно, то это отношение эквивалентности. Следовательно, множество всех вершин графа разбивается на непересекающиеся классы взаимодостижимых вершин.
Пример
1 класс: V7
2 класс:V6,V5
3 класс:V1,V2,V3,V4
Каждый из этих трех классов выделяет три подграфа, каждый из которых является сильно связанным. Подобные задачи решаются построением матрицы h и выделением в ней блочных диагональных матриц, каждая из которых целиком состоит из единиц.
Деревья
Неориентированный граф называется деревом, если он связан и не имеет циклов.
Докажем следующие факты:
В дереве между любыми двумя вершинами существует единственная соединяющая их цепь.
Доказательство:
Существование следует из связанности цикла. Единственность доказываем от противного, предполагая, по крайней мере, две цепи, т.е. образуется цикл, что противоречит условию.
Дерево содержит n вершин и имеет n-1 ребро.
Доказательство:
Берем дерево с n-1 вершинами, выбрасываем из него одну дугу, получим два дерева. Выбрасываем в одном из них одну дугу, получаем три дерева. Когда мы выбросим n-1 дугу, мы получим, n деревьев, содержащих одну вершину.
Дерево, являющееся подграфом графа и содержащее все его вершины, называется покрывающим деревом данного графа.
Ориентированный граф называется деревом, если он связан, не имеет циклов, и для любой вершины этого графа существует единственный путь между особой выделенной вершиной (корнем дерева) и данной вершиной.
Оптимизация на графах
Взвешенный граф – это граф, каждой дуге (или вершине, или и вершине и дуге) ставится в соответствие некоторое число.
1. Задача нахождения покрывающего дерева с минимальной суммой весов дуг.
В данном случае рассматривается граф с взвешенными дугами. Покрывающее дерево этого графа с указанными свойствами будет называться минимальным покрывающим деревом.
Алгоритм Краскала(алгоритм из разряда жадных)
Составляется список ребер в порядке увеличения весов ребер. Затем осуществляется вычеркивание ребер, начиная с ребра, имеющего минимальное значение. Если очередное выбранное ребро приводит к образованию цикла, то его отбрасывают. После выбора n-1 процесс завершается успешно.
Медиана
Существует широкий класс задач, связанных с оптимальным размещением в сети обслуживания определенных центров. Многие такие задачи решаются с помощью задачи нахождения особой вершины – медианы.
Для решения этой задачи необходимо сначала определить кратчайшее расстояние в графе от каждой вершины I к каждой вершине k. (p(i-k)).
Далее для каждой вершины обозначим кратчайшее расстояние от всех вершин до данной и назовем его внешнепередаточным числом этой вершины . qk – вес каждой k-вершины.
Внешняя медиана – такая вершина, для которой внешнее передаточное число минимально.
Номер медианы:
Внешняя медиана Vi0.
Вершина, в которой минимально внутренне число.
Медиана – вершина, для которой сумма внешнего и внутреннего чисел минимальна.
5.Алгоритм Дейкстры
Задача о поиске путей с минимальным значением в ориентированных графах. Значением или весом пути называется сумма значений или весов дуг образующих данный путь. Обозначим конечный путь из Vs вершины в Vt конечную (s, t) – путь. Для каждой пары вершин может быть несколько таких путей.
Минимальный путь (s, t) – путь, значение которого минимально. Вес или значение дуг в графе удобно задавать с помощью матрицы Pij – вес дуги (Vi - Vj). Если дуга из Vi в Vj отсутствует, то pij – бесконечно большое. Необходимо таким образом при заданной конфигурации графа и матрицы Р для двух вершин Vs и Vt найти (s, t) путь минимальной длины.
Алгоритм Дейкстры состоит в следующем:
- в процессе построения минимального пути мы будем помечать вершины, и присваивать им некоторые значения (qi – значение вершины Vi).
- перебор начинаем с вершины Vs
- всем вершинам изначально ставим в соответствие ∞.
Шаг 1. Помечаем величину Vs, qs =0.
Шаг 2. i=S.
Шаг 3. Для каждой неотмеченной вершины Vj: вычисляем qj:=min(qi, qi+pij).
Шаг 4. Проверяем условие qj<∞. Если для любого j, qj =∞ процедура заканчивается, следовательно, пути из S в T не существует. Если существуют такие вершины Vj,что qj <∞, то отметим Vj, у которой это qj минимально и отмечена та дуга, по которой мы добрались в вершину Vj с получением этого минимального значения qj.
Шаг 5. Полагаем, i=j.
Шаг 6. Проверяем условие j=t. Если это условие выполняется, то путь St найден и длина пути L(s,t)=qj. Этот путь будет состоять из отмеченных ранее дуг. Если jt, то переходим к шагу 3.
Пример
1. Полагая, qs:=0; qj:=∞.
2. i:=S.
3. q1:=min(q1,qs+ps1)=2;
q2:=min(q2,qs+ps2)= ∞;
q3:=min(q3,qs+ps3)=3;
q4:=min(q4,qs+ps4)= ∞;
qt:=min(qt,qs+pst)= ∞.
4. q1:=2;
q2:=3.
5. i:=1.
3. q2:=min(q2,q1+p12)= 2+5=7;
q3:=min(q3,q1+p13)=3;
q4:=min(q4,q1+p14)= 2+4=6;
qt:=min(qt,q1+p1t)= ∞.
4. q3=3.
5. i:=3.
3. q2:=min(q2,q3+p32)= ∞;
q4:=min(q4,q3+p34)= ∞;
qt:=min(qt,q3+p3t)= ∞.
4. q4:=6.
5. i:=4.
3. q2:=min(q2,q4+p42)= 7;
qt:=min(qt,q4+p4t)= 11;
qt:=min(qt,q2+p2t)= 8.
4. q2:=7.
5. i:=2.
Найден кратчайший путь из вершины Vs в Vt. Значение пути =8 и он образован ветвями Vs, V1; V1, V2; V2, Vt. Найден кратчайший путь до всех вершин графа, построено дерево, образованное кратчайшими путями.
Исключение: алгоритм мог образоваться до того, как мы выделили все вершины, оборваться, когда дошли до конечной вершины Vt.
Замечание:
Может стоять задача определить кратчайшее расстояние между заданной вершиной и всеми остальными, при этом, можно пользоваться тем же алгоритмом, за исключением правила остановки, в данном случае она произойдет, когда отмечены все вершины.