Журнал удивительных идей


Совместный проект учителей и учеников 192 школы










Спор информатиков

о задачке для 7-го класса
Спор возник между Ильиным (автором) и Маргулевым (пользователем) о решении следующей задачи:
Известно, что в классе 16 мальчиков и 8 девочек. Сколько бит содержит ответ на вопрос «Кого в классе больше, мальчиков или девочек?»?

М: Да, еще я не уверен, что понимаю, сколько бит содержит вопрос о том, кого больше – мальчиков или девочек? По моим расчетам – 1. А на самом деле?

И.: 0, так как эта информация вычисляется из исходных данных. Неопределенность на этот счет не уменьшается.

М.: Твой ответ к задаче я не понял. Разъясни, пожалуйста!

И.: В данном случае, для подсчета количества информации используется содержательный подход, при котором количество информации зависит от того, что мы знаем до получения информационного сообщения. Например, сообщение «в этом классе учится 28 человек» может нести от 0 (мы знаем это уже) до бесконечности бит (если подразумевается, что в классе может учиться любое количество человек). Дополнительное знание о том, что людей всего 6 миллиардов, устанавливает верхнюю границу в 33 бита.
Мы знаем, что в классе 8 мальчиков и 16 девочек. Из этого без дополнительной информации мы получаем:
1) В классе 16 девочек.
2) В классе 8 мальчиков.
3) Количество мальчиков не делится на 3.
4) Девочек в два раза больше, чем мальчиков.
5) В классе есть как минимум 6 мальчиков и т.д.
Получив все эти утверждения в качестве информационного сообщения мы получаем ровно 0 бит.

М.: Я не могу согласиться с такой трактовкой. Логическое выражение 30>8 или 30<8 имеет логическое значение 0 или 1, то есть несет 1 бит информации. То есть все равно нам приходится задавать вопрос: «Число мальчиков больше числа девочек?» – даже если количество мальчиков и девочек нам известно. Потому что знать число мальчиков и девочек мало: надо еще уметь определять, что больше!
Вообще, когда есть вопрос, ответ не может быть в 0 бит!

И.: Мы исходим из того, что события (из определения неопределенности) равновероятны. Но два вышеприведенные высказывания для человека, обладающего математическими навыками не равновероятны ни разу. Выходов два: либо сказать, что мы не умеем считать количество в таких случаях, либо честно рассчитать по формуле Шеннона.
Можно внести в формулировку дополнение. Типа «это все что мы знаем о данном классе и еще мы умеем считать». Но это бред, потому что также можно уточнять много чего. Это ясно и так.
Еще раз кратко. У нас было «одно» событие (в пространстве равновероятных событий). Мальчиков меньше. И ответ Да, мальчиков действительно меньше не принес информацию. То есть 0 бит.
Интересное утверждение («Вообще, когда есть вопрос, ответ не может быть в 0 бит!» – М.).
– Что вы достали из колоды, – спрашиваем мы у человека, который держит в руках карту рубашкой к нам?
– Карту!
Сколько информации мы получаем?

М.: У нас не было такого события: мальчиков меньше. Были факты: 16 девочек и 8 мальчиков. И 2 равновероятных исхода их сравнения – для компьютера это точно так. Ответ на вопрос не наблюдался непосредственно через органы чувств, как в случае карты, а являлся результатом умозаключения, ответа на вопрос, хотя и очень простой, совпадающий с заданным.
Мы должны строить математические модели таких задач как бы для алгоритмического решения. В случае карт таких равноправных моделей неопределенное количество, вопрос некорректный, ответы могут быть: карту, ничего, семерку пик и т.д. – в зависимости от модели.
Давай, когда ты будешь держать в руках сторублевку, я спрошу тебя: что ты достал из моего кошелька? Боюсь, нулем бит тут дело не ограничится...

И.: Нам известно, что в классе 8 мальчиков и 16 девочек.
Сколько информации несут сообщения
1) В классе 8 мальчиков.
2) Если один мальчик уйдет из класса – останется 7.
3) В классе на 2 мальчика больше чем сторон в шестиугольнике.
Три простых вопроса. Твои ответы?

М.: Эти сообщения не несут никакой информации. 0 бит. Потому что они не уменьшают какую- либо неопределенность. Более того, сообщение нам «девочек больше, чем мальчиков» тоже несет ДЛЯ НАС 0 бит информации. А вот если нам задают вопрос: кого больше, мальчиков или девочек? – то наш ответ дает вопрошающему 1 бит информации. Наличие такого вопроса предполагает, что вопрошающий не знает, как по записи количества определяются соотношения между множествами. А мы это знаем, для нас это мгновенное умозаключение (и то только в том случае, если задан вопрос, а если дан сразу ответ, то до фазы умозаключения дело даже не доходит). Здесь нет ничего удивительного – количество информации в сообщении вообще говоря зависит от получателя сообщения! Лицо, задающее вопрос, кого больше – мальчиков или девочек, если мальчиков 16, а девочек 8, – отличается от нас, поскольку для нас такого вопроса не существует.

И.: Для того человека, который разумен, и имеет информацию 16-8 данный ответ не несет никакой информации.
Ровно так, если я спрошу, какая у тебя фамилия, – твой ответ не принесет мне никакой информации. И ты не можешь мне запретить задавать этот вопрос. Вопрос существует, но вряд ли ты на него будешь отвечать. Твое молчание для меня будет в информационном смысле весить столько же, сколько слово «Маргулев».
Вопрос задавать бессмысленно? Конечно! Но я могу его задать и получить ответ весом в 0 бит. Вес 0 бит и есть критерий бессмысленности.
Вот уж ответ 1 бит совсем не верен. Для того, чтобы получить 1 бит информации на этот вопрос, необходимо, чтобы события «девочек больше», «мальчиков больше» были равновероятны. А это не так, потому что нам дано количество и тех и других.
Как раз наоборот. Не вопрос плохой, а владение информацией. Из того, что человек получает в ответ на вопрос про мальчиков-девочек больше 0 – значит он не владеет информацией о количестве.
Может ему не сказали, может он просто дурак, но в любом случае, он не использует эту информацию. А это не про нашу задачу.

М.: Сам дурак! :)
Вопрос о наличии равновероятности мы вообще не рассматривали.
Да, именно так – не использует информацию о количестве. И тут могут быть варианты. Я об этом и пишу, что он, очевидно, не умеет использовать ее так, как мы, поэтому и спрашивает. Возможно, он слышал что-то про десятичную систему и при надобности может перевести эти записи в привычную римскую (он не любит арабов), но решил не париться, а узнать сразу, кого согласно этим данным больше. То есть нельзя сказать, что он совсем не имеет информации, но не так быстро умеет ее извлекать.
Если ты мне скажешь, что в школе XIC женщин и VIIL мужчин, я тоже спрошу – кого больше? – и получу ответ в 1 бит информации (я надеюсь...). Таким образом, «добросовестный» вопрошатель получит 1 бит информации, а проходимец – 0, что вполне справедливо... :) Но я не знаю, почему ты, Володя, предлагаешь мне оказывать предпочтение проходимцу…

Cпор продолжается по сей день...

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

(прим. ред.)

М
а
т
е
м
а
т
и
к
а
Ф
и
з
и
к
а
Х
и
м
и
я
Б
и
о
л
о
г
и
я
И
н
ф
о
р
м
а
т
и
к
а