Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Судоку и хроматические многочлены
Раздел: Рефераты по математике
Тип: реферат Добавлен 13:25:45 05 сентября 2009 Похожие работы
Просмотров: 234 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

ОТДЕЛ ОБРАЗОВАНИЯ ГОМЕЛЬСКОГО ГОРОДСКОГО

ИСПОЛНИТЕЛЬНОГО КОМИТЕТА

Государственное учреждение образования

"Средняя общеобразовательная школа № 22 г. Гомеля"

Конкурсная работа

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

Ученика

9Б класса

ГУО СОШ№22 г. Гомеля

Громыко Ильи Алексеевича

Научный руководитель -

Горский Сергей Михайлович,

учитель математики

Государственного учреждения образования

СОШ №22 г. Гомеля

Гомель 2009

Содержание

Введение

1. Хроматические многочлены

2. Подсчет решений судоку

Заключение

Список использованных источников

Приложение

Введение

Первое упоминание о латинских квадратах (в связи с решением карточных задач) относится к 1723 г. Систематическое изучение латинских квадратов началось с работ Эйлера.

В XVIII веке, когда Эйлер ввел понятие греко-латинских (ортогональных) квадратов, они были просто новыми чисто математическими объектами. В дальнейшем латинские и особенно ортогональные латинские квадраты нашли применения в различных областях.

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

Системы попарно ортогональных латинских квадратов используются при построении сеточных методов интегрирования в вычислительной математике.

В 30-х годах XX века Р. Фишер предложил использовать латинские (и ортогональные латинские) квадраты для планирования сельскохозяйственных экспериментов.

Еще одна область применения латинских квадратов - построение кодов, исправляющих ошибки.

Вряд ли Эйлер предполагал, что латинские квадраты будут столь широко применяться, однако его математическая интуиция помогла правильно оценить естественность конструкции и нетривиальность свойств латинских квадратов.

Между головоломкой судоку и латинскими квадратами существует прямая взаимосвязь: завершенная сетка судоку является специальным типом латинского квадрата с дополнительной особенностью - никаких повторяющихся чисел в любом блоке 3х3.

Для каждого, кто пытался, решить задачу судоку, естественно возникают несколько вопросов. Для данной задачи, решение существует? Если решение существует, оно единственное? Если решение не единственное, сколько решений есть? Кроме того, есть систематический путь определения всех решений? Каково минимальное количество данных, с помощью которых можно гарантировать уникальное решение? В большинстве задач - минимум 17. Неизвестно в настоящее время, если задача с 16 данными, дающее единственное решение. Gordon Royle собрал 36 628 задач судоку с 17 числами, имеющие единственное решение.

Мы переформулируем эти вопросы в математическом контексте и попытаемся ответить на них. Более точно, мы интерпретируем судоку как задачу окрашивания вершин в теории графов. Это позволит нам, обобщить вопросы и рассматривать их в более широком смысле.

1. Хроматические многочлены

m-раскраска графа G - отображение f между вершинами G и множеством {1, 2,..., ь}. Такое отображение называется соответствующей раскраской, если f (x) <>f (y) всякий раз, когда x и y смежные в G. Минимальное количество цветов требовавшихся, чтобы правильно окрашивать грани графа G называется хроматическое число G и обозначенное x (G). Не трудно видеть, что судоку является проблемой раскраски графа. На самом деле, мы соединяем граф с сеткой 9 x 9 судоку следующим образом. Граф будет иметь 81 грани с каждой вершиной, соответствующей ячейке в сетке. Две четких грани будут смежными тогда и только тогда соответствующие ячейки в сетке, также в той же строчке, или той же колонне, или той же подсетке.

Мы обозначим этот графа Xn и называем это граф судоку ранга n. Квадрат судоку ранга n будет соответствующей раскраской этого графа, использовавшего n2 цвета. Задача судоку интерпретируется в частичную раскраску, и вопрос является независимо ли от этой частичной раскраски раскраска может быть завершена.

Множество направлений раскраски графа G с m цветами как хорошо известно будет полиномом в со степенью m и будет равняться количеству граней G.

