Алгоритмы генерации магических квадратов (стр. 1 из 5)

Введение

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

Поэтому актуальной является задача программной реализации алгоритма заполнения магического квадрата.

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

Для достижения поставленной цели в выпускной квалификационной работе решаются следующие задачи:

1) Рассмотреть все известные виды магических квадратов.

2) Ознакомиться с различными алгоритмами заполнения магических квадратов.

3) Проанализировать компьютерную реализацию магических квадратов.

4) Реализовать некоторые алгоритмы заполнения магических квадратов на языке программирования высокого уровня.

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

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

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

Структура и объём работы. Выпускная квалификационная работа состоит из введения, 3 глав основного раздела и списка литературы. Содержание работы изложено на 42 страницах, включая список литературы из 15 наименований.

Глава 1. Обзор магических фигур

1.1 История магических фигур

Магические фигуры – геометрические фигуры, обладающие одним общим математическим свойством – суммы по всем строкам, столбцам, диагоналям равны между собой. Существуют магические треугольники, квадраты и кубы. Треугольники можно рассматривать как учебное пособие для детей младших классов. Квадраты же находят свое применение в криптографии - хотя для развития навыков программирования подходят просто блестяще. Магические кубы также находят свое применение в криптографии. Однако использовать их в качестве учебного пособия можно только в ВУЗах, т.к. они имеют очень сложные алгоритмы составления и требуют немалых вычислительных мощностей. Поэтому далее мы сосредоточим свое внимание на магических квадратах.

Мы не знаем страну, в которой были придуманы магические квадраты, не знаем век (и даже тысячелетие!), в котором они были впервые составлены. Известно только, что они появились задолго до эры вульгарис, и их родиной был Древний Восток. Существует китайская легенда, в которой говорится, что во времена правления императора Юй (около 2200 г. до н.э.) из вод Хуанхэ всплыла черепаха, у которой на панцире были начертаны таинственные иероглифы, эти знаки известны под названием ло-шу и равносильны магическому квадрату. Сравните рис. 1 с квадратом из первого примера п.1. [6]

Первый магический квадрат с тремя клетками в основании был описан в арабском манускрипте конца восьмого века, где упоминался его автор – греческий философ-неопифагореец Аполлоний Тианский (инвоцированный, кстати, Элиафасом Леви!), живший в начале эры вульгарис. Однако не он был создателем этого древнейшего из всех магических квадратов. Аполлоний лишь вновь открыл то, что было известно за много веков до него.

Рис.1

В XI в. магические квадраты появились в Индии, а затем в Японии, где в XVI в. им была посвящена обширная литература. По-видимому, первое сочинение о магических квадратах, дошедшее до наших дней, было написано византийским грамматистом и лексикографом Мануэлем Мосхопулосом (примерно 1300 г). Он опубликовал многие построенные им МК с разным числом клеток в основании.

За работой Мосхопулоса последовали труды сотен математиков, в том числе крупнейших ученых, основоположников современной науки (Гаусс, Эйлер, Ферма).

В начале XVI в. магический квадрат появился в искусстве.

Великий немецкий художник Альбрехт Дюрер выпустил в 1514 г. гравюру, названную им «Меланхолия». На её заднем плане помещен магический квадрат 4 × 4, два средних числа его нижней строки (15 и 14) образуют дату создания гравюры.

С глубокой древности и до времени Дюрера сохранилось учение о том, что люди разного темперамента находятся под влиянием разных планет. Сангвиникам покровительствуют планеты Юпитер и Венера, холерики находятся под влиянием Марса, флегматики направляются Луной, а меланхолики - Сатурном. Почему для защиты Меланхолии Дюрер изобразил магический квадрат именно 4-го порядка, а не 5-го, например? Ответ мы находим в работе Корнелия Агриппы «Об оккультной философии». Агриппа пользовался древней космогонией Птолемея: в центре мира - Земля; вокруг нее небесные сферы, вложенные друг в друга, как старинные китайские резные шары из слоновой кости. Каждая сфера содержит орбиту одной планеты. На внутренней - Луна. Далее - Меркурий, Венера, Солнце, Марс, Юпитер и на внешней - Сатурн. Планеты Юпитер и Сатурн враждуют друг с другом, как и их божественные прототипы, Кронос и победивший его Зевс. (Кстати, в своем сочинении Агриппа описал семь магических квадратов, имеющих в основании от 3 до 9 клеток. Он назвал их «планетными таблицами», связав с каждой из семи планет).

Именно поэтому Дюрер для защиты своего крылатого Гения от судьбоносного Сатурна (3) изобразил магический квадрат Юпитера (4). Юпитер должен был вновь победить Сатурна. (Однако, судя по выражению лица персонажа, этого не произошло)

Дюрер, как и любой настоящий художник, и учёный, занимался оккультизмом, о чём свидетельствует его колода Таро (см. рисунок).[5]

Рис.2

В конце XVII в. были опубликованы сочинения о магических квадратах французских математиков Арно, Озанама и Симона де Лялюбера.

Сочинения академика Бернара Френикля де Бесси были впервые напечатаны в результате хлопот математика Лягира только в 1693 г, спустя 18 лет после смерти Френикля. Не будь Лягира, неизвестно, сколько еще лет лежали бы работы Френикля в архивах Королевской академии.

В «Общей таблице магических квадратов в четыре» Френикль привёл все 880 магических квадратов четвёртого порядка. Таблица занимает 43 страницы книги. Трудно представить себе, сколько времени заняла у Френикля эта работа.

В 1705 г. в Париже было издано сочинение уже упомянутого ранее Филиппа де Лягира «Новые начертания и соображения о магических квадратах с их демонстрацией. Начертания магических квадратов при четном числе клеток в основании». Эта работа особенно интересна тем, что в ней Лягир впервые рассмотрел и описал особый тип магического квадрата, который он назвал «панмагическим». В нем содержится наибольшее число равных сумм чисел. В дальнейшем квадраты этого типа называли, также, «дьявольскими», «сатанинскими», «чертовскими».

Дьявольский магический квадрат — магический квадрат, в котором с константой совпадают также суммы чисел по ломаным диагоналям в обоих направлениях.

Ломаной диагональю называется диагональ, которая, дойдя до границы квадрата, продолжается параллельно первому отрезку от противоположного края (на рисунке такую диагональ образуют закрашенные клетки). [1]

Рис.3

Существует всего три дьявольских квадрата 4×4:

Современные математики называют подобные квадраты «совершенными». Стало быть, «совершенный» и «дьявольский» для современных математиков – синонимы!

Но есть еще один МК не менее интересный, чем дьявольский. Выдающийся американский масон, ученый, общественный деятель и дипломат Бенджамин Франклин составил квадрат 16×16 (см. рис. 4), который помимо наличия постоянной суммы 2056 во всех строках, столбцах и диагоналях имел еще одно дополнительное свойство. Если вырезать из листа бумаги квадрат 4×4 и уложить этот лист на большой квадрат так, чтобы 16 клеток большего квадрата попали в эту прорезь, то сумма чисел, появившихся в этой прорези, куда бы мы ее не положили, будет одна и та же – 2056.

Рис. 4

Этот квадрат является самым магически-магическим из всех МК, составленных когда-либо каким-либо магом.

В 1917 г. на франко-германском фронте, унтер-офицер Франц Буль, занимаясь мародерством на поле боя, нашел в кармане убитого солдата-индуса длинную полоску плотной бумаги, которая была исписана квадратами, разделенными на клетки, заполненными арабской вязью. Он передал эту полоску немецкому профессору, который занимался магическими квадратами. Скорее всего, полоска содержала талисман, не спасший, однако, его обладателя от смерти.

После перевода с арабского языка, выяснилось, что документ содержит магический квадрат 3-его порядка и полумагический квадрат 4-ого порядка. В квадрате 4 × 4 числа повторяются, и суммы диагоналей не совпадают с константой:

Затем следовал список заклинаний, имён богов и демонов, который профессор просто оторвал и уничтожил.[2]

Традиционной сферой применения МК являются талисманы. (Полный список планетных талисманов можно найти в монографии А.Санарова «Магия талисманов. Практическое пособие»).