2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Упорядочить вслепую.
Сообщение19.12.2013, 01:10 
Аватара пользователя


29/08/12
40
Вечно зеленый
лишнии 5$ никогда не помешают, только я у себя нашел

 Профиль  
                  
 
 Re: Упорядочить вслепую.
Сообщение19.12.2013, 15:46 
Заслуженный участник
Аватара пользователя


06/04/10
3152
BatMan в сообщении #803344 писал(а):
нашел 2 лишних сравнения)

По сравнению с картинкой?

 Профиль  
                  
 
 Re: Упорядочить вслепую.
Сообщение20.12.2013, 12:32 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Остался вопрос про возможность доказательства нижней оценки. В лоб, перебором, явно не проходит...

 Профиль  
                  
 
 Re: Упорядочить вслепую.
Сообщение20.12.2013, 12:45 


14/01/11
3040
Кстати, каково максимальное число транспозиций в минимальном разложении перестановки из 8 элементов?

 Профиль  
                  
 
 Re: Упорядочить вслепую.
Сообщение20.12.2013, 14:59 
Заслуженный участник


04/05/09
4587
Sender в сообщении #803834 писал(а):
Кстати, каково максимальное число транспозиций в минимальном разложении перестановки из 8 элементов?
7?

 Профиль  
                  
 
 Re: Упорядочить вслепую.
Сообщение20.12.2013, 15:10 


14/01/11
3040
Да, похоже на то. По крайней мере, мы имеем доказанную нижнюю оценку. :-)

 Профиль  
                  
 
 Re: Упорядочить вслепую.
Сообщение22.12.2013, 01:59 
Аватара пользователя


03/10/13
449
nikvic в сообщении #803832 писал(а):
Остался вопрос про возможность доказательства нижней оценки. В лоб, перебором, явно не проходит...

Да вроде-таки в лоб и перебором. В энвики написано, что оптимальную сортирующую сеть из 8 элементов (с док-вом оптимальности, видимо) нашёл Кнут аж в 1997 году; и вот что-то мне не кажется, что было красивое доказательство нижней оценки с использованием, например, каких-то инвариантов, а кажется, что к 1997 году вычислительные мощности стали такими, что позволили сделать перебор.

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

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



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

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


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

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