uzluga.ru
добавить свой файл
БИЛЕТ#1

1. Множество: агрегатная и атрибутивная точки зрения на первичные понятия

теории множеств; способы задания


Агрегатная точка зрения рассматривает множество как набор вещей (по Кантору), а с атрибутивной точки зрения множеством считается свойство (атрибут) вещи. Символическая запись этих точек зрения следующая: хМ (х есть элемент множества М) хМ (х обладает свойством М).

Здесь х, М – исходные неопределяемые (первичные) понятия “элемент” и “множество” а отношение принадлежности (инцидентности) и предикации  относятся к первичным (неопределяемым) отношениям.


2. Основные свойства булевых операций алгебра логики


Совокупность подмножеств X, Y, Z, … некоторое множество М, имеющее наименьшее подмножество (нулевой элемент) О и наибольшее подмножество (наибольший элемент) 1, с тремя алгебраическими операциями: f12 (аддитивная операция ), f22 (мультипликативная операция) и f1 (унарная операция), удовлетворяющие аксиомам:

-коммутативности (для f12 и f22)

-ассоциативности (для f12 и f22)

-дистрибутивности (для f12 относительно f22 и f22 относительно f12)

-поглощения (для f12 относительно f22 и f22 относительно f12)

-комплементарности (f12 относительно f22, f1 и f22 относительно f22 , f1)

называется булевой алгеброй М ,f12 , f22, f1.


3. Гиперграфы: определение понятия «четкого» и «нечеткого» монографов;

способы задания


Гиперграф, ребра которого суть нечеткого подмножества вершин, называют нечетким гиперграфом. H = < V, E > . Множество всегда является четким.

(лекц: ) N = Гиперграф – это сеть, в которой число полюсов представляет собой пустое множество. Н= < V, E >, т.е. сеть, в которой Е – пустое множество, ) U Ei =V


Гиперграф - пара (V,E), где V - непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а E - семейство непустых (необязательно различных) подмножеств множества V, называемых ребрами гиперграфа. Ясно, что Г. является таким обобщением понятия графа, когда ребрами могут быть не только двухэлементные, но и любые подмножества вершин.


Четный граф - граф с четным числом вершин.


БИЛЕТ#2

1. Множество: числовые характеристики, операции разбиения и покрытия

+ см 1-1


мощность,…

Разбиение это проц создания подмножеств данного множества

Покрытие – это объединение нек множеств {A1,A2, ..., Ak}

2. Основные тождества эквивалентных преобразований логических выражений

алгебры логики

Эквивалентные преобразования логических выражений

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

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

1) xy = yx

xy = yx - коммутативность  и 

2) x(yz) = (x)yz

(xÙy) z = x  (y z) - ассоциативность  и 

3) x(yz) = (xy)  (x z)

x Ú (y Ùz) = (x Úy)(xz) - дистрибутивность  и 

4) xx=x, xx=x - повторение  и 

эти свойства являются законом идемпотентности  и 

5) x = x - закон двойного отрицания (эндоморфизм 2-го порядка, инволюция)

6) x1=x, x0=0

x1=1, x0=x

0 =1, 1 = 0

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

7) xy = yx

xy = yx

эти тождества – соотношения двойственности (закон де Моргана)

8) xx = 0

xx = 1

Эти тождества – закон дополнения (комплементарности противоречия) и закон исключенного третьего (закон двузначности высказывания)

{Тождество – это уравнение, которое удовлетворяется тождественно, то есть справедливо для любых допустимых значений входящих в него переменных. С логической точки зрения, Т. - это предикат(св-во), изображаемый формулой х = у (читается: "х тождественно у", "х то же самое, что и y"), которому соответствует логическая функция, истинная, когда переменные х и у означают различные вхождения "одного и того же" предмета, и ложная в противном случае.}


3. Обходы графа: Эйлеровы и Гамильтоновы пути (маршруты); основные

теоремы и критерии


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


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

Теоремы и критерии об обходе графа 


    • Если граф связный, а Vi и Vj есть его единственные вершины нечетной степени, то этот граф обладает эйлеровым маршрутом с концами Vi и Vj

    • Если граф  обладает эйлеровым маршрутом( путем) с концами Vi и Vj (ViVj), то граф  связный, а вершины Vi и Vj являются его единственными вершинами нечетной степени. Если граф связный и содержит ровно k вершин нечетной степени, то минимальное число покрывающих граф  ребер – непересекаюшихся цепей не обязательно простых равно k/2.

    • Если граф  связный и все его вершины четной степени, то он обладает эйлеровым циклом.

    • Если граф  обладает эйлеровым циклом(контуром), то он – связный и все его верщины четной степени.

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

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

А  В = (АВ)  (ВА).


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



  • Связный граф  с вершинами |V| >3 есть гамильтонов, если степень произвольной его вершины degVi  |V| / 2

  • Если для любой пары V и V несмежных вершин графа  с числом вершин |V| 3 выполняется неравенство deg Vi + deg Vj  |V|, то граф  - гамильтонов.

  • Утверждение. В турнире ( орграф, основанием которого является полный граф) существует гамильтонов путь.


БИЛЕТ#3

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

Символы правил соответствий .

Общие символы для обозначения правил соответствия элементов 2x множеств.

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

  • Если все элементы первого множества сопоставляются некоторым элементам второго множества по какому-то правилу, то говорят об отображении элементов первого множества, вводя для его обозначения символ Г.

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

  • Символ отношения R используют, когда сопоставляются элементы одного и того же множества.

  • Если отношения R функционально (однозначно), то для его обозначения принимают символ f.


Символы операций .

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

Символ , где i – арность операции, а j индекс(номер) операции

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

Пример: - унарная операция.

- бинарная операция


Наиболее часто соответствия задают:

–множеством картежей;

–матрицей;

–сечением (фактор-множеством);

–диаграммой.


2. Основные правила эквивалентных преобразований логических формул

см 2-2

правила – упрощение, минимизация

3. Дерево: символ, алгоритм Краскала


Символ дерева.

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

(Т)=


Получение символа дерева и получение дерева по заданному символу осуществляется по алгоритму Пруффера: если задано дерево с помеченными номерами вершинами, то согласно алгоритму Пруффера:

1: выбираем висячую вершину с наименьшим номером.

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


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


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


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


БИЛЕТ#4

1. Нечеткие подмножества данного множества: определение, способы задания

Если степень принадлежности элемента множества M множеству A есть

субъективно множественная оценка f(x)= 0, если xA

]0,1], если x A, то говорят о нечетком подмножестве A множества М (множество М всегда четко!).


Символическая запись А М (здесь-символ отношения включения всех элементов А в В).

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

Логическая экспликация(пояснение) понятия подмножества А мн-ва М с агрегатной и атрибутивной точек зрения следующая: х(()


2. Однородные и неоднородные логические функции


Если логическая функция и ее аргументы (переменныеXi) принимают значения из одного и того же множества A, содержащего k различных значений, то эта функция называется однородной k-значной логической функцией.

+см 5-2


3. Покрывающие деревья: определения, способы задания, формула Кэли


Покрывающее дерево – любая совокупность ребер на множестве вершин данного…

способы: графически, матрично, аналитически


Формула Кэли (частный случай матричной теоремы Кирхгофа, когда граф  является полным):

_Число различных помеченных деревьев порядка V равноVV-2

Теорему Кэли легко доказать с помощью символа дерева (Т) и с помощью теоремы Трента; множество символов М={I(T)} длины V-2 можно рассматривать как множество картежей из элементов- номеров вершин, т.е.

М=V*V*…*V=VV-2


V-2 раз


БИЛЕТ#5

1. Множество: числовые характеристики, операции разбиения и покрытия

см 2-1


2. Определение и способы задания логических функций


Логическая функция - это функция логических переменных, которая может принимать только два значения : 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения : 0 или 1.

Логический элемент - это устройство, реализующее ту или иную логическую функцию.

Y=f(X1,X2,X3,...,Xn) - логическая функция, она может быть задана таблицей, которая называется таблицей истинности. + аналитически


3. Плоские графы: определение, теоремы и критерий планарности

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

Достаточным признаком планарности графа является выражение |U| ( |V|+2)

Разбиение плоскости плоским графом на отдельные области называется плоской картой. Критерием планарного графа является теорема Эйлера. |V| - |U| + |Г| = 2,

где |V| - мощность множества вершин, |U| - мощность множества ребер, |Г| - мощность множества граней.


БИЛЕТ#6

1. Множество: числовые характеристики, способы задания

см 2-1 + способы

2. Алгебра логики: определение, аксиомы булевой алгебры, задача Венна

Алгебра логики - раздел матлогики на основе математических методов, изучающих логические операции над высказываниями. (Матлогика - логика, развиваемая математическим методом)

(Булева алгебра - частный случай алгебры логики.)

Совокупность подмножеств X, Y, Z, … некоторое множество М, имеющее наименьшее подмножество (нулевой элемент) О и наибольшее подмножество (наибольший элемент) 1, с тремя алгебраическими операциями: f12 (аддитивная операция ), f22 (мультипликативная операция) и f1 (унарная операция), удовлетворяющие аксиомам:

-коммутативности (для f12 и f22)

-ассоциативности (для f12 и f22)

-дистрибутивности (для f12 относительно f22 и f22 относительно f12)

-поглощения (для f12 относительно f22 и f22 относительно f12)

-комплементарности (f12 относительно f22, f1 и f22 относительно f22 , f1)

называется булевой алгеброй М , f12 , f22, f1.


  1. Задача Венна.

В уставе клуба записано:

    • финансовый комитет избирается из состава членов общего комитета

    • никто не может быть одновременно членом и общего, и библиотечного комитета, если только он не состоит также и членом финансового комитета.

    • никто из членов библиотечного комитета не может быть в финансовом комитете.



Упростить правила устава (до 2-х правил).

B, g, f- библиотечный, общий и финансовый комитеты.

 - «если, то»

Учтем, что xy = x y

Интерпретация выражения эквивалентна следующему:

    • члены финансово комитета избираются из членов общего

    • члены общего комитета не могут быть членами библиотечного



3. Обходы графа: Эйлеровы и Гамильтоновы пути ( маршруты ); основные теоремы и критерии

см 2-3


БИЛЕТ#7

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


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

  • Символ X принят для обозначения неалгебраической теоретико-множественной операции полного(декартового) произведения.

Символы , ,\,–, соответственно обозначают алгебраические операции объединения , пересечения, разности, дополнения и прямой суммы множеств

+ см 3-1


2. Решение задачи Венна

см 6-2


3. Поток транспортной сети: определение, теорема Форда-Фалкерсона

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

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

Разрезом (А,В) - множество которых начинаются в А, а кончаются в В.

{Предположим, что в сети нашли поток такой, что не существует увеличивающей S-t цепочки. Постороим разбиение AB, взяв в качестве А множество всех вершин Х, для которых существует увеличивающая S-X цепочка и вершину S.Все оставшиеся вершины образуют B. Найдя наибольшую пропускную способность мы и найдем величину наибольшего потока.

{Увеличивающаяся цепочка - это цепочка, у которой на прямых ребрах величина потока меньше чем пропускная способность и не равна нулю на обратных ребрах.}


БИЛЕТ#8

1. Морфизм алгебраических систем

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

М = 1,2,

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

Гомоморфизм - отображение, сохраняющее базовые операции и отношения на сопоставляемых множествах.

Гомоморфизмом алгебраической системы А1 M1,O1,R1 в однотипную ей систему А2 M2,O2,R2 называется отображение Г: А1А2, удовлетворяющее условиям:

1.Гf(fina1,а2,а3,…,аni)= fin (Г(а1),Г(а2),…,Г(аni))

2
. a1,а2,а3,…,аnrj ((а1),Г(а2),…,Г(аm)) rj1



2. Логические функции математической логики

см 5-2 + 4-2


3. Идентификация графов, заданных своими представлениями


БИЛЕТ#9

1. Морфизмы реляционных систем

Алгебраическая система A = называется реляционной системой (или моделью), если на основном множестве M заданы только отношения R (т.е. в этом случае пусто множество операций O, что означает O = )


2. Булева алгебра функции и эквивалентные преобразования

см 1-2 + см 2-2


3. Двудольные графы: определение, теорема Кенига

{ДВУДОЛЬНЫМ называется гpаф в котоpом множество веpшин V является объединением двух непеpесекаемых подмножеств V' и V" и нет pебpа обе веpшины котоpого пpинадлежат одному из множеств V' или V" }

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

{Графическим представлением бинарного соответствия между множествами M1 и M2 может быть диаграмма (двудольный граф.)}

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


Теор: если граф двудольный, то число вершинного покрытия графа = числу реберного покрытия

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

Реберное покрытие - такое подмножество E' ребер графа, что каждая вершина в графе инцидентна по крайней мере одному ребру из E'. Р.п. называется минимальным, если в нем не содержатся покрытия с меньшим числом ребер, и наименьшим, если число ребер в нем наименьшее среди всех покрытий. Мощность наименьшего Р.п. называется числом реберного покрытия и обозначается через (G).


{ Граф бихроматический (двудольный граф, граф Кенига) (bipartite graph) - 2-хроматический граф или граф, не содержащий нечетных циклов.

Цикл - замкнутая цепь (У простого цикла совпадают только начальная и конечная вершины) }


БИЛЕТ#10

1. Множество: агрегатная и атрибутивная точки зрения на первичные понятия

теории множеств; способы задания

cm 1-1

2. Булева алгебра функций и эквивалентные преобразования

см 9-2


3. Плоские графы: определение, теоремы и критерий планарности

см 5-3


БИЛЕТ#11

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

см 3-1

2. Логические функции математической логики

см 8-2

3. Гиперграфы: определение понятия «четкого» и «нечеткого» монографов; способы задания

см 1-3


БИЛЕТ#12

1. Отношения на множестве: определение, классификация, способы задания

Подмножество декартового произведения множеств A1 X A2 X ….X An называется отношением степени n (n-арным отношением).


Определение 7. Мощность множества кортежей, входящих в отношение , называют мощностью отношения


{~см 3-1

Теория множеств – математическая теория, изучающая наиболее общие свойства и отношения конечных и бесконечных совокупностей объектов, свойства самих объектов



В том случае, если M1=M2=…=Mn, то пишут


Часто Mn называют универсальным отношением }


2. Алгебра логики: задача Венна

см 6-2


3. Дерево: символ, алгоритм Краскала

см 3-3


БИЛЕТ#13

1. Отображение множества: определение, классификация и символическая запись

Отображение множества А в множество В, соответствие, в силу которого каждому элементу х множества А соответствует определённый элемент у = f (x) множества В, называют образом элемента х (элемент х называют прообразом элемента у). Иногда под О. понимают установление такого соответствия.


2. Задача Венна

см 6-2


3. Покрывающие деревья: определения, способы задания, формула Кэли

см 4-3


БИЛЕТ#14

1. Множество: числовые характеристики, способы задания

см 2-1 и 6-1(способы)

2. Алгебра логики: определение, задание логических формул и их преобразования

~ см 5-2

3. Поток транспортной сети: определение, теорема Форда-Фалкерсона

см 7-3


БИЛЕТ#15

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

см 7-1

2. Однородные и неоднородные логические функции

см 4-2

3. Псевдограф: определение, классификация, лемма о рукопожатиях

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

Мультиграф - пара (V,E), где V - непустое множество вершин, а E - семейство подмножеств множества V Х V (ребра); другими словами, мультиграф есть граф с кратными ребрами.

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

В понятие псевдограф включаются следующие понятия:

  • простой (обыкновенный) граф (нет кратных ребер, петлей)- однородный гиперграф

  • тривиальный (пустой) гиперграф

  • мультиграф (однородный гиперграф с кратными ребрами)

  • граф тождественных отношений (гиперграф, ребра которого есть одноэлементные множества))

Лемма о рукопожатиях.

В связном графе = сумма степеней всех его вершин – четное число, равное удвоенному числу ребер графа: |V| degVi = 2|U| i=1

Частные случаи:

  • для однородного связного графа степени 2 : |V| = |U| имеем колесо

- для полного графа: |V| |V-1| = 2U

Следствия леммы о рукопожатиях:

  1. Число вершин нечетной степени любого связного графа – четно

  2. Число вершин однородного кубического графа всегда четно

3|V| = 2|U|

  1. Во всяком графе с вершинами |V|2 найдутся по меньшей мере 2 вершины с одинаковыми степенями.

  2. Если в графе с вершинами |V|>2 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени «0» , либо в точности одна вершина степени |V-1|


БИЛЕТ#16

1. Морфизм алгебраических систем

см 8-1

2. Основные правила эквивалентных преобразований логических формул

см 3-2

3. Двудольные графы: определение, теорема Кенига

см 9-3


БИЛЕТ#17

1. Морфизмы реляционных систем

см 9-1

2. Основные свойства булевых операции алгебры логики: упрощение логических выражений

см 1-2 + 2-2


3. Двудольные графы: определение, теорема Кенига

см 9-3


БИЛЕТ#18

1. Множество: агрегатная и атрибутивная точки зрения на первичные понятия теории множеств; способы задания

см 1-1

2. Способы задания логических функции, задача Венна

см 5-2

+ 6-2

3. Покрывающие деревья: определения, способы задания, формула Кэли

см 4-3


БИЛЕТ#19

1. Множество: агрегатная и атрибутивная точки зрения на первичные понятия теории множеств; способы задания

см 1-1

2. Алгебра логики: задача Венна, канонические формы логических функций

см 6-2

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

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

  1. СДНФ (совершенной ДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций и все элементарные конъюнкции, содержат одни и те же переменные (длина одинакова). Причем каждая переменная входит только один раз, включая вхождение под знак отрицания. xy  xy  xy - СДНФ

  2. СКНФ – совершенная конъюнктивная нормальная форма, такая форма, в которой нет одинаковых сомножителей и все сомножители содержат одни и те же переменные, причем каждая переменная только 1 раз включает знак вхождения под знак отрицания.

(xy)(xy) - СКНФ.

Утверждение: логическая функция n аргументов не равная тождественно 1 реализуется однозначно СКНФ.


3. Покрывающие деревья; определения, способы задания, формула Кэли

см 4-3

БИЛЕТ#20

1. Отношения на множестве: определение, классификация, способы задания

см 12-1

2. Основные свойства булевых операций алгебры логики

см 1-2

  1. Дерево: символ, алгоритм Краскала

см 3-3


Экономичные СС:

Под экономичностью системы понимается тот запас чисел, который можно записать с помощью данного количества знаков. Чтобы записать 1000 чисел (от 0 до 999) в десятичной системе, нужно 30 знаков (по десять в каждом разряде), а в двоичной системе с помощью 30 знаков можно записать 215=32768 чисел, что гораздо больше 1000. То есть двоичная система явно экономичнее десятичной. В общем случае, если взять n знаков в системе с основанием x, то количество чисел, которые при этом можно записать, будет равно x^(n/x). Легко найти максимум такой функции, который будет равен иррациональному числу е=2.718282....

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


Максимальное число А, которое можно изобразить в системе счисления с основанием q равно:


x^|M|/x