Метод простых итераций Якоби.

Правило сложения

Если некот объект х можно выбр n1 способами, а объект у можно выбр n2 способами, причем первые и вторые выборы таковы, что они взаимно искл друг друга и не могут быть получены одновременно, то объект хUу (х или у) можно выбр n1+n2 способами.

Пример: Четыре города M,N,P,K соединены дорогами так, что из M в N ведут 5дорог, из N в K – 6 дорог, из M в P ведут 4 дороги, из P в К – 3 дороги.

Сколькими способами можно проехать из М в К?

Решение: Из М в К через N ведут 5*6=30 дорог, Из М в К через P ведут 4*3=12 дорог

Из М в К ведут 30+12=42 дороги.

 

2. Размещения, перестановки, сочетания.

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

Если элементы комбинации не повторяются.

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

Размещения с повторениями обозначаются Ã и вычисляются по формуле:

Примеры в 1ом вопросе!

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

Пример: Имеется 5 равных геом фигур: 3 желтых и 2 белых круга. Сколько различных узоров можно составить из этих кругов, располагая их в ряд?

Решение: Желтые круги будут повт 2! раз

Белые - 3! раз

Число разл узоров будет равно 5!/2!*3!=10

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

Где

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

Пример: Сколькими способами можно выбрать 3 представителей учебной группы в студ совет, если в группе 25чел.

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

Обозначается – Č и вычисл по форм:

 

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

Бином Ньютона – это формула, представляющая выражение в виде многочлена.

Она имеет вид:

Её можно записать иначе:

, где - число сочетаний из n элементов по k,

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

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

Любой элемент треугольника паскаля, распол в n-ой строке на k-ом месте выражает ,

Где отчет n ведется от 1, а отчет k ведется от 0.

Пример: Представить в виде многочлена

Решение:

 

4. Булевы функции. Определение. Примеры.

Алгебра логики, выстроенная в XIX веке, долго существовала как абстрактная, хотя и очень красивая наука. Но в середине XX века оказалось, что она имеет конкретное и очень важное применение в современной жизни. Булева алгебра в настоящее время служит основой для описания логики работы аппаратных и программных средств ЭВМ. Она ис­пользует логические переменные, которые принимают лишь два значения 0 и 1. Аналогично и ЭВМ использует лишь сигналы 0 и 1, воспринимая их как логические переменные.

Рассмотрим множество В = {0;1}.

Тогда В² = {(0;0),(0;1),(1;0),(1;1). Снимем разделительный к внутри каждой пары и уберём скобки. Тогда В² = {00, 01,10,11}. Аналогично В³ = Вх В² ={000,001,010,011,100,101,110,111} и т. д.,

Каждому элементу множества Вⁿ поставим в соответствие единст­венный элемент множества В - {0; 1}. Полученное соответствие наз булевой функцией. Элементы множества Вⁿ являются значениями аргумента булевой функции. Они представляют собой наборы, состоящие из нулей и единиц, и называются кортежами. Длиной кортежа назы­вается число цифр, образующих кортеж. Множество Вⁿ - область определения функции

Множества значений булевой функции, вообще говоря это значение функции В = {0;1}.

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

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

Область определения D(f) булевой функции n = 1 это совокупность двух точек 0 и 1 числовой прямой, т.е. одномерного куба

Если п = 2, то D(f) = {00,01,10,11}- это множество вершин квадрата, т. е. двухмерного куба

Если п = 3, то D(f) = {000,001,010,01 1,100,101,110,111}

множество вершин трёхмерного куба в декартовой системе координат.

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

Если n=1, то число простейших булевых функций равно 4, если n=2, то их 16, если n=3, то их 256

Если n=1, то существует 4 простейших булевых функций:

- константа 0(тождественный 0)

- константа 1(тождественная 1)

- тождественная функция

- отрицание

 

5. Реализация булевых функций формулами.

 

, - отрицание

- конъюнкция (логическое умножение)

- дизъюнкция

- импликация

- отрицание импликации

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

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

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

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

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

Самой старшей считается «отрицание»

Затем – «конъюнкция», «штрих Шеффера», «стрелка Пирса»

Затем – «дизъюнкция»

Затем – «импликация»

На самом низком уровне – эквиваленция и сумма по модулю 2.

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

Итак, стрелка Пирса равна антидизъюнкции, штрих Шеффера равен антиконъюнкции.

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

 

 

6. Совершенная конъюнктивная нормальная форма.

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

Пример

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

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

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

Если каждая входящая в КНФ элементарная дизъюнкция является полной относительно набора , то КНФ называется совершенно конъюнктивной нормальной формой (СКНФ)

Пример:

Любую булеву функцию , не равную тождественной единице, можно представить в виде СКНФ.

Получить СКНФ можно преобразовывая формулы, а можно по таблице истинности.

 

7. Совершенная дизъюнктивная нормальная форма.

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

Пример

Одна третья конъюнкции является полной элементарной.

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

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

Если каждая входящая в ДНФ элементарная конъюнкция является полной относительно набора , то ДНФ называется совершенно дизъюнктивной нормальной формой (СДНФ)

Пример:

Получить СДНФ можно преобразовывая формулы, а можно по таблице истинности.

 

 

8. Переключательные функции. Способы задания.

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

Основы перекл функций заложил англ матем Дж.Буль в 19 веке.

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

Отсутствие сигнала как на входе, так и на выходе будет сигнализировать 0, наличие – 1.

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

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

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

Областью определения переключательной функции от n переменных является множество из 2n двоичных наборов. Для того чтобы задать переключательную функцию, нужно указать соответствие между этими наборами и значениями функции. Такое соответствие проще всего описать с помощью таблицы, число строк в которой определяется числом наборов, а число столбцов на единицу больше числа переменных. Пример такой формы задания функции приведен в табл. 2.1. Обозначим множество переключательных функций, зависящих от n аргументов: Pn = {?i(x1, x2,..., xn)} и найдем число элементов этого множества |P(n)|, т. е. число различных переключательных функций от n аргументов. В случае табличного задания столбцы значений различных функций должны иметь различие хотя бы в одной строке. Следовательно, для того чтобы найти число различных функций n переменных, нужно подсчитать какое количество различных столбцов значений может быть в таблице, имеющей 2n строк. Если каждую позицию в столбце считать двоичной переменной, то задача сводится к определению числа наборов для 2n переменных.Исходя из этого, получаем, что

|P(n)| = 22n

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

 

9. Переключательные функции от 2-х и п переменных.

Переключательные функции от 2х переменных – это булевы функции двух переменных.

Для n - логических переменных (аргументов) существует 2n (2 в степени n) их комбинаций или двоичных наборов. На каждом таком наборе может быть определено значение функции 0 или 1. Если значения функции отличаются хотя бы на одном наборе, функции - разные. Общее число переключательных функций (ПФ) от n аргументов равно N=2(2n). Для n=2, N=16. При n=3, N=256 и далее очень быстро растет. Практическое значение имеют 16 функций от 2-х переменных, т.к. любое сложное выражение можно рассматривать как композицию из простейших.

Переключательные функции двух аргументов.

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

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

 

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

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

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

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

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

Заметим, что в силу законов де Моргана:

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

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

Итак, примеры функциональных систем:

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

 

 

11. Специальные разложения переключательных функций.

Любую перекл функцию кроме тожд нуля можно представить в виде СДНФ. А в свою очередь, любую функцию, представленную в виде СДНФ, можно представить с помощью суммы по модулю 2, конъюнкции и константы 1. Т.е. любую перекл функцию можно представить с помощью функций: сумма по модулю 2, конъюнкция и константы 1. Отсюда следует, что система функций явл полной.

Более того эта система является еще и базисом.

Базис называется системой Жегалкина.

Теорема.Каждая перекл функция единственным образом допускает представление в виде полинома Жегалкина.

Пример: . Представим эту функцию в виде полинома Жегалкина.

Решение

 

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

 

 

12. Классы Поста. Теорема о функциональной полноте.

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

Существуют 5 классов перекл функций. Это классы Поста (Пост – Америк логик 20 века.

1. Класс линейных функций

Перекл функция назыв линейной, если она представима полиномом Жегалкина первой степени:

Число линейных функций рано например при n=2 число линейных функций равно 8:

2. Класс функций, сохраняющих 0

Если перекл функция на кортеже 00…0 равна нулю, то говорят, что функция сохран нуль

Т.о. функция принадлежит классу функций, сохраняющих 0, если

Для 2х переменных таких функций 8.

3. Класс функций, сохраняющих 1

Если перекл функция на кортеже 11…1 равна 1, то говорят, что функция сохран единицу

Т.о. функция принадлежит классу функций, сохраняющих 1, если

Для 2х переменных таких функций 8

4. Класс монотонных функций

- монотонная функция

Таких функций 6

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

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

На кортежах 00 и 11,01,10 противоположные значения могут иметь функции

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

-хотя бы одну функцию, не сохраняющую 1

-хотя бы одну функцию, не явл линейной

-хотя бы одну функцию, не явл монотонной

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

Каждый базис содержит не более 4х булевых функций.

 

13. Минимизация переключательных функций. Основные понятия,

 

14. Способы построения минимальных ДНФ.

Минимизация ДНФ включает следующие этапы:

1. Получение простых импликант и сокращенной ДНФ
2. Получение тупиковой ДНФ
3. Выбор из тупиковых ДНФ минимальной

Для реализации первого этапа алгоритма будем применять один из след методов: Метод Квайна, геометрический, карты Карно

Метод Квайна

В его основе лежат следующие равносильности:

1. Полного склеивания

2. Поглощения

3. Не полного склеивания

Если в СДНФ провести все операции неполного склеивания (тем самым усложнив СДНФ), а затем провести операции поглощения, то получится сокращенная ДНФ.

 

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

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

Суть метода: 1) для функции n переменных отмечаются вершины куба, соответств кортежам, на которых функция принимает значение 1.

2) проводят склеивание – отмечают ребра, содерж 2 отмеч вершины.

3) проводят поглощение – отмечают грани, содерж все 4 склеенные вершины.

Цель действий – накрыть множество, всех отмеченных вершин, как можно меньшим числом граней, ребер.

 

 

Карты Карно

Могут быть использованы для минимизации булевой функции любого числа переменных. Но наиболее удобно использовать его, если n=3 или n=4

Переменные кортежа разбиваются на 2 части. Первая часть является кодом столбца, вторах – строк. Таким образом, карты Карно неявно задают сами кортежи.

Например:

 

х3	х1х2

 

Процесс минимизации СДНФ представляет собой склеивание кодов кортежей для каждого сплошного участка причем колво единиц на таком сплошном участке должно быть степенью числа 2.

 

 

15. Понятие графа. Виды графов. Изоморфизм.

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

Графом G называется совокупность 2х конечных множеств V(множество вершин) и E(множество ребер), между элементами которых определено отношение инцидентности. Каждое ребро инцидентно 2м вершинам, которое оно соединяет.

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

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

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

Ребро, концевые вершины которого совпадают, называют петлей.

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

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

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

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

 

 

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

В общем виде «задать граф» означает: описать множество его вершин и ребер, а также отношение инцидентности.

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

1. Графический

2. Перечислением вершин и ребер.

3. Задание графа матрицей инцидентности. Строки матрицы характеризуют вершины графа, столбцы – ребра графа.

Для неориентир графа: 1 – если вершина и ребро инцидентны, 0 – если не инциндентна.

Для ориентир - -1 если вершина является началом ребра, 1 – если концом ребра, 0 – не инциндентны, 2 – ребро – петля.

4. Задание графа матрицей смежности.

Матрица смежности – это квадратная матрица размера n*n, которая по горизонтали и по вертикали учитывает все вершины графа.

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

5. Задание графа матрицей весов.

