Сортировка с помощью обжига стружки

МЕНЮ


Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости

Новостная лента форума ailab.ru


Этот пост касается различных динамических систем, состояния которых являются конфигурациями меченых чипов на одномерной целочисленной решетке. В этих конфигурациях несколько чипов могут занимать один и тот же сайт на решетке (и “относительное” положение чипов на одном и том же сайте не имеет значения).

Основным результатом работы [ 3 ] является следующая теорема:

Теорема. Поместите фишки, помеченные (1) (северный) на участке 0 на целочисленной решетке, и повторно примените движения формы

Если обломоки (ля) и (b) оба на месте к с a  , то сползите обломок (ля) к месту к-1 и обломок (b) к месту к+1

до тех пор, пока не будет сделано никаких дальнейших шагов. Затем, если n  equiv 0  mod 2 окончательная конфигурация фишек не зависит от сделанных ходов, и в частности, фишки сортируются в том смысле, что если a  затем фишка (ля) находится слева от чипа (b) .

Обратите внимание , что еслиn  equiv 1  mod 2 , там может быть несколько конечных конфигураций и чипы не нужно в конечном итоге отсортированы.

Следующие гипотезы являются вариантами приведенной выше теоремы.

ОПАК-006. Поместите фишки, помеченные (1) (северный) на участке 0 на целочисленной решетке, и повторно примените движения формы

Если обломоки(ля) , (b) и (с) все на месте к с a < b  , то сползите обломок (ля) к месту к-1 и обломок (с) к месту к+1

до тех пор, пока не будет сделано никаких дальнейших шагов. Покажите, что еслиn  equiv 3  mod 4 , то конечная конфигурация фишек не зависит от сделанных ходов, и в частности, фишки слабо сортируются в том смысле, что если a  тогда фишка (ля) находится не справа от фишки (b) .

Примечание: это частный случай гипотезы 22 из [ 3 ].

ОПАК-007. Поместите фишки, помеченные (1) (северный) на участке 0 на целочисленной решетке, и повторно примените движения формы

Если чипы (ля) (b) , (с) и (д) все на сайте к Сa < b < c  , то слайд чипы (ля) и (b) на сайт к-1 и чипы (с) и (д) на сайт к+1

до тех пор, пока не будет сделано никаких дальнейших шагов. Покажите, что еслиn  equiv 0  mod 4 , то конечная конфигурация фишек не зависит от сделанных ходов, и в частности, фишки слабо отсортированы.

Примечание: это частный случай гипотезы 25 из [ 3 ].

Вполне возможно, что методы этого документа могли бы быть приложены с целью решения этих проблем. Однако я бы предпочел видеть новый и более простой подход (возможно, используя связь с корневыми системами, изученными в [ 1 ] и [ 2 ]).


Источник: realopacblog.wordpress.com

Комментарии: