Сеть компьютеров
От: Oleg_Gashev http://files.rsdn.org/5774/button-debian.png
Дата: 19.03.03 23:27
Оценка: 72 (6)
16 компьютеров связаны в сеть в виде решетки 4*4.
В памяти каждого имеется своя информация. За один
такт компьютер может передать ИЛИ принять от ОДHОГО
из соседей информацию любого объема.
За сколько тактов и каким образом ВСЕ компьютеры
могут получить ВСЮ информацию?

К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К
Либо я найду путь, либо проложу его. © Свифт
Re: Сеть компьютеров
От: uzzy Россия  
Дата: 20.03.03 06:30
Оценка:
Здравствуйте, Oleg_Gashev, Вы писали:

OG>16 компьютеров связаны в сеть в виде решетки 4*4.

OG>В памяти каждого имеется своя информация. За один
OG>такт компьютер может передать ИЛИ принять от ОДHОГО
OG>из соседей информацию любого объема.
OG>За сколько тактов и каким образом ВСЕ компьютеры
OG>могут получить ВСЮ информацию?
OG>
OG>
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>


12 тактов:

такты:
1: 3-й ряд берет инфу из 4-го
2: 2-й ряд берет инфу из 3-го
3: 1-й ряд берет инфу из 2-го
4: 2-й ряд берет инфу из 1-го
5: 3-й ряд берет инфу из 2-го
6: 4-й ряд берет инфу из 3-го
дальше тоже самое для столбцов
Re[2]: Сеть компьютеров
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 20.03.03 07:09
Оценка:
Здравствуйте, uzzy, Вы писали:

U>12 тактов:


По крайней мере, за 8 можно:

1: 1->2, 3->4
2: 2->4
3: 4->2
4: 2->1, 4->3

И так же для стообцов
... << RSDN@Home 1.0 beta 5 >>
Re[3]: Сеть компьютеров
От: uzzy Россия  
Дата: 20.03.03 07:16
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

ММ>Здравствуйте, uzzy, Вы писали:


U>>12 тактов:


ММ>По крайней мере, за 8 можно:


ММ>1: 1->2, 3->4

ММ>2: 2->4
ММ>3: 4->2
ММ>4: 2->1, 4->3

ММ>И так же для стообцов


Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ...
по крайней мере я шел из этих рассуждений .
Re[4]: Сеть компьютеров
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 20.03.03 07:19
Оценка: 12 (2)
Здравствуйте, uzzy, Вы писали:

U>Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ...

U>по крайней мере я шел из этих рассуждений .

Виноват, поправлюсь:

1: 1->2, 4->3
2: 2->3
3: 3->2
4: 2->1, 3->4
... << RSDN@Home 1.0 beta 5 >>
Re[3]: Сеть компьютеров
От: Михаил Можаев Россия www.mozhay.chat.ru
Дата: 20.03.03 07:22
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

Ответ лежит в промежутке [6..8] Меньше точно нельзя, т.к., например, из левого верхнего угла в правый нижний можно дойти только за 6 ходов.
... << RSDN@Home 1.0 beta 5 >>
Re[5]: Сеть компьютеров
От: uzzy Россия  
Дата: 20.03.03 07:25
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

ММ>Здравствуйте, uzzy, Вы писали:


U>>Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ...

U>>по крайней мере я шел из этих рассуждений .

ММ>Виноват, поправлюсь:


ММ>1: 1->2, 4->3

ММ>2: 2->3
ММ>3: 3->2
ММ>4: 2->1, 3->4
ММ>

Странно... я когда считал такой вариант ... у меня получались два раза больше .
Пойду учить арифметику.
Re: Сеть компьютеров
От: limax Россия http://mem.ee
Дата: 20.03.03 08:04
Оценка: 24 (2)
Здравствуйте, Oleg_Gashev, Вы писали:

OG>16 компьютеров связаны в сеть в виде решетки 4*4.

OG>В памяти каждого имеется своя информация. За один
OG>такт компьютер может передать ИЛИ принять от ОДHОГО
OG>из соседей информацию любого объема.
OG>За сколько тактов и каким образом ВСЕ компьютеры
OG>могут получить ВСЮ информацию?
OG>
OG>
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>


Меньше 6-ти быть не может, т.к. из (1.1) в (4.4) быстрее не передашь.
(столбец,ряд)

Я нашёл только 8:

свёртка:
1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
3: (x.2)->(x.3), где x=2,3 => вся инфа в (2.3) и (3.3), простаивает весь периметр (12 компов);
4: (2.3)->(3.3) => всё есть в (3.3), простаивают 14 компов;

развёртка назад:
5: (3.3)->(2.3) => полная инфа в каждом из (2,3) и (3.3);
6: (x.3)->(x.2), где x=2,3 => полная инфа в каждом из внутреннего квадрата;
7: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
8: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.
Have fun: Win+M, Ctrl+A, Enter
http://www.rsdn.org/File/6363/avatar60.png
Re[5]: Сеть компьютеров
От: limax Россия http://mem.ee
Дата: 20.03.03 08:15
Оценка:
Здравствуйте, Михаил Можаев, Вы писали:

ММ>1: 1->2, 4->3

ММ>2: 2->3
ММ>3: 3->2
ММ>4: 2->1, 3->4

Нерационально с точки зрения лишней передачи данных, т.к. многие компы передают ненужную информацию.
По количеству передач — у меня меньше: у тебя (8+4+4+8)*2=48, у меня (8+4+2+1)*2=30 , однако кол-во ходов всё равно не меняется.
Have fun: Win+M, Ctrl+A, Enter
http://www.rsdn.org/File/6363/avatar60.png
Re[2]: Сеть компьютеров
От: uzzy Россия  
Дата: 20.03.03 09:43
Оценка:
Здравствуйте, limax, Вы писали:

L>Здравствуйте, Oleg_Gashev, Вы писали:


OG>>16 компьютеров связаны в сеть в виде решетки 4*4.

OG>>В памяти каждого имеется своя информация. За один
OG>>такт компьютер может передать ИЛИ принять от ОДHОГО
OG>>из соседей информацию любого объема.
OG>>За сколько тактов и каким образом ВСЕ компьютеры
OG>>могут получить ВСЮ информацию?
OG>>
OG>>
OG>>К - К - К - К
OG>>|   |   |   |
OG>>К - К - К - К
OG>>|   |   |   |
OG>>К - К - К - К
OG>>|   |   |   |
OG>>К - К - К - К
OG>>


L>Меньше 6-ти быть не может, т.к. из (1.1) в (4.4) быстрее не передашь.

L>(столбец,ряд)

L>Я нашёл только 8:


L>свёртка:

L>1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
L>2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
L>3: (x.2)->(x.3), где x=2,3 => вся инфа в (2.3) и (3.3), простаивает весь периметр (12 компов);
L>4: (2.3)->(3.3) => всё есть в (3.3), простаивают 14 компов;

L>развёртка назад:

L>5: (3.3)->(2.3) => полная инфа в каждом из (2,3) и (3.3);
L>6: (x.3)->(x.2), где x=2,3 => полная инфа в каждом из внутреннего квадрата;
L>7: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
L>8: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.
L>

Если уж пошел вопрос об оптимизации транзакций тогда так:
такты:
1:
1.1 -> 2.1
1.2 -> 2.2
3.1 -> 3.2
4.1 -> 4.2
4.3 -> 3.3
4.4 -> 3.4
1.4 -> 1.3
2.4 -> 2.3
2:
2.1 -> 2.2
4.2 -> 3.2
3.4 -> 3.3
1.3 -> 2.3
дальше все как у тебя
Re[3]: Сеть компьютеров
От: limax Россия http://mem.ee
Дата: 20.03.03 09:51
Оценка:
Здравствуйте, uzzy, Вы писали:

U>Если уж пошел вопрос об оптимизации транзакций тогда так:

U>такты:
U>1:
U> 1.1 -> 2.1
U> 1.2 -> 2.2
U> 3.1 -> 3.2
U> 4.1 -> 4.2
U> 4.3 -> 3.3
U> 4.4 -> 3.4
U> 1.4 -> 1.3
U> 2.4 -> 2.3
U>2:
U> 2.1 -> 2.2
U> 4.2 -> 3.2
U> 3.4 -> 3.3
U> 1.3 -> 2.3
U>дальше все как у тебя

А смысл? Те же 8 транзакций на первом шаге, 4 — на втором.
Have fun: Win+M, Ctrl+A, Enter
http://www.rsdn.org/File/6363/avatar60.png
Re[6]: Сеть компьютеров
От: uzzy Россия  
Дата: 20.03.03 10:00
Оценка:
Здравствуйте, limax, Вы писали:

L>Здравствуйте, Михаил Можаев, Вы писали:


ММ>>1: 1->2, 4->3

ММ>>2: 2->3
ММ>>3: 3->2
ММ>>4: 2->1, 3->4

L>Нерационально с точки зрения лишней передачи данных, т.к. многие компы передают ненужную информацию.

L>По количеству передач — у меня меньше: у тебя (8+4+4+8)*2=48, у меня (8+4+2+1)*2=30 , однако кол-во ходов всё равно не меняется.

Либо опять у меня с арифметикой проблемы либо твой вариант имеет : (8+8+2+1) + (8+4+2+1) = 34
Это число все-таки — количестов операций обмена инфо.
А вот вариант который я предложил (в ответ на твой) как раз имеет 2*(8+4+2+1) = 30.
С уважанием.
Re[4]: Сеть компьютеров
От: uzzy Россия  
Дата: 20.03.03 10:05
Оценка:
Здравствуйте, limax, Вы писали:

L>А смысл? Те же 8 транзакций на первом шаге, 4 — на втором.


Виноват ... просто твой x — я понимал... как 1-4 во второом такте, однозначно сегодня не мой день.
Re[3]: Сеть компьютеров
От: yogi Россия  
Дата: 20.03.03 10:11
Оценка:
Здравствуйте, uzzy, Вы писали:

U>Если уж пошел вопрос об оптимизации транзакций тогда так:

Ну её "оптимизацию транзакций" тут надо кол-во шагов уменьшить. Если у меня две проги работают по полчаса и приводят к одинаковому результату, то для меня (как пользователя) монопенисуально какая из них якобы оптимальнее.
Путь к сердцу женщины лежать не должен.
Re[4]: Сеть компьютеров
От: limax Россия http://mem.ee
Дата: 20.03.03 10:21
Оценка:
Здравствуйте, yogi, Вы писали:

Y>Ну её "оптимизацию транзакций" тут надо кол-во шагов уменьшить. Если у меня две проги работают по полчаса и приводят к одинаковому результату, то для меня (как пользователя) монопенисуально какая из них якобы оптимальнее.


Ты в корне не прав. Если обе проги работают по пол-часа, но одна из них занимает все 100% процессорного времени и имеет приоритет High, а другая — 50% и приоритет Normal, то при выборе из этих двух, любой нормальный пользователь выберет вторую, просто потому, что при использовании второй проги компьютер для него на эти пол-часа не умрёт.
Have fun: Win+M, Ctrl+A, Enter
http://www.rsdn.org/File/6363/avatar60.png
Re[2]: Сеть компьютеров
От: WoldemaR Россия  
Дата: 20.03.03 10:38
Оценка:
Здравствуйте, limax, Вы писали:

К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К


L>Я нашёл только 8:


L>свёртка:

L>1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
L>2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
L>3: (x.2)->(x.3), где x=2,3 => вся инфа в (2.3) и (3.3), простаивает весь периметр (12 компов);
L>4: (2.3)->(3.3) => всё есть в (3.3), простаивают 14 компов;

L>развёртка назад:

L>5: (3.3)->(2.3) => полная инфа в каждом из (2,3) и (3.3);
L>6: (x.3)->(x.2), где x=2,3 => полная инфа в каждом из внутреннего квадрата;
L>7: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
L>8: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.

Решение в 7 тактов:
Свёртка:
1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
Круговой обмен:
3: (2.2)->(2.3), (3.3)->(3.2) => вся инфа в (2.3) и (3.2), простаивает весь периметр (12 компов);
4: (2.3)->(3.3), (3.2)->(2.2) => вся инфа в (2.2) и (3.3), простаивает весь периметр (12 компов);
5: (3.3)->(3.2), (2.2)->(2.3) => полная инфа в каждом из внутреннего квадрата, простаивает весь периметр (12 компов);
Развёртка назад:
6: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
7: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.
http://www.akusherstvo.ru/lines/lineika/41887.gif
Re[3]: Сеть компьютеров
От: yogi Россия  
Дата: 20.03.03 10:53
Оценка: 8 (1)
Здравствуйте, WoldemaR, Вы писали:

WR>Решение в 7 тактов:

WR>Свёртка:
WR>1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
WR>2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
WR>Круговой обмен:
WR>3: (2.2)->(2.3), (3.3)->(3.2) => вся инфа в (2.3) и (3.2), простаивает весь периметр (12 компов);
WR>4: (2.3)->(3.3), (3.2)->(2.2) => вся инфа в (2.2) и (3.3), простаивает весь периметр (12 компов);
WR>5: (3.3)->(3.2), (2.2)->(2.3) => полная инфа в каждом из внутреннего квадрата, простаивает весь периметр (12 компов);
Неправда, в (2,2) и (3,3) неполная!!!
WR>Развёртка назад:
WR>6: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
WR>7: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех
Путь к сердцу женщины лежать не должен.
Re[4]: Сеть компьютеров
От: limax Россия http://mem.ee
Дата: 20.03.03 10:58
Оценка:
Здравствуйте, yogi, Вы писали:

WR>>Круговой обмен:

WR>>3: (2.2)->(2.3), (3.3)->(3.2) => вся инфа в (2.3) и (3.2), простаивает весь периметр (12 компов);
WR>>4: (2.3)->(3.3), (3.2)->(2.2) => вся инфа в (2.2) и (3.3), простаивает весь периметр (12 компов);
WR>>5: (3.3)->(3.2), (2.2)->(2.3) => полная инфа в каждом из внутреннего квадрата, простаивает весь периметр (12 компов);
Y>Неправда, в (2,2) и (3,3) неполная!!!

Ага, я тоже хотел сначала так сделать
Даёт полную инфу только в (3.2) и (2.3). К сожалению это не получилось использовать.
Have fun: Win+M, Ctrl+A, Enter
http://www.rsdn.org/File/6363/avatar60.png
Re: Автора !
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 07:36
Оценка:
Здравствуйте, Oleg_Gashev, Вы писали:

Очень бы хотелось увидеть решение автора.
Или хотя бы ответ.
Считает ли он, что задача закрыта?
Re[2]: Автора !
От: Oleg_Gashev http://files.rsdn.org/5774/button-debian.png
Дата: 21.03.03 10:58
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Oleg_Gashev, Вы писали:


P>Очень бы хотелось увидеть решение автора.

P>Или хотя бы ответ.
P>Считает ли он, что задача закрыта?

Меньше 8 тактов решение не вижу.
Либо я найду путь, либо проложу его. © Свифт
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.