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

Для обозначения номеров строк и столбцов матрицы наборы X и Y индексируются положительными целыми числами: i варьируется от 1 до мощности (размер) X и j варьируется от 1 с числом элементов Y. Подробнее см. запись в индексированных наборах.

ЕслиG – граф (ориентированный или нет) без кратных дуг, то его матрица смежностиA являетсябулевой, то есть состоит из нулей и единиц. Для произвольной матрицыX = (xij) с неотрицательными элементами будем обозначать через sign(X) булеву матрицу, полученную изX заменой всех ее положительных элементов единицами. Например,

	1	2	0		1	1	0
sign	0	2	1	=	0	1	1	.
3		0	1	1		0	1

Равенство sign(X) =X означает, что матрицаX булева. Легко видеть, что

sign(X+Y) = sign(sign(X) + sign(Y)),

sign(X·Y) = sign(sign(X)·sign(Y))

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

sign(X+Y) = sign(X) sign(Y) (дизъюнкция булевых матриц вычисляется поэлементно).

ПустьA иB – булевы матрицы. Матрицу sign(A·B) будем называть ихбулевым произведениеми обозначать черезAB. В

соответствии с определением sign(A·B) =AB. ЕслиA = (aij) и

B = (bij), то элементы булева произведенияAB = (cij) определяются формулами

cij = ai1b1j = ai2b2j … ainbnj ,

гдеn – число столбцов матрицы

---

A и число строк ПоложимA[k]= sign(Ak) и будем называть матрицу степенью матрицыA.

матрицыB.A[k]булевой

ЕслиA – матрица смежности графаG, то на месте (i,j) матрицыA[k]находится 1, если на графеG существует путь длиныk изi вj, и 0 в противном случае. Пустьn – число вершин графаG. Тогда матрица

EAA[k]… A[n–1]

содержит 1 на месте (i,j) в том и только том случае, когда на графеG имеется хотя бы один путь из вершиныi в вершинуj.


33. Мощность. Счетные множества.

Определение 1.ПустьN- множество натуральных чисел. Множество S называется счётным множеством, если оно равномощно N, то есть S N.

Мощность конечного множества А называется число элементов этого множества.

Все счетные множества имеют мощность равную мощности натурального ряда чисел

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

действительных чисел R (с доказательством).
Несчётное мно́жество — бесконечное множество, не являющееся счётным.

• 
  не существуетинъективногоотображения� вомножество натуральных чисел� ;
  
• 
  �  непустое, и для каждой нумерованной последовательности элементов� существует по крайней мере один элемент� , не входящий в неё;
  
  • 
    иными словами:� непусто, и не существуетсюръективногоотображения множества натуральных чисел� на� ;
    
• 
  мощность� не является ни конечной, ни равнойℵ0 .
  

---

Данные определения являются эквивалентными всистеме Цермело— Френкелябез использованияаксиомы выбора. Доказательство эквивалентности данных определений со следующим:

• 
  мощность �  строго превышает ℵ0
  

— требует привлечения аксиомы выбора.

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

 Теорема 2.Любой отрезок множества действительных чисел состоит из несчетного множества точек.

Доказательство:Пусть это не так, тогда все точки отрезка[a, b], a<bможно пронумеровать,[a, b]={x₁,x₂…}. Выберем отрезок[a₁, b₁][a, b]не содержащийх₁. Таким образом если выбрать отрезок[a_n, b_n]то дальше выберем отрезок[a_n+1, b_n+1]. Продолжая этот процесс получим систему вложенных отрезков[a_n, b_n]такую чтоx_nне принадлежит[a_n, b_n], следовательно ни одна точка не принадлежит пересечению   [a_n, b_n]но согласно принципу вложенных отрезков существует точкаξпринадлежащая всем отрезкам. Следовательноξпринадлежит[a, b].

Теорема 3.(Кантор).Множество всех действительных чисел несчетно.

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


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

---

алгоритм сложения матриц. Сложение матриц выполняется для каждого / и каждого у. Поскольку / принимает t значений, a j принимает p значений, то выполняется tp операций сложения. Пусть N= max {/и, п). Тогда число выполняемых арифметических операций имеет порядок 0(7V²);
алгоритм умножения матрицы Л размера т х р на матрицу В размера р х п. Поскольку к принимает значения от 1 до р, то выполняется р операций сложения и р операций умножения. Величина к изменяется от 1 до р для каждого / и каждого у, поэтому к пробегает значения от 1 до р тп раз. Таким образом, выполняется тпр операций сложения и тпр операций умножения. Следовательно, всего выполняется 2тпр операций. Пусть N = = max{/n, п, р}. Тогда число выполняемых арифметических операций имеет порядок 0(N³);

37. Алгоритм сортировки выбором (СВ). Пример. Оценка числа операций.

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

Оценка - сортировка выбором. Рассмотрим число сравнений в процедуре СВ для списка из п элементов. Первый элемент сравнивается с остальными элементами и так далее до ( 1)-го элемента, который сравнивается только с одним элементом. Таким образом, (п 1) + (п 2) + ... + 2 + 1 = я(я 1)/2, так что число сравнений имеет порядок 0(и²);

function selectionSort(T[n] a):

for i = 0 to n - 2

for j = i + 1 to n - 1

if a[i] > a[j]

swap(a[i], a[j])
38. Граф и подграф. Основные понятия.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.

Подграфом графа G(V,E) называется граф, все вершины и ребра которого содержатся среди вершин и ребер исходного графа G(V,E).

Определим некоторые операции на графах.

---

Удаление или добавление ребра.

Удаление вершины. Из множества вершин удаляем выбранную вершину, а из множества ребер все инцидентные ей ребра.

Стягивание ребра. Отождествляем (стягиваем) вершины инцидентные выбранному ребру.

Добавление вершины (разбиение ребра). Выберем некоторое ребро (u,v) из множества ребер и удалим его. В множество вершин добавим новую вершину w, а в множество ребер новые ребра (u,w) и (w,v).

39. Орграф, мультиграф, размеченный граф. Основные понятия. Пути, связность.

Ориентированный граф (или сокращенно орграф)G = (V,Е) состоит из множества вершинV и множества дугЕ. Вершины также называют узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v,w), где вершинаv называется началом, a w – концом дуги. Дугу (v,w) часто записывают какv →w и изображают в виде

Говорят также, что дугаv →w ведет от вершиныv к вершинеw, а вершинаw смежная с вершинойv.

Нарис. 5.1показан орграф с четырьмя вершинами и пятью дугами.



Маршрутом длиныиз в в орграфе называется последовательность рёбер вида



т.е. вторая вершина каждого ребра совпадает с первой вершиной следующего ребра. //

Часто удобно представлять маршрут последовательностью вершин



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

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

---