Наши посетители

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

       

 

Судоку помогла математикам 'перемешивать' изображения

 Математики воспользовались судоку для "перемешивания" изображений. Статья пока не принята к публикации в рецензируемом журнале, однако ее препринт доступен на сайте arXiv.org. Судоку - головоломка, представляющая собой квадрат 9 на 9 клеток, разбитый в свою очередь на 9 подквадратов 3 на 3. Суть головоломки состоит в том, что игроку дается частично заполненная таблица, которую он должен "дозаполнить" цифрами от 1 до 9. Правила заполнения просты - ни в одной строке, ни в одном столбце, ни в одном подквадрате 3 на 3 не должны встречаться одинаковые цифры. 

 
 В работе ученые взяли уже заполненную головоломку. Каждая клетка в такой таблице имеет несколько наборов координат. Ученые рассмотрели два таких набора: первый - номер столбца и номер строки, второй - номер подквадрата и цифра от 1 до 9, стоящая в данном квадрате. Эти два набора взаимно однозначно определяют друг друга, то есть, по данному решению судоку из одного можно получить другой и наборот. 
 
 Принцип работы "перемешивания" следующий. Ученые разбивали картинку на куски 9 на 9 пикселей. Дальше, в каждом таком куске они меняли координаты точек с первого типа на второй. Далее пиксели переставлялись особым образом так, чтобы координаты второго типа становились координатами типа первого. 
 
 Например, если в табличке во втором ряду на втором месте стояла цифра девять, то координаты этой клетки первого типа (2, 2), а второго (1, 9), поскольку она располагается в первом квадрате 3 на 3. После перестановки этот пиксель попадет на пересечение первой строки и девятого столбца. 
 
 Применив такую перестановку достаточно много раз, ученые получают из картинки месиво разноцветных пикселей. Чтобы теперь вернуть изображение в исходное состояние, нужно знать решение судоку, которое использовалось для кодировки. Как следствие, картинка оказывается зашифрованной. 
 
 По словам ученых, результат выглядит довольно случайным. Более того, по сравнению с другими методами "перемешивания" картинок он работает гораздо быстрее. Сами ученые, правда, не проводили анализ устойчивости к взлому своего алгоритма, поэтому о практическом его применении речи не идет. 
 
 В январе 2012 года ирландские ученые решили так называемую проблему подсказок в судоку. Они установили, какое минимальное число цифр нужно выставить в таблице головоломки, чтобы она имела единственное решение. Оказалось, что это число равно 17. 
 
 
Источники: Lenta.Ru

На страницах данного портала администрация надеется собрать все интересные (с точки зрения администрации) материалы, которые связаны с математикой.
Администрация портала надеется, что все книги и пособия по математике, задачи занимательной математики , статьи по математике подойдут почти любому ищущему данные материалы.
Самое главное все, что находится на сайте вы можете качать совершенно бесплатно, и запомните, все ссылки здесь работают, потому что этот сайт сделан Вам в помощь,
так как администрации хорошо известно как тяжело найти на бескрайних просторах интернета нужный материал.
Все материалы, опубликованные на данном сайте, предназначены исключительно для образовательных и ознакомительных целей.