WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS


Pages:     || 2 | 3 | 4 |

«С. М. Гусейн-Заде РАЗБОРЧИВАЯ НЕВЕСТА Издательство Московского центра непрерывного математического образования Москва • 2003 УДК 519.216 ББК 22.171 Г96 Аннотация ...»

-- [ Страница 1 ] --

Библиотека

Математическое просвещение

Выпуск 25

С. М. Гусейн-Заде

РАЗБОРЧИВАЯ

НЕВЕСТА

Издательство Московского центра

непрерывного математического образования

Москва • 2003

УДК 519.216

ББК 22.171

Г96

Аннотация

Примерно 40 лет тому назад М. Гарднер придумал такую задачу: В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?.

В 1965 году формулировку этой задачи и её решение рассказал на своём семинаре Е. Б. Дынкин. Но его метод был необобщаем на другие варианты задачи: например, когда целью является выбор не наилучшего, а одного из трёх лучших. В таком виде задача была решена автором при помощи метода, который легко переносится и на ряд близких задач. Так из полушуточной задачи вырос новый раздел математики — т е о р и я о п т и м а л ьн о й о с т а н о в к и с л у ч а й н ы х п р о ц е с с о в.

Текст брошюры представляет собой обработку записи лекции, прочитанной автором 30 ноября 2002 года на Малом мехмате МГУ для школьников 9—11 классов (запись Ю. Л. Притыкина).

Брошюра рассчитана на широкий круг читателей: школьников, студентов, учителей.

Издание осуществлено при поддержке Департамента образования г. Москвы и Московской городской Думы.

ISBN 5-94057-076-3 © С. М. Гусейн-Заде, 2003.

© МЦНМО, 2003.

Сабир Меджидович Гусейн-Заде.

Разборчивая невеста.

(Серия: Библиотека,,Математическое просвещение“. Вып. 25).

М.: МЦНМО, 2003. — 24 с.: ил.

Редактор Ю. Л. Притыкин.

Художник А. Ю. Шамшурина. Техн. редактор М. Ю. Панов.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано в печать 14/VII 2003 года.

Формат бумаги 6088 116. Бумага офсетная № 1. Печать офсетная. Физ. печ. л. 1,50.

/ Усл. печ. л. 1,47. Уч.-изд. л. 1,44. Тираж 3000 экз. Заказ 2711.

Издательство Московского центра непрерывного математического образования.

119002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 72 85, 241 05 00.

Отпечатано с готовых диапозитивов в ФГУП Производственно-издательский комбинат ВИНИТИ.

140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.

Невеста-девушка смышляла жениха;

Тут нет ещё греха, Да вот что грех: она была спесива.

Сыщи ей жениха, чтоб был хорош, умён, И в лентах, и в чести, и молод был бы он (Красавица была немножко прихотлива):

Ну, чтобы всё имел. Кто ж может всё иметь?

Ещё и то заметь, Чтобы любить её, а ревновать не сметь.

Хоть чудно, только так была она счастлива, Что женихи, как на отбор, Презнатные катили к ней на двор.

Но в выборе её и вкус и мысли тонки:

Такие женихи другим невестам клад, А ей они на взгляд Не женихи, а женишонки!

Ну, как ей выбирать из этих женихов?

И. А. Крылов Разборчивая невеста Речь в данной брошюре пойдёт о задаче, которая, с одной стороны, достаточно элементарна, чтобы её можно было рассказать от начала и до конца, и, с другой стороны, была придумана не когда-то там в девятнадцатом веке или раньше, а во вполне обозримом прошлом, в веке двадцатом, причём положила начало новому разделу теории вероятностей или даже прикладной теории вероятностей, который называется теорией оптимальной остановки случайных процессов. История этой задачи такова. В 1960 году её придумал Мартин Гарднер, автор огромного количества книг с увлекательными задачами и головоломками, связанными с математикой.

Его можно назвать популяризатором математики. Оказалось, что на тот момент эта задача в теории вероятностей не рассматривалась.

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

В 1966 году под влиянием и по совету того же Дынкина я занялся этой задачей и нашёл решение в достаточно общем виде. Позже с этой задачей оказался связанным очень известный в современной России человек, фамилия которого Березовский. Борис Абрамович Березовский известен как бизнесмен и политический деятель, но когда-то он был математиком и защитил докторскую диссертацию по проблемам, связанным как раз с обобщениями этой задачи.

Теперь я расскажу саму задачу, ровно так, как её формулировал Гарднер. Это задача о разборчивой невесте. Пусть в некотором царстве, в некотором государстве принцесса решила, что ей пора найти себе жениха. Созвали царевичей и королевичей со всего света, и явилось 1000 претендентов. Про любых двух когда-либо увиденных принцесса может сказать, кто из них лучше. При этом царевичи, как говорят математики, образуют упорядоченное множество, т. е. если Иван Царевич лучше Василия Царевича, а Василий Царевич лучше Фёдора Царевича, то Иван Царевич лучше Фёдора Царевича. Претенденты входят к принцессе по очереди, по одному, причём их порядок определён случайным образом, т. е.

вероятность появления какого-то царевича первым, или пятисотым, или тысячным совершенно одинакова. Принцесса, разумеется, умея их сравнивать, может сказать, что, например, вошедший тридцатым является десятым по качеству, т. е. девять из предыдущих были лучше, а остальные — хуже, и т. д. Цель принцессы — получить самого хорошего жениха, т. е. даже второй её не устраивает. На каждом шаге, т. е. после встречи с каждым из царевичей, она решает, берёт ли она его в мужья. Если берёт, то на этом смотр претендентов заканчивается, они все разъезжаются по домам.

Если же принцесса ему отказывает, то царевич, будучи отвергнутым, тут же уезжает домой, потому что все царевичи и королевичи — люди гордые. Показ претендентов на замужество при этом продолжается. Если в конце концов принцесса не получает лучшего, то считается, что она проиграла, выходить замуж вообще не будет, а уйдёт в монастырь (про монастырь я уже от себя придумал, у Гарднера этого не было). Спрашивается, как действовать принцессе, чтобы с наибольшей вероятностью получить лучшего жениха.

В основе решения задачи заложен простой принцип, имеющий громкое название динамическое программирование. На самом деле это просто планирование, решение задачи с конца. Сейчас я поясню, что имеется в виду. Предположим, что принцесса пропустила 999 претендентов и сейчас встречается с последним.

Тогда у неё нет никакой альтернативы, всё совершенно ясно. Если последний и есть самый лучший, то принцесса выиграла, добилась своего, если он не самый лучший, то принцесса проиграла и уходит в монастырь. В любом случае отвергать последнего претендента бессмысленно, это к победе точно не приведёт. Теперь предположим, что принцесса знает, как вести себя на 601-м шаге. Попробуем понять, что делать при встрече с 600-м, т. е. за шаг до этого.

Ясно, что если 600-й претендент не лучше всех предыдущих, то и думать нечего, ему нужно отказывать. Вообще в нашей задаче принцесса будет останавливаться только на тех, кто лучше всех предыдущих, иначе она точно проиграет, ведь её устраивает только самый лучший. Если же он действительно лучше всех предыдущих, то у принцессы есть выбор. Например, когда приходит первый, то, естественно, он лучше всех предыдущих, так как и предыдущих-то никаких не было, но останавливаться на нём как-то очень странно, шансов победить мало, с таким же успехом можно и на десятом остановиться, лучше ещё подождать хоть немного, может, кто-нибудь получше появится. Итак, пусть 600-й лучше всех предыдущих, и принцессе нужно оценить (она, наверное, и не может, но ведь для этого математики и существуют), что лучше: выбрать этого самого 600-го или отказать ему, перейти к следующему, а там, как мы помним, уже всё известно, понятно, как нужно поступать, и шансы на получение лучшего жениха мы посчитать сможем.

Итак, объявим для начала, что 1000 мы обозначим за n, т. е.

решим задачу для произвольного количества претендентов. Далее, пусть принцесса находится на шаге t (это номер шага, т. е. натуральное число). Первое, что ей нужно знать — это вероятность победы в случае выбора жениха в момент t, при условии, что он лучше всех предыдущих, т. е. вероятность того, что он не только лучше всех предыдущих, а вообще лучше всех. Обозначим эту вероятность за gt. Кроме того, необходимо знать ещё одну величину — это вероятность того, что она в конце концов получит самого хорошего жениха, при условии, что она пропустит первых t претендентов и дальше будет пользоваться оптимальной стратегией (здесь подразумевается наше предположение о том, что принцесса знает, как себя оптимально вести начиная с шага t+1, это и есть принцип, используемый в динамическом программировании). Обозначим эту вероятность за ht. Зная эти две величины для любого t, мы можем легко понять оптимальную стратегию поведения для принцессы: если на шаге t претендент не лучше всех предыдущих, то, ясное дело, его нужно отвергнуть, если же он действительно лучший среди первых t претендентов, то нужно сравнить gt и ht, если больше gt, то нужно остановиться на претенденте t, если больше ht, то нужно его отвергнуть и перейти к следующему, такая стратегия следует прямо из определения этих вероятностей.

Что же делать в случае равенства? Понятно, что это неважно, так как вероятность победы в каждом из случаев одинакова, поэтому давайте договоримся, что в случае равенства gt и ht принцесса будет, например, всё время останавливаться на текущем претенденте.

Стратегия нами уяснена, осталось только посчитать gt и ht.

Вероятность gt я посчитаю прямо сейчас, явно, а ht пока считать не буду, только скажу достаточно очевидный факт о том, как эта вероятность себя ведёт в зависимости от t.



Pages:     || 2 | 3 | 4 |
 


Похожие работы:

«ОРГКОМИТЕТ КОНФЕРЕНЦИИ Федосюк В.М., ГО НПЦ НАН Беларуси по материаловедению, Минск, Беларусь, председатель Олехнович Н.М., ГО НПЦ НАН Беларуси по материаловедению, Минск, Беларусь, зам. председателя Мудрый А.В., ГО НПЦ НАН Беларуси по материаловедению, Минск, Беларусь, ученый секретарь Агабеков В.Е., ИХНМ НАН Беларуси, Минск, Беларусь Анищик В.М., БГУ, Минск, Беларусь Башкиров Л.А., БГТУ, Минск, Беларусь Витязь П.А., Президиум НАН Беларуси, Минск, Беларусь Гордиенко А.И., ФТИ НАН Беларуси,...»

«Как стать героем в глазах ребенка Новая жизнь, 1995. СОДЕРЖАНИЕ Предисловие Выражение признательности Часть I. Требуются герои с положительным родительским планом 1 Требуются герои с положительным родительским планом 2 Можно обжулить жулика, можно одурачить дурака, но нельзя обманывать ребенка 3 Не пускайте на самотек, планируйте Часть II. Принятие: фундамент уверенности и самоуважения 4 Принятие: фундамент уверенности и самоуважения 5 Когда вы принимаете их, они принимают себя сами 6 Принятие:...»

«УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС технология производства по дисциплине Козоводство, молока, мяса, шерсти и пуха 5В080200 - Технология производства продуктов животноводства (очная форма обучения) АЛМАТЫ 2013 Кулатаев Б.Т., доцент Автор: Учебно-методический комплекс дисциплины составлен на основе ГОСО РК по специальности 5В080200 – Технология производства продуктов животноводства и рабочей учебной программы дисциплины Козоводство, технология производства молока, мяса, шерсти и пуха....»

«17 сентября 2011 года Начало в 15.30 Регистрация начинается в 15.00 Отель MARRIOTT MOSCOW ROYAL AURORA Москва, ул. Петровка, д.11/20 Предаукционный просмотр лотов с 29 августа по 16 сентября 2011 года ежедневно кроме воскресенья в офисе Аукционного Дома “Империя”, расположенного по адресу: Москва, ул. Остоженка, 3/14 (вход с 1-го Обыденского переулка) с 11.00 до 20.00. Заявки на участие в аукционе, телефоны и заочные биды, заказ каталогов: Тел.: +7 (495) 695-27-23 +7 (495) 695-27-70 E-mail:...»

