ГлавнаяАрхивО понятии равносильности недоопределённых алфавитов

О понятии равносильности недоопределённых алфавитов | Прикладная дискретная математика. 2014. № 3 (25).

Для недоопределённых алфавитов предложена формализация понятий: а) один алфавит сильнее другого и б) алфавиты равносильны. Рассмотрены несколько подходов к определению этих понятий. Функциональный подход основан на выразимости одного алфавита через другой, три остальных подхода - комбинаторный, вероятностный и алгоритмический - терминологически связаны с подходами Колмогорова к введению меры информации. Доказано, что эти подходы к сравнению алфавитов эквивалентны. Если алфавиты равносильны, то решение задачи оптимального сжатия для одного алфавита фактически обеспечивает решение этой задачи и для второго. Установлено, что соотношения (а) и (б) допускают проверку за полиномиальное время.
  • Title О понятии равносильности недоопределённых алфавитов
  • Headline О понятии равносильности недоопределённых алфавитов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3 (25)
  • Date:
  • DOI
Ключевые слова
Kolmogorov complexity, entropy of underdeter-mined data, alphabets of equal strength, underdetermined alphabet, сложность по Колмогорову, энтропия недоопределённых данных, равносильные алфавиты, недоопределённый алфавит
Авторы
Ссылки
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416с.
Потапов В. Н. Обзор методов неискажающего кодирования дискретных источников // Дискретный анализ и исследование операций. 1999. Сер. 1. Т.6. №4. С.49-91.
Шоломов Л. А. О функционалах, характеризующих сложность систем недоопределенных булевых функций // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 123-139.
Шоломов Л. А. Элементы теории недоопредёленной информации // Прикладная дискретная математика. Приложение. 2009. №2. С. 18-42.
Галлагер Р. Теория информации и надежная связь. М.: Сов. радио, 1974. 720 с.
Шоломов Л. А. Разложение недоопределенных данных // Дискретный анализ и исследование операций. 2012. Т. 19. №6. С. 72-98.
Шоломов Л. А. Преобразование нечетких данных с сохранением информационных свойств // Дискретный анализ и исследование операций. 2005. Сер. 1. Т. 12. №3. С. 85-104.
Колмогоров А. Н. Три подхода к определению понятия «количество информации» // Проблемы передачи информации. 1965. Т. 1. Вып. 1. С. 3-11.
О понятии равносильности недоопределённых алфавитов | Прикладная дискретная математика. 2014. № 3 (25).
О понятии равносильности недоопределённых алфавитов | Прикладная дискретная математика. 2014. № 3 (25).