2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Комбинаторика информации
Сообщение29.05.2014, 13:23 


29/01/14
25
Несложная задача, но не могу решить ее комбинаторно.

Есть 4 поезда, только один из них едет в Москву. Сколько битов понадобиться для того, чтобы записать информацию о номере платформы, где стоит поезд на Москву?

Есть переборное решение: нужно все 4 различать, тогда нужно 4 символа: 00, 01, 10, 11, а это 2 бита.

Есть четыре поезда, каждый из них либо едет, либо не едет в Москву, а потому это Размещение из 2 по 4, то есть 16 бит.

Первый ответ правильный(проверил по формуле Хартли (которая с двоичным логарифмом)), но я никак не пойму как можно получить размещение из 2 по 2. Помогите, пожалуйста!

 Профиль  
                  
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 13:37 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
constant в сообщении #869166 писал(а):
Есть четыре поезда, каждый из них либо едет, либо не едет в Москву, а потому это Размещение из 2 по 4, то есть 16 бит.
Только один едет в Москву, поэтому каждому из них либо ехать, либе нет не разрешается.

 Профиль  
                  
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 14:54 
Заслуженный участник


23/07/08
10626
Crna Gora
Из того, что поездов $4$, лишь со скрипом следует (т.е., собственно говоря, не следует), что платформ тоже $4$. А указывать надо платформу.

 Профиль  
                  
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 16:08 


29/01/14
25
Понял, почему мое решение неверно, а каким тогда будет верное и притом комбинаторное решение?

 Профиль  
                  
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 16:58 
Заслуженный участник


23/07/08
10626
Crna Gora
Вот такое. Пусть у нас есть $k$ бит, каждый из них может принимать значение $0$ или $1$. Сколько различных комбинаций значений существует? (Видите слово «комбинация»? Значит, решение комбинаторное!) Очевидно, $2^k$. Сопоставим каждой из $n$ платформ некоторую из $2^k$ комбинаций, так, чтобы разным платформам соответствовали разные комбинации. Это можно сделать, в соответствии с принципом Дирихле, при условии $2^k\geqslant n$, или, так как логарифм монотонно возрастающая функция, $k\geqslant \log_2 n=\log_2 4=2$

Предыдущий абзац был наукообразной шуткой, но Вы, по-моему, примерно такого решения и хотели.

 Профиль  
                  
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 17:02 
Заслуженный участник


09/05/13
8904
svv

(Оффтоп)

Жуть какая. :shock:

 Профиль  
                  
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 17:08 


29/01/14
25
svv в сообщении #869227 писал(а):
Вот такое. Пусть у нас есть $k$ бит, каждый из них может принимать значение $0$ или $1$. Сколько различных комбинаций значений существует? (Видите слово «комбинация»? Значит, решение комбинаторное!) Очевидно, $2^k$. Сопоставим каждой из $n$ платформ некоторую из $2^k$ комбинаций, так, чтобы разным платформам соответствовали разные комбинации. Это можно сделать, в соответствии с принципом Дирихле, при условии $2^k\geqslant n$, или, так как логарифм монотонно возрастающая функция, $k\geqslant \log_2 n=\log_2 4=2$

Предыдущий абзац был наукообразной шуткой, но Вы, по-моему, примерно такого решения и хотели.

Да, то что надо - спасибо!


Otta
А как бы Вы решали, чтобы явно получилось размещение?

 Профиль  
                  
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 17:20 
Заслуженный участник


23/07/08
10626
Crna Gora
svv в сообщении #869227 писал(а):
логарифм монотонно возрастающая функция
Читать как «логарифм по основанию $2$ монотонно возрастающая функция.»

Otta
:-)
Скорее всего, под размещением понимается «перестановка, сочетание, размещение или другая подобная комбинаторная штуковина».

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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



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

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


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

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