Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 4210 ]  На страницу Пред.  1 ... 57, 58, 59, 60, 61, 62, 63 ... 421  След.
Автор Сообщение
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 10:39 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7479
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
646 раз в 566 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Avgust
проверила. Увы! Диагональных ОЛК нет к этому ДЛК.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 20:39 
Не в сети
Продвинутый
Аватара пользователя
Зарегистрирован:
29 фев 2016, 15:44
Сообщений: 92
Cпасибо сказано: 2
Спасибо получено:
42 раз в 29 сообщениях
Очков репутации: 10

Добавить очки репутацииУменьшить очки репутации
Восстановил по памяти свою программу проверки ДЛК на изоморфизм.

Эта программа любой ДЛК10 приводит к канонической форме. Все ДЛК, принадлежащие одному и тому же классу изоморфизма (изоморфы), имеют одну и туже каноническую форму, а ДЛК, принадлежащие разным классам изоморфизма, имеют разные канонические формы.

Для проверки двух ДЛК на изоморфизм, нужно их привести к канонической форме и сравнить. ДЛК изморфны тогда и только тогда, когда из канонические формы равны.

Сейчас у меня нет доступа к нормальному компилятору, поэтому выкладываю исходик. Его нужно скопировать, вставить в какой-нибудь онлайн-компилятор, например http://ideone.com/, и кликнуть Run.

Исходный ДЛК прописан в программе, для проверки другого ДЛК, замените код:

int isxodn[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{9,8,7,6,5,4,3,2,1,0},
{6,4,9,8,7,2,1,0,5,3},
{5,0,1,7,3,6,2,8,9,4},
{3,5,0,1,2,7,8,9,4,6},
{4,9,8,2,6,3,7,1,0,5},
{1,2,3,5,9,0,4,6,7,8},
{7,6,4,9,1,8,0,5,3,2},
{2,3,5,0,8,1,9,4,6,7},
{8,7,6,4,0,9,5,3,2,1}};

нужным.

Текс программы в оффтопе.
#include <iostream>

using namespace std;

const int chprst = 120;
const int chkrtzh = 32;
const int prst[chprst] = {
3,2,1,0,3,0,1,2,3,1,3,2,1,0,1,0,1,2,3,2,3,2,1,0,
1,0,1,2,3,1,3,2,1,0,3,0,1,2,3,0,3,2,1,0,3,0,1,2,
3,1,3,2,1,0,1,0,1,2,3,2,3,2,1,0,1,0,1,2,3,1,3,2,
1,0,3,0,1,2,3,0,3,2,1,0,3,0,1,2,3,1,3,2,1,0,1,0,
1,2,3,2,3,2,1,0,1,0,1,2,3,1,3,2,1,0,3,0,1,2,3,0};
const int krtzh[chkrtzh] = {
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4};

int isxodn[10][10] = {
{0,1,2,3,4,5,6,7,8,9},
{9,8,7,6,5,4,3,2,1,0},
{6,4,9,8,7,2,1,0,5,3},
{5,0,1,7,3,6,2,8,9,4},
{3,5,0,1,2,7,8,9,4,6},
{4,9,8,2,6,3,7,1,0,5},
{1,2,3,5,9,0,4,6,7,8},
{7,6,4,9,1,8,0,5,3,2},
{2,3,5,0,8,1,9,4,6,7},
{8,7,6,4,0,9,5,3,2,1}};

int kanon[100] = {10};

void rabota();
void vvod(int izomorf[][10][10]);

inline void preobr_4(int x, int izomorf[10][10]){
for(int i = 0; i < 10; i++){
swap(izomorf[i][x], izomorf[i][x + 1]);
swap(izomorf[i][9 - x], izomorf[i][8 - x]);
}
for(int i = 0; i < 10; i++){
swap(izomorf[x][i], izomorf[x + 1][i]);
swap(izomorf[9 - x][i], izomorf[8 - x][i]);
}
}

inline void preobr_2(int x, int izomorf[10][10]){
for(int i = 0; i < 10; i++) swap(izomorf[x][i], izomorf[9 - x][i]);
for(int i = 0; i < 10; i++) swap(izomorf[i][x], izomorf[i][9 - x]);
}

int main(){
rabota();
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++)
cout << kanon[i * 10 + j] << (j != 9 ? ' ' : '\n');
cout << endl;
return 0;
}

void rabota(){
int izomorf[4][10][10];
int temp[10][10];
int kraska[10];
vvod(izomorf);
for(int kvadrat = 0; kvadrat < 4; kvadrat++) for(int i = 0; i < chprst; i++){
for(int j = 0; j < chkrtzh; j++){
for(int k = 0; k < 10; k++) kraska[izomorf[kvadrat][0][k]] = k;
for(int k = 0; k < 10; k++) for(int l = 0; l < 10; l++){
temp[k][l] = kraska[izomorf[kvadrat][k][l]];
}
for(int k = 0; k < 100; k++){
if(kanon[k] > temp[k / 10][k % 10]){
for(int l = 0; l < 100; l++) kanon[l] = temp[l / 10][l % 10];
break;
}
else if(kanon[k] < temp[k / 10][k % 10]) break;
}
preobr_2(krtzh[j], izomorf[kvadrat]);
}
preobr_4(prst[i], izomorf[kvadrat]);
}
}

void vvod(int izomorf[][10][10]){
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++){
izomorf[0][i][j] = isxodn[i][j];
izomorf[1][j][i] = izomorf[0][i][j];
}
for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++){
izomorf[2][i][j] = izomorf[0][i][9 - j];
izomorf[3][i][j] = izomorf[1][i][9 - j];
}
}

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю whitefox "Спасибо" сказали:
Nataly-Mak
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 21:52 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7479
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
646 раз в 566 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
whitefox писал(а):
Восстановил по памяти свою программу проверки ДЛК на изоморфизм.

Эта программа любой ДЛК10 приводит к канонической форме. Все ДЛК, принадлежащие одному и тому же классу изоморфизма (изоморфы), имеют одну и туже каноническую форму, а ДЛК, принадлежащие разным классам изоморфизма, имеют разные канонические формы.

whitefox
здорово! Важнейшая программа классификации всех изоморфов ДЛК. Она даёт надежду на получение всей БД ДЛК.

Тестирую программу. Первый ДЛК для проверки - основной ДЛК Брауна:

0 8 5 1 7 3 4 6 9 2
5 1 7 2 9 8 0 3 4 6
1 7 2 9 5 6 8 0 3 4
9 6 4 3 0 2 7 1 5 8
3 0 8 6 4 1 5 9 2 7
4 3 0 8 6 5 9 2 7 1
7 2 9 5 1 4 6 8 0 3
6 4 3 0 8 9 2 7 1 5
2 9 6 4 3 7 1 5 8 0
8 5 1 7 2 0 3 4 6 9

Программа выдала следующую какноническую форму для данного ДЛК:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 9 5 6 7 8
3 5 9 1 2 7 8 0 4 6
5 9 8 7 6 3 2 1 0 4
7 6 4 9 8 1 0 5 3 2
4 0 1 2 3 6 7 8 9 5
9 8 7 6 5 4 3 2 1 0
2 3 5 0 1 8 9 4 6 7
6 4 0 8 7 2 1 9 5 3
8 7 6 5 9 0 4 3 2 1

Теперь беру один из ДЛК, полученных по матрице Avgust:

6 5 0 2 4 9 3 8 1 7
0 2 4 7 1 5 6 9 3 8
2 4 7 1 0 8 5 6 9 3
1 8 3 9 6 7 4 2 0 5
9 6 5 8 3 2 0 1 7 4
3 9 6 5 8 0 1 7 4 2
4 7 1 0 2 3 8 5 6 9
8 3 9 6 5 1 7 4 2 0
7 1 8 3 9 4 2 0 5 6
5 0 2 4 7 6 9 3 8 1

Программа выдала такую каноническую форму для этого ДЛК:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 9 5 6 7 8
3 5 9 1 2 7 8 0 4 6
5 9 8 7 6 3 2 1 0 4
7 6 4 9 8 1 0 5 3 2
4 0 1 2 3 6 7 8 9 5
9 8 7 6 5 4 3 2 1 0
2 3 5 0 1 8 9 4 6 7
6 4 0 8 7 2 1 9 5 3
8 7 6 5 9 0 4 3 2 1

Как видим, кононическая форма такая же, как в первом примере, значит, эти два ДЛК принадлежат одному классу изоморфизма (это все ДЛК, получаемые переобозначением элементов, в этом классе 10! изоморфов).

Третий ДЛК для тестирования - полученный мной М-преобразованием изоморф основного ДЛК Брауна:

5 2 9 3 8 1 6 0 7 4
7 0 3 1 4 5 8 6 9 2
8 5 7 0 6 3 9 2 4 1
0 3 8 4 2 7 5 1 6 9
1 4 2 9 3 6 0 7 5 8
9 6 1 5 7 2 4 8 3 0
2 9 6 8 5 4 1 3 0 7
4 7 0 6 1 8 3 9 2 5
6 1 4 2 9 0 7 5 8 3
3 8 5 7 0 9 2 4 1 6

Для этого ДЛК программа выдала следующую каноническую форму:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 9 5 6 7 8
4 0 8 2 3 6 7 1 9 5
9 8 7 6 5 4 3 2 1 0
3 5 9 8 7 2 1 0 4 6
2 3 5 9 8 1 0 4 6 7
7 6 4 0 1 8 9 5 3 2
8 7 6 5 9 0 4 3 2 1
6 4 0 1 2 7 8 9 5 3
5 9 1 7 6 3 2 8 0 4

Как видим, получилась другая каноническая форма, потому что это другой класс изоморфизма (ДЛК, получаемые М-преобразованиями).

whitefox
всё правильно поняла?
Если мы возьмём любой из 10! изоморфов основного ДЛК Брауна из класса изоморфизма - переобозначение элементов, получим для него одну и ту же каноническую форму. Так?
Точно так же для класса изоморфизма - М-преобразования.
А какие ещё будут классы изоморфизма?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 21:57 
В сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13571
Откуда: Москва
Cпасибо сказано: 1292
Спасибо получено:
3625 раз в 3182 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak
Вот теперь нужно тщательно рассмотреть две канонические формы и понять, как производить другие виды.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 22:01 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7479
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
646 раз в 566 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Четвёртый тест - нормализованный основной ДЛК Брауна

0 1 2 3 4 5 6 7 8 9
2 3 4 9 8 1 0 5 6 7
3 4 9 8 2 7 1 0 5 6
8 7 6 5 0 9 4 3 2 1
5 0 1 7 6 3 2 8 9 4
6 5 0 1 7 2 8 9 4 3
4 9 8 2 3 6 7 1 0 5
7 6 5 0 1 8 9 4 3 2
9 8 7 6 5 4 3 2 1 0
1 2 3 4 9 0 5 6 7 8


Выданная программой каноническая форма:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 9 5 6 7 8
3 5 9 1 2 7 8 0 4 6
5 9 8 7 6 3 2 1 0 4
7 6 4 9 8 1 0 5 3 2
4 0 1 2 3 6 7 8 9 5
9 8 7 6 5 4 3 2 1 0
2 3 5 0 1 8 9 4 6 7
6 4 0 8 7 2 1 9 5 3
8 7 6 5 9 0 4 3 2 1

Всё правильно: первый класс изоморфизма.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 22:05 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7479
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
646 раз в 566 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Avgust писал(а):
Вот теперь нужно тщательно рассмотреть две канонические формы и понять, как производить другие виды.

Совершенно верно. Только канонических форм, наверное, будет не две, а больше (?). Это нам whitefox расскажет. Хотя я пока не знаю других классов изоморфизма для ДЛК.

Вот смотрите: мой генератор генерирует ДЛК тысячами, но среди этих тысяч принципиально разных (не изоморфных) ДЛК раз-два и ... нету. Значит, надо генерировать сразу различные ДЛК, то есть при генерации проверять все получаемые ДЛК по канонической форме всех классов изоморфизма. Вот тогда в принципе возможно получить полную базу данных (БД) всех ДЛК. А сейчас их многие миллионы и разобраться в этой куче невозможно.

whitefox
а основные преобразования ЛК - повороты и отражения - у вас вошли в класс М-преобразований?
По идее вроде бы не должны, это отдельный класс изоморфизма.


Последний раз редактировалось Nataly-Mak 01 мар 2016, 22:29, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 22:26 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7479
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
646 раз в 566 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Повернула на 90 градусов нормализованный ДЛК Брауна и проверила его по программе.

Это проверяемый ДЛК (повёрнутый ДЛК Брауна в нормализованном виде):

1  9  7  4  6  5  8  3  2  0 
2 8 6 9 5 0 7 4 3 1
3 7 5 8 0 1 6 9 4 2
4 6 0 2 1 7 5 8 9 3
9 5 1 3 7 6 0 2 8 4
0 4 8 6 2 3 9 7 1 5
5 3 9 7 8 2 4 1 0 6
6 2 4 1 9 8 3 0 5 7
7 1 3 0 4 9 2 5 6 8
8 0 2 5 3 4 1 6 7 9

Программа выдала каноническую форму:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 9 5 6 7 8
3 5 9 1 2 7 8 0 4 6
5 9 8 7 6 3 2 1 0 4
7 6 4 9 8 1 0 5 3 2
4 0 1 2 3 6 7 8 9 5
9 8 7 6 5 4 3 2 1 0
2 3 5 0 1 8 9 4 6 7
6 4 0 8 7 2 1 9 5 3
8 7 6 5 9 0 4 3 2 1

Это класс изоморфизма - М-преобразования.
Получается, что и основные преобразования, и М-преобразования в одном классе изоморфизма, и всего изоморфов в этом классе 15360.
Так?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 22:30 
В сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13571
Откуда: Москва
Cпасибо сказано: 1292
Спасибо получено:
3625 раз в 3182 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Пока что опять только две канонические формы (КФ). А желательно 5-6 КФ, чтобы
понять свойства.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Avgust "Спасибо" сказали:
Nataly-Mak
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 22:43 
Не в сети
Свет и истина МРК
Аватара пользователя
Зарегистрирован:
06 янв 2015, 22:27
Сообщений: 7479
Откуда: Саратов
Cпасибо сказано: 842
Спасибо получено:
646 раз в 566 сообщениях
Очков репутации: -228

Добавить очки репутацииУменьшить очки репутации
Avgust
вы молодец!
Я сначала немного не так поняла количество канонических форм (КФ). Это количество совсем не равно количеству классов изоморфизма. КФ позволяет определить всех изоморфов для данной группы ДЛК.

Я нашла третью КФ!
Взяла нормализованный ДЛК Гергели

0 1 2 3 4 5 6 7 8 9
8 2 6 4 0 9 5 3 7 1
2 3 4 9 8 1 0 5 6 7
3 4 0 8 7 2 1 9 5 6
5 0 8 2 3 6 7 1 9 4
6 5 9 1 2 7 8 0 4 3
7 6 5 0 1 8 9 4 3 2
1 7 3 5 9 0 4 6 2 8
9 8 7 6 5 4 3 2 1 0
4 9 1 7 6 3 2 8 0 5

и проверила его по программе. Выдалась совсем другая КФ:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 9 5 6 7 8
3 4 9 8 7 2 1 0 5 6
4 0 1 7 3 6 2 8 9 5
9 8 7 6 5 4 3 2 1 0
5 9 8 2 6 3 7 1 0 4
6 5 0 1 2 7 8 9 4 3
7 6 5 0 8 1 9 4 3 2
2 3 4 9 1 8 0 5 6 7
8 7 6 5 9 0 4 3 2 1

В-о-о-о-о-т! Значит, ДЛК Гергели - совсем новый ДЛК, не имеющий никакого отношения к ДЛК Брауна, не получающийся из него никакими преобразованиями.

Итак, три КФ у нас уже есть. Сколько же их будет всего?
Для этого надо генерировать ДЛК и проверять их программой whitefox на КФ.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Ортогональные латинские квадраты 10-го порядка
СообщениеДобавлено: 01 мар 2016, 22:51 
Не в сети
Продвинутый
Аватара пользователя
Зарегистрирован:
29 фев 2016, 15:44
Сообщений: 92
Cпасибо сказано: 2
Спасибо получено:
42 раз в 29 сообщениях
Очков репутации: 10

Добавить очки репутацииУменьшить очки репутации
Nataly-Mak писал(а):
Получается, что и основные преобразования, и М-преобразования в одном классе изоморфизма, и всего изоморфов в этом классе 15360.
Так?
Всего имеется [math]15360\cdot 10!=55\ 738\ 368\ 000[/math] изоморфизмов ДЛК. В это число входят и повороты и отражения и М-преобразования и переобозначения элементов. И все ДЛК, которые любым из этих [math]55\ 738\ 368\ 000[/math] способов приводятся к одной и той же канонической форме, принадлежат одному классу изоморфизма.
Nataly-Mak писал(а):
Третий ДЛК для тестирования - полученный мной М-преобразованием изоморф основного ДЛК Брауна:
Какое именно преобразование вы применили?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.    На страницу Пред.  1 ... 57, 58, 59, 60, 61, 62, 63 ... 421  След.  Страница 60 из 421 [ Сообщений: 4210 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
О теме "Отрогональные латинские квадраты 10-го порядка"

в форуме Предложения, Замечания, Обратная связь

Nataly-Mak

21

2646

14 июн 2018, 05:28

Ортогональные векторы

в форуме Векторный анализ и Теория поля

kala12

2

273

02 ноя 2021, 15:04

Ортогональные собственные вектора

в форуме Аналитическая геометрия и Векторная алгебра

HJey

0

252

18 апр 2019, 23:18

Ортогональные центральные композиционный план

в форуме Исследование операций и Задачи оптимизации

AHAHAC

2

488

08 дек 2016, 09:20

Ряд Фурье и другие ортогональные разложения

в форуме Ряды Фурье и Интегральные преобразования

Chelovekley

1

515

29 апр 2015, 14:47

Обобщенные вещественно ортогональные формы в радиосвязи

в форуме Линейная и Абстрактная алгебра

mike84

2

593

14 июн 2015, 13:37

Доказать, что ортогональные проекции вершин н-мерного куба

в форуме Геометрия

Arzybek

13

587

18 сен 2020, 21:29

Квадраты

в форуме Интересные задачи участников форума MHP

Krash

20

864

18 июл 2021, 17:46

Квадраты и степени

в форуме Теория чисел

ammo77

1

319

23 дек 2019, 01:08

Квадраты в окружности

в форуме Начала анализа и Другие разделы школьной математики

nerzul88

8

622

20 май 2020, 09:48


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

Сейчас этот форум просматривают: Avgust, Gagarin и гости: 2


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2024 MathHelpPlanet.com. All rights reserved