Завдання телефоністок

(Економічна схема швидкого сортування каналів зв'язку)

Здогадатися до принципу, на якому працює поштова служба, може, по всій видимості, вже кмітливий школяр. Спрощено: потрібно зібрати всі листи спочатку на головній сортувальної станції і, розсортувавши їх з цифр першого розряду поштового індексу, відправити відповідні множини (листів) на більш дрібні регіональні сортувальні вузли, що відповідають кожен своєю цифрі, далі поступати аналогічно. Зовсім не просто, виявляється, узагальнити цей метод сортування каналів зв'язку. Колись адресацію дзвінків вирішували за допомогою дівчат-телефоністок, це відбувалося так:
перед дівчиною стояв тумблер з клемами, іноді якісь клеми виявлялися «пов'язаними» з абонентами, які бажають додзвонитися по якомусь «адресою». Дівчина могла тимчасово з'єднатися з такою клемою і, з'ясувавши у абонента необхідну інформацію, замкнути її дротом (кондуктором) із іншою відповідною клемою — таким чином продовживши канал зв'язку далі. Більш схематично «телефоністка» зображена на рис. 1.

В залежності від того, які сигнали надходять на вхідні клеми, Т приймає рішення про те, які з вхідних клем вона з'єднає з вихідними. Також Т в деяких ситуаціях може здійснювати власні «виклики», посилаючи сигнал за вихідними каналами.
Для ілюстрації розглянемо задачу одностороннього сполуки А з В1-В4 (рис.2)

А запитує з'єднання з В2 у телефоністки 1, згідно з цим 1 з'єднує його з 2, утворився каналу зв'язку А-1-2. А повідомляє 2 про призначеному абонента, в результаті чого 2 з'єднує його з лівого каналу з 3. Телефоністка 3 введена фіктивно, для спільності з іншими схемами, вона може, не чекаючи ніяких сигналів, з'єднати свої єдині «вхідну» і «виходить» клеми.
Ускладнимо завдання. Нехай тепер потрібно з'єднати абонентів А1-А4 з В1-В4, за умови, що таке з'єднання утворює перестановку (ніякі два не адресують виклик одному). Сортування дзвінків (рис.3) відбувається у 2 етапи і ще 3 ступені телефоністок «збирають» вхідні дзвінки в один.

На першій ступені, ясна річ, має бути 0(N) телефоністок. Кожна з них направляє виклик направо або наліво. Кожен з каналів, провідних направо повинен з'єднати з деякою телефоністкою другого ступеня, те ж саме для каналів, які ведуть наліво. Таким чином, на другому ступені кількість телефоністок подвоїлася. Якщо подібними методами сортувати далі то кожна наступна сортирующая щабель буде вимагати в два рази більше телефоністок, ніж попередня. Всього в подібній мережі буде задіяно 0(N2) телефоністок, що для практичних цілей, зрозуміло, неприйнятно.
Варто зауважити, що в кожному конкретному поєднанні беруть участь всі телефоністки першої ступені, лише половина-другий і чверть-третьої. Оскільки, наприклад, у наведеній схемі (рис. 3) телефоністок правого крила другого ступеня, що виробляють поділ, потрібно завжди лише дві, то можна спробувати сконструювати пристрій, «концентрирующее» задіяні канали зв'язку. Схематично воно зображено на рис. 4, а телефонна мережа із застосуванням таких пристроїв на рис. 5.


Як нескладно помітити, економічна вартість подібних схем є 0[N ln N]+вартість усіх використаних концентраторів. Проведемо необхідні оцінки.
Здійснення конкретного з'єднання між N абонентами і N адресатами еквівалентно виділення однієї з N! можливих перестановок N-елементного безлічі. Згідно із законом необхідної різноманітності телефоністками повинно бути внесено не менше ln N!~ N ln N одиниць інформації. Оскільки кожна телефоністка вносить не більше 0(1) інформації, то 0[N ln N]-нижня оцінка кількості телефоністок для будь-телефонної станції, здатної одночасно сполучати N абонентів. Нескладно показати такий же інформаційної оцінкою, що 0[ln N]-нижня межа для затримки з'єднання.
Будь-концентратор, у якого на виході немає білих квадратиків, при кожному конкретному розташуванні «вхідних» чорних квадратиків визначає певну, властиву тільки цим розподілом, функціональне відповідність для прикладу рис 4
½К в К. Оскільки різноманітність можливих розподілів досить велике х=К!/([(Kn)!]〖^2〗), то кількість задіяних в концентраторі телефоністок не менше 0[lnx]=0(K), однак ця оцінка дещо занижена. Автор має в своєму розпорядженні кілька математизированным доказом, тому тут дещо недоречним, що виконана оцінка 0(KlnK). Метод полягає в тому, щоб порахувати кількість претендентів на крісло у портер». Для концентраторів, при їх розумному визначенні, у яких на виході можуть бути білі квадрати — все дещо цікавіше. Нижче буде наведено концентратор з N до N/(2 ), що вимагає 0[N(lnN)2] телефоністок, і його поліпшення до 0[N(lnN)lnlnN].
При їх використанні виходять телефонні станції величини 0[N(lnN)3] з затримкою 0[(lnN)3] і 0[N(lnN)2 lnlnN] з затримкою 0[(lnN)2lnlnN]. Зауважимо, що нижньою оцінкою для станцій наведеної схеми з концентраторами «без білих квадратів» є:
0[N(lnN)2] за обсягом
0[(lnN)2] по затримці з'єднання.
Робота концентратора 1-го типу природно розпадається на lnN ступенів (рис. 6)

Робота на рівні кожної k-ої сходинки на lnk кроків (рис. 7)

Заповнених сигналами телефоністок будемо зображати схематично чорними квадратами на картатих смужках. На початку k-ої ступені все телефоністки діляться на групи по 2k всього 2N-k груп. У кожній групі вхідні сигнали розподілені так, що зображують їх картаті смужки розбиваються на ліві білі подполоски і чорні праві. Ці смужки об'єднуються в пари, і в кінці ступені кожна така пара стає смужкою, що складається з лівої білої і правою чорної подполоски. Перетворення на першому кроці полягає у зчепленні смужок, при цьому виходить смужка з чорним острівцем по центру. Потім цей острівець зсувається на максимальні ступені двійки вправо на кожному останньому кроці. Таких кроків потрібно не більш ніж lnk. Реалізація ступені (частини ступені) зображена на рис. 9, де М — множник сигналу (рис. 8)


Телефоністка, позначена символом I, посилає інструкцію про перенаправлення всіх вхідних абонентських каналів зв'язку «з косою», якщо її канал зв'язку «порожній» і «паралельним» у протилежному випадку.
Нескладно підрахувати, що для кожного кроку потрібно 0(N) телефоністок, для реалізації k-го ступеня — N(lnN)2. Цей концентратор дає затримку в 0(lnN)2 характерних одиниць часу.
Щоб прискорити роботу концентратора, зауважимо, що можна величини всіх зрушень вирахувати «заздалегідь» і, не спираючись на індикатори, подати відповідні сигнали «на зсув». Це саме по собі не економить ні час, ні обсяг. Однак при обчисленнях можна робити «округлення», при цьому способі концентрування, правда, на виході все ж будуть присутні «порожні» канали зв'язку, але їх кількість можна значно скоротити. Нехай на кожному кроці робиться округлення величиною α, оскільки ступенів всього lnN, то наприкінці замість чорної смужки довжиною L, буде отримана смужка, в якій всі чорні клітини розташовані на лівій подполоске довжини 1/((1-d) 〖^lnN〗)L.
Якщо α брати близько 1/lnN, то така помилка терпима при недостатній доопрацювання схеми телефонической станції. Необхідне для такої точності кількість кроків (зрушень) х на кожній ступені визначається з співвідношення 1/2х<1/lnN=>x≈lnlnN, що дає концентратор економічної вартості 0[lnNxN]=0[N (lnN)(lnlnN)] і затримки 0[(lnN)(lnlnN)].
Пред'явлені схеми мають один маленький недолік: якщо перестановка адресацій зміниться хоча б на кілька транспозицій, то доведеться пересортировывать, може так статися більшу частину каналів. Все ж нерозривне з'єднання навіть із застосуванням цих схем можливо при використанні дублювання двох станцій один одним. Ці станції працюють позмінно: на запит про деяку перестановку з'єднання перша прокладає канали зв'язку, якщо після цього деякий безліч абонентів змінили адреси призначення, перша продовжує об'єднувати інших, а друга обчислює» нову перестановку для всіх абонентів і прокладає свої канали зв'язку. Для абонентів, які не змінили своїх адресатів, канали зв'язку, таким чином, дублюються. Після того, як другий станцією встановлено з'єднання, канали, побудовані першої, обробляються. В результаті позмінної роботи будь абоненти можуть мати безперервне з'єднання скільки завгодно довго і незалежно від інших, проте воно буде здійснюватися, взагалі кажучи, мінливих каналах зв'язку.

Цікаві проблеми, що вимагають свого рішення.

Для реалізації телефонної станції не обов'язково застосовувати концентратор, обрывающий всі «порожні» канали зв'язку. Для того, щоб стріляло не потрібно уран обтащать на 100%- це економічно занадто дорого. Досить, щоб була можливість подвоїти концентрацію, як на рис. 10.

Автору не вдалося узагальнити нижню оцінку 0(NlnN) за кількістю використаних телефоністок для таких схем. Більше того, існує непрямі наведення, що такі концентратори можуть бути реалізовані з використанням 0(N) телефоністок і затримкою 0(1). Якщо це так, то використання призводить до телефонних станцій, досягають нижньої оцінки 0(NlnN) за обсягом та 0(lnN) за затримку. Ця остання оцінка непогано вписується в картину світу:
1)Можна помітити, що кількість жителів столиці деякої країни приблизно дорівнює кількості жителів всіх обласних центрів і приблизно дорівнює чисельності жителів у всіх її районних центрах. Пояснення цьому давала б схема рис. 5, за умови існування економічних і швидких концентраторів.
2)Як було показано, для телефонних станцій властива мінімум сесії робота. Якби існували економічні швидкі концентратори, то тривалість сеансів становила б ≈lnN характерних часів спрацьовування телефоністки. Кількість нейронів мозку ≈1012 ≈418 ( з деяких причин 4 більш природне число для нейрона). Максимальна частота роботи нейрона 1000 Гц, частота хвиль мозку в момент активності 40 Гц, що приблизно 1000Гц/(〖log〗_4×4^18 ).
Ще одна проблема полягає у постійній пересортировке каналів зв'язку. Якщо б вдалося знайти більш статичну схему адресації, подібною схемою рис. 3, де адресація відбувається незалежно, то ця схема могла б бути моделлю формування рефлексів: якщо певний канал досить часто виділяється, то він може перейти в постійний, відокремившися від сортирующей схеми.

Сергій Коваленко,
осінь, 2014 рік, р. Дубна.
www.webisgroup.ru
Автор висловлює свою вдячність Анастасії Одиноковой, люб'язно погодилася передрукувати рукопис і виконати малюнки.
Будь-які зауваження ви можете надіслати на пошту magnolia@bk.ru

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.