2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



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


11/01/07
1
Помогите решить задачу

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

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

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

 Профиль  
                  
 
 
Сообщение14.02.2007, 19:27 


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

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

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

 Профиль  
                  
 
 
Сообщение14.02.2007, 19:27 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Смотря как записано, однако. Если по-простому, то можно уложить и в 50, и в 100, :) а если нет, то можно и меньше - кажется, вообще 33 хватит...

 Профиль  
                  
 
 
Сообщение14.02.2007, 20:07 


21/03/06
1545
Москва
e2e4 писал(а):
P.S. Я бы уложился в 25 байт, учитывая, что в байте 8 бит :)

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

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

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

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

 Профиль  
                  
 
 
Сообщение14.02.2007, 20:46 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение14.02.2007, 20:47 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение14.02.2007, 20:58 
Экс-модератор
Аватара пользователя


23/12/05
12046
ИСН писал(а):
2 e2e4: Зиповать нечестно!
Но, наверное, можно.

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

 Профиль  
                  
 
 
Сообщение14.02.2007, 20:58 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Даже если зиповать, все равно в среднем по всем возможным последовательностям станет больше.

 Профиль  
                  
 
 
Сообщение14.02.2007, 21:07 


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

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


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

 Профиль  
                  
 
 
Сообщение14.02.2007, 21:24 


21/03/06
1545
Москва
neo66, крут крут.
Может расскажешь неучам, каким образом? :D :D :D

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

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

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

 Профиль  
                  
 
 
Сообщение14.02.2007, 21:36 
Заслуженный участник


14/01/07
787
e2e4 писал(а):
neo66, крут крут.
Может расскажешь неучам, каким образом? :D :D :D


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

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

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

 Профиль  
                  
 
 
Сообщение14.02.2007, 21:50 


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

 Профиль  
                  
 
 
Сообщение14.02.2007, 21:57 
Экс-модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение14.02.2007, 21:59 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Записываем 100-значное число в шестиричной системе счисления, после чего переводим его в двоичную.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group