Делимость бита

← →
It's not me (2009-03-12 18:20) [0]

Наверняка, многие читали и посмеялись над цитатой с баша:

xxx: Сестра попросила решить задачку по информатике. Задача: Каким количеством бит можно закодировать 48 символов? Я ответил, что понадобится 6 бит. xxx: Сегодня она пришла из школы и сказала, что я ничего не знаю. Оказывается, ответ 5,5 бит, но это еще не все. xxx: В доказательство она мне привела учебник, где была решена похожая задача и ответ был 7,3 бита.

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

Но потом натолкнулся на обсуждение в забавном сообществе на эту тему, может кому и будет интересно. Вырезка:

1) на мат. уровне:

Объясняю. Предполжим, у нас есть текст длинной N символов, причём каждый символ принадлежит алфавиту из 48 букв. Таких сообщений — 48^N, следовательно одно такое сообщение может быть закодировано с помощью N*log2(48) битов. То есть один такой символ несёт log2(48) информации

2) на бытовом уровне (правда, по ходу немного некорректно, но для размышления):

Вопрос1: Что ты будешь на завтрак, яичницу ИЛИ кашу?
Ответ1: Кашу
В данном случае у спрашивающего была неопределенность (1 из 2), и ответ ее разрешил. Был передан 1 бит информации.

Вопрос2: У нас есть яичница, каша, запеканка и бутерброды. Что выберешь?
Можно ответить
Ответ2: яичницу.
Неопределённость была 1 из 4, и ответ её полностью снял. Этот ответ содержит 2 бита.

А можно ответить так:
Ответ3: Хрен знает... но кашу точно не буду!
И вот этот ответ содержит меньше, чем 1 бит информации. У спрашивающего всё еще осталась неопределённость (1 из 3). Ему осталось получить еще log2 3 = 1.58 бита, чтобы выполнить заказ.

Путано немного, но смысл примерно такой.

← →
It's not me (2009-03-12 18:22) [1]

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

← →
turbouser © (2009-03-12 18:28) [2]

Ничего удивительного :)))
http://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82

← →
Kostafey © (2009-03-12 18:45) [3]

> запостил чисто из любопытства, мне было интересно. Мож кто
> тоже удивится и задумается.

Да, когда впервые об этом услышал тоже сильно удивился.

Сейчас меня удивило другое: такие вещи уже в школе проходят?
Хорошая у вашей сестры школа! :)

← →
депутатъ (2009-03-12 19:01) [4]

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

← →
Palladin © (2009-03-12 19:06) [5]

> депутатъ (12.03.09 19:01) [4]

не путай теплое с мягким... ~90% теоретиков ни одного приложения не реализовали и фик чего знают о разработке как таковой... кстати обратное тоже верно )

← →
Rouse_ © (2009-03-12 19:56) [6]

как только мне покажут последовательность, которую процессор воспринимает как 5 с копейками бит, соглашусь со всем, включая кубиты :)

← →
Palladin © (2009-03-12 20:02) [7]

> Rouse_ © (12.03.09 19:56) [6]

а ты не путай мягкое с теплым... ~90% теоретиков понития не имеют, шо це таке процессор и почему нельзя по "человечески" подходить к понятию информации... особенно в плане ее объема и адресации... кстати обратное тоже верно :))))

← →
TUser © (2009-03-12 20:02) [8]

> Rouse_ © (12.03.09 19:56) [6]
>
> как только мне покажут последовательность, которую процессор
> воспринимает как 5 с копейками бит, соглашусь со всем, включая
> кубиты :)

не все то интел, что процессор

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

← →
Rouse_ © (2009-03-12 20:06) [9]

Теоретики от практиков отличаются тем, что практики имеют практический бутерброд с икрой, а теоретики теоретически представляют его себе :)

← →
Mystic © (2009-03-12 20:07) [10]

Ерунда все это. Например, есть 22 варианта, чтобы хранить надо 5 бит. Чтобы хранить 46 вариантов надо 6 бит. А вот чтобы хранить 22 * 46 = 1012 вариантов надо 10 бит. Но 5 + 6 = 11. Так что ответ на вопрос сколько бит зависит от того, что потом с этими битами потом делать.

Если взять шахматы Фишера (рэндом-960), то там 960 вариантов начального расположения. Все позиции пронумерованы и упакованы. Но если их генерировать, то получаем:
4 варианта расстановки чернопольного слона (2 бита)
4 варианта расстановки белопольного слона (2 бита)
6 вариантов расстановки ферзя (3 бита)
5*4/2 = 10 вариантов расстановки коней (4 бита)
далее по правилам король располагается между ладей

Всего вариантов 4 * 4 * 6 * 10 = 960 позиций (10 бит).
Но если суммировать биты по отдельности, то получаем 2 + 2 + 3 + 4 = 11 бит.

← →
Rouse_ © (2009-03-12 20:13) [11]

> Всего вариантов 4 * 4 * 6 * 10 = 960 позиций (10 бит).
> Но если суммировать биты по отдельности, то получаем 2 +
> 2 + 3 + 4 = 11 бит.

Битовые маски рулят :)

← →
TUser © (2009-03-12 20:16) [12]

> TUser © (12.03.09 20:02) [8]
>
>

Слишком сильное утверждение. Идеальный комп с теоретической точки зрения - 2.71-битный. В переводе с него наши биты иррациональны и наоборот. Ближайшее целое - три, что и было реализовано в сссре. Говорят, круто.

> Rouse_ © (12.03.09 20:06) [9]
>
> Теоретики от практиков отличаются тем, что практики имеют
> практический бутерброд с икрой, а теоретики теоретически
> представляют его себе :)
>

Это да, трехразрядный компьютер тихо почил. Но без теоретиков куда деваться? Они нужны, хотя и по-своему.

← →
Игорь Шевченко © (2009-03-12 20:17) [13]

делимость бита - это ладно, а вот кто б напомнил, почему оптимальным основанием системы счисления является число е (2,718...), было бы интересно.

← →
Palladin © (2009-03-12 20:23) [14]

> Игорь Шевченко © (12.03.09 20:17) [13]

:) источник информации хотелось бы узнать

> Rouse_ © (12.03.09 20:13) [11]

проблема в том, что 2 + 2 + 3 + 4 в маску не залезет :)

← →
TUser © (2009-03-12 20:24) [15]

> Игорь Шевченко © (12.03.09 20:17) [13]
>
>

Каждый разряд = барабан с нашлепками. Например, в 10-ричной надо для числе до сотни 2 барабана, то есть 20 нашлепок. В 2-ричной - 7 по 2 = 14. В 3-ричной - 4 по 3 = 12. Теоретический минимум - е. Зачем надо - хз.

← →
Kostafey © (2009-03-12 20:24) [16]

> [13] Игорь Шевченко © (12.03.09 20:17)

Оно и не является. Иногда просто пишут:

I = log(N)

основание не уточняется.

Кстати, если говорить про число e, то это уже не бит, а нит :)

← →
Rouse_ © (2009-03-12 20:26) [17]

> о без теоретиков куда деваться? Они нужны, хотя и по-своему.

Мошт и так, я махонький пример приведу. Однажды, лет так шесть семь назад заинтересовался я как же таки работают компиляторы интерпретаторы и прочая непонятная мне шелупонь. Был у меня один знакомый теоретик преподающий в достаточно известном вузе, он мне по чесному пытался все это расжевать... дооолго расжевывал, но...
А потом как-то однажды сел я с практиком Зотычем, который сказал: "Та Ё, Сань - этож все просто" и на обычных салфектах нарисовал общую схему. За три часа обьяснений от практика, я понял на порядок больше, чем мне обьяснял почти неделю теоретик :)

ЗЫ: Но теоретики наверное все-же нужны :)

← →
Rouse_ © (2009-03-12 20:27) [18]

> проблема в том, что 2 + 2 + 3 + 4 в маску не залезет :)

Так ужимать надо :)

← →
Palladin © (2009-03-12 20:29) [19]

два одинаковых значениях в маске не ужимутся :)

← →
TUser © (2009-03-12 20:30) [20]

> Rouse_ © (12.03.09 20:26) [17]
>
>

Теоретики - они разные. От того же практика Зотыча мы тут неоднократно читали суждения о том, что теория - это хорошо. Может поэтому он и сумел все толково разжевать?

← →
Rouse_ © (2009-03-12 20:31) [21]

Энтропия в маске есть? Есть - ужмуццо, никуда не денуться :)

← →
TUser © (2009-03-12 20:33) [22]

Вот у меня обратный пример. Два человек обсуждают некий стереометрический расчет. Он сложен. Они маются. А я (ну, типа теоретик) объясняю, как это сделать в два плевка. Потому что я векторную алгебру изучал (ну совершенно абстрактный раздел для нас на первом курсе, разве что к физике приткнуть). И через векторное произведение - легко получалось.

Самому когда-то пригодилось. И как бы я жил без теоретиков с их векторными призведениями?

← →
TUser © (2009-03-12 20:33) [23]

← →
Игорь Шевченко © (2009-03-12 20:48) [24]

Palladin © (12.03.09 20:23) [14]

> :) источник информации хотелось бы узнать

Экзамен по основам цифровой техники, Московский Ордена Ленина Ордена Октябрьской Революции авиационный институт имени Серго Орджоникидзе. Доп. вопрос после ответа на билет :)
Я честно сказал, что не знаю, но свои 5 баллов все равно получил.

> Игорь Шевченко © (12.03.09 20:48) [24]

хем... казалось бы... при чем здесь золотое сечение... надо подумать о геометрическом смысле и обратится к отцу информатики... как до дому доберусь :)

http://marklv.narod.ru/inf/izminf.htm

> > Игорь Шевченко © (12.03.09 20:17) [13]

Взято от сюда http://www.intuit.ru/department/hardware/archsys/6/archsys_6.html

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

Считаем "p" - величиной непрерывной. Находим производную от (6.1) по величине "p". Берем вторую производную по "p". Увидим, что первая производная обращается в нуль, а вторая - больше нуля при p = e. Т.е. получаем минимум при p = e.

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

Но е = 2,718...

Поэтому оптимальной является система с основанием р = 3.

Эще забыл скопировать :
Таким образом, при заданном числе M количество цифроразрядов при основании "p":

p*n = p* logpM, (6.1)

где:

цифроразряд - эквивалент оборудования,

p*n - число устойчивых состояний элемента памяти,

n - число разрядов в числе.

на самом деле самые лучшие теоретики - это практики

Кащенко :)

← →
kaif (2009-03-15 02:43) [34]

xxx: Сестра попросила решить задачку по информатике. Задача: Каким количеством бит можно закодировать 48 символов?

Я думаю здесь многое еще зависит от вероятности появления этих символов в тексте. Ответ 5,5 бит корректен только если все символы равновероятны.
Попытаюсь проиллюстировать. Допустим вероятность появления первых 4 символов 99%, а всех остальных - 1%. Тогда я, пожалуй, смогу в большинстве случаев закодировать такой текст, используя в среднем менее 3 бит на символ.

Пусть сестра закодирует 5.5 бит на символ, а потом просто зазипует и посмотрит,то вышло.

:)

> Rouse_ © (12.03.09 20:26) [17]

Это был плохой теортик - вот и все. :) А с практиком тебе повезло - а выводов наделал уже...страсть.

> boa_kaa © (13.03.09 20:48) [31]

Самые лучшие теоретики - это лучшие теоретики. Но если они еще и к практике склонны через практиков - так им цены нет.

Делимость бита Найти похожие ветки