Полуквантовое кодирование в компьютерных многомерных комбинаторно-топологических моделях. Г.Г.Рябов (НИВЦ МГУ) Доклад на XII международной конференции. - презентация

1 Полуквантовое кодирование в компьютерных многомерных комбинаторно-топологических моделях. Г.Г.Рябов (НИВЦ МГУ) Доклад на XII международной конференции «Информационные средства и технологии».Москва.МЭИ.2009 Работа поддержана грантом РФФИ ( ) Работа поддержана грантом РФФИ ( )

2 Геометрико-топологические модели в современной науке. Модели-посредник между теоретическими построениями и компьютерными методами расчетов. Модели-посредник между теоретическими построениями и компьютерными методами расчетов. Решетки, сетки, симплициальные и кубические комплексы, многообразия… Решетки, сетки, симплициальные и кубические комплексы, многообразия… Многомерность и комбинаторная сущность квантовых систем как это отразится на суперкомпьютерах следующих поколений? Многомерность и комбинаторная сущность квантовых систем как это отразится на суперкомпьютерах следующих поколений?

3 Кубические структуры. Многие комбинаторные структуры вложимы в кубические комплексы. Многие комбинаторные структуры вложимы в кубические комплексы. Комплексы изучаются в пространствах R n c (вершины- целые точки Z n ). Комплексы изучаются в пространствах R n c (вершины- целые точки Z n ).

4 Глобальная модель климата (MIT gcm) и корректирующие коды. Кубическая сфера с конформной решеткой – база всех климатических расчетов. Кубическая сфера с конформной решеткой – база всех климатических расчетов. Хэммингово расстояние между кодами- вершинами n-куба – базовая мера в теории корректирующих кодов. Хэммингово расстояние между кодами- вершинами n-куба – базовая мера в теории корректирующих кодов.

5 Кубические комплексы в I n (R n ). 0-грани- вершины, 0-грани- вершины, 1-грани- ребра, 1-грани- ребра, 2-грани-квадраты 2-грани-квадраты 3-грани-кубы 3-грани-кубы 4-грани и т.д. 4-грани и т.д. f(k)=C n k 2 n-k ; f(k)=C n k 2 n-k ;

6 Пирамида Паскаля и k-мерные грани n-куба. Пирамида Паскаля- рекурсивная процедура в трехмерной решетке. Пирамида Паскаля- рекурсивная процедура в трехмерной решетке. Сумма чисел вдоль ребер (y=k) в плоскости х+y+z=n равна числу k-граней в n-кубе. Сумма чисел вдоль ребер (y=k) в плоскости х+y+z=n равна числу k-граней в n-кубе.

7 Биекция: множество всех n- разрядных троичных кодов множество всех граней n-куба. E=e 1,e 2,…e i,…e n ; R n ; E=e 1,e 2,…e i,…e n ; R n ; D=d1,d2,…di,…dn; di {0,1,2}; D=d1,d2,…di,…dn; di {0,1,2}; E D; ei di; E D; ei di; e 2 xe 4 xe 5 транс. в вершину ; трехмерная грань(куб) в шестимерном кубе e 2 xe 4 xe 5 транс. в вершину ; трехмерная грань(куб) в шестимерном кубе.

8 Грани в I 3. Все грани в I 3 - все трехразрядные троичные коды. Все грани в I 3 - все трехразрядные троичные коды. Алфавит {0,1,2} Алфавит {0,1,2} 222-весь I весь I 3.

9 Кубанты Кубант в n-мерном евклидовом простанстве –троичный n- разрядный код, отражающий размерность грани и ее положение в n-мерном единичном кубе. Кубант в n-мерном евклидовом простанстве –троичный n- разрядный код, отражающий размерность грани и ее положение в n-мерном единичном кубе.

10 Кубанты и в I 6.

11 Комплексы из кубантов в I 6. a).Комплекс из 3-х кубантов (3-куб,3-куб,4-куб). a).Комплекс из 3-х кубантов (3-куб,3-куб,4-куб). b).Комплекс из 9-и кубантов (8 квадратов и 3-куб). b).Комплекс из 9-и кубантов (8 квадратов и 3-куб).

12 Умножение (пересечение) кубантов. Умножение кубантов- поразрядная операция над словами, задаваемая данной таблицей. Умножение кубантов- поразрядная операция над словами, задаваемая данной таблицей. Ø-пустое множество. Ø-пустое множество.

13 Кубанты и псевдокубанты( с Ø) образуют полугруппу с единицей (моноид). Расширение алфавита {Ø,0,1,2}. Расширение алфавита {Ø,0,1,2}. Все четверичные n-разрядные слова (кубанты и псевдокубанты) образуют полугруппу по умножению. Все четверичные n-разрядные слова (кубанты и псевдокубанты) образуют полугруппу по умножению. Кубант х кубант=кубант или п/кубант. П/кубант х кубант=п/кубант. Кубант х кубант=кубант или п/кубант. П/кубант х кубант=п/кубант. Единица моноида-кубант 222…2. Единица моноида-кубант 222…2.

14 Машинное представление Ø 0;0 1;1 2;2 3; Таблица поразрядного умножения элементов моноида при машинном представлении. Таблица поразрядного умножения элементов моноида при машинном представлении.