Матрица весов - вариант матрицы смежности для взвешенного графа, представляет собой квадратную матрицу размером n n (n - число вершин), (i,j)-й элемент которой равен весу ребра / дуги (v, v), если таковое имеется в графе; в противном случае (i,j)-й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи.

 

17. Маршруты и циклы. Связность.

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

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

Маршрут называется замкнутым, если . Незамкнутым - если

Маршрут, в котором нет повторений ребер, называется цепью. Замкнутая цепь называется циклом. Цепь, все вершины различны, кроме, может быть её концов, называется простой. Замкнутая простая цепь называется простым циклом и обозначается , где р – число вершин.

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

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

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

Две вершины называются связными, если их соединяет хотя бы одна простая цепь.

Отношение связности – это отношение эквивалентности.

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

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

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

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

 

 

18. Эйлеровы и гамильтоновы графы.

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

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

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

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

Если в простом графе G(V,E) с p вершинами степень любой вершины v удовлетворяет неравенству p(v)≥p/2

 

 

19. Планарные графы. Теорема Понтрягина-Куратовского.

Все графы, изоморфные другому, несут одну и ту же информацию, но их изображение может быть различным.

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

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

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

Очевидно, что 1) всякий подграф планарного графа планарен.

2) граф планарен, тогда и только тогда, если каждая связная компонента этого графа – планарный граф.

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

Теорема Понтрягина-Куратовского.

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К₅ или К_3.3

 

 

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

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

n-m+p=2, где n-число вершин, m – ребер, p-граней.

Следствие: Если в простом связном плоском графе n≥3, то m≤3n-6

Формулой Эйлера удобно пользоваться при исследовании графа на планарность.

 

 

21. Раскраска графов.

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

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

Хроматическим числом элементов (вершин, рёбер или граней) графа рыпается минимальное число цветов для раскраски элементов графа.

В конце XIX века была сформулирована гипотеза четырёх красок: всякий планарный граф 4-раскрашиваем. Попытки доказать эту гипотезу привели к следующей теореме: ВСЯКИЙ ПЛАНАРНЫЙ ГРАФ 5-РАСКРАШИВАЕМ.

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

 

 

22. Деревья. Минимальное остовное дерево.

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

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

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

Следовательно, деревья являются компонентами леса.

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

Если дерево имеет п вершин, то оно имеет п-1 ребро

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

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

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

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

Граф может иметь несколько остовов.

Обратим внимание, что ВСЕ ОСТОВЫ одного графа имеют ОДИНАКОВОЕ ЧИСЛО РЁБЕР, НО ИХ ВЕС НИ ЯВЛЯЕТСЯ Величиной ПОСТОЯННОЙ ДЛЯ ДАННОГО ГРАФА, ЗАВИСИТ ОТ ВЕСОВ ВЫЬРАнНЫХ ребер.

 

 

23. Жадный алгоритм.

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

Один из эффективных способов решения поставленной задачи —реш ение с помощью алгоритма Краскала или «жадного алгоритма».

Жадный алгоритм:

1. Необходимо упорядочить множество весов
2. выбрать ребро наименьшего веса и инцидентные ему вершины и включит их в остовное дерево.
3. Исключить выбранное ребро из списка рёбер
4. повторяем шаг 2 и3 пока не построим все вершины
5. посчитать все полученного остовного дерева.

 

 

24. Алгоритм Прима.

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

Один из эффективных способов решения поставленной задачи —решение с помощью алгоритма Краскала или «жадного алгоритма».

Алгоритм Прима или, как его ещё называют, алгоритм ближайшего соседа.

Анализируем матрицу весов. Начинаем с произвольной вершины v_i