Теорема 1. Пусть G будет конечный граф с v гранями. Пусть, C будет частичная соответствующая раскраска t граней G, использовавших d0 цвета. Пусть pGC (m) быть множеством направлений, завершающим эту раскраску использования m цветами, чтобы получать соответствующую раскраску G. Тогда, pGC (m), полином с целыми коэффициентами и степенью v-t для m>d0.

Данная задача Sudoku (X3, C), имеет уникальное решение тогда и только тогда это число pX3 C (9) = 1. Это будет чрезвычайно интересным, чтобы определяться под которым условия частичная раскраска может быть распространена на уникальную раскраску.

Теорема 2. Пусть, G будет граф с хроматическим числом x (G) и C будет частичная раскраска G, использовавшая только x (G) - 2 цвета. Если частичная раскраска может быть завершена в общую соответствующую раскраску G, тогда есть по крайней мере два пути расширения раскраски.

2. Подсчет решений судоку

Мы кратко рассмотрим вопрос единственности решения для задачи Sudoku. В начале не всегда ясно имеет ли данная задача решение. В этой части, мы получим необходимые условия для того, чтобы быть определить единственное решение.

На рисунке 1. пример задачи судоку, которая имеет точно два решения.

Это наблюдение лидирует в следующее замечания. Если в решении в задачу судоку мы указали бы, что конфигурация на рисунке 3 в том же вертикальном стеке, тогда по крайней мере одно из этих данных должны быть включены как "данный" в начальной задаче, в противном случае, у нас было бы два возможных решения в начальной задаче возникающие просто перестановкой a и b в конфигурации.

Как замечено ранее, если точное число "цветов" использованных в данной задаче судоку - самое большее семь, тогда есть по крайней мере два решения в задачу. Мы отметим, что это было таким поскольку мы могли взаимообмен два неиспользованных цвета и все еще получать правильное решение. Множественность решений может также видна из хроматического многочлена. Если d0 количество использовавшихся цветов, мы видели, что pX3,C (m), полином по m, m> d0. Так как хроматическое число X3 = 9, мы должны иметь pX 3 C (m) = 0 для m = d0,d0 + 1,...,8. Как pX 3C (m), полином с целыми коэффициентами, мы можем записать pX3,C (m) = (m - d0) (m- (d0+ 1)) … (m-8) q (m), для некоторого полинома q (ь) с целыми коэффициентами. При m = 9 получаем pX3,C (9) = (9-d0) Б=q (9) и право сторонняя сторона больше или равна 2 если d0>= 7. Это дает нам установленное необходимое условие для там, чтобы было единственное решение, при условии, что у задачи есть решение.

Заключение

Интересно отметить, что задача судоку чрезвычайно популярна по нескольким причинам. Заслуживает внимания то, что эта задача судоку вызвала несколько проблем математической природы, которые пока нерешены. Мы уже упомянули проблему "минимальной задачи судоку", где мы спрашиваем, если есть задача судоку с 16 или меньшими данными, которые допускают единственное решение.

Мы уже прокомментировали что, если только 7 или меньшее количество цветов использованы, задача не имеет единственного решения.

Эти вопросы предполагают более общий вопрос определения "минимума судоку" для общей задачи ранга n.

Мы уже отмечали различные симметрии квадратов судоку. Например, применяя перестановку к элементам {1,2,..., n2}, мы получим новый квадрат судоку. Таким образом, начиная с одного такого квадрата, мы можем произвести n2 ! новых судоку. Есть также ленточные перестановки их n!, а также перестановки столбцов, которых также n!. Мы можем переставить колонки в пределах полосы, а также столбцы в пределах стека - n! n симметрий. В итоге, это генерирует группу симметрии, которые могут быть рассмотрены как подгруппа Sn4. Будет интересным определить размер и структуру этой подгруппы.

Список использованных источников

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.

Приложение

Рис. 1

Рис. 2

Рис. 3

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:36:12 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:06:15 29 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150687)
Комментарии (1839)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru