| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| Ортогональные латинские квадраты 10-го порядка http://mathhelpplanet.com/viewtopic.php?f=57&t=46638 |
Страница 41 из 421 |
| Автор: | ivashenko [ 28 фев 2016, 00:17 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Nataly-Mak писал(а): Из книги М. Гарднера "Математические досуги" (М.: Мир, 1972): Цитата: После 1959 года резко возросли как скорость электронно-вычислительных машин, так и изобретательность математиков-программистов. Паркер написал программу для электронно-вычислительной машины UNIVAC-1206. которой требовалось от 28 до 45 минут рабочего времени, чтобы осуществить полный поиск квалратов, ортогональных заданному латинскому квадрату десятого порядка, то есть машина работала примерно в три триллиона раз быстрее старой SWAC. Результатом были сотни новых греко-латинских квадратов десятого порядка. Nataly-Mak писал(а): ivashenko так за сколько времени Паркер мог на ЭВМ находить все ортогональные соквадраты для заданного ЛК? Просветились? Получается, что я ничего не пререпутала. Нет? А где здесь сказано, что он находил их методом Эйлера? |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 00:20 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
svb писал(а): Вот, что пишет Кнут (т.4А): "Но даже в этом случае подход Эйлера-Паркера оказывается в тысячу раз лучше подхода Пейджа-Томпкинса. "Разложив" задачу на две отдельные фазы, одну для поиска секущих и вторую - для их объединения, Эйлер и Паркер, по сути, уменьшили стоимость вычислений с произведения T1T2 до суммы T1+T2. Мораль этой истории очевидна: комбинаторные задачи могут поставить нас перед лицом огромной совокупности возможностей, но мы не должны сразу же опускать руки. Одна хорошая идея может на много порядков сократить количество требующихся вычислений." примечание. Поиск секущих это поиск трансверсалей. ivashenko вы этот пост вроде читали. Нет? Предвижу вопрос: "А где здесь сказано, за сколько времени он находил ортогональный соквадрат к заданному ЛК?"
|
|
| Автор: | ivashenko [ 28 фев 2016, 00:23 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Nataly-Mak писал(а): svb писал(а): Вот, что пишет Кнут (т.4А): "Но даже в этом случае подход Эйлера-Паркера оказывается в тысячу раз лучше подхода Пейджа-Томпкинса. "Разложив" задачу на две отдельные фазы, одну для поиска секущих и вторую - для их объединения, Эйлер и Паркер, по сути, уменьшили стоимость вычислений с произведения T1T2 до суммы T1+T2. Мораль этой истории очевидна: комбинаторные задачи могут поставить нас перед лицом огромной совокупности возможностей, но мы не должны сразу же опускать руки. Одна хорошая идея может на много порядков сократить количество требующихся вычислений." примечание. Поиск секущих это поиск трансверсалей. ivashenko вы этот пост вроде читали. Нет? Читал, но здесь нет ни слова о том, что всё это относится к поиску ортогональных латинских квадратов. |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 00:25 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Вопрос оказался ещё интереснее, чем я предположила
|
|
| Автор: | ivashenko [ 28 фев 2016, 00:29 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Nataly-Mak писал(а): Вопрос оказался ещё интереснее, чем я предположила ![]() Это был не вопрос, а утверждение. Вы опять всё перепутали.
|
|
| Автор: | Avgust [ 28 фев 2016, 00:32 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Я правильно понял, что квадрат ![]() - это один из 808. И нужно найти подобные еще 807 штук. |
|
| Автор: | ivashenko [ 28 фев 2016, 00:36 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Avgust писал(а): Я правильно понял, что квадрат ![]() - это один из 808. И нужно найти подобные еще 807 штук. Это врядли. 808 трансверсалий, многие из них пересекаются, квадратов будет гораздо меньше. Нужно найти хотябы еще один такой квадрат, такой, что поместив содержимое его ячеек в соответствующие ячейки первого квадрата например справа от стоящих элементов первого квадрата, (т.е. в каждой ячейке окажется пара элементов) получим квадрат в котором нет одинаковых пар. |
|
| Автор: | ivashenko [ 28 фев 2016, 00:39 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Кстати, я производил расчет операций и времени исходя из того, что существует лишь 2 ОЛК, однако если их больше, то время расчета может существенно сократиться. |
|
| Автор: | Avgust [ 28 фев 2016, 00:44 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko Раз их намного меньше, чем 808, то есть какой-то простой способ определения всех квадратов. Наверное, это и есть конечная цель исследований в данной теме. |
|
| Автор: | ivashenko [ 28 фев 2016, 00:50 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Avgust писал(а): ivashenko Раз их намного меньше, чем 808, то есть какой-то простой способ определения всех квадратов. Наверное, это и есть конечная цель исследований в данной теме. Да, вот например Паркер, пользуясь подходом Эйлера, сумел определить с помощью ЭВМ все эти квадраты. А мы пока не можем додумать, в чем же заключается этот самый метод Эйлера, попытки же решить задачу простым перебором требуют слишком больших объемов вычислений. Т.е. перебор здесь однозначно присутствует, вопрос в том как сократить объем перебираемых вариантов. |
|
| Страница 41 из 421 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|