Изменения
→Декомпрессор
{{Определение
|definition=
Назовём '''декомпрессором''' (англ. decompressor) <tex>D : \{0, 1\}^* \to
\left[\begin{array}{l}\{0, 1\}^* \\
\bot\end{array}\right.</tex> алгоритм, восстанавливающий разжатый текст из сжатого.
Пусть <tex>x \in \{0, 1\}^* </tex>, тогда назовем '''колмогоровской сложностью''' строки <tex>K_D(x) = \min \limits_{y}\ \{|y|\ |\ D(y) = x \}</tex>, размер минимальной строки <tex>y</tex>, такой, что <tex>D(y) = x</tex>. <br> Если такого <tex>y</tex> не существует, тогда <tex>K_D(x) = +\infty</tex>.
}}
===Примеры===
* <tex>D(x) = x</tex>, тогда <tex>K_D(x) = |x|</tex>
