Как стать автором
Обновить
131
0
Александр Смаль @avsmal

преподаватель

Отправить сообщение

Не смог пройти мимо

Мне кажется, что в статье не хватает всё же каких-то более строгих и конкретных утверждений.

  1. Во введении я бы рекомендовал более подробно написать, что исследуется сложность последовательности задач, зависящая от N. И может быть привести какой-то пример. Кроме того, слово "конечный" используется в разных смыслах и не всегда ясно, что имеется в виду.

  2. Как правильно отмечено, в некоторых играх оценивается не сложность поиска выигрышной стратегии, а сложность поиска оптимального хода или стратегии при известной конфигурации. Собственно, хотелось бы более ясно понимать, для какой игры что именно оценивается. Формулировка "сложность игры" неоднозначна.

  3. Амазонки. Не ясно, как устроена игра размера N. Изменяется только размер доски или количество амазонок тоже?

  4. Криптарифмы. Аналогично, совершенно не ясно как устроена задача размера N. А следующая фраза, очевидно, сформулированна некорректно: "Однако при использовании других систем счисления, является NP-полной." (других, это каких? двоичная система счисления подходит? Очевидно, что нет.) Как основание системы счисления должно зависеть от N?

  5. Пятнашки. Тут понятна задача, но совершенно не ясен смысл фразы "Что интересно «не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек N×N за разумное время»". Что значит "разумное"?

  6. Го и шахматы. Аналогично. Как устроена задача для размера N. Какие фигуры в шахматах N x N?

В каждом определении зашита некоторая субъективность.

В определении Хартли "наши знания" определяются "областью поиска".

В определении Шеннона - тем, какие вероятности мы назначаем событиям.

В определении Колмогорова субъективность зашита в конкретный способ описания.

Отвечаю на вопрос, который не понял сразу.

То есть, мне кажется, что вы должны были предполагать некоторую последовательность сообщений, длинна n которых стремится к бесконечности.

Нет, последовательность здесь не нужна. В том виде, в котором эта теорема записана, она верна для произвольной строки такого вида. Давайте сформулирую со всеми кванторами.

Теорема. Существует константа Cтакая, что для любогop\in [0,1], любого натурального n и битовой строки xс\lceil np\rceil единицами выполняется: K(x) \le n\cdot h(p) + C\cdot(1+\log n), где h(p) = - p\log p - (1-p)\log(1-p).

Я вроде бы точно описал про стреление к 1 ....

Да, тут я неправильно понял ваше утверждение.

то для достаточно больших n это утверждение верно, но не для всех n.


Верно для всех nначиная с некоторого момента (момент зависит от \epsilon). Точно так же ваше утверждение про среднюю длину вашего кодирования верно не для любого n, а начиная с некоторого момента:

... я смогу назвать вам такое натуральное "эн" и такой способ записи натуральных чисел с разделителителем, что для сообщения любой длинны "эм" большей "эн" описанный мной способ кодирования даст математическое ожидание длины шифровки не более чем в (1+"эпсилон") раз превышающюю энтропию этого сообщения.

Мой тезис заключается в том, что колмогоровская сложность в своем рафинированном виде никак не может помочь на него ответить.

Я и не делал из этого формального утверждения. Я явно написал об этом в первом же комментарии. Я говорил только о том, что такой подход позволяет объяснить интуицию.

Всегда есть машина Тьюринга, которая напечатает данный конкретный текст "на пустом" входе.

Это не проблема, а совершенно естественный и ожидаемый эффект, согласующийся с интуицией. У разных людей могут быть разные множества текстов, которые им кажутся не "случайными", т.к. каждый оценивает сложность относительно своего собственного способа описания.

Рассмотрим следующий эксперимент. Возьмём двух человек, Алису и Боба. Сгенерируем "настоящий" случайный текст, покажем его Алисе и просим её запомнить. После этого возьмём новый листок со "случайным" текстом, покажем его обоим игрокам и попросим каждого сказать, верит ли он/она, что этот текст получен в результате случайного набора на клавиатуре. Если второй текст совпадает с первым, то Боб скорее всего скажет, что текст похож на случайный (т.к. первый был случайным), а Алиса скажет, что она только что видела точно такой же текст, поэтому не верит, что именно он получился в результате случайного набора. Это и соответствует тому, что в её способе описания этот текст имеет очень короткое описание "такой же, как мне показали до этого".

Да, насчет разделителя я был не точен, но ведь это не меняет сути дела: двойной логарифм (1/p) для достаточно малых p будет пренебрежимо мал по сравнению с "просто" логарифмом (1/p).

И всё же тут нужно быть аккуратным. Если в вашем способе кодирования вы добавляете разделитель на каждый символ, то в сумме получитсяO(n\log\log n)(то, что "характерная" длина промежутка равна 1/p, не исключает возможности, что будет много промежутков порядка n). А добавка такого размера уже может быть сравнима nH(...). Энтропия может быть очень маленькой и поэтому добавлять что-то на каждый символ — не самая хорошая идея. Вполне возможно, что если аккуратно всё посчитать и применить неравенство Йенсена, то всё сойдётся, но мне не кажется это совсем уж очевидным.

Колмогоровская сложность одного объекта - есть понятие зависящие от языка. Подходящим выбором языка она может быть сделана любой, как очень большой, так и равной нулю.

Выбор языка не является параметром. В классическом определении мы в качестве языка выбираем совершенно конкретную универсальную машину Тьюринга. Можно выбрать и другой способо, но как было сказано, результат изменится не более, чем на константу.

Однако если как-то задана последовательнсть конструктивных объектов

Что значит "конструктивных" объектов? Все конечные строки конструктивны. Но для конечных строк это утверждение

отношение обоих сложностей будет стремится к 1.

просто не верно. Возьмём произвольную последовательность строк сложности nи последовательность нулей (сложность будет \log n). Отношение сложностей будет в пределе будет бесконечным.

Мне кажется это единственный способ корретно приписать смысл вашего утвержения об "колмогоровской сложности (случайных?) последовательностей из np единиц и mp нулей". То есть, мне кажется, что вы должны были предполагать некоторую последовательность сообщений, длинна n которых стремится к бесконечности.

Про какое утверждение идёт речь? Про теорему в секции "Связь с энтропией Шеннона"? Это теорема. Ничего про случайность там нет. Теорема говорит о том, что колмогоровская сложность любой строки такого вида длины nограничена nh(p) + O(\log n) (константа в O общая для всех строк и не зависит n). Докательство я привёл двумя комментариями выше.

Если вы мне назовете алфавит ... (1+"эпсилон") раз превышающюю энтропию этого сообщения.

Эту часть я понял сразу. Повторюсь, что моё замечание было только по форму утверждения. Вы не ограничиваете способ кодирования, так что вполне достаточно было бы просто записать частоты и назвать номер последовательности в лексикографическом порядке всех последовательностей с такими частотами. Получилось бы такая же оценка.

Да "эн" в действительности будет непрактично большим, однако я задам способ равномерно по всем длинным сообщениям, а не для какой-то конкретной их последовательности. Например, вы можете генерировать только сообщения какой-то определенной большой длинны "эм" - мое утверждение останется верным, а вот о колмогоровской сложности (ее математическом ожидании) на сообщениях этой конкретной длинны говорить не приходится - все зависит от языка описания.

Вы как-то смешиваете ваш способ кодирования и колмогоровскую сложность, что я не могу понять, что вы мне хотите доказать. Вы говорите, что начиная с некоторого nсредняя длина кода будет nH(1+\epsilon).Но ровно такое же утверждение верно и для колмогоровской сложности. Единственная разница, что n, начиная с которого это будет выполняться, сложно задать контретно. Для вычисления придётся запрограммировать генератор такой последовательности на машине Тьюринга.

это все-таки больше теорема об энтропии: никакое описание в среднем не может быть меньше энтропии

В вашей формулировке два понятия: описание и энтропия. Как вы решили, что это формулировка больше об энтропии, чем об описаниях?)

однако подходящим выбором достаточно грамоздкого языка может быть сделано сколь угодно большим.

Ещё раз повторюсь, что способ описания не является параметром.

Да, и нет тут никакой колмогоровской сложности, не вводите себя в
заблуждение - у меня конечная, хоть и очень длинная последовательность сиволов.

Любой алгоритм кодирования битовых последовательностей задаёт верхнюю оценку на колмогороскую сложность с точностью до константы. В тексте поста есть такая теорема о связи энтропии и колмогоровской сложности.

Вы снова пытаетесь применять теоремы о колмогоровской сложности к конечным конструктивным объектам

И какую теорему я применил? )

она в них безсильна.

Не понял этого утверждения. Мы тут рассматриваем не конкретную длину, а асимптотическую оценку. Какая бы не была константа вылезающая из "нужной громодкости" при асимптотических рассуждениях (а тут речь именно про них и вы сами об это пишете) её вкад будет ничтожен.

1) частоты предполагаются чрезвычайно малыми, следовательно логарифм и логарифм плюс единица - в относительном мастабе по сути равны (устремляя частоты к нулю можно сделать (математическое ожидание) эти отношения сколь угодно близкими к единице)

У вас не получится сделать разделитель однобитным: для кодировки пары чисел суммарной длины mнужно порядка \log m + O(\log\log m)битов. Соответственно, на каждый разделитель потребуется порядкаO(\log\log(1/p)).

но для неслучайных последовательностей нужно делать оговорки. (...)
Применять понятие энтропии к неслучайным последовательностям

Не очень понимаю, что вы имеете в виду. Как вы сами правильно заметили для конечных последовательностей не получается формально определить понятие случайности. Это, кстати, и к вашему способу кодирования относится. Вы там пишете про "случайнонабранное сообщение", а по сути просто хотите сделать оценку в среднем.

Применять понятие энтропии к неслучайным последовательностям

Я его нигде и не применяю, т.к. энтропия определена не для последовательностей, а для случайных величин.

Эти рассуждения в другом сеттинге. Речь в разделе про кодирование шла про коды, которые кодируют отдельно каждый символ. То, что вы доказываете в первом абзаце — это оценка колмогоровскую сложность строки длины n с np единицами (вы приводите некоторый способ кодирования, который к посимвольным кодам не имеют никакого отношения). То же самое можно получить, просто указав номер этой последовательности среди всех последовательностей длины n с np единицами. Таких последовательностей: \binom{n}{np}. Для записи такого числа потребуется

\log_2 \binom{n}{np} = \log_2 \frac{n!}{(np)!(n(1-p))!}\approx \log_2 \frac{\mathrm{poly}(n)\cdot (n/e)^n}{(np/e)^{np}(n(1-p)/e)^{n(1-p)}}

Сокращает на (n/e)^nи получаем

\log_2 \frac{\mathrm{poly}(n)}{p^{np}\cdot(1-p)^{n(1-p)}} = n\left(p\log_2\frac{1}{p} + (1-p)\log_2\frac{1}{1-p}\right) + O(\log n)

В этом случае не нужно ничего предполагать про "характерное расстояние". В вашем рассуждении с этим есть проблема. Если для записи расстояния не хватило -\log_2pсимволов, то не понятно, что с этим делать. Добавлять разделители?

Идею про отсутствие то, как определять, что начались числа для следующего числа я тоже не понял (когда сумма перевалила за n). Ведь при таком кодировании могут быть неоднозначности: прn=5последовательность 2, 1, 1... может разбиваться как (2,1) (1,..., так и как (2) (1,1,.... Либо нужно как-то кодировать количество чисел в самом начале.

Для kсимволов это тоже обоющается (картинка из моего конспекта, переписывать лень)

Ваша нижняя оценка предлагает именно такое рассуждение выше с подсчётом числа последовательностей такого вида. Но она тоже по сути про колмогоровскую сложность, т.к. вы никак не пользуетесь тем, что это именно код определенного вида. Её с соответствующими оговорками и пояснениями можно применить к любому кодированию, но мы потеряем ту точность, что есть в соответствующей теореме Шеннона.

Информативность относительно языка? Слово "стена" не несёт информацию само по себе, а количество передаваемой им информации зависит от контекста. Сомневаюсь, что такие (математические) модели существуют.

Спасибо за содержательный комментарий.

  1. Я не ставил перед собой задачу объяснить, откуда там в теоремах Шеннона для кодов возникает энтропия. Это почти нереально сделать в рамках такого обзора. При этом я постарался в меру своих возможностей объяснить, почему формула для энтропии именно такая. Не уверен, что это хорошо получилось, но это действильно важный момент, вы совершенно правы.

  2. Про объяснение случайности для конечных объектов вы правы, что нет возможности определить случайность для конечных объектов без фиксации способа описания. Но я здесь и не пытаюсь определить случайность для конечных объектов, а только объясняю человеческую интуцию, которая неплохо позволяет отличать "случайные" и "неслучайные" тексты. Всё, что я хотел сказать, это то, что текст, который для конкретного человека кажется "неслучайным", это обычно текст имеющий какие-то завимости и закономерности с точки зрения конкретного человека, т.е. не текст не максимальной сложности относительно способа описания конкретного человека. В этом случае мы по сути зафиксировали способ описания тем, зафиксировали человека. Так что никакой проблемы тут нет. При этом определение случайной последовательности я даю только для бесконечных последовательностей.

    На замечание про сырость и вредность позволю себе не отвечать. Отмечу только, что вопрос о существовании абсолютного понятия сложности не кажется мне таким очевидным.

С математической точки зрения это просто константа, зависящая от выбора универсального способа описания.

На практике её можно попытаться оценить сверху при помощи сжатия. Если сжали до 2Мб, то можно считать, что информации там не более 2Мб. Для текстов это неплохо работает, а вот для числа \piбудет работать плохо.

Прямого отношения к Степику не имею, но дружу с ними. Про видеозаписи — это хороший вопрос. Если там будет такая возможность, то сделаем записи и выложим их, конечно. Если вас подобная тематика интересует, то посмотрите на курсы Computer Science клуба. Там много значительно более подробных курсов, в том числе и курсы по некоторым из тем, представленных на школе.
Хороший вопрос) У каждого предподавателя есть личная страничка и там у некоторых есть ссылка на github и на другие проекты. Добавлять в статью нет смысла, т.к. он не об этом, да и эта информация быстро потеряет актуальность.
Производная произведения (ab)' вычисляется по формуле: (ab)' = a'b + ab'.
exp(x) — это то же самое, что e в степени x.
Видео теперь доступно по ссылке на лекцию (вчера только лекция была, я не успел залить).
Программа обучения открыта, так что судите сами. Там действительно встречаются курсы, которые по программе могут пересекаться с тем, что изучается в бакалавриате, но обычно это компенсируется глубиной изложения. Т.е. название курса такое же, но курс более продвинутый и глубокий.
А можете уточнить, про какие именно задачи идёт речь? Вроде бы первые две задачи решаются школьными методами. Третья — тоже (если забыть про возможность отсутствия предела, но в тесте требуется только ввести ответ). Для задач 4 и 5 достаточно начальных знаний из университетского курсов теории вероятностей и дискретной математики. Задача 6 — задача на интеграл, обычно это на первом курсе проходят.
Расстояние между 4 и 8 равно 8 — 4 = 4, что больше чем 2.

Информация

В рейтинге
Не участвует
Откуда
Санкт-Петербург, Санкт-Петербург и область, Россия
Дата рождения
Зарегистрирован
Активность