Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Латинську квадрат



План:


Введення

Латинську квадрат - таблиця n n, заповнена n різними символами таким чином, щоб в кожному рядку і в кожному стовпці зустрічалися всі n символів (кожен по одному разу). Нижче наводяться два приклади:

\ Begin {bmatrix} 1 & 2 & 3 \ \ 2 & 3 & 1 \ \ 3 & 1 & 2 \ \ \ end {bmatrix}\ Begin {bmatrix} A & B & C \ \ B & C & A \ \ C & A & B \ \ \ end {bmatrix}

Латинські квадрати існують для будь-якого n.

Будь латинський квадрат є таблицею множення ( таблицею Келі) квазігруппи.

Назва "латинський квадрат" бере початок від Леонарда Ейлера, який використовував латинські букви замість цифр у таблиці.


1. Ортогональні латинські квадрати

Два латинських квадрата називаються ортогональними, якщо різні всі впорядковані пари символів (a, b), де a - символ в деякій клітині першого латинського квадрата, а b - символ в тій же клітини другого латинського квадрата. Приклад пари ортогональних латинських квадратів:

\ Begin {bmatrix} 1 & 2 & 3 \ \ 2 & 3 & 1 \ \ 3 & 1 & 2 \ \ \ end {bmatrix} \ quad \ quad \ begin {bmatrix} 1 & 2 & 3 \ \ 3 & 1 & 2 \ \ 2 & 3 & 1 \ \ \ end {bmatrix}

Легко бачити, що у відповідному квадраті з пар всі пари різні:

\ Begin {bmatrix} 11 & 22 & 33 \ \ 23 & 31 & 12 \ \ 32 & 13 & 21 \ \ \ end {bmatrix}

Ортогональні латинські квадрати існують для будь-якого порядку n крім 2 і 6. Для n є ступенем простого числа є набір n -1 попарно ортогональних латинських квадратів. Такий набір можна взаємооднозначної зіставити з кінцевою проективної площиною порядку n.

Якщо в кожній діагоналі латинського квадрата всі елементи різні, такий латинський квадрат називається діагональним. Пари ортогональних діагональних латинських квадратів існують для всіх порядків, крім 2, 3 та 6. Приклад пари діагональних ортогональних латинських квадратів 5-го порядку:

\ Begin {bmatrix} 1 & 2 & 3 & 4 & 5 \ \ 5 & 3 & 4 & 1 & 2 \ \ 4 & 5 & 2 & 3 & 1 \ \ 2 & 4 & 1 & 5 & 3 \ \ 3 & 1 & 5 & 2 & 4 \ \ \ end {bmatrix} \ quad \ quad \ begin {bmatrix} 1 & 2 & 3 & 4 & 5 \ \ 4 & 5 & 2 & 3 & 1 \ \ 5 & 3 & 4 & 1 & 2 \ \ 3 & 1 & 5 & 2 & 4 \ \ 2 & 4 & 1 & 5 & 3 \ \ \ end {bmatrix}

Квадрат з пар елементів двох ортогональних латинських квадратів називається греко-латинську квадратом. Подібні квадрати часто використовуються для побудови магічних квадратів. [1]


2. Використання латинських квадратів для планування експериментів

Припустимо, що потрібно провести декілька експериментів, що залежать від 3 параметрів 1 ≤ a, b, cn, так щоб для кожної пари параметрів були випробувані всі n варіантів. Тоді потрібно взяти будь латинський квадрат порядку n і провести n експериментів з параметрами a = номер рядка, b = номер стовпця, c = значення в клітці латинського квадрата.

3. Завдання про заповнення латинського квадрата

Нехай дана таблиця n n, в якій деякі осередки порожні, а в деяких стоять числа від 1 до n. Завдання про заповнення латинського квадрата формулюється так: чи існує спосіб вписати числа в порожні клітинки так, щоб отримана таблиця стала латинським квадратом?

Завдання про заповнення латинського квадрата NP-повна. Однак, якщо заповнені кілька верхніх рядків, то квадрат завжди можна доповнити до латинського.

Примітки

  1. М. Макарова. Нові аспекти методу латинських квадратів - www.natalimak1.narod.ru/aspekty.htm

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Латинську мову
Квадрат
Кодекартов квадрат
Декартом квадрат
Квадрат Полібія
Семіотичний квадрат
Квадрат (кінь)
Червоний квадрат
Чорний квадрат
© Усі права захищені
написати до нас
Рейтинг@Mail.ru