AOP_Tom3 (1021738), страница 8

Файл №1021738 AOP_Tom3 (Полезная книжка в трёх томах) 8 страницаAOP_Tom3 (1021738) страница 82017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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п) другими участниками турнира.

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

Характеристики

Тип файла
DJVU-файл
Размер
10,16 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6543
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее