2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 количество информации в дискретной последовательности
Сообщение14.02.2007, 19:05 
Помогите решить задачу

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

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

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

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

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

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

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

 
 
 
 
Сообщение14.02.2007, 20:07 
e2e4 писал(а):
P.S. Я бы уложился в 25 байт, учитывая, что в байте 8 бит :)

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

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

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

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

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

 
 
 
 
Сообщение14.02.2007, 20:47 
Аватара пользователя
2 e2e4: Зиповать нечестно!
Но, наверное, можно.
Но этого же явно не предполагалось...

 
 
 
 
Сообщение14.02.2007, 20:58 
Аватара пользователя
ИСН писал(а):
2 e2e4: Зиповать нечестно!
Но, наверное, можно.

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

 
 
 
 
Сообщение14.02.2007, 20:58 
Аватара пользователя
Даже если зиповать, все равно в среднем по всем возможным последовательностям станет больше.

 
 
 
 
Сообщение14.02.2007, 21:07 
Никаких архивирований, допускаются произвольные последовательности состояний.

Может я и ошибаюсь, но вот ход моих мыслей:
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 байта, я то-то не пойму :(

 
 
 
 Кто меньше?
Сообщение14.02.2007, 21:13 
Какие все щедрые :) .
Я готов уложиться в 2 байта, точнее в 10 битов.

 
 
 
 
Сообщение14.02.2007, 21:24 
neo66, крут крут.
Может расскажешь неучам, каким образом? :D :D :D

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

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

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

 
 
 
 
Сообщение14.02.2007, 21:36 
e2e4 писал(а):
neo66, крут крут.
Может расскажешь неучам, каким образом? :D :D :D


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

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

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

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

 
 
 
 
Сообщение14.02.2007, 21:57 
Аватара пользователя
Ясное дело, что при наличии ресурсов, всякий нормальный человек задействует 38 байт, но если припечет, как этому, то можно и экономить

 
 
 
 
Сообщение14.02.2007, 21:59 
Аватара пользователя
Записываем 100-значное число в шестиричной системе счисления, после чего переводим его в двоичную.

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group