Символьные матрицы над конечным алфавитом, как представление комплексов в n-кубе. Г.Г.Рябов, В.А.Серов Научно-исследовательский вычислительный центр МГУ. - презентация

1 Символьные матрицы над конечным алфавитом, как представление комплексов в n-кубе. Г.Г.Рябов, В.А.Серов Научно-исследовательский вычислительный центр МГУ Лаборатория методов компьютерной визуализации

2

3 Кубанты-биективное представление k-граней в n-кубе Cлово из n букв-в позиционной системе для представления действий (декартового произведения и трансляции),привязанной к порядку базисных векторов репера (0;e 1,…e n ), заданного в R n. k-грань в n-кубе: f nk d 1,d 2,…d n ПI(е i )+TI(e j ); d i A{0;1;2}; i:di=2 j:dj=0,1 k n-k

4 Кубант(n-разрядное троичное слово) k-грань n-куба. Пример k- граней в 9- кубе и их курантов: (3- грань) (3- грань) (2- грань)

5 Основные операции на курантах. #(a)D-число символов «а» в кубание D. D-кубани для грани, антиподальной к D D1+D2-сумма курантов (выпуск.оболочка граней) D1xD2-произведение (пересечение граней) HH (D1,D2)-расстояние Хаусдорфа-Хемминга D-мн-во курантов для гиперграней границы грани

6 k-мерные кратчайшие пути и их представление Минимальное число k-граней, примыкающих друг к другу k-1-мерными гипергранями и соединяющими две вершины (0…0 и 1…1) n-куба.. Множество курантов как множество строк символьной (троичной) матрицы с выполнением определенных свойств по строкам и столбцам.

7 Троичные матрицы n-k+1 n … … … …0 Т s = …0 T s+c = …0 ………….. …………. 111… …12 D i -строка Т #(2)D i =k; D j *-столбец Т #(2)(D j *xD j+1 *)=k-1; Вид D j * {(2);(2)(1);(0)(2)(1);(0)(2)} j =#(2)D j *;(T s 1,2,3…3,2,1;T s+c 7,7,1…1;)

8 И форма 3-путей для Ts и Ts+c

9 Действие S n на мн-ве столбцов =перестановка номеров базисных векторов = автоморфизм n-куба. Разбиение для матрицы Т: {#(2)D 1 *;#(2)D 2 *;…#(2)D n *}-> (T) инвариант для определения классов эквивалентности k-путей в n-кубе (D i *-i-ый столбец матрицы Т). Класс эквивалентности своя форма «жгута» кратчайшего k-пути.

10 Каждый класс своя внутренняя «кривизна» k-пути

11 Динамика расщепления матрицы Т s -генерация классов K(n,k)

12 Класс =(5,3 3,2 2,1 3 )

13 Класс =(6,5,3,2,1 5 )

14 Оценка числа классов. k С(k-i/n-k-i) K(n,k) {k(n-k+1),n,n-k+1}; i=1 Пример: 16 K(9;3) < 45;

15 Cпасибо за внимание!