2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Каменные биты.
Сообщение07.08.2013, 10:49 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
EtCetera в сообщении #752643 писал(а):
На этой картинке показано, каким образом первый агент может передать 13 сообщений (второй при этом передает 12 сообщений). Конфигурация дерева вариантов на картинке немного не соответствует данным, полученным с помощью моей программы (это сделано для того, чтобы картинка была покомпактнее).

Что такое "передать сообщение"? Перечислите все сообщения первого и все сообщения второго, которые они (независимо друг от друга) могут передать друг другу.

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


06/04/10
3152
TOTAL в сообщении #752809 писал(а):
Что такое "передать сообщение"?

Передать номер сообщения.
Т.е. списки сообщений у каждого есть, и подразумевается известный сюжет, "анекдот номер 5".

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


23/08/07
5420
Нов-ск
nikvic в сообщении #752813 писал(а):
TOTAL в сообщении #752809 писал(а):
Что такое "передать сообщение"?

Передать номер сообщения.
Т.е. списки сообщений у каждого есть, и подразумевается известный сюжет, "анекдот номер 5".

Перечислите все сообщения первого и второго.

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


06/04/10
3152
TOTAL в сообщении #752816 писал(а):
Перечислите все сообщения первого и второго.

$1,2,.... f$
$1,2,.... s$
:wink:

(формулы)

 i  Deggial: добавить пару долларов - это так сложно...

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение07.08.2013, 21:19 
Заслуженный участник


28/04/09
1933
Думаю, стоит уточнить, что в предыдущих моих сообщениях фраза "передать $N$ сообщений" означала, что агент имеет принципиальную возможность передачи $N$ различных сообщений, в то время как за один сеанс связи он может передать лишь одно из $N$ сообщений.

TOTAL
TOTAL в сообщении #752809 писал(а):
Что такое "передать сообщение"?
Пусть серия бросков выглядит так: $a_1,a_2,a_3\dots a_k$ (здесь $a_j$ $\text{---}$ количество камней в $j$-ом броске, $a_j\ge 1$, $\sum\limits_{j=1}^k a_j=n$). Броски с нечетными номерами выполнены первым агентом, броски с четными $\text{---}$ вторым. "Передать сообщение" означает выполнить свои броски таким образом, чтобы по общей серии другой агент мог понять, какая фраза из заранее заготовленного словаря фраз имеется в виду.
Подход venco, насколько я понял, заключается в том, что агенты заранее договариваются о следующей процедуре обмена сообщениями (для четного числа камней $n$): каждый обязуется использовать по $\frac{n}{2}$ камней и реализовать их за некоторое (одинаковое для обоих) число бросков $\frac{k}{2}$: $\sum\limits_{j=1}^{k/2}a_{2j-1}=\sum\limits_{j=1}^{k/2}a_{2j}=\frac{n}{2}$. Для каждого из агентов существует $\binom{n/2}{k/2}$ вариантов реализации своих бросков. Таким образом, каждый из них может однозначно идентифицировать одну из $\binom{n/2}{k/2}$ фраз словаря, которая подразумевалась при передаче его партнером. В таком подходе агенты используют при кодировании только собственные броски, не обращая внимания на то, как именно бросает свои камни партнер. Максимальное число сообщений, которое в принципе можно передать, составляет $\binom{n/2}{\left\lceil n/4\right\rceil}$.
Большее число сообщений можно передавать, заранее договорившись о такой схеме передачи, при которой для идентификации переданного сообщения используются не только броски партнера, но и свои собственные. Именно такой подход использует мой алгоритм передачи сообщений. Картинка из предыдущего моего сообщения в этой теме иллюстрирует тот факт, что при таком подходе наибольшее число сообщений, которое может передавать каждый из агентов, может составлять больше $\binom{n/2}{\left\lceil n/4\right\rceil}$. Правильно ли я понимаю, что картинка требует дополнительных пояснений?

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


23/08/07
5420
Нов-ск
EtCetera в сообщении #753034 писал(а):
Правильно ли я понимаю, что картинка требует дополнительных пояснений?
Спасибо, EtCetera, я понял, что набор сообщений, который я ожидаю от партнера, зависит от того, сколько камней я бросил первым броском. И т.д.

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение08.08.2013, 11:09 
Аватара пользователя


21/02/10
1594
Екатеринбург
Существует 2^26 способов бросания 26 камней. То есть теоретически можно закодировать числа от 1 до 67108864. То есть каждый мегамозг может передать число от 1 до Y. Где Y+Y^2=67108864.

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


06/04/10
3152
EtCetera в сообщении #753034 писал(а):
Большее число сообщений можно передавать, заранее договорившись о такой схеме передачи, при которой для идентификации переданного сообщения используются не только броски партнера, но и свои собственные.

Геометрически каждый сеанс связи может быть представлен как ломаная с шагами вверх и вправо.
Было бы интересно понять, как устроены "траектории" сеансов для заданных объёмов передачи.

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


23/08/07
5420
Нов-ск
Pavlovsky в сообщении #753160 писал(а):
Существует 2^26 способов бросания 26 камней.

Сколько существует способов бросания 2 камней?

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение08.08.2013, 11:58 
Аватара пользователя


21/02/10
1594
Екатеринбург
Два. (2), (1,1)
Ой ошибся. Существует 2^25=33554432 способов бросания 26 камней.

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение08.08.2013, 13:18 
Заслуженный участник


28/04/09
1933
Pavlovsky
По Вашей формуле выходит, что при наличии $n=5$ камней агенты могут передать по 3 сообщения, не так ли? Если так, то не могли бы Вы продемонстрировать, каким образом им это удается?

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


01/08/06
3049
Уфа
Наконец-то и до меня дошло, какая здесь зависимость.
Подтверждаю таблицу EtCetera. По крайней мере, для $n=17$ у меня тоже получилось (119, 119), а для $n=26$ — (2537, 2535) и (2535, 2536). Ну и $n=30$ совпало.
Подробности будут позже.

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


01/08/06
3049
Уфа
Обозначим через $f_n(m)$ ($n\in\mathbb{Z}_+$, $m\in\mathbb{N}$) максимальное количество сообщений, которое бросающий первым может передать с помощью $n$ имеющихся в его распоряжении камней при условии, что второму обеспечивается возможность передачи не менее $m$ сообщений. В обозначениях таблицы EtCetera $f_n(m)=k$ эквивалентно тому, что среди всевозможных пар перечисленных в 3-м столбце $n$-й строки таблицы присутствует пара (k,m).

Я, в отличие от EtCetera, интерпретирую как ноль камней, так и один камень, как возможность передачи не нуля, а одного сообщения (поскольку логарифм от этой единицы даёт правильное значение — ноль бит информации, которое можно передать). Однако если второму бросающему никак нельзя дать возможность передать $m$ сообщений, если первому досталось $n$ камней, то $f_n(m)=0$. Поэтому в моих обозначениях $f_0(1)=1$, $f_1(1)=1$, а для $m>1$ будет $f_0(m)=f_1(m)=0$.

Пусть мы хотим вычислить $f_n(m)$, где $n>1$, для всех $m$. Первый может бросить $i$ камней если и только если $f_{n-i}(k)\geqslant m$ для какого-то $k$ (поскольку, очевидно, $f_n(k)$ не убывает с ростом $k$ при фиксированном $n$, то достаточно потребовать $f_{n-i}(1)\geqslant m$).

Итак, пусть первый кинул $i$ камней (разрешённое количество). Зададимся вопросом: сколько максимально сообщений первый сможет передать после ответного броска второго? Иными словами, какое максимальное количество сообщений второй может позволить передать первому при своём следующем ходе (не забывая при этом о своих $m$ сообщениях)? Ответ на это, по определению функции $f$, таков: максимальное $k$, при котором $f_{n-i}(k)$ всё ещё не меньше $m$, или $\max\limits_{f_{n-i}(k)\geqslant m}k$.

Суммируя варианты передачи по всем разрешённым $i$, имеем полное количество сообщений, которое может передать первый при указанном ограничении:$$f_n(m)=\sum\limits_{i=1}^n\max\limits_{f_{n-i}(k)\geqslant m}k$$
Этому выражению можно придать другую форму:$$f_n(m)=\#\{(j,k)|j<n,f_j(k)\geqslant m\}$$
Если к этому добавить, что максимальное $m$, для которого $f_n(m)>0$, мы уже ранее вычислили как $F_n$ ($n$-й член последовательности Фибоначчи), то остаётся только считать. Искомое количество сообщений для $n$ камней будет равно $$\max\limits_{m=1}^{F_n}\min\{m, f_n(m)\}$$
Вот таблица первых $f_n(m)$:
$$\begin{array}{|l|r|r|r|r|r|r|r|r|r|}
\hline
m\diagdown n&0&1&2&3&4&5&6&7&8\\ \hline
1&1&1&2&3&5&8&13&21&34\\ \hline
2&&&&1&2&4&7&12&20\\ \hline
3&&&&&1&2&4&8&15\\ \hline
4&&&&&&1&3&6&11\\ \hline
5&&&&&&1&2&4&8\\ \hline
6&&&&&&&1&3&7\\ \hline
7&&&&&&&1&3&6\\ \hline
8&&&&&&&1&2&5\\ \hline
9&&&&&&&&1&3\\ \hline
10&&&&&&&&1&3\\ \hline
11&&&&&&&&1&3\\ \hline
12&&&&&&&&1&3\\ \hline
13&&&&&&&&1&2\\ \hline
14&&&&&&&&&1\\ \hline
15&&&&&&&&&1\\ \hline
\dots&\dots&\dots&\dots&\dots&\dots&\dots&\dots&\dots&1\\ \hline
21&&&&&&&&&1\\ \hline
\end{array}$$

-- Пт авг 09, 2013 12:41:53 --

EtCetera это всё уже писал, даже обозначения почти те же. Только я его сначала не понял :-(

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


06/04/10
3152
EtCetera в сообщении #751959 писал(а):
Вот что она выдала:...

Первое разночтение у нас с Вами - строка 46, столбец 45. Вам хватает 14 камней, мне нужно 15.
Ваша таблица не захватывает это место. На какие слагаемые Первый разбивает свои 46 сообщений?

 Профиль  
                  
 
 Re: Каменные биты.
Сообщение09.08.2013, 16:16 
Супермодератор
Аватара пользователя


20/11/12
5728
 ! 
Pavlovsky в сообщении #753160 писал(а):
Существует 2^26 способов бросания 26 камней. То есть теоретически можно закодировать числа от 1 до 67108864. То есть каждый мегамозг может передать число от 1 до Y. Где Y+Y^2=67108864.
Pavlovsky, замечание за неоформление формул $\TeX$ом

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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