Шаг 1. Изучая i-ю строку матрицы весов, выбираем ребро, инцидентное v_i и имеющее наименьший вес. Выбранное ребро ( v_i v_j- первое ребро остова. Удаляем его из матрицы весов.

Шаг 2. Изучая i-ю и.j-ю строки матрицы весов, выбираем ребро минмального веса, инцидентное одной из двух вершин. Присоединяем выбранное ребро к остову и удаляем из матрицы весов.

И так далее. Процесс повторяется до тех пор, пока в остов не будут включены все вершины графа.

 

 

25. Алгоритм Дейкстры.

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

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

 

 

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

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

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

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

Функция φ, определенная на множестве дуг сети, называется допустимым потоком, если:

1. для любой дуги e_i выполнено условие 0≤φ≤с(e_i)

т.е. для любой дуги допустимый поток не превышает её пропускной способности.

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

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

Дуга e_i называется насыщенной, если (если допустимый поток равен пропускной способностью)

Суммарный поток, вытекающий из источника, равен суммарному потоку, втекающему в сток. Этот поток будем называть потоком в сети.

 

27. Полный и максимальный потоки в сети.

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

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

Разрезом L сети G(V,E) называется множество насыщенных дуг, отделяющих источник s от стока t.

 

28. Минимальный разрез. Способы нахождения максимального потока в сети.

Разрезом L сети G(V,E) называется множество насыщенных дуг, отделяющих источник s от стока t.

Минимальный разрез – разрез с минимальной пропускной способностью.

Теорема Форда – Фалкерсона (1955). Максимальный поток между вершинами t и s равен величине минимального сечения между этими вершинами.

Из теоремы вытекает один из способов нахождения максимального потока в сети:

1. Построить все разрезы графа
2. найти пропускные способности всех разрезов
3. выбрать минимальную пропускную способность разреза(ей соответствует минимальный разрез).
4. указать максимальный поток (он равен пропускной способности минимального разреза.

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

 

29. Понятие предиката. Кванторы.

Предикат (n-местный, или n-арный) — это функция с областью значений {0,1} (или «Истина» и «Ложь»), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M он характеризует либо как «истинную», либо как «ложную». тождественно-ложный и тождественно-истинным

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

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

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

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

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

Пример предикатов. Возьмём высказывания: ``Сократ - человек'', ``Платон - человек''. Оба эти высказывания выражают свойство ``быть человеком''. Таким образом, мы можем рассматривать предикат ``быть человеком'' и говорить, что он выполняется для Сократа и Платона.

В теории предикатов вводятся кванторы двух видов:

- квантор всеобщности

- квантор существования

Читается: - для любого х

- при всех х

- найдется значение х, для которого

- для некоторого х

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего упоминают квантор всеобщности (обозн-ие:А, читается: «для всех…», «для любого…» или «любой…») и квантор сущест-ия (обозн-е:Е, чит-ся: «существует…» или «найдется…»).

Переменную х в после навешивания квантора на предикат называют связанной переменной.

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

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

Так как квантор всеобщности, навешенный на предикат – обобщение конъюнкции, а квантор существования, навешенный на предикат – обобщение дизъюнкции:

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

 

 

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

В математической логике семантика изучает смысл, а синтаксис – форму формул и вывода (перехода от посылки к заключению).

Если интересуются только синтаксисом, то используют термин «формальная система» или «исчисление предикатов, высказываний»

Определение формулы логики высказываний:

1. Переменная есть атомарная (элементарная) формула
2. Если А и В – формулы, то , , , , - формулы

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

Синтаксис логики предикатов:

1. Алфавит. Разрешается использовать символы 4 типов: константы, переменные, функциональные символы, предикатные символы.
2. Термы.

Константа есть терм, переменная есть терм, если Р-n местный функциональный символ и t1, t2, ….tn – термы, то f(t1, t2, ….tn) – терм.

Никаких других терм нет.

3. Формулы

Если Р-n местный функциональный символ и t1, t2, ….tn – термы, то f(t1, t2, ….tn) – атомарная формула

Если А и В – формулы, то , , , , - формулы

Если х – свободная переменная, а F – формула, то ,

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

 

31. Предварённая нормальная форма. Процедура получения предварённой нормальной формы.

Предваренная нормальная форма(ПНФ) – это форма вида , где при любом натуральном I от 1 до n, - формула, не имеющая кванторов, с операциями конъюнкция, дизъюнкция, отрицание, причем - КНФ.

Процедура получения ПНФ:

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

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

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

• Найти самое левое вхождение предметной переменной такое, что это вхождение связано некоторым квантором и существует еще одно вхождение этой переменной
• Сделать замену связанного вхождения на вхождение новой переменной

Операцию повторять пока возможна замена связных переменных.

4. Вынести кванторы влево по законам алгебры логики

5. Преобразовать бескванторную формулу к виду КНФ.

6. Сформулировать ответ.

Формулу, не содержащую кванторов, называют матрицей формы.

 

32. Клаузальная нормальная форма.

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

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

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

Любая сколемовская форма допускает эквивалентную клаузальную форму.

 

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

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

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

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

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

Чаще всего имеется возможность эффективно выяснить, является ли данная формула аксиомой. В таком случае теория называется эффективно аксиоматизированной или аксиоматической.

Аксиоматическая систе6ма состоит из:

1. Множество символов, образ алфавит теории.
2. Множество формул, составленных из символов по синтаксическим правилам.
3. Подмножество формул, называемых аксиомами.
4. Множество правил вывода, с помощью которых и формул получают новые формулы.

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

Аксиомы делятся на 2 вида: логические и специфические.

Аксиомам соответствуют тождественно истинные высказывания.

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

 

 

34. Исчисление предикатов.

Рассмотрим аксиоматическую теорию исчисления предикатов:

1. Символы теории – это константы, переменные, функциональные символы, предикатные символы, термы, специальные символы:

2. Формулы

3. Схемы аксиом

4. Правила вывода:

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

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

Исчисление предикатов полно, но не разрешимо.

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

 

35. Метод резолюций.

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

Метод был предложен Дж. Робинсоном в 1965 году. Его основой является аксиоматическая теория первого порядка, которая обобщаеть доказательство от противного

1. Язык метода резолюций – язык дизъюнктов.
2. Аксиомы только собственные.
3. Правило вывода использует расширенный принцип силлогизма (дедуктивное логическое умозаключение) и унификацию и называется резолюцией.

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

Алгоритм метода резолюций:

Шаг 1. Принять отрицание заключения, т.е.

Шаг 2. привести все формулы посылок и к КНФ

Шаг 3. Выписать множество дизъюнктов всех посылок и шага 2.

Шаг 4. Проанализировать пары множества K по правилу:

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

Шаг 5. Если в результате соединения дизъюнктов образовалась пустая резольвента, то док-во завершено. В противном случае необходимо включить резольвенту в множество дизъюнктов К и вернуться к шагу 4, выбирая другую пару дизъюнктов.

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

Метод резолюций может быть формализован и положен в основу языка программирования. Наиболее известный язык такого типа – ПРОЛОГ (программирование с помощью логики)

 

 

36. Нечёткие множества и операции над ними.

Нечёткая логика и теория нечётких множеств — раздел математики, являющийся обобщением классической логики и теории множеств. Понятие нечёткой логики было впервые введено профессором Лютфи Заде в 1965 году. В этой статье понятие множества было расширено допущением, что функция принадлежности элемента к множеству может принимать любые значения в интервале [0...1], а не только 0 или 1. Такие множества были названы нечёткими. Также автором были предложены различные логические операции над нечёткими множествами и предложено понятие лингвистической переменной, в качестве значений которой выступают нечёткие множества.

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

Высотой нечеткого множества называется верхняя грань значений :

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

Операции:

Дополнением нечеткого множества А называется нечеткое множество с функцией принадлежности

Пересечение

Объединение

Содержание

Совпадение

Произведение

Сумма

---

<== предыдущая лекция | следующая лекция ==> Задания для выполнения расчетно-графической работы № 1 |

Поделиться с друзьями:

---

Дата добавления: 2017-03-18; Мы поможем в написании ваших работ!; просмотров: 286 | Нарушение авторских прав

---

Лучшие изречения:

© 2015-2024 lektsii.org - Контакты - Последнее добавление