Неравенство Крафта - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:43:38Z

rollbackEdits.php mass rollback

185.220.100.241 в 03:24, 1 сентября 2022

2022-09-01T03:24:23Z

Lapenok.aleksej в 13:01, 19 марта 2018

2018-03-19T13:01:52Z

Damm1t в 23:12, 4 января 2018

2018-01-04T23:12:57Z

Damm1t в 22:47, 4 января 2018

2018-01-04T22:47:24Z

Damm1t в 22:24, 4 января 2018

2018-01-04T22:24:30Z

Damm1t в 21:43, 4 января 2018

2018-01-04T21:43:06Z

Damm1t в 21:39, 4 января 2018

2018-01-04T21:39:47Z

Damm1t в 21:23, 4 января 2018

2018-01-04T21:23:00Z

Damm1t в 21:21, 4 января 2018

2018-01-04T21:21:55Z

← Предыдущая		Версия 16:43, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
−

	Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.		Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.

← Предыдущая		Версия 03:24, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
		+

	Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.		Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.

@@ Строка 5: / Строка 5: @@
 |about=неравенство Крафта
 |statement=
-  Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которые имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>.
+  Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которых имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>.
 Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:

@@ Строка 36: / Строка 36: @@
 #Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .
 #:Пусть у нас есть <tex>n</tex> символов, кодовые слова имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. Давайте разделим данные символы на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса.
-#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен:
+#:Докажем, что в таком случае группа будет либо полностью укомплектована <tex>(\sum\limits r ^{-l_i} = \dfrac{1}{r})</tex>, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен:
 #: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center>
 #:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i - l_j</tex> неотрицательно при <tex> i \geqslant j </tex> , и <tex> r \in \mathbb{N} </tex>. Следовательно числитель — натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма группы <tex> \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.

@@ Строка 5: / Строка 5: @@
 |about=неравенство Крафта
 |statement=
-  Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>.
+  Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которые имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>.
 Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:
@@ Строка 35: / Строка 35: @@
 #Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> .
 #Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .
-#:Пусть у нас есть <tex>n</tex> символов, кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. Давайте разделим данные символы на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса.
+#:Пусть у нас есть <tex>n</tex> символов, кодовые слова имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. Давайте разделим данные символы на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса.
 #:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен:
 #: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center>

← Предыдущая		Версия 22:24, 4 января 2018
Строка 30:		Строка 30:

	'''Достаточность:'''		'''Достаточность:'''
		+
		+	[[file:Tree2forkraft.jpg\|thumb\|300px\|Пример разбиения на группы, при <tex> r = 2</tex>, символах ''a, b, c'', где <tex> l_a = 2, l_b = 2, l_c = 1</tex>]]

	#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> .		#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> .

@@ Строка 37: / Строка 37: @@
 #: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center>
 #:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i - l_j</tex> неотрицательно при <tex> i \geqslant j </tex> , и <tex> r \in \mathbb{N} </tex>. Следовательно числитель — натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма группы <tex> \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.
 #Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.
 #По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен.

@@ Строка 7: / Строка 7: @@
   Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>.
-Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:
+Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:
 <center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center>