Реферат: Судоку и хроматические многочлены


Рубрика: Математика, логіка
Вид: реферат
Мова: російський
Розмір файлу: 56 кБ

Скачати реферат

Первое упоминание о латинских квадратах (в связи с решением карточных задач) относится к 1723 г. Систематическое изучение латинских квадратов началось с работ Эйлера.
В XVIII веке, когда Эйлер ввел понятие греко-латинских (ортогональных) квадратов, они были просто новыми чисто математическими объектами. В дальнейшем латинские и особенно ортогональные латинские квадраты нашли применения в различных областях.
В комбинаторике полные системы ортогональных латинских квадратов соответствуют конечным аффинным и проективным плоскостям. Латинские квадраты используются при построении квадратов Рума (турниров игры в бридж). В конце XIX века Кэли показал, что таблица умножения элементов конечной группы является латинским квадратом. В 30-х годах XX века возникло понятие квазигруппы, в которой таблицей умножения может быть любой латинский квадрат.
Системы попарно ортогональных латинских квадратов используются при построении сеточных методов интегрирования в вычислительной математике.
В 30-х годах XX века Р. Фишер предложил использовать латинские (и ортогональные латинские) квадраты для планирования сельскохозяйственных экспериментов.
Еще одна область применения латинских квадратов - построение кодов, исправляющих ошибки.
Вряд ли Эйлер предполагал, что латинские квадраты будут столь широко применяться, однако его математическая интуиция помогла правильно оценить естественность конструкции и нетривиальность свойств латинских квадратов.
Между головоломкой судоку и латинскими квадратами существует прямая взаимосвязь: завершенная сетка судоку является специальным типом латинского квадрата с дополнительной особенностью - никаких повторяющихся чисел в любом блоке 3х3.

Список використаної літератури:


1. S. Bammel and J. Rothstein, The number of 9 Ч 9 Latin squares, Discrete Math.11 (1975), 93-95.
2. C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, J.comb. Theory Ser. B 48 (1990), no.1, 19-44.
3. B. Felgenhauer and A. F. Jarvis, Mathematics of Sudoku I, Mathematical Spectrum 39 (2006), 15-22.
4. E.russell and A. F. Jarvis, Mathematics of Sudoku II, Mathematical Spectrum 39 (2006), 54-58.
5. J. H. Van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992. Безкоштовно скачати реферат "Судоку и хроматические многочлены" в повному обсязі