Аноним

Коды Ли: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Коды Ли''' (''Lee scheme'') - относятся к классу ''линейных кодов'' деревьев. Пусть <m...)
 
Нет описания правки
Строка 1: Строка 1:
'''Коды Ли''' (''Lee scheme'') -  
'''Коды Ли''' (''[[Lee scheme]]'') - относятся к классу ''[[линейный код|линейных кодов]]'' [[дерево|деревьев]]. Пусть <math>T</math> --- [[бинарное дерево]], каждая [[внутренняя вершина]] помечена числом 1, а каждая [[висячая вершина|висячая]] --- числом 0. Рассматриваются следующие вариации кодов Ли:
относятся к классу ''линейных кодов'' деревьев. Пусть <math>T</math> --- бинарное дерево,
каждая внутренняя вершина помечена числом 1, а каждая висячая --- числом 0. Рассматриваются следующие вариации кодов Ли:


1) <math>u</math>-''кодом Ли'' дерева <math>T</math> называется последовательность пометок вершин, написанных в порядке обхода его в ширину;
1) <math>u</math>-''кодом Ли'' дерева <math>T</math> называется последовательность [[пометка|пометок]] [[вершина|вершин]], написанных в порядке [[обход графа в ширину|обхода его в ширину]];


2) <math>p</math>-''кодом Ли'' дерева <math>T</math> называется последовательность номеров единиц в <math>u</math>-коде дерева
2) <math>p</math>-''кодом Ли'' дерева <math>T</math> называется последовательность номеров единиц в <math>u</math>-[[код дерева|коде дерева]] <math>T</math>, перечисленных в порядке их возрастания;
<math>T</math>, перечисленных в порядке их возрастания;


3) ''поуровневый позиционный код Ли'' дерева <math>T</math> высоты <math>h</math> --- это последовательность
3) ''поуровневый позиционный код Ли'' дерева <math>T</math> высоты <math>h</math> --- это последовательность <math>M=M_1,M_2,\ldots,M_{h-1}</math>, где <math>M_i</math> --- последовательность номеров внутренних вершин [[уровень вершины|уровня]] <math>i</math>, перечисленных в порядке их возрастания.
<math>M=M_1,M_2,\ldots,M_{h-1}</math>, где <math>M_i</math> --- последовательность номеров внутренних
вершин уровня <math>i</math>, перечисленных в порядке их возрастания.


См. также ''Код Гапта для 2-3-деревьев, Коды, свободные от повторений, Коды с дублированием номеров вершин, Коды с использованием ограничителей, Линейный код, Уровневые коды корневых деревьев, Ротационный код.''
[[Файл:Lee scheme.png|500px]]
 
==См. также==
''[[Код Гапта для 2-3-деревьев]], [[Коды, свободные от повторений]], [[Коды с дублированием номеров вершин]], [[Коды с использованием ограничителей]], [[Линейный код]], [[Уровневые коды корневых деревьев]], [[Ротационный код]].''
==Литература==
==Литература==
[Евстигнеев-Касьянов/94]
[Евстигнеев-Касьянов/94]