«ПОСТАНОВЛЕНИЯ МЕЖВЕДОМСТВЕННОГО СТРАТИГРАФИЧЕСКОГО КОМИТЕТА И ЕГО П О С Т О Я Н Н Ы Х КОМИССИИ ВЫПУСК 23 Ленинград, 1987 МИНИСТЕРСТВО ГЕОЛОГИИ СССР А К А Д Е М И Я НАУК СССР ВСЕСОЮЗНЫЙ ОРДЕНА ЛЕНИНА НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ГЕОЛОГИЧЕСКИЙ ИНСТИТУТ имени А.П.КАРПИНСКОГО (ВСЕГЕИ) МЕЖВЕДОМСТВЕННЫЙ СТРАТИГРАФИЧЕСКИЙ КОМИТЕТ СССР ПОСТАНОВЛЕНИЯ МЕЖВЕДОМСТВЕННОГО СТРАТИГРАФИЧЕСКОГО КОМИТЕТА И ЕГО ПОСТОЯННЫХ КОМИССИЙ ВЫПУСК 23 Ленинград, 1987 УДК 551.7.061.7 Постановления Межведомственного...»

«КОНКУРСНАЯ ДОКУМЕНТАЦИЯ по проведению конкурсного отбора научных проектов в рамках выполнения проектной части государственного задания в сфере научной деятельности образовательным организациям высшего образования, подведомственным Минобрнауки России СОГЛАСОВАНО Директор Департамента науки и технологий Министерства образования и науки Российской Федерации /С.В. Салихов/ Москва, 2014 г. 1 2 ОГЛАВЛЕНИЕ I. ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ II. ИНФОРМАЦИЯ О КОНКУРСЕ 1. Общие положения 2. Требования к...»

«ГЕОЛОГИЧЕСКИЕ ЭКСКУРСИИ П О КРЫМУ Санкт-Петербург 2010 Санкт-Петербургский государственный университет Геологический факультет 60-летию Крымской учебной практики Санкт-Петербургского государственного университета посвящается В.В. Аркадьев ГЕОЛОГИЧЕСКИЕ ЭКСКУРСИИ ПО КРЫМУ Санкт-Петербург Издательство РГПУ им. А.И. Герцена 2010 УДК 551(234.86) ББК 26.3 А 82 Аркадьев В.В. Геологические экскурсии по Крыму - СПб.: Изд-во РГПУ им. А.И. Герцена, 2010. - 132 с. ISBN 978-5-8064-1503-6 В книге описаны...»

«Конфиденциально, только для членов АА Издается с 7 апреля 1993 года Единый информационный телефон АА Москвы и Московской области 8(495)220-09-69 8(985)220-09-69 Будни с 10 до 21 выходные с 10 до 18 Январь 2014 Московской Интергруппы Содружества АА России 8 февраля 2014 года в г.Кременчуге пройдет конференция АА — путь к НОВОСТИ свободе, посвященная 4-летию группы Магнит Тел. 050-7886332Павел, 067-5887015 - Оксана ГРУПП 15-16 февраля 2014 года в Киеве состоится Международный Форум, посвященный...»

«Вопрос 1: Стандарты отчетности Все международные стандарты бухгалтерского учета в государственном секторе (IPSAS), Пособие по статистике правительственных финансов (GFS) и Европейская система счетов (ESA) 95 – это стандарты отчетности. Они определяют следующее: В случае IPSAS – форму и содержание финансовых отчетов общего назначения; В случае GFS или ESA 95 – форму и содержание статистических отчетов. Ни один из указанных выше стандартов не определяет напрямую процессы бухгалтерского учета....»

«Roland Легкий способ бросить пить: Добрая книга; Москва; 2007 ISBN 978-5-98124-191-8 Оригинал: Allen Carr, “Easy Way to Control Alcohol” Перевод: Юлия Шпакова Вероника Венюкова Аннотация Аллен Карр, разработавший собственный способ избавления от никотиновой зависимости, ныне известный всему миру как Легкий способ бросить курить, применил свой новаторский метод и к проблеме алкоголизма. В книге Легкий способ бросить пить он развенчивает иллюзии, которые окружают проблему алкоголизма и изображают...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.