Ключевое слово
15 | 12 | 2018
Новости Библиотеки

Шахматы онлайн

Чессбомб

Welcome, Guest
Username: Password: Remember me

TOPIC: Математика для чайников №3

Математика для чайников №3 29 Нояб 2018 03:23 #1351

  • Хайдук
  • Хайдук's Avatar
  • NOW ONLINE
  • Посадник
  • Posts: 34066
  • Thank you received: 74
  • Karma: 22
Grigoriy wrote:
Гостей обозначим числами 0, 1, 2, ... 11 Карточки с номерами считаем последовательно размещёнными по кругу по часовой стрлеке- 0, 1, 2, ...11
Место(обозначенное карточкой) на которое сел i-ый гость обозначим А(i)
Решение.
предположим, что утверждение задачи неверно - есть такое расположение А, что нельзя повернуть стол так, чтобы 2 человека оказались на своих местах.
Это означает, что для всех i числа А(i)-i различны (в самом деле, это число показывает, насколько надо повернуть стол по часовой стрелке, что бы i-ый гость оказался на месте изначально для него предназначенным). Эта разность очевидно может принимать значения от нуля до 11. Т к всего гостей 12 - все значения встречаются по одному разу.
Теперь рассмотрим сумму (А(0) - 0) + (А(1) - 1) + (А(2) - 2) + ... + (А(11) -11)
В силу предыдущего замечания она равна 0 + 1 + 2 + ... + 11 = 66 = 6(напоминаню, мы рассматриваем числа по модулю 12)
как-будто в выкладках сферху будет дыра, Григорий: лишь сумма модулей (поскольку может А(i)-i < 0) |А(0) - 0| + |А(1) - 1| + |А(2) - 2| + ... + |А(11) -11| будет (модули упорядочены) 0 + 1 + 2 + ... + 11 = 66 при поворотах по часовой стрелке, но сравнение с суммой (А(0) - 0) + (А(1) - 1) + (А(2) - 2) + ... + (А(11) -11) = 0 НЕ будет приводить к противоречию и значит выводов нельзя выводить.

различные А(i)-i ограничивают посадки гостей (один из них должен сесть на своё место), что видимо противорчит возможности произвольной посадки, но пока не нашёл убедительного и ясного рассуждения :dumb:
Last Edit: 29 Нояб 2018 04:15 by Хайдук.

Математика для чайников №3 29 Нояб 2018 03:55 #1352

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12968
  • Thank you received: 324
  • Karma: 12
Всё в порядке, дорогой друг Хайдук, всё под контролем. Никаких дыр.

Математика для чайников №3 29 Нояб 2018 04:10 #1353

  • Хайдук
  • Хайдук's Avatar
  • NOW ONLINE
  • Посадник
  • Posts: 34066
  • Thank you received: 74
  • Karma: 22
ну-ну :unsure:

Математика для чайников №3 29 Нояб 2018 04:14 #1354

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12968
  • Thank you received: 324
  • Karma: 12
Вы невнимательно изучили творчество гениального Теэтета, дорогой друг. Но это неважно. Как учит нас не менее гениальный Руми

Благословенна глупость, коль она на благо от Аллаха мне дана.


Так что Ваше впутывание ни к селу ни к городу модулей - безусловно послано Аллахом Вам на благо.
Last Edit: 29 Нояб 2018 04:17 by Grigoriy.

Математика для чайников №3 29 Нояб 2018 04:19 #1355

  • Хайдук
  • Хайдук's Avatar
  • NOW ONLINE
  • Посадник
  • Posts: 34066
  • Thank you received: 74
  • Karma: 22
ни гениального Теэтета, ни такового Руми не знаю :blush:

Математика для чайников №3 29 Нояб 2018 04:24 #1356

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12968
  • Thank you received: 324
  • Karma: 12
Я думаю, что Вам ещё не поздно расширить Ваше образование, изучив творчество сих великих гениев. Но нужно ли?! Повторяю:

Благословенна глупость, коль она на благо от Аллаха мне дана.

Математика для чайников №3 29 Нояб 2018 04:27 #1357

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12968
  • Thank you received: 324
  • Karma: 12
Всё-таки поясню. Если А(i) меньше i, то надо не брать модуль, а прибавить 12 - и тогда получится число, показывающее на сколько надо повернуть стол чтобы i-ый товарищ оказался на своём месте. По модулю 12 это тоже самое число.

Математика для чайников №3 29 Нояб 2018 04:30 #1358

  • Хайдук
  • Хайдук's Avatar
  • NOW ONLINE
  • Посадник
  • Posts: 34066
  • Thank you received: 74
  • Karma: 22
ну, как правило глупость меня чурается как оборотень деревянного креста :rain:

Математика для чайников №3 29 Нояб 2018 15:00 #1359

  • Хайдук
  • Хайдук's Avatar
  • NOW ONLINE
  • Посадник
  • Posts: 34066
  • Thank you received: 74
  • Karma: 22
дело в том, Григорий, что разница А(i)-i < 0 означает поворот в другую сторону, ПРОТИВ часовой стрелки; такие -разницы могут (в зависимости от того как пьяные гости обрушились на стулья) обнулить равные им +разницы (для других i) ПО стрелке и останется отличная от 0 разница +/-6 лишь благодаря тому, что число 11 нечётное; трюк не пройдёт, однако, с нечётным числом гостей :unsure:

Математика для чайников №3 29 Нояб 2018 15:10 #1360

  • procrastinator
  • procrastinator's Avatar
Хайдук, мне конечно лень искать, что и как Григорий писал, но по сути речи о взятии модуля (абсолютной величины) не могло идти. Речь шла о вычислениях по модулю 12. Используется то же слово, но смысл у него другой.

Математика для чайников №3 29 Нояб 2018 15:13 #1361

  • Хайдук
  • Хайдук's Avatar
  • NOW ONLINE
  • Посадник
  • Posts: 34066
  • Thank you received: 74
  • Karma: 22
это я понимаю, +/- разницы это по модулю 12 :glasses:

Математика для чайников №3 29 Нояб 2018 15:30 #1362

  • procrastinator
  • procrastinator's Avatar
Извините, не вчитался. Думал Вы по-прежнему Григория опровергаете.
Для нечетных n эта сумма (n+1)n/2 = 0 (mod n), и приведенное решение не работает. Более того реально существует перестановка, исключающая больше одного совпадения при любом повороте стола.

Математика для чайников №3 29 Нояб 2018 18:24 #1363

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12968
  • Thank you received: 324
  • Karma: 12
Хайдук wrote:
трюк не пройдёт, однако, с нечётным числом гостей
Разумеется. Но разве я утверждал что-то для нечётных n?

Математика для чайников №3 09 Дек 2018 04:28 #1364

  • сам-пят
  • сам-пят's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 476
  • Thank you received: 10
  • Karma: 1
При частом сравнении сложных объектов полезной оказывается идея хеширования, сокращающая время перебора и состоящая в том, что на множестве этих объектов вводится некоторая функция и сравниваются не они, а значения этой хеш-функции; к самим же объектам обращаются только при совпадении ее значений на них, хранимых в их классах хеш-эквивалентности в виде хеш-таблицы. Эти хеш-значения должны просто вычисляться и пореже (по возможности равномерно) совпадать.

Чем больше область значений применяемой хеш-функции, тем меньше ожидаются их совпадения. Например, если объектами являются подмножества пронумерованного множества, то в качестве хеш-функции можно взять мощность этих подмножеств. Так я и сделал и решил некую задачу на компьютере за 2 часа; а потом просто сменил хеш-функцию, взяв вместо мощности подмножества сумму исходных номеров его элементов, гораздо более многозначную, и решил ту же самую задачу всего за 2 минуты! Кстати, номера элементов тоже, по сути, есть хеш-значения, реноме элементов.

P.S. А если бы я хеш-функцию не использовал, то не решил бы задачу за разумное время вообще.
"Позвольте, товарищ, у меня все ходы записаны!"
Last Edit: 09 Дек 2018 04:36 by сам-пят.

Математика для чайников №3 09 Дек 2018 06:10 #1365

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
сам-пят wrote:
Чем больше область значений применяемой хеш-функции, тем меньше ожидаются их совпадения. Например, если объектами являются подмножества пронумерованного множества, то в качестве хеш-функции можно взять мощность этих подмножеств.
а потом просто сменил хеш-функцию, взяв вместо мощности подмножества сумму исходных номеров его элементов, гораздо более многозначную
Оптимистичное заявление...
сам-пят wrote:
Кстати, номера элементов тоже, по сути, есть хеш-значения, реноме элементов.
Это просто очень частный случай.

Вот будет проблемка сравнивать слова или даже текстики произвольной длины...
Тогда придется крепче подумать, как выбирать хэш :)
Каждому - своё.

Математика для чайников №3 09 Дек 2018 07:52 #1366

  • сам-пят
  • сам-пят's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 476
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
Оптимистичное заявление...

Я заявил это конкретно, по факту. Исходное множество у меня состоит из 255 элементов, пронумерованных от 0 до 254. Мощность рассматриваемых мною его подмножеств в упомянутой задаче не превосходит 69, всего-то. А вот если складывать номера элементов подмножества, то сумма может достигать, правда, не 186 + ... + 254, но 10 351, что тоже гораздо больше 69.
"Позвольте, товарищ, у меня все ходы записаны!"
Last Edit: 09 Дек 2018 07:55 by сам-пят.

Математика для чайников №3 09 Дек 2018 09:31 #1367

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
сам-пят wrote:
А вот если складывать номера элементов подмножества, то сумма может достигать, правда, не 186 + ... + 254, но 10 351, что тоже гораздо больше 69.
Это самое последнее из критериев, которые нужно использовать при выборе хэш-функции
Каждому - своё.

Математика для чайников №3 09 Дек 2018 11:44 #1368

  • сам-пят
  • сам-пят's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 476
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
сам-пят wrote:
А вот если складывать номера элементов подмножества, то сумма может достигать, правда, не 186 + ... + 254, но 10 351, что тоже гораздо больше 69.
Это самое последнее из критериев, которые нужно использовать при выборе хэш-функции

Не совсем понял, поскольку и до этого-то я додумался не сразу.
"Позвольте, товарищ, у меня все ходы записаны!"

Математика для чайников №3 09 Дек 2018 12:13 #1369

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
сам-пят wrote:
Не совсем понял, поскольку и до этого-то я додумался не сразу.

Главный критерий хэш-функции это вероятность коллизий. А для криптографии еще и стойкость к обратному преобразованию, но это тут лишнее, как я понимаю.
Поэтому число возможных вариантов должно быть как можно больше. Для бытовухи достаточно 32 (2 лярда) или 64 (очень очень много) битного числа в качестве хэша даже для очень больших массивов.

При сложении как выше вариантов маловато, притом коллизии возникают при самом простом 1+4 и 2+3. Это неэффективно
Вообще обычно уже есть готовые классы для этого типа HashMap, так что изобретать велосипед не нужно, там уже все встроено

Если же хочется немного своё, то тут обзорчик Некриптографические хеш-функции
Можно взять старинную CRC32, на ней все архиваторы древние целостность архивов проверяли
habr.com/post/178955/
Каждому - своё.

Математика для чайников №3 09 Дек 2018 12:33 #1370

  • сам-пят
  • сам-пят's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 476
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
При сложении как выше вариантов маловато, притом коллизии возникают при самом простом 1+4 и 2+3. Это неэффективно
Вообще обычно уже есть готовые классы для этого типа HashMap, так что изобретать велосипед не нужно, там уже все встроено

Вряд ли стоит говорить о неэффективности, когда задача оказывается решенной за 2 минуты (вместо 2 часов). Объекты у меня - это множества, набираемые из последовательности чисел 0, ..., 254 по некоторому критерию, каждый раз разному. Заранее их нет. И задача состоит в том, чтобы подсчитать количество различных множеств, поскольку они могут совпадать. Какую "более эффективную" хеш-функцию здесь можно предложить? Я использовал уже встроенную просто функцию Sum().
"Позвольте, товарищ, у меня все ходы записаны!"
Last Edit: 09 Дек 2018 12:35 by сам-пят.

Математика для чайников №3 09 Дек 2018 13:01 #1371

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
сам-пят wrote:
Вряд ли стоит говорить о неэффективности, когда задача оказывается решенной за 2 минуты (вместо 2 часов).
Ну и ладушки
Каждому - своё.

Математика для чайников №3 09 Дек 2018 13:15 #1372

  • сам-пят
  • сам-пят's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 476
  • Thank you received: 10
  • Karma: 1
Vladimirovich wrote:
Ну и ладушки

Я, между прочим, пробовал использовать хеш-коды, вырабатываемые по умолчанию для моих множеств (списков), какие-то довольно большие числа. Тут же возникли проблемы с памятью. Может, я не понимаю, что такое хеш-таблица, но я брал ее размером с максимальное хеш-значение.
"Позвольте, товарищ, у меня все ходы записаны!"

Математика для чайников №3 09 Дек 2018 13:22 #1373

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
сам-пят wrote:
Тут же возникли проблемы с памятью. Может, я не понимаю, что такое хеш-таблица, но я брал ее размером с максимальное хеш-значение.
Ну при таком подходе ни один компьютер не потянул бы современные 512 битные хэш-ключи (например SHA-512)
Каждому - своё.

Математика для чайников №3 09 Дек 2018 13:41 #1374

  • сам-пят
  • сам-пят's Avatar
  • OFFLINE
  • Кравчий
  • Posts: 476
  • Thank you received: 10
  • Karma: 1
Я почему возник здесь с идей хеш-функции. Просто мне захотелось изложить эту полезную идею просто и кратко, для чайников. А то даже в Википедии все это излагается каким-то нечеловеческим языком. ((

Кстати, все общие понятия похожи на хеш-значения. Например, человек (в смысле вообще). Если бы этого понятия (или ему эквивалентного) не было, а мы с вами захотели бы сказать о человеке что-то интересное, то нам, думаю, пришлось бы перечислять миллиарды имен тех, кого мы имеем в виду, подряд.
"Позвольте, товарищ, у меня все ходы записаны!"

Математика для чайников №3 11 Дек 2018 06:12 #1375

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12968
  • Thank you received: 324
  • Karma: 12
Совсем простенькая задачка.


Расположить 6 неотточенных круглых карандашей что бы все они касались друг друга.

Математика для чайников №3 14 Дек 2018 13:41 #1376

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
Grigoriy wrote:
Совсем простенькая задачка.
Warning: Spoiler! [ Click to expand ]
Каждому - своё.

Математика для чайников №3 14 Дек 2018 16:17 #1377

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 12968
  • Thank you received: 324
  • Karma: 12
Всё гораздо проще:

Warning: Spoiler! [ Click to expand ]


Я очень озлился на себя - увидев эту картинку - что м б проще - а я не додумался :-(

Математика для чайников №3 14 Дек 2018 16:24 #1378

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
У меня красивее :)
Каждому - своё.

Математика для чайников №3 15 Дек 2018 05:09 #1379

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 75167
  • Thank you received: 937
  • Karma: 77
В общем так
Warning: Spoiler! [ Click to expand ]
Каждому - своё.
Last Edit: 15 Дек 2018 05:13 by Vladimirovich.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум