Простая колмогоровская сложность: определение и теорема о существовании оптимального декомпрессора. Энтропия Шеннона как верхняя оценка для колмогоровской сложности. Теорема Колмгорова—Левина о сложности пары. Симметричность взаимной информации и информационные неравенства для колмогоровской сложности.