AOP_Tom3 (1021738), страница 8
Текст из файла (страница 8)
1 24. (МЯ) (Ю. Л. Лолер (Е. Е, Еаи"1ег).) Каково максимальное число сравнений, необходимых Лля следующего алгоритма слияния ш элементов с и > т элементами? "Установить 1 +- (18(п/т)) и использова~ь алгоритм 5.2.4М лля слияния Ам Ам ..., А,„с Вэ, Вххч ..., Вэ х. где д = (и/2'). Затем вставить каждый элемент А, на свое место среди Вь." ь 25. [25) Предположим, что (хп) есть матрица т х п с неубывающими строками и столбцами: хи < хц+П, прн 1 < 1 < т и хн < хцз+П при 1 < 1 < п.
Покажите, что М(гл, п) есть минимальное число сравнений, необходимых для того, чтобы выяснить, присутствует ли данное число х в матрице, если все сравнения выполняются между х и некоторым элементом матрицы. «Б.З.З. Выбор с минимальным числом сравнений При поиске наилучших возможных процедур для выбора $-го элемента в порядке убывания из н элементов мы встречаемся с классом задач, подобнгях рассмотренным в предыдущем разделе.
История постановки и поиска решений этой проблемы восходит к занимательному (хотя и серьезному) эссе преподобного Ч. Л. Доджсона (С. Е. Поббэоп) о турнирах по теннису, появившемуся в Вс..уашеэ "э Сахеые 1 августа 1883 года (с. 5-6). Доджсон, который, разумеется, более известен как Льнущие Кэррол, рассматривал несправедливые правила, по которым присуждались (и до сих пор присуждаются) призы в турнирах по теннису. Рассмотрим, например, рис.
39, на котором показана схема типичного турнира с выбыванием между 32 игроками, помеченными 01, 09,..., ЯЯ. В финале игрок 01 одерживает победу над игроком 05, поэтому ясно, что игрок 01 — чемпион и заслужил первый приз. Несправедливость проявляется в том, что игрок 05 обычно получает второй приз, хотя он может и не быть вторым по силе игроком. Выиграть второй приз можно, даже если играешь хуже половины игроков турнира. В самом деле, как заметил Доджсон, второй по силе игрок выигрывает второй приз в том и только том случае, если первоначально он и чемпион находились в противоположных частях турнирной таблицы; для турнира с 2" участниками это происходит с вероятностью 2" '/(2" — 1), так что почти в половине случаев второй приз получает не тот игрок! Если проигравшие в полуфинале (игроки 95 и 17 на рис. 39) соревнуются за третий приз, то весьма маловероятно, что третий по силе игрок получит третий приз.
Поэтому Доджсон решил найти такую схему турнира, которая правильно определяет второго и третьего по силе игроков в предположении, что соблюдается закон транзнтивности. (Иначе говоря, если игрок А побеждает игрока В, а В побеждает С, то можно считать, что игрок А победит С.) Доджсон придумал процедуру, в которой проигравшим дается возможность сыграть еще несколько игр, пока не станет определенно известно, что они слабее других трех игроков. Пример схемы Доджсона приводится на рис. 40.
Здесь изображена сетка нгр дополнительного турнира; его следует провести вместе с турниром, схема которого показана на рис. 39. Доджсон попытался составить пары игроков, у которых до сих пор были равные результаты, и исключить матчи между игроками, побежденнымя одним и тем же участником. В таком конкретном примере игрок 16 проигрывает игроку 11, а игрок 15 проигрывает игроку 19 в первом туре; после того как игрок 16 проигрывает игроку 16 во втором туре, игрок 16 исключается, так как теперь известно, что он слабее игроков 11, 19 и 15. В третьем туре исключается встреча игроков 19 и 91, Чемпион = 01 01 Об Тур 4 01 25 Тур З 01 ог гб 29 — — — — г — л-з г-л — з тур 2 01 Оз 02 01 25 26 29 зо глз глз глз глз глз глз глз глз турл о1 отоз1о огов 01 Овгбгв 262729 зг зоз1 05 гт 05 11 17 1В 05 Об 11 12 17 20 1В 21 ~~л~л~~~ об 15 06 ц п 261г гз гт 21 го гз 1в 19 г1 22 Рис.
39. Турнир между 32 игроками с выбываннелл. Третье место = ОЗ г 1 ОЗ 05 Вторае место = 02 тур э 05 Тур В 02 Тур ' ОЗ ОЗ 17 глз ОЗ 11 17 25 — — глз ОЗ 26 11 1В глз Оз 01 26 зо 06 07 г Об 29 07 29 г11 г 1 Г 1 06 27 гв 57 07 ОВ Г 1 Г 1 Г~1 ГЛЗ ГЛЗ 27 22 ВЗ 21 21 З2 07 10 ОВ 09 Тур 6 Ог Тур в ог Тур 4 02 20 12 глч Тур З 20 г1 Гг Гв г 1 Тур 2 19 22 12 Г 1 12 Ц г 1 Г ) 12 16 11 15 Рис. 40. Сетка теннисного турнира Льюиса Кэррола (в дополнение к сетке, представлен- ной па рис. 39). На математическом семинаре в 1929-1930 годах Гуго Штейнгауз (Нпйо БСе1п11апв) сформулировал постановку задачи нахождения минимального числа поединков, требуемых для определения первого и второго игроков в турнире, если всего так как они оба были побеждены игроком 18, но нельзя автоматнческн исключить проигравшего во встрече игроков 1В и В1.
Было бы приятно сообщить, что схема турнира, предложенная Льюисом Кэрролом, оказалась оптимальной, но, к сожалению, это не так. Из записи в его дневнике от 23 июля 1883 года явствует, что он составил это эссе примерно за шесть часов и чувствовал, что, "поскольку 1теннисный) сезон приближается к концу, будет лучше сделать так, чтобы оно [эссе) появилось побыстрее, чем чтобы оно было хорошо написано'.
В его процедуре делается больше сравнений, чем необходимо, и она не с11юрмулирована достаточно четко, чтобы квалифицировать ее как алгоритм. С другой стороны, в ней имеются некоторые очень интересные аспекты, если судить с точки зрения параллельных вычислений.
Предложенную схему можно считать отличной турнирной сеткой, поскольку Кэррол включил в нее несколько драматнческих эффектов; например, он определил, что два финалиста должны пропустить пятый тур и сыграть дополнительный матч в турах 6 и 7. Однако организаторы турниров, по-видимому, сочли его предложение излишне логичным, и потому система Кэррола, скорее всего, никогда не испытывалась. Вместо этого практикуется метод "рассеивания" более сильных игроков, чтобы они попали в разные части дерева. имеется и > 2 участников. В работе 3. Бс!пе!ег, Магйез!э Ро!йа 7 (1932), 154 — 160, приведена процедура, требующая самое болыпее и — 2 + (18 и) матчей. В ней использован, по существу, тот же метод, что и на первых двух стадиях процесса, который мы назвали сортировкой посредством выбора из дерева (см.
раздел 5.2.3, рис. 23), однако не выполняли дополнительных сравнений с — оо. В работе также утверждается, что и — 2+ ~!йп) — нанлучшее возможное значение, но приведенное доказательство было ошибочным, как и еще одна попытка доказательства, предпринятая в работе Я. 6!вереск!, Со!!ойи!пш Ма1Летайсиш 2 (1951), 286 — 290. Прошло 32 года, прежде чем С. С.
Кислицыным было опубликовано правильное, хотя и очень сложное, доказательство [Свбирский математический журнал 5 (1964), 557-564). Пусть Ъ;(и) обозначает минимальное число сравнений, требуемых для определения 1-го в порядке убывания элемента из и элементов, 1 < ! ( и, и пусть И~(п) равно наименьшему числу сравнений, необходимых для определения наиболыпего, второго,... и 1-го элементов всех сразу. Вследствие симметрии имеем Ъ1(п) = У„+, ~(п), очевидно также, что (2) (3) (4) 1)(и) = И'~(п), Ъ~(п) < И',(и), И~„(п) = И"„~ (и) = Я(п). Как следует из леммы 5,2.3М, (5) 1~(п) = и — 1. Существует удивительно простое доказательство этого факта -- каждый участник турнира, кроме чемпиона, должен проиграть, по крайней мере, одну игру. 'Обобщая эту идею и используя "соперника", как в разделе 5.3.2, можно без особого труда доказать теорему П!рейера-Кислицына.
Теорема В. 1з(п) = Ия(п) = п — 2+ (!8п) прн п > 2. ,цоказательсшво. Предположим, что в турнире, в котором после проведения некоторой заданной процедуры должен определиться второй игрок, участвуют п игроков и пусть пу — число игроков, проигравших !' или больше матчей. Общее число сыгранных матчей будет тогда равно а, + аз + аз + . Нельзя определить второго игрока, не выявив заодно и чемпиона (см. упр. 2), поэтому из предыдущих рассуждений получаем а~ — — — п — 1.
Для завершения доказательства покажем, что всегда существует последовательность результатов матчей, которая приводит к а > /!8п) — 1. Предположим, что к концу турнира чемпион сыграл р игр и победил р игроков; одним из них был второй по силе игрок, а остальные должны проиграть, по крайней мере, еще по одному разу, поэтому аз > р — 1. Итак, можно завершить доказательство, построив соперника, предопределяющего результаты игр, таким образом, чтобы чемпиону пришлось сыграть еще хотя бы с ~!8п) другими участниками турнира.
Пусть соперник считает, что игрок А сильнее игрока В, если А ранее не проигрывал, а В хотя бы однажды проиграл или если оба не проигрывали, но В выиграл к этому моменту меньше поединков, чем А. При других обстоятельствах соперник может принимать произвольное решение, не противоречащее некоторому частичному упорядочению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
