Итерационные алгоритмы разрезания графа на куски
Лекция
Итерационные алгоритмы разрезания графа на куски
Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания с дальнейшими перестановками вершин с одного куска в другой с целью минимизации числа соединительных ребер.
Вспомним, Что Матрица Смежности Для Графа G (X, E), Имеющего N Вершин - это Матрица R=||rIj||N*N, Элементы Которой Соответствуют Числу Ребер, Соединяющих Вершину XI С Вершиной XJ.
Т. к. матрица смежности полностью описывает граф, то разрезание графа G на L кусков G1, G2, ..., GL эквивалентно разбиению матрицы смежности R графа G на L клеток (подматриц). Например, граф задан матрицей смежности R. Граф разрезан на 2 куска - G1={е1, е2, е3} и G2={е4, е5, е6, е7}.
|
R= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
2 |
1 |
0 |
1 |
0 |
2 |
0 |
0 |
|
3 |
1 |
1 |
0 |
0 |
0 |
0 |
3 |
|
4 |
1 |
0 |
0 |
0 |
2 |
1 |
0 |
|
5 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
|
6 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
7 |
0 |
0 |
3 |
0 |
0 |
1 |
0 |
Очевидно, что клетки по главной диагонали задают подграфы GI', включающиеся в куски GI, а остальные клетки определяют наличие ребер между кусками.
За критерий оптимальности можно брать минимум числа ребер между кусками (см. формулу (3.2) лекции 3)
(7.1)
Либо максимум числа ребер внутри кусков
(7.2)
Или G > max (7.3)
(Согласно материалу лекции 3 множество UIj определяет подмножество ребер UIj ? U, попадающих в разрез между кусками GI и GJ графа G, а множество UIi определяет подмножество ребер, т. е. кол-во связей Внутри Куска GI). Разрезание графа будем сводить на каждом шаге к разрезанию графа на два куска. Число вершин первого куска равно числу вершин выделяемого куска, а число вершин второго куска - числу всех оставшихся вершин графа. Таким образом, в первом куске пусть будет множество ЕI вершин, а во втором ЕI = Е ЕI.
Тогда множество ребер разобьем на три класса:
- 1) внутренние ребра, лежащие в куске; GI; 2) внешние ребра, лежащие в куске GI; 3) соединяющие ребра между кусками GI и GI.
Число внутренних ребер куска GI равно
(7.4)
Где (eI) - сумма локальных степеней вершин куска GI, KI - число соединительных ребер кусков GI и GI
Число внешних ребер, которые являются внутренними для куска GI равно
(7.5)
Для Каждой Вершины EK Введем Число Связности Вершины (разность Кол-ва Внешних И Внутренних Связей K-го Элемента)
K= RK (GI) - rK (GI), если eKEI (7.6)
RK (GI) - rK (GI), если eKEI(7.7)
Где: RK (GI) - число ребер, соединяющих вершину EK с вершинами куска GI (K-й элемент, I-й кусок); RK (GI) - число ребер, соединяющих вершину EK с вершинами куска GI.
Обозначим: K - число Связности Для Вершин EKEI; K - число Связности Для Вершин EKEI.
Поясним понятие связности на примере графа G, разбитого на 2 части G1 и G2, приведенного на рис. 7.1
Тогда числа связности для вершин G1 Определяется следующим образом:
(x1) =r1 (G2) - r1 (G1) =1-2=-1;
(x2) =r2 (G2) - r2 (G1) =2-2=0;
(x3) =r3 (G2) - r3 (G1) =3-2=1;
Числа связности для вершин G2:
(x4) =r4 (G1) - r4 (G2) =1-3=-2
(x5) =r5 (G1) - r5 (G2) =2-2=0;
(x6) =r6 (G1) - r6 (G2) =0-2=-2;
(x7) =r7 (G1) - r7 (G2) =3-1=2;
Очевидно, что число связности может быть положительным, отрицательным или равным нулю. Физический смысл числа связности следующий. Например, (x1) =-1 означает, что при перестановке вершины X1 из G1 в G2 число ребер в сечении увеличится на 1. Значение (x2) =0 говорит о том, что перестановка вершины X2 из G1 в G2 оставит без изменения число соединительных ребер.
Рассмотрим теперь итерационный алгоритм с использованием матрицы смежности. Он основан на Теореме:
Перестановка двух произвольных вершин EKEI и EQEI приводит к уменьшению числа соединительных ребер между кусками в случаях:
A) если EK и EQ не смежные, и выполняется: K+Q> 0 (7.7)
Б) если EK и EQ смежные, и выполняется: K+ Q >2 (7.8)
В общем случае K+ Q >2rKq (7.9)
Докажем утверждение А). Очевидно, что перестановка целесообразна, если KI=KI-K'I>0 (например, было 5 внешних реберных соединений, стало 2), где KI и K'I - числа внешнего реберного соединения до и после перестановки и
KI=rK (GI) + rQ (GI) (7.10) K'I=rK (GI) + rQ (GI) (7.11)
Тогда
KI=rK (GI) +rQ (GI) - K (GI) - rQ (GI) = K+Q>0 (7.12)
Аналогично доказывается утверждение Б).
Теперь опишем суть алгоритма:
- 1. Разрезание начинаем выделением в матрице R двух произвольных подматриц Q и Q. Порядок подматрицы Q равен числу вершин первого выделяемого куска, а порядок Q - числу всех оставшихся вершин. 2. Перестановка элементов из одного куска в другой будет соответствовать перестановке строк и столбцов матрицы R. 3. Матрица смежности графа, приведенного на рис. 7.1, имеет вид:
|
R0= |
1 |
2 |
3 |
4 |
5 |
6 |
7 | ||
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
-1 |
K |
|
2 |
1 |
0 |
1 |
0 |
2 |
0 |
0 |
0 | |
|
3 |
1 |
1 |
0 |
0 |
0 |
0 |
3 |
1 | |
|
4 |
1 |
0 |
0 |
0 |
2 |
1 |
0 |
-2 |
Q |
|
5 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
0 | |
|
6 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
-2 | |
|
7 |
0 |
0 |
3 |
0 |
0 |
1 |
0 |
2 |
Разрежем эту матрицу на 2 подматрицы по 3 и 4 элемента. Сумма всех элементов закрашенных подматриц, деленная на два, соответствует числу внутренних ребер кусков, а элементы, не принадлежащие главной диагонали, определяют соединяющие ребра между кусками. Тогда
(7.13)
(7.14)
Для каждой строки матрицы смежности подсчитываем K или Q в зависимости от того, к какой подматрице принадлежит данная строка. Запишем эти числа справа матрицы.
4. Построим матрицу В =||bkq||ni* (n-ni), в которой строки определяются вершинами ekEi, а столбцы вершинами eqEi. На пресечении k - ой строки и q - го столбца элемент
BKq= K+Q-2rKq (7.15)
Где RKq - элемент матрицы R.
Элемент BKq характеризует изменение числа соединительных ребер между кусками GI и GI при перестановке вершин EKGI и EQGI.
Выбираем Для Перестановки Пару С Наибольшим Положительным BKq.
- 5. Осуществляется перестановка строк и столбцов K и Q в матрице R и процесс снова повторяется пока в матрице B все элементы не станут со знаком "-". 6. Исключается из графа G кусок G1, соответствующий подматрице Q1 и процесс повторяется для матрицы Q1 с выделением куска с N2 элементами и т. д.
Пример.
Итерационный алгоритм разрезание граф
Задана матрица смежности R0 графа G. Надо разрезать граф с рис.7.1 на 3 куска по 5, 3, 4 вершин
|
R0= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 | ||
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
+4 |
K |
|
2 |
0 |
0 |
0 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 | |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
+2 | |
|
4 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
+1 | |
|
5 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
1 |
0 |
0 |
+2 | |
|
6 |
0 |
1 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
+1 |
Q |
|
7 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
+2 | |
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
-2 | |
|
9 |
2 |
0 |
0 |
0 |
2 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
+2 | |
|
10 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
+1 | |
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-4 | |
|
12 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
3 |
0 |
-4 |
Согласно п.1 алгоритма выделяем в матрице R0 две подматрицы, в одной из которых 5 строк, т. е. включаем в первый кусок элементы E1, E2, E3, E4, E5 (т. к. разбиваем на куски по 5, 3, 4 вершин), в оставшейся части 7 строк.
Согласно п.3 алгоритма для каждой строки матрицы смежности по формулам (7.13) и (7.14) подсчитываем K и K и записываем в столбец справа от матрицы смежности. Число соединительных ребер между G1 и G1 (число внешних связей) для этого разбиения K1=14 (сумма элементов одной из невыделенных частей)
Согласно п.4 алгоритма по формуле (7.15) построим матрицу В. Для примера:
B16= 1+6-2r16=4+1-2*0=5, b411= 4+11-2r411=1-4-2*0=-3
|
B0= |
E6 |
E7 |
E8 |
E9 |
E10 |
E11 |
E12 |
|
E1 |
+5 |
+2 |
+2 |
+2 |
+5 |
0 |
0 |
|
E2 |
-2 |
-1 |
-3 |
+1 |
0 |
-5 |
-5 |
|
E3 |
+3 |
+4 |
-2 |
+4 |
+3 |
-2 |
-4 |
|
E4 |
+2 |
+3 |
-1 |
-1 |
0 |
-3 |
-3 |
|
E5 |
-1 |
+4 |
0 |
+4 |
+1 |
-2 |
-2 |
Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным B16=5, т. е. из B0 выбираем для перестановки элементы E1 и E6.
Согласно п.5 алгоритма, в матрице R0 Переставляем Строчки И Столбцы, Соответствующие E1 И E6, и смотрим, как изменится число внешних связей между кусками от этой перестановки.
Матрица R1
|
R1= |
6* |
2 |
3 |
4 |
5 |
1* |
7 |
8 |
9 |
10 |
11 |
12 | ||
|
6* |
0 |
1 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
-1 |
K |
|
2 |
1 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-3 | |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
2 | |
|
4 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
1 | |
|
5 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 | |
|
1* |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
-4 |
Q |
|
7 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
-2 | |
|
8 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
-2 | |
|
9 |
0 |
0 |
0 |
0 |
2 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
-2 | |
|
10 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 | |
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-4 | |
|
12 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
3 |
0 |
-2 |
Число соединительных ребер между G1 и G1 (число внешних связей) для этого разбиения K2=9 (сумма элементов выделенной части).
Число соединительных ребер между G1 и G1Снизилось с 14 До 9, т. е. перестановка элементов E1 и E6 дает уменьшение числа соединительных ребер. Переход к п.4. Согласно п.4 по формуле (7.15) строим матрицу В1:
|
B1= |
E1 |
E7 |
E8 |
E9 |
E10 |
E11 |
E12 |
|
E6 |
-5 |
-3 |
-3 |
-3 |
0 |
-5 |
-7 |
|
E2 |
-7 |
-7 |
-5 |
-5 |
0 |
-7 |
-7 |
|
E3 |
-2 |
0 |
-2 |
0 |
+5 |
-2 |
-4 |
|
E4 |
-3 |
-1 |
-1 |
-5 |
+2 |
-3 |
-3 |
|
E5 |
-6 |
-4 |
-4 |
-4 |
-1 |
-6 |
-6 |
Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным B310=5, т. е. из B1 выбираем для перестановки элементы E3 и E10.
В матрице R1 переставляем строчки и столбцы, соответствующие E3 и E10.
|
R'2= |
6 |
2 |
10 |
4 |
5 |
1 |
7 |
8 |
9 |
3 |
11 |
12 | ||
|
6 |
0 |
1 |
1 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
K |
|
2 |
1 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-3 | |
|
10* |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-3 | |
|
4 |
0 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
-1 | |
|
5 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-2 | |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
-4 |
Q |
|
7 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
-2 | |
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
-4 | |
|
9 |
0 |
0 |
0 |
0 |
2 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
-2 | |
|
3* |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
-2 | |
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-4 | |
|
12 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
3 |
0 |
-4 |
Число соединительных ребер между G1 и G1 снизилось до 4.
Согласно п.5 алгоритма т. к. в R'2 все значения БК и БQ отрицательные, то в В2 не будет положительных элементов, и процесс выделения подграфа G1 закончен, 1-й кусок построен: E1=e6,e2,e10,e4,e5
Строим кусок E2, содержащий 3 вершины Включаем в него элементы E1, E7, E8.
Согласно п.6 алгоритма, исключив из R'2 кусок, соответствующий G1, получим:
Матрица
|
R''0= |
1 |
7 |
8 |
9 |
3 |
11 |
12 | ||
|
1 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
0 |
K |
|
7 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 | |
|
8 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
4 | |
|
9 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
4 |
Q |
|
3 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 | |
|
11 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
-2 | |
|
12 |
0 |
0 |
1 |
0 |
1 |
3 |
0 |
-3 |
Строим матрицу B''0:
|
B''0= |
E9 |
E3 |
E1 |
E12 |
|
E1 |
1 |
-1 |
-3 |
-3 |
|
E7 |
-5 |
0 |
-7 |
-4 |
|
E8 |
6 |
2 |
0 |
-1 |
Выбираем Max B89=6. Из B''0 выбираем для перестановки элементы E8 и E9. В матрице R''0 переставляем строчки и столбцы, соответствующие E8 и E9:
|
R''1= |
1 |
7 |
9 |
8 |
3 |
11 |
12 | ||
|
1 |
0 |
2 |
2 |
0 |
0 |
0 |
0 |
-4 |
K |
|
7 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
-3 | |
|
9 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
-2 | |
|
8 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
-2 |
Q |
|
3 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
-2 | |
|
11 |
0 |
0 |
0 |
1 |
0 |
0 |
3 |
-4 | |
|
12 |
0 |
0 |
0 |
1 |
1 |
3 |
0 |
-5 |
Число соединительных ребер между G2И G2Снизилось с 7 До 1, т. е. перестановка элементов E8 и E9 дает уменьшение числа соединительных ребер.
Т. к. все БК и БQ отрицательные, то в В''1 все члены будут со знаком "-" и перестановки не может быть. Тогда
E2=e1,e7,e9, E3=e8,e3,e11,e12.
Число соединительных ребер между кусками =5.
Число внутренних ребер равно 9+5+7=21.
? (G) =21/5=4,2.
Результат разбиения приведен на рис.7.2.
Материал из лекции 3
Пусть граф G (E, U) разбит на L кусков G1, G2,...,GL. Тогда множество ребер U графа G можно представить в виде:
(3.3)
Где
U1=U1,1U1,2...U1,l
U2=U2,1U2,2...U2,l
...... ......................
Ui=Ui,1Ui,2... Ui, l
... .........................
U1=Ul,1 Ul,2...Ul, l (3.4)
Где:
- - UI - Подмножество всех ребер, инцидентных вершинам EI куска GI; - UI, I - подмножество ребер, соединяющих подмножество вершин EI куска GI между собой; - UI,J - подмножество ребер, соединяющих куски GI и GJ.
Назовем Коэффициентом Разбиения ? (G) Графа G отношение суммарного числа внутренних ребер (ребер подмножеств UI, I) к суммарному числу соединяющих ребер UI,J.
(3.5)
Коэффициент ? (G) Служит для оценки разбиения графа G на куски. Для графа на рис. 3.1 ? (G) =5/12.
Этот коэффициент можно также использовать как критерий для сравнения различных алгоритмов разбиения графа. Оптимальным разбиениям для одного и того же графа соответствуют Наибольшие Значения ? (G).
Похожие статьи
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным,...
-
Входные параметры: входной файл, выходной файл, номер вершины, номер вершины. Если задаваемые номера вершин положительные, то добавляется соответствующее...
-
Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан...
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6]. Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это...
-
Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке...
-
Исследования временных затрат алгоритмов - Алгоритмы нескольких махов
Исследования временных затрат алгоритмов были проведены для трех вариантов программ: LBFS4, LBFS3, MNS3; для двух вариантов сборки исполняемого файла:...
-
Численные эксперименты были проведены для следующих целей: Подтверждение корректности алгоритмов. Подтверждение линейности временных затрат алгоритмов. В...
-
Введение - Алгоритмы нескольких махов
Теория графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике и социологии, а также в генетике,...
-
Стек технологий При выборе стека технологий основное внимание уделялось следующим факторам, в порядке убывания значимости: § Кроссплатформенность; §...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Модификации алгоритма Лемпеля-Зива, предложенная Терри Уэлчем - Анализ алгоритма Лемпеля-Зива
В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не...
-
Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги
В данном пункте нужно проанализировать используемый алгоритм поиска кратчайшего пути. Алгоритм Дейкстры Находит кратчайший путь от одной из вершин графа...
-
Теоретические аспекты поставленной задачи В этой части проекта будут объяснены этапы применения МКЭ для плоской фермы. В первой главе было рассмотрено...
-
Для оценки возможности выполнения проекта имеющимся в распоряжении разработчика штатным составом исполнителей, нужно рассчитать их среднее количество,...
-
Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных...
-
Элементы теории графов. Сеть Петри. Конечный автомат
Вариант №8 Задача 1. Элементы теории графов Связный ориентированный граф G(Х, Г) задан множеством вершин X={x1, x2, ..., xn} и отображением Гxi={x|Ik|,...
-
Для вычисления цвета могут быть использованы различные подходы. Вычисление цвета может проводиться одновременно с геометрической реконструкцией,...
-
Поворот точки относительно центра на заданный угол: X = o. X + (p. X-o. X) * cos(angle) - (p. Y-o. Y) * sin(angle) Y = o. Y + (p. X-o. X) * sin(angle) +...
-
В этом разделе намеренно допущено отступление от общей методики - не смешивать разные компоненты. Это сделано для облегчения демонстрации построения...
-
Структура и интерфейс программы - Исследование алгоритмов
В этой части работы описывается процесс создания мобильного приложения на платформе Android, способного использовать обученные каскадные классификаторы...
-
Заключение - Разработка программы для реализации редактора временных графов синхронизации
Результатом выполнения задания является реализованный редактор временных графов синхронизации (класс временных сетей Петри), соответствующий задачам,...
-
Н. Н.&;nbsp;Константинов, Висновки - Визначні постаті у розвитку комп'ютерної графіки
Народився в м Москві. Закінчив фізичний факультет Московського державного університету ім. М. В. Ломоносова в 1960 році. Кандидат фізико-математичних...
-
ВВЕДЕНИЕ - Анализ алгоритма Лемпеля-Зива
Одна из задач любой информационной системы обеспечивать хранение и передачу информации. Причем хранение и передача информации занимают определяющее место...
-
Задание: 1. Прочитать текст "Алгоритм и его свойства", в таблице №1 "Алгоритм и его свойства" проверьте правильное заполнение таблицы. Запишите в тетрадь...
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
Вступ - Комп'ютерна графіка - погляд у майбутнє
Комп'ютерна графіка з'явилась достатньо давно -- вже у 1960-х роках існували повноцінні програми роботи з графікою. Сьогодні прийнято користуватися...
-
Програмна реалізація алгоритмів лінійної структури Алгоритм (латинізов. Algorithmi за араб. ім'ям узб. математека аль-Хороезмі) -- набір інструкцій, які...
-
Свойства алгоритмов - Алгоритм
Данное выше определение алгоритма нельзя считать строгим - не вполне ясно, что такое "точное предписание" или "последовательность действий,...
-
В алгоритме Zhou&;Koltun при вычислении отклонений цвета используется изображение, переведенное в градации серого. В данной реализации используется...
-
Слово "Алгоритм" происходит от algorithmi - латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из...
-
Для создания трехмерной реконструкции сцены или объекта необходимо создать его трехмерную модель и вычислить цвет ее вершин. Для геометрической...
-
Приложение, которое необходимо разработать, должно производить геометрическую реконструкцию сцены и вычисление цвета вершин модели. Для геометрической...
-
Алгоритм работы декодера кода Рида - Маллера будем разрабатывать на основе уже приведенных выше уравнений. Алгоритм приведен на рисунке 12. В начале...
-
В основе алгоритма лежит численное исследование пространства управляемых параметров редуктора. Процесс поиска оптимального решения выполняется за четыре...
-
Множество D с двумя заданными на нем операциями (плюс) и (умножение) называется диоидом, если выполнены следующие аксиомы: § Ассоциативность. §...
-
Цифровий підпис на основі алгоритму Ель Гамаля (EGSA) Хешування відбувається за схемою, зображеної на рис. 2.1 Рисунок 2.1 - Схема функції хешування...
Итерационные алгоритмы разрезания графа на куски