15 Свойства произведения кубантов. П(D1,D2)=D3; П(D1,D2)=D3; ω(D3) = число разрядов с Ø. ω(D3) = число разрядов с Ø. Если ω(D3)=0,то D3–кубант-пересечение. Если ω(D3)=0,то D3–кубант-пересечение. Если ω(D3)= r>0, то Lmin(D1,D2)=r; (минимальный путь по ребрам n-куба- обобщение метрики Хэмминга для двоичных кодов). Если ω(D3)= r>0, то Lmin(D1,D2)=r; (минимальный путь по ребрам n-куба- обобщение метрики Хэмминга для двоичных кодов). Структура комплекса полностью определяется перемножением кубантов. Структура комплекса полностью определяется перемножением кубантов.

16 Матрица парных произведений. D1=112202; D2=121122; D3=122211; D1=112202; D2=121122; D3=122211; D4=120122; D5=002212; D4=120122; D5=002212; Ø ØØ22Ø Ø ØØ22Ø Ø122 Ø Ø122 Ø Ø Ø Ø Ø D1,D2,D3,D4-образуют цикл (общие ребра, D5 отстоит на Lmin=1 от D2,D3,D4 и на Lmin=3 от D1; D1,D2,D3,D4-образуют цикл (общие ребра, D5 отстоит на Lmin=1 от D2,D3,D4 и на Lmin=3 от D1; Обобщение матрицы смежностей для графов. Обобщение матрицы смежностей для графов.

17 Хаусдорфова метрика на кубантах (обобщение метрики Хэмминга) р Н (D1,D2)=max{max minL(D1 D2),max minL(D2 D1)}; р Н (D1,D2)=max{max minL(D1 D2),max minL(D2 D1)}; Хаусдорфово сжатие D1/D2=D1* и D2/D1=D2*;Cамое большое L из самых коротких путей.Сжатие-поразрядная операция. Хаусдорфово сжатие D1/D2=D1* и D2/D1=D2*;Cамое большое L из самых коротких путей.Сжатие-поразрядная операция Ø122ØØ ØØ2211 max{ 3,2}=3 pH=3; Ø122ØØ ØØ2211 max{ 3,2}=3 pH=3;

18 Полная матрица Н-метрики для кубантов I 3. Обозначения: Обозначения: Черный-3 Черный-3 Тем.сер.-2 Тем.сер.-2 Свет.сер.-1 Свет.сер.-1 Белый-0 Белый-0

19 Структура матрицы Н-метрики для кубантов I n. Матрица 3 n x3 n Матрица 3 n x3 n Миноры Н(k,m) k x m, где k,m- размерности граней. Миноры Н(k,m) k x m, где k,m- размерности граней. r = [s,t]-диапазон значений r H в миноре. r = [s,t]-диапазон значений r H в миноре.

20 Распределения значений Н-метрики по размерностям граней при n. Ассиметрия распределений. Ассиметрия распределений. r=0 3 n ; r=0 3 n ; r=n 4 n -2 n-1 ; r=n 4 n -2 n-1 ;

21 Панельное топологическое строительство. Бутылка Клейна в 75 байт. Всех комплексов из гиперграней 64-для хранения номера комплекса -один байт памяти. Всех комплексов из гиперграней 64-для хранения номера комплекса -один байт памяти.

22 Полиморфизм кубантов (четверичного кодирования). Cлово Cлово Число Число Множество точек R n. Множество точек R n. Геометрическая фигура Геометрическая фигура Часть топологического комплекса. Часть топологического комплекса. Элемент алгебраической структуры (моноид). Элемент алгебраической структуры (моноид). Результат одной операции содержит информацию о связности, мин пути, размерности пересечения, положении внутри n-куба. Результат одной операции содержит информацию о связности, мин пути, размерности пересечения, положении внутри n-куба. Кубанты-гиперметрическое пространство. Кубанты-гиперметрическое пространство.

23 Кубанты и супервычисления. Поразрядные операции над четверичными словами практически неограниченной длины, равной размерности исследуемого пространства. Поразрядные операции над четверичными словами практически неограниченной длины, равной размерности исследуемого пространства. Перевод вычисления метрики Хаусдорфа для кубантов из задач сложности 2 n в задачи сложности n 2. Перевод вычисления метрики Хаусдорфа для кубантов из задач сложности 2 n в задачи сложности n 2. Хранение в табличном виде (заранее рассчитанных) n- мерных комплексов гиперграней (нумеративный подход). Хранение в табличном виде (заранее рассчитанных) n- мерных комплексов гиперграней (нумеративный подход). Исследования асимптотического поведения гиперрешеток (10d-11d) в интересах теоретической физики. Исследования асимптотического поведения гиперрешеток (10d-11d) в интересах теоретической физики. Одна из проблем-значительное расширение оперативной памяти суперкомпьютера.Для 10d рабочее поле со стороной 100 требует память объемом 10 8 терабайт. Одна из проблем-значительное расширение оперативной памяти суперкомпьютера.Для 10d рабочее поле со стороной 100 требует память объемом 10 8 терабайт.

24 Инструментальная система «Топологический процессор».

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

26 Приложение.Многомерные построения k-путей.

27 Многомерные построения k-путей

28 Н-метрика в k-путях.

29 Многомерные построения. Процесс расслоения Процесс расслоения Процесс слияния Процесс слияния Следы процесса на гранях пространст ва- полиэдра Следы процесса на гранях пространст ва- полиэдра

30 Случайная динамика в n-кубе.

31 3-пути (траектории) события (встречи).

32 Вероятная история события.

33 Спасибо за приглашение и внимание! Интернет журнал «Вычислительные методы и программирование» т.10,2009,с Интернет журнал «Вычислительные методы и программирование» т.10,2009,с