к вопросу о математической грамотности

[a_shen]

и упорядоченных множествах

Comments

[thrasymedes.livejournal.com]

А если множество состоит из одного элемента ?

утверждение

[a-shen.livejournal.com]

о рекорде предполагает максимальность в смысле какого-то порядка, даже если пока других элементов нет...

[shultz-flory.livejournal.com]

А что не так? Хаски в упряжке вполне упорядочены :)

[akopyan.livejournal.com]

То есть это сертификат автобусу?

[gaz-v-pol.livejournal.com]

Кажется, Владимир Игоревич Арнольд (?) учил, что нужно в таком случае пытаться мысленно встать на место составителей задачи и попытаться понять, что же они на самом деле имели в виду.

В данном конкретном случае, как ни пытаюсь -- не могу понять.

[taki-net.livejournal.com]

Вот-вот.

[buddha239.livejournal.com]

Возможно, более тяжелые автобусы собаки не тащили, а этот не удалось сдвинуть 9 собакам?:)

А по-моему, все понятно.

[ver1958.livejournal.com]

На множестве пар (количество собак, масса автобуса) имеется частичный порядок: (с1,a1) >= (c2,a2), если c1<=c2, a1>=a2. Диплом удостоверяет, что указанная в нем пара является одним из максимальных элементов этого множества. А точнее, что его владельцы смогли, а никто до сих пор не мог сделать следующего: с помощью 10 (или меньше) собак сдвинуть автобус массой 2920 кг (или больше). Вот это они имели в виду.

Re: А по-моему, все понятно.

[a-shen.livejournal.com]

То есть по одной номинации - собаки и автобусы - может быть сразу несколько несравнимых рекордсменов? вроде так не принято

Re: А по-моему, все понятно.

[edd-l.livejournal.com]

У меня есть своя хорошая программисткая задача, связанная с этим порядком.

В файле представленны сто миллионов пар (кол-во собак, масса автобуса) из нескольких стран мира, которые участвовали в регистрации подобных рекордов, правильных для каждой страны в смысле порядка http://a-shen.livejournal.com/103922.html?thread=4829682#t4829682

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

(На самом деле, можно даже определить какие данные к какой стране относятся, если дополнительно предположить, что кривые Парето для разных стран мира не пересекаются; задача, кстати, возникла на практике, но не для собак и автобусов, конечно).

Re: А по-моему, все понятно.

[a-shen.livejournal.com]

В смысле, надо разложить это в минимальное число антицепей, или найти самую длинную цепь (это одно и то же) - а сколько даётся для этого времени?

Re: А по-моему, все понятно.

[edd-l.livejournal.com]

После предварительной быстрой сортировки - линейное, то есть n log n в итоге.

UPD. На самом деле разложение на антицепи не всегда однозначное, хотя их количество предопределено. Поэтому, строго говоря, надо разложить на антицепи только те пары, для которых антицепь определяется однозначно.

Re: А по-моему, все понятно.

[a-shen.livejournal.com]

в смысле, не требуется за n log n определить в любом случае минимальное число антицепей, на которое разлагается множество (максимальную длину цепи)?

Re: А по-моему, все понятно.

[edd-l.livejournal.com]

За время n log n требуется

1) Определить максимальную длину цепи = минимальное число антицепей (обозначим это число m) на которое разлагается множество.

2) Всё множество представить в виде объединения m+одного непересекающегося подмножества: все элементы попавшие в i-е подмножество, i=1,...,m, будут относиться к одной и той же антицепи при любом разбиении на m антицепей; элементы последнего подмножества при разных разбиениях могут попасть в разные антицепи.

Моё UPD в предыдущем комменте обращало внимание только на тот тривиальный факт, что m+1-е подмножество, вообще говоря, не пустое.

Re: А по-моему, все понятно.

[edd-l.livejournal.com]

Кстати, квадратичный алгоритм для произвольных ЧУМов, который Вы, наверняка, нашли, если подумали над задачей, непонятно как довести в общем случае (а может это и нельзя сделать) до сложности n log n. Предлагаемый алгоритм работает только для ЧУМов, чья размерность https://en.wikipedia.org/wiki/Order_dimension равна двум.

Re: А по-моему, все понятно.

[edd-l.livejournal.com]

Легенду для этой задачи можно прямо с натуры брать:
В некой стране чиновники очень любят собак и выдают им сертификаты о разных рекордах. А ещё они любят летать с ними в другие страны мира и заражать своими странными увлечениями чиновников других стран. Для сохранения информации о собачьих рекордах в стране был принят закон о закупке всеми провайдерами серверов огромной мощности, которые нужны исключительно для записи файлов данных всего мира о национальных рекордах собак разных пород: хаски, корги, и т.д. В каждом тесте на вход программы подаётся файл с набором рекордов собак определённой породы. Вам нужно определить минимально возможное число стран, данные которых представлены в этом файле.

Re: А по-моему, все понятно.

[edd-l.livejournal.com]

Ой-ой, забыл обратить внимание на важную деталь: все рассуждения выше о сложности при предположении, что m ограничено константой (количество стран в мире ограничено).

Re: А по-моему, все понятно.

[ver1958.livejournal.com]

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

Re: А по-моему, все понятно.

[a-shen.livejournal.com]

Удивительное искусство оправдывать неграмотность разнообразными толкованиями (это ещё из более вменяемых) - когда совершенно понятно, что какие-то товарищи штампуют за небольшие деньги такие бумажки, вписывая туда то, что скажет заказчик, и не парятся - я привёл этот курьёз как хорошую иллюстрацию к идее частично упорядоченных множеств, даже не предполагая, что найдутся глубокомысленные объяснения, что бы такого они могли иметь в виду. Да ничего они не имели, неужели это не очевидно?

Re: А по-моему, все понятно.

[ver1958.livejournal.com]

Иллюстрация хорошая, как пример отличия понятия наибольшего от максимального.

Возможно, что и в самом деле товарищи "штампуют и не парятся", но это, как и неграмотность, уже не очевидно. У "гиннесистов" нет какого-то ограниченного списка номинаций, новые номинации возникают постоянно. Как по-твоему, грамотные должны были написать в дипломе "наибольшая масса автобуса, сдвинутая упряжкой из не более чем 10 собак" ? Или вообще не регистрировать рекорда?

[misha-b.livejournal.com]

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

[a-shen.livejournal.com]

Наверно, надо уговорить собак, что надо всем толкать автобус в одну и ту же сторону...

[misha-b.livejournal.com]

Ну санки-то они таскают в упряжке на соревнованиях.

[misha-b.livejournal.com]

Кстати, из любопытства посмотрел рекорд в книге Гиннеса.
Человек 30м тянул пожарную машину весом в 57 тонн!

http://www.guinnessworldrecords.com/world-records/heaviest-vehicle-pulled-over-100ft-male

[bbb.livejournal.com]

Скорее, это к вопросу о дефиците бензина и дизельного топлива...

[akor168.livejournal.com]

Судя по спонсору там двигают какую-то конкретную "Газель".

[(Anonymous)]

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

прошу подписывать комментарии

[a-shen.livejournal.com]

Максимизировать массу автобуса бессмысленно, пока не указано свойство, которым этот автобус должен обладать.

Re: прошу подписывать комментарии

[zeev.livejournal.com]

Быть автобусом? Судя по массе, автобус был особо малой вместимости (примерно ГАЗель), то есть примерно самый лёгкий из всех автобусов (транспортных средств для перевозки пассажиров, для которых недостаточно категории B ;)).

Re: прошу подписывать комментарии

[a-shen.livejournal.com]

конкурс на самый тяжёлый автобус - это всё же немного другое...

Re: прошу подписывать комментарии

[zeev.livejournal.com]

Ещё раз - не на самый тяжёлый автобус. На минимум собак, сдвигающих с места хоть какой-то автобус.

Re: прошу подписывать комментарии

[a-shen.livejournal.com]

ну тогда нелепо писать "автобус наибольшей массы" в тексте...

[ichthuss]

Объясните, что в вашей формулировке значат "во-первых" и "во-вторых". Если сравнивать два эпизода, в одном из которых тяжелее автобус, а в другом меньше собак, кто из них заслуживает рекорда? Можно ли ваше "во-первых" интерпретировать как то, что при различии масс автобусов учитывается только этот показатель, а "во-вторых", т.е. число собак, учитывается только в случае совпадения масс?

[anna-frid.livejournal.com]

Ну, я бы предположила, что массу сдвинутого автобуса делили на количество собак. По крайней мере, это дает внятную шкалу.

может быть

[konstantin57.livejournal.com]

Pareto optimal?

Re: может быть

[a-shen.livejournal.com]

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

Re: может быть

[konstantin57.livejournal.com]

Почему бы и нет? И так, и так ценность этого рекорда сомнительна. Хотя мне тяжело судить - я не большой любитель даже рекордов Гиннесса.

[z3vv5yqifqx6.livejournal.com]

Мне кажется, что фраза формально трактуется — а места было мало.

«автобус наибольшей массы, сдвинутый упряжкой с наименьшим количеством собак»

Это автобус наибольшей массы из всех автобусов, которые были сдвинуты какой-либо упряжкой с наименьшим количеством собак. Наименьшим количеством из каких упряжек? Из всех упряжек, сдвинувших с места автобус. Рекорд из книги рекордов России, так что автобус — это то, что поставлено на учёт в РФ с типом транспортного средства «автобус» — «Транспортные средства, используемые для перевозки пассажиров, имеющие, помимо места водителя, более восьми мест для сидения»

И именно поэтому начинается всё с автобуса — иначе было бы «упряжка с наименьшим количеством собак, сдвинувшая автобус наибольшей массы» — и тогда автобус выбирался бы из всех, сдвинутых упряжкой, а потом уже из сдвинувших этот автобус упряжек выбиралась упряжка с наименьшим количеством собак.

Я честно расшифровал фразу как есть, а _потом_ поискал новость. Действительно, наращивалась упряжка, пока не хватило. Организаторы грозились поставить рекорд по количеству собак в упряжке, но ГАЗель поехала раньше…

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

— М.Р.