alleukemist: (Darwin)
[personal profile] alleukemist
Разговаривал давеча с коллегой [livejournal.com profile] roomd за обедом. Интересный, надо сказать, человек. Он программист, соответственно какое-то прикладное математическое образование (к сожалению, я забыл какое именно), но много толкался по биологическим лабораториям за свою карьеру, имел отношение к классификации и алгоритмам анализа химических соединений, так что было о чем поговорить. Так вот, разговорились мы с ним о математике, затронули судоку, к которой я, если помните, безуспешно пытался найти способы поиска решения без перебора. И он меня огорошил известием, что невозможность такого решения уже доказана математически. Это побудило меня написать данный пост, который, подозреваю, наберет 0 комментариев, но мне важно записать мои собственные мысли.
Дело в том, что таких задач в математике огромное количество. Математики не могут найти формулу для простых чисел, кроме как перебором. Решить ту же судоку в общем виде, кроме как перебором. Между прочим, даже простейший алгоритм оптимального расположения звездочек на американском флаге (помните, я писал об этом) требует перебора. Этих задач огромное множество, с ними сталкиваются на каждом шагу, и все они имеют одно общее свойство: это задачи, требующие решений в целых числах. Как ни странно, насколько мне известно (а мне известно, к сожалению, крайне мало, но я не встречал никогда иного), математика практически не может оперировать с целыми числами. Я не имею в виду арифметические правила. Вот смотрите, сколько всего мощного есть для рациональных чисел: тут тебе и понятие функции, и дифференциальный анализ, и возможность работать с бесконечными множествами - куча всего. Я понимаю, что сейчас вызываю смех у профессиональных математиков и прошу их простить меня - суть не в этом. Что же мы имеем для столь же глубокого анализа целых чисел? Ничего. Функция, определенная только для целых чисел, недифференцируема, и вот весь анализ отпадает. Множество целых чисел бесконечно, однако оно счетное, и большая часть инструментов для работы с множествами тоже отпадает. Мне кажется, что это какая-то досадная оплошность. Можете смеяться, но я уверен, что простые числа - это всего лишь какая-то функция целых чисел. Как и числа Фибоначчи (а ведь они имеют даже биологическое значение, то есть в природе функциональны!). Если бы эту теорию функций целых чисел кто-то взялся разработать, думаю, это дало бы большой прорыв в математике и заставило бы полностью пересмотреть современные подходы к компьютерной безопасности, которая основывается на условно необратимых операциях (перемножении больших простых чисел). К сожалению, я этого сделать не могу: у меня времени нет, да и я уже слишком специализировался в биологии и никогда не стану математиком. Это так, пожелание грядущим поколениям. :-)

(no subject)

Date: 2012-12-22 01:24 (UTC)
From: [identity profile] saint-dragon.livejournal.com
Это ты о каком-то конкретном судоку или в целом? Я тут с американцами тему судоку раскрыла, выяснилось, что еще одна девочка в лабе их очень любит. Я решила ее еще с японскими познакомить - притащила парочку из числа привезенных мамой.

(no subject)

Date: 2012-12-22 04:02 (UTC)
From: [identity profile] alleukemist.livejournal.com
В целом, конечно. Я решал задачу в общем виде, используя вероятностный подход. Он работает в большинстве случаев, но не решает самые сложные судоку.
А парочку чего ты притащила? Книжек или разновидностей каких-то? Если хочешь, я могу скинуть коллекцию из более чем 30,000 судоку, причем минимальных (то есть с 17 числами; судоку с 16 числами неизвестны вообще). Считаются очень сложными. Если у нее есть смартфон, то Open Sudoku программа ей должна понравиться.

(no subject)

Date: 2012-12-22 19:13 (UTC)
From: [identity profile] saint-dragon.livejournal.com
Парочку китайских кроссвордов. Про судоку она сама знала.

(no subject)

Date: 2012-12-22 16:05 (UTC)
From: [identity profile] aip2.livejournal.com
"Что же мы имеем для столь же глубокого анализа целых чисел? "
на первом курсе мехмата есть предмет, называемый ТЧ. Там много чего используется, в том числе и матан в виде всяких производящих функций, рекуррентных соотношений и всякие другие дела, подробнее не знаю, поскольку сам на математике не учился, а у нас только слегка касались этой темы.
http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm

(no subject)

Date: 2012-12-22 17:27 (UTC)
From: [identity profile] alleukemist.livejournal.com
Леша, рад видеть.
Да, куда-то в эту область надо копать, но нет времени разобраться основательно. И потом, раз простые числа не описали, значит, там есть еще где работать.

(no subject)

Date: 2012-12-26 15:49 (UTC)
From: [identity profile] zapiens.livejournal.com
...числа Фибоначчи (а ведь они имеют даже биологическое значение, то есть в природе функциональны!)

Очень интересно. Хотел спросить, где они встречаются в природе, потом сам нагуглил.

(no subject)

Date: 2012-12-26 16:08 (UTC)
From: [identity profile] alleukemist.livejournal.com
Да, это совершенно удивительный факт.
Page generated 2017-09-19 11:36
Powered by Dreamwidth Studios