Здравствуйте, KoriBRand, Вы писали:

KBR>В зоопарке всего 32 обезьяны, которые сидят в двух вальерах A и B. Среди них есть одна обезьяна-альбинос. Сообщение "обезьяна-альбинос находится в вальере A" занимает 4 бита. Сколько обезьян сидит в вольере B?

KBR>Дискасс

Не передать словами, как меня бесят такие формулировки.

В поисках смысла, я открыл тот самый документ, ссылку на который дал samius, и понял вот что.

Размер вольера А — 2 обезьяны.
Размер вольера Бэ — 30 обезьян.

На этом основании всех обезьян поделили на группы из 2 обезьян (объем меньшего вольера, выраженный в обезьянах) и каждой группе присвоили номер. Групп таких получилось ровно 16. Затем номер группы, в которую входит обезьяна-альбинос (он же — номер группы, сидящей в вольере А), передали из зоо на волю. Чтобы передать один номер из 16 возможных, нужно 4 бита.

Крутим рассуждения в обратную сторону — типа, решаем задачу. Имея 4 бита можно передать один номер из 16 возможных. Значит (вот тут-то я и ох... нул!) передается номер группы, в которую входит обезьяна-альбинос (он же — номер группы, сидящей в вольере А) и таких групп — 16. Всего обезьян 32, значит в одной группе (она же — сидельцы вольера А) — 2 обезьяны. Путем вычитания 2 из общего числа обезьян находится объем вольера Бэ.

Если передатчик и приемник договорились бы между собой обозначить вольер А нулем, а Бэ — единицей, для передачи сообщения о том, в каком именно вольере сидит альбинос, им бы понадобился один бит, а не четыре. А если они ни о чем не договаривались... я посмотрел бы, какую рожу скорчил К. Поляков, получив из зоопарка сообщение "1011" (сцена для пьесы "Палата №666").

Понимание формулы "n^m" (Q^2 для битмасок) приходит с опытом. Нужно не один месяц дизъюнкать WS_* и выконъюнкивать их обратно, чтобы понять. Велик соблазн херануть по голове "мощностью алфавита", чтобы ускорить процесс, но я не знаю ни одного случая, когда бы потом такой скороспелка мог догадаться, как передать в колбэк 32 флага, имея на руках единственный dwUserData.

Здравствуйте, KoriBRand, Вы писали:

KBR>В зоопарке всего 32 обезьяны, которые сидят в двух вальерах A и B. Среди них есть одна обезьяна-альбинос. Сообщение "обезьяна-альбинос находится в вальере A" занимает 4 бита. Сколько обезьян сидит в вольере B?

KBR>Дискасс :)

Мне кажется, что 4.

По битам:
0 — номер клетки
1,2 — номер обезьяны
3 — альбинос или нет

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

В таком случае, по Вашим умозаключениям, всего закодировано 8 обезьян?

Здравствуйте, COFF, Вы писали:

COF>Мне кажется, что 4.

COF>По битам:
COF>0 — номер клетки
COF>1,2 — номер обезьяны
COF>3 — альбинос или нет

COF>Так как на номер обезьяны внутри клетки отводится два бита, то в ней сидит 4 обезьяны

Здравствуйте, KoriBRand, Вы писали:

KBR>В зоопарке всего 32 обезьяны, которые сидят в двух вальерах A и B. Среди них есть одна обезьяна-альбинос. Сообщение "обезьяна-альбинос находится в вальере A" занимает 4 бита. Сколько обезьян сидит в вольере B?

KBR>Дискасс

По-моему, тут все понятно.
Обезъяну-альбиноса посадили отдельно, чтобы избежать недружелюбного отношения со стороны сородичей.
Ответ — в вольере B находится 31 особь.
Сообщение занимает 4 бита, так как это естественный размер слова на популярных современных 32-битных архитектурах.

Здравствуйте, KoriBRand, Вы писали:

KBR>В зоопарке всего 32 обезьяны, которые сидят в двух вальерах A и B. Среди них есть одна обезьяна-альбинос. Сообщение "обезьяна-альбинос находится в вальере A" занимает 4 бита. Сколько обезьян сидит в вольере B?

Забавно читать комменты профессиональных программистов ))
А тем временем, школа на дремлет — недавно племянница попросила помочь решить задачку по информатике (10-й класс обычной школы):
==

В классе 30 человек. За контрольную по математике получено 6 пятёрок, 15 четвёрок, 8 троек и 1 двойка.
Какое количество информации в сообщении о том, что Иванов получил 4, 5, 3, 2?

==

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

Здравствуйте, notacat, Вы писали:

N>>>Чтобы у детей интерес не отбить, им надо более конкретные знания давать

N>>Откуда такое мнение? Несогласный я
N>Ну, с того момента, как я закончила школу, прошло много лет. В первую очередь забывается то, что никогда в жизни не пригодилось. А одновременно с этим обнаруживается куча вещей, о которых тебе никто не догадался вовремя сказать. Время — это конечный ресурс, надо его с пользой тратить.
N>Все-таки, некоторые специфичные знания, которые пригодятся одному ребенку из класса, лучше оставить ВУЗ'у. А детям дать то, что понадобится большинству или хотя бы половине.
Вот вы, извините, дальше своего носа не видите. Я ни в школе, ни в универе ни одним нейроном не мог подумать, что я буду преподавателем. Более того, в универе теорию информации, так же как и теорию графов я просто мимо ушей пропустил, думая, что эта фигня мне никогда не пригодится... А по численным методам у меня даже хвост был. Случайный (я его потом на 5 сдал), но все же был. Я практически 20 лет работал программистом. И в 40 лет вдруг попал в преподаватели.
Угадайте с трех раз, какую дисциплину мне пришлось читать самую первую? Блин, на небе за нами точно кто-то следит! Я читал численные методы!
А теория информации и кодирования — это обязательные знания любого профи-программиста. Любой zip-архиватогр — это коды Хаффмена. Или кодирование по Хаффмену-Фано. А что такое блочный линейный код — не знаете? Так это код ASCII. И для таких кодов — вся математика уже написана — это линейное векторное пространство над полем Галуа! А многочлены — это непрерывные коды...
А как синдром ошибки вычисляется в кодах, защищенных от ошибок, знаете? Матрица на вектор умножается — и получается нулевой или нет вектор. Если нулевой вектор — то ошибок не было. А если не нулевой, то ненулевая координата показывает, где ошибка.
И мне пришлось ее преподавать. И студентам объяснять, что алгебру они не просто так проходили. И что zip-архиватор — это коды Хаффмена.
А теорию графов мне пришлось практически заново изучать, когда стал диссером заниматься.
Вот тоже в универе не думал, не гадал, что теория графов мне понадобится!
Так что судить в школе о том, что пригодится, а что нет — несколько опрометчиво.
N>Только сейчас обнаружила, что в этом году ввели вступительный по информатике на все специальности, которые более-менее имеют отношение: http://bak-innovation.blogspot.com/2009/06/blog-post_24.html. Раньше, насколько я помню, вступительный по информатике брали только в некоторых избранных местах и предлагался выбор типа информатика или иностранный. На ВМК, например, раньше просили математику с физикой и информатикой не заморачивались.
N>В общем, печальное явление, информатику в большинстве школ преподают по остаточному принципу, а то и просто разрешают детям в игрушки играть.
N>А я еще удивлялась, почему в этом году из нашей гимназии никто на ВМК не пошел, а только на мехмат. Вот, оказывается, в чем дело.
На направление (бакалавриат) Информатика и вычислительная техника обязательный экзамен — информатика. Физика — это на специальность, как раньше.

Ой, блин! Только сейчас обратил внимание на дату...

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, KoriBRand, Вы писали:

KBR>>В зоопарке всего 32 обезьяны, которые сидят в двух вальерах A и B. Среди них есть одна обезьяна-альбинос. Сообщение "обезьяна-альбинос находится в вальере A" занимает 4 бита. Сколько обезьян сидит в вольере B?

A>Забавно читать комменты профессиональных программистов ))
A>А тем временем, школа на дремлет — недавно племянница попросила помочь решить задачку по информатике (10-й класс обычной школы):
A>==
A>

A>В классе 30 человек. За контрольную по математике получено 6 пятёрок, 15 четвёрок, 8 троек и 1 двойка.
A>Какое количество информации в сообщении о том, что Иванов получил 4, 5, 3, 2?

A>==

A>Тут, кстати, в ответе число битов уже нецелым получается — простыми вероятностями по степеням двойки уже не отделаешься ))

Напугал ежа голой задницей...

С точностью до того, что Иванов в классе один (что далеко не очевидно), и что он не двоешник (что также далеко не очевидно), можно предположить, что для него вероятность получить 5,4,3 и 2 равны соответственно 1/5,1/2,4/15 и 1/30. Тогда школьник может просто "тупо" воспользоваться формулой log2(1/p) и получить log2(5),1,log2(15)-2,log2(15)+1. Проблема не в этом. Если ему правильно преподавали, то он понимает, почему это так, он понимает, что изначальное число возможных (по условию) и равновероятных (по предположению) вариантов сокращается в 2 раза в случае получения сообщения о четверке Иванова, и даже, наверное, понимает, почему это так. И главное, он понимает, что его ответ верен ТОЛЬКО если сделать такие предположения! Что при отклонении от них, количество полученной информации будет другим, так как будет другой изначальная неопределенность. Он также понимает, что количество информации -- это не log2(1/p), а мера уменьшения неопределенности, и т.п. Но проверить это очень легко. Например, спросить, а что, если Иванов известен тем, что он отличник, или, наоборот, получает только двойки и тройки, причем двойки в два раза чаще. Или, если в классе два Иванова. Ну и т.д.

В изначальной задаче про альбиноса еще хуже. Там тоже предполагается, что полученное сообщение сократило число возможных равновероятных вариантов в 16 раз, т.е. вероятность того, что сказано в сообщении, равна 1/16. Хотя это совсем не так. Энтропия сократилась в 16 раз, это да. Но варианты могли быть совсем не равновероятными, например. Поэтому остается чувство какой-то недосказанности. Т.е. здесь предполагается, что обезьян сажают так: сначала определили, сколько посадочных мест в первой клетке, сколько во второй, а потом случайным образом выбрали нужное количество в первую клетку, остальных -- во вторую. Но есть и другие схемы посадки. Где в задаче указано про то, какая неопределенность была изначально, чтобы оценить количество полученной информации? Вообще, информация о том, что альбинос в первой клетке равна 4 битам ТОЛЬКО если заранее известно, что в первой клетке 2 обезьяны, во второй -- 30, и распределение обезьян по клеткам равновероятно. Т.е., зная это заранее, можно сказать, что количество информации 4 бита, а наоборот -- нельзя. Нельзя вывести гипотезу из следствия, могут быть варианты, как говорится, и при многих из них будет получаться 4 бита. Любой вариант, при котором энтропия сокращается ровно на 4 бита, подойдет, причем при некоторых из них вообще нельзя будет сказать точно, сколько обезьян в каждой клетке.

Вот, например. Среди 32 обезьян проводятся бои. 5 раундов плей-офф: 1/16 финала, 1/8 финала, четвертьфинал, полуфинал, финал. Известно, что обезьяна-альбинос сильная и выносливая, и выигрывает с вероятностью 0.57434917749851750339931347338896. Победителя сажают в клетку А, остальных сбрасывают в клетку Б. Информация о том, что альбинос в клетке А, равна (внимание!) 4 битам! А в клетке Б 31 обезьяна...

В общем, исходная задача предполагает, что из того, что было получено 4 бита информации, я должен предположить конкретную схему распределения, при которой получится требуемый ответ. И проблема, в общем, даже не в этом -- от школьника ТРЕБУЮТ предположить, что схема распределения такая-то, потому, что его учили подставлять 1/p в логарифм только для такой схемы.

В общем, мне до сих пор не очень понятно, чему это учит, да и зачем для того, чтобы "запутать отличников" давать подобные "заковыристые" формулировки. Школьник первым образом должен понимать, что количество полученной информации служит мерой измерения уменьшения неопределенности. И поэтому говорить о количестве полученной информации можно только в контексте нормально описанной неопределенности, которая существовала до того, как сообщение было получено. А не делать предположения об этой самой неопределенности по количеству информации -- бред какой-то. Либо сразу описать схему, т.е. было известно, что там n обезьян, получили сообщение, а потом спросить, при каком n оно 4 бита. А запомнить, что надо 1/p подставить в логарифм, много ума не надо. Надеюсь, что подобные задачи не прививают то самое мышление, когда "отличники ЕГЭ" знают, что и куда подставить, и не знают почему.