количество информации в дискретной последовательности

[truler]

Помогите решить задачу

Обычный дорожный светофор без дополнительных секций подает шесть видов
сигналов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый,
красный и желтый одновременно). Электронное устройство управления светофором
последовательно воспроизводит записанные сигналы. Подряд записано 100 сигналов
светофора. Определить объем данной информации в байтах.

и даны варианты ответа :

1) 37
2) 38
3) 50
4) 100

[e2e4]

Чтобы задача стала корректной, необходимо уточнить кол-во бит в Вашем байте.

А какие у Вас есть мысли по поводу ее решения?

P.S. Я бы уложился в 25 байт, учитывая, что в байте 8 бит

[ИСН]

Смотря как записано, однако. Если по-простому, то можно уложить и в 50, и в 100, а если нет, то можно и меньше - кажется, вообще 33 хватит...

[e2e4]

e2e4 писал(а):

P.S. Я бы уложился в 25 байт, учитывая, что в байте 8 бит

Точнее в 194 бита

Добавлено спустя 19 минут 1 секунду:

Ё-маё, этот результат еще можно немного улучшить... Вечером посижу посчитаю.

Парадоксально, но в среднем получается меньше 2-х бит на одно состояние светофора!

[PAV]

33 байта хватит (259 бит), а 194 - этого мало. Если допускаются любые последовательности состояний, то очевидно, что мало, так как
$2^{194}<6^{100}$

[ИСН]

2 e2e4: Зиповать нечестно!
Но, наверное, можно.
Но этого же явно не предполагалось...

[photon]

ИСН писал(а):

2 e2e4: Зиповать нечестно!
Но, наверное, можно.

но размер архиватора в битах давайте тогда уж тоже учитывать

[PAV]

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

[e2e4]

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

Может я и ошибаюсь, но вот ход моих мыслей:
1. Очевидно, что для кодирования 6 состояний светофора необходимо 3 бита.
2. 3 бита кодируют вообще-то 8 состояний. Следовательно, любые два "лишних состояния" составляют как раз 1 дополнительный бит.
3. Закодировав 3 последовательных положения светофора, у нас накопится три "лишних" бита, а это - еще одно положение светофора!
4. Т.е. вместо 300 бит/100 положений мы получили 225 бит.
5. Смотрим далее. 3 "лишних" бита точно так же кодируют 8 вместо необходимых нам 6 состояний.
6. Следовательно, каждые 3*3 положения светофора получаем еще один лишний бит.
7. И так далее, пока кол-во необходимых положений для кодировки нового, бонусного положения, светофора не перерастет общее кол-во необходимых положений. Т.е. на 3*3*3*3 остановимся, получив 194 бита(!) на 100 положений светофора.
8. Результат можно еще улучшить, если не просто отбрасывать непарные 3-м бонусные биты, а учитывать их. Если непонятно, приведу вычисления.

Вообще-то, это в принципе и есть архивирование .

Учитывать размер архиватора в битах? Нуну. Тогда уж приплюсуйте к результату 38 байт размер функции, вытаскивающей упакованные в байты полезные биты и т.п.

А вот как вы получили 33 байта, я то-то не пойму

[neo66]

Какие все щедрые .
Я готов уложиться в 2 байта, точнее в 10 битов.

[e2e4]

neo66, крут крут.
Может расскажешь неучам, каким образом?

Добавлено спустя 9 минут 29 секунд:

Осознал свою ошибку, 194 бита конечно же мало.

Объясните, как получилось 33 байта?

[neo66]

e2e4 писал(а):

neo66, крут крут.
Может расскажешь неучам, каким образом?

Слегка поторопился .

Но, по моему, дело обстоит следующим образом:

Всего мы имеем 6^{100} состояний нашей системы. Их можно закодировать 259 битами, поскольку $6^{100} < 2^{259}$.
Значит достаточно 259 бита или 33 байта, а меньше нельзя.

[e2e4]

Математически все верно, вопрос в том - как физически поместить информацию в 33 байта? В 38 - проще простого, а в 33?

[photon]

Ясное дело, что при наличии ресурсов, всякий нормальный человек задействует 38 байт, но если припечет, как этому, то можно и экономить

[PAV]

Записываем 100-значное число в шестиричной системе счисления, после чего переводим его в двоичную.