Как решаются подобные задачи?

На лекциях объясняли.

а вот и нет.

Есть что по делу сказать?

Первая ассоциация — теория информации: оптимальный префиксный код. Хотя в данном случае, да, можно проще.

a) log2(кол-во символов), округлять вверх

б) кол-во символов умножить на пункт а

http://ru.wikibooks.org/wiki/Системы_счисления

Я не прошу чтобы за меня решили. Мне достаточно объяснения.

Тыц :)

разве это то?

Исключительно ради проверки. Ответ на пункт б = 5 ?

б) посчитайте в байтах объём информации который содержится в письме числа 31214

Даже вопрос нормально сформулировать не могут.

а) log2(5) = 3 бита на символ

б) 3 * 11 символов = 33 бита

Это разве не для позиционных систем счисления?

Причём тут СС? Чмсло вам показали чтобы запутать. Имеем некоторый алфавит и сообщение на нём.

Древнекритский ребус.

Теперь понял. Спасибо)

в байтах

В байтах да 5

Объясняю. Допустим, алфавит: a-1 b-10 c-100 d-1000 e-10000

Допустимые варианты - это

eeedddcba

Недопустимые -

abcde

То есть есть ограничение на порядок следования символов, за счет чего количество информации принципиально иное.

Недопустимые

Это откуда? Не было такого. У меня все ходы записаны.

В непозиционных системах порядок не имеет значения.

А посмотри, как кодируется число по ссылке. Там как раз аналог eeeddcbbaaaa.

Возможно, я что-то перепутал, но согласно википедии

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

Что и показано на второй ссылке.

Не выдумывай. Или ты в этих значках вычитал?

Да. Смотри сам.

Число - 31214

Запись - три значка, означающих 10000, один, означающий 1000, два, означающих 100, один 10, четыре по одному.

Аналогия видна?

От перестановки слагаемых сумма не меняется.

Верно. В отличие от позиционной системы счисления, формулы для которой ты и привел.

Это формулы для сообщения с помощью некоторого алфавита.

Хорошо. Но здесь они неприменимы по причине того, что в сообщении переставлять местами символы нельзя, иначе его суть изменится. Здесь - можно.

Хорошо. Но здесь они неприменимы по причине того, что в сообщении переставлять местами символы нельзя, иначе его суть изменится. Здесь - можно.

Но здесь они неприменимы ... Здесь - можно.

Быстрей разупоряйся - завтра понедельник :)

А по делу сказать есть что?

Возьмем простейший случай. Алфавит - 1 и 0

Если имеет значение позиция символов, сообщение 10011100 содержит ровно 8 бит информации. Если позиция значения не имеет, то важно только то, что в сообщении 4 нуля и 4 единицы, и требуется только 6 бит - 3 на количество нулей и 3 на количество единиц.

Пример ясен?

Мне достаточно объяснения.

Я сам подумать попробуй. Закодировать ты можешь любое десятичное число длиной не более 5 цифр. Нуля наверно есть (пустое сообщение). И того 10^5 вариантов. Ну а дальше логарифм по основанию 2.

Ты изобрел сжатие. Но в случае ТС'а таких указаний не было. Сказано

содержится в письме числа

Я показал отличие количества информации при позиционной и непозиционной записи. У ТС она непозиционная, это видно из второй ссылки. Ты дал формулы для позиционной. Ergo, твои формулы неприменимы в случае ТС.

в письме числа

В ЗАПИСИ числа!

Чьорд. Пойду тоже что ли пиваса возьму.

Именно в записи. Если запись подчиняется определенной структуре, то количество информации, заложенное в этой записи, меньше, чем если бы она была абсолютно неструктурирована.

Что такое количество информации?

За единицу количества информации принимается такое количество информации, которое содержится в информационном сообщении, уменьшающем неопределенность знания в два раза.

Приняв это определение, посмотрим, как увеличивается информация в ЗАПИСИ при добавлении к этой записи одного символа.

В случае неструктурированной записи, действительно, оно увеличивается на ceil(log_2(5)) бит.

В случае структурированной, как у ТС записи, новый элемент может быть либо текущим, либо следующим за ним. То есть информация увеличивается только на один бит.

То есть информация увеличивается только на один бит.

Отнюдь. А какой стартовый элемент, чтоб считать его текущим?

обычная десятичная система счисления. Просто вместо 40 пишут ☣☣☣☣, здесь ☣ значит: «десятки».

Что-бы получить число символов, нужно сложить все ЦИФРЫ, например 3+1+2+1+4 == 11

Исправляюсь. Неточно описал. Текущий элемент действительно кодируется ceil(log_2(n)) битами информации. Пусть этот элемент - k<n. Но тогда следующий за ним, новый элемент, может быть только элементом >=k, то информация, данная следующим элементом, будет составлять только ceil(log_2(n-k+1)) бит.

Приняв это определение, посмотрим, как увеличивается информация в ЗАПИСИ при добавлении к этой записи одного символа.

при добавлении одного символа количество информации увеличивается неравномерно, и его так просто не посчитать. Смотря какое число, и какой символ. Можно посчитать группируя символы в метасимволы. Например ☣☣☣☣ == 40, а ☣☣☣☣☣ == 50. Тогда можно посчитать энтропию «4» и «5», она равна -log₂(1/10) (в битах).

А как разделить элементы? Чтоб было понятно, что следующая запись на бит меньше?

пояснение: после девяти ☣, энтропия ☣ равна 0, ибо мы знаем, что чисел с 10ю десятками не бывает. После восьми ☣, равна 1/10, ибо только в каждом десятом числе есть ровно 9 десяток.

ceil

откуда у тебя это взялось? Энтропия совсем не обязана быть целой. И да, она совсем никак не зависит от целой части логарифма. Да ещё и двоичного. Она зависит от дробной части десятичного логарифма, т.к. СС десятичная.

первый элемент задан точно. Второй - разница между тем, что должно и предыдущим. И так далее. То есть если следующий =k, то кодируется 0, если k+i, то i.

Так я об этом и говорю. Да, так можно, и количество информации при таком кодировании меньше, чем при кодировании каждого знакоместа ln_2(n) битами. А ceil - для компьютерного кодирования, там все целое.

Да, так можно, и количество информации при таком кодировании меньше, чем при кодировании каждого знакоместа ln_2(n) битами.

столько же. Если считать ценность одного «знакоместа» целиком.

А ceil - для компьютерного кодирования, там все целое.

энтропия в битах целая только если есть ровно 2^n равновероятных варианта. В общем случае энтропия дробная. Обычно она ещё и трансцендентная. Т.к. на практике нужно много кодировать, то и кодируют скажем 2 символа по 1.5 бита, тремя битами.

Если считать целиком. А у ТС оно зависит от предыдущих знакомест.

от предыдущих НЕ зависит. Пример: 123456? Как зависит "?" от предыдущих? Никак.

Зато знакоместо зависит само от себя, ибо оно из нескольких определённых символов.

из нескольких определённых символов.

Вот именно, оно зависит тем, что эти определенные символы определены предыдущими. То есть если взять нотацию, как я приводил выше, то к записи fffeedddcc можно добавить только c, b и a, но нельзя f, e и d. Вот таким образом зависит.

то к записи fffeedddcc можно добавить только c, b и a, но нельзя f, e и d. Вот таким образом зависит.

все меньше c можно добавлять, с равной вероятностью, от 0 до 9 штук. И это ни от чего не зависит. А вот саму c можно добавлять только от 0 до 7 штук, потому-что 2 уже есть. Энтропия больше c равна 0, ибо их вероятность известна, и равна тоже 0.

Энтропия количества символов c в данном случае ровно 3 бита, ибо 2³ вариантов(равновероятных и независимых).

Так. Верно. Но в запись мы добавляем лишь один символ. Это может быть c, b, a. В запись ffeedd можно добавить уже d, c, b, a. То есть количество информации, требуемой для записи одного следующего символа зависит от того, какие символы были ранее.

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