Алгоритмы - построение и анализ (1021735), страница 259
Текст из файла (страница 259)
Задачи В-1. Шары и корзины В этой задаче мы рассмотрим размещение и шаров по б различным корзинам. а) Предположим, что все и шаров различны, а их порядок в корзине не имеет значения. Докажите, что имеется о" способов разместить шары в корзинах. б) Предположим, что все п шаров различны, а их порядок в юрзине существенен. Докажите, что имеется ровно (б+ п — 1)!/(б — 1)! способов размещения шаров в корзинах. (Указанигс подсчитайте количество способов разместить в ряд и различных шаров и 6 — 1 неразличимых разделителей.) в) Предположим, что все шары идентичны, а следовательно, их порядок в корзине не имеет значения. Покажите, что количество способов, юторыми можно разместить шары в корзинах, равно ( +"„').
(Указанигс воспользуйтесь тем же способом, что и в части б, только теперь шары также неразличимы.) г) Покажите, что если шары идентичны, и ни в одной корзине не может находиться больше одного шара, то разместить шары в корзинах можно („) способами. д) Покажите, что если шары идентичны и ни одна корзина не должна остаться пустой, то разместить шары в корзинах можно (" ) способами. Часть Ч!1!. Приложения: математические основы 1256 Заключительные замечания Общие методы решения вероятностных задач впервые обсуждались в знаменитой переписке Паскаля (В. Рааса!) и Ферма (Р. де Реппа!), начавшейся в 1654 году, и в книге Гюйгенса (С.
Ниуйепз, 1657 год). Строгая теория вероятности началась с работ Бернулли (Л Вепш!11, 1713 год) и Муавра (А. де Мо(чге, 1730 год). Дальнейшее развитие теории вероятности связано с именами Лапласа (Р.Б. де 1.ар1асе), Пуассона (8.-0. Ро1ззоп) и Гаусса (С.Р. Оаизз). Суммы случайных величин исследовались П.Л. Чебышевым и А.А. Марковым. Аксиоматизация теории вероятности была выполнена А.Н. Колмогоровым в 1933 году.
Оценки хвостов распределений приведены в работах Чернова (СпегпоП) [591 и Хеффдинга (Нос!И1п8) [150!. Важные результаты о случайных комбинаторных структурах принадлежат Эрдешу (Р. Еп1оз). Материал по элементарной комбинаторике можно найти в книгах Кнута (Клита) [182! и Лю (Ь1п) [205Б по теории вероятности — в книгах Биллингсли (В[11шйз!еу) [421, Чанга (СЬип8) [60), Дрейка (Пга!се) [801, Феллера (Ре11ег) [881 и Розанова (Когапоч) [263].
Библиография [!] М!!гоп АЬгашотч)гх апд 1гепе А. Вте8пп. Напт!Ьоо1т о!'МатЬетат1са1 Гипс!!опт. Почет, 1965. [2] О. М. АдеГвоп-ЧеГв!т17 апд Е. М. 1.апд!в. Ап А18огйЬш 1Ьг дте Ог8ап1хат!оп ор 1п!Ьппаг!оп. Яочгес Майетадсв 1)о!т!аду, 3:1259-1263, 1962. [3) 1.еопагд М. Ад!ешап, Саг1 Ротпегапсе апд КоЬетГ 8. Кшпе!у. Оп Пвт!п8п1вЬ!п8 Рппте ЫшпЬегв Ргош Сошров!ге ЫшпЪегв.
Аппа!в о7МатЬетат1св, 117:173-206, 1983. [4] А!о!с А88аттча! апд )ейгеу Ясотт Чтпег. ТЬе 1прпт/Оптрпт Сотпр1ехйу ор Яотт!п8 апд Ке!агед РгоЫептв. Соттитсадопв о!' тЬе АСМ, 3119):1116 — 1127, 1988. [5] А1 Ггед Ч. АЬо, 3оЬп Е. Норсгой апд 1е!Тгеу П. !Л! тпап. ТЬе Оев1дп апд Апа1уяв о! Сотритег А18ог!тЬтя Адд!воп-%ев!еу, 1974.
[6] А!йед Ч. АЬо, )оЬп Е. Норсгой апд )е1Тгеу 13. 11!Ьпап. 7)ага 51гистигев апс1 А1уоПйтв. Адд1воп-Чттев1еу, 1983. А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. — М.: "Вильямс", 2000. [7] Качдпдга К. АЬща, ТЬошав 1.. Ма8папй апд )ашев В. Ог!ш. 1Чепчог1т г"!отчет 77теоту, А1доПйтв, апд Арр!1сат1опв.
Ргепйсе На11, 1993. [8) Кач!пдга К. АЬща, Кпгг МеЫЬотп, )ашев В. Ог1ш апд КоЬетт Е. Тат)ап. Равтег А18оддппв !Ьг гЬе ВЬоггевг РатЬ РгоЫеш..гоигпа! о!' йе АСМ, 37:213 — 223, 1990. [9] Катдпт1га К. АЬща апд Лешев В. Ог1ш. А Равт апд яшр!е а18оддпп !Ьг дте шахппшп йотч ргоЫеш. Орегадопз ЯевеагсЬ, 37(5):748-759, 1989. [10] Качдпдга К. АЬща, 1атпев В.
Ог1ш апд КоЬетт Е. Тат)ап. 1шргочед Типе Воппдв Рог гйе Мах!пппп Р!оъч РгоЫеш. БРАМ Лоигпа! оп Сотритгп8, 1815):939-954, 1989. 1258 Библиография [11] М1!с!оя А!га1, Запоя Кот1оя апс! Епс!ге Бхетегес!1. Богг)пд 1п с1одгг рага11е! ягерв. СотЬ1пагоПса, 3:1 — 19, 1983. [12] М1!с!ов А!га1, Ы!тгос! Мед)сЫо апс! Ог11 Чсгааггв. 1тргочес3 А!дог!1Ьспя апс! Апа!- уя!в Гог есгегагу РгоЫетя апс! Оепега!!габопв.
1п Ргосеес1!лдя о1 йе Збй Аппиа1 Бутрозгит оп Гоипс1аг1опя о!' Сотригег Бссепсе, радев 473-482, 1995. [13] МоЬатас! А1сга апс! Ьопау Вакх!. Оп сЬе Бо!шюп оГ Е|пеаг Кесшгепсе Ес!пабопв. Сотригаг1опа! Орс1т!гас!оп апс!Арр1!саг!олз, 10(2):195 — 210, 1998. [14] Иода А1оп. Оепегасшд ряепс!о-гапс!от репппгаг!опя апс! тахппшп !)осч а!доп0ппв. 1п/отта!!оп Ргосеяя1пд Тег(егя, 35:201-204, 1990. [15] Агпе Апс!егвяоп. Ва!апсес1 БеагсЬ Тгеев Мас)е Бппр1е. 1п Ргосеес!1пдя о3'йе ТЫпс1 КЬгЫюр оп А!дог!гЬтя апс! 13ага Бггисгигез, пшпЬег 709 ш 1.есгше Хосея ш Сотрпсег Бс)епсе, радея 60-71. БрПпдег-Чег1ад, 1993 [16] Агпе Апс!егяяоп.
Равгег с!егегт!п1вс!с яогг!пд апс! яеагсЫпд ш 11пеаг врасе. 1п Ргосеес1!лдз о3гЬе 3 7гЬ Аллиа1 Бутроя1ит ол Роилс1аг!оля о1 Сотригег Бсселсе, радея 135-141, 1996 [17] Агпе Апс!егявоп, ТогЬеп Надетр, БсеГап Ы!!язеп апс! Ка)ееч Катал. Босс!пд т ! шеаг г!те? волгла! о!' Сотригег апс! Бузгет Бс!епсез, 57: 74-93, 1998. [18] Тот М. Аровго1. Са1си1ия, чо!шпе 1. В1а!вс!е!1 РпЫ!вЫпд Сотрапу, яесопс! ес!!г!оп, 1967. [19] Бащееч Агога.
РгоЬаЫ11ягк сЬесйлд о1'ргоо3я алс! йе Ьагс?пеяя о/арргох1тагюп ргоЫетя. РЬО сЬея)я, !)п!чегв!гу оГ СаИогп!а, Вег)се!еу, 1994. [20] Бащееч Агога. ТЬе Арргох!таЫ11су оГХР-Ьагс) РгоЫетв. 1п Ргосееас1лдз о3'гЬе 30й Аплиа1 АСМ Бутроясит оп ТЬеогу о3' Сотриг!лд, радея 337 — 348,1998. [21] Бащееч Агога. Ро1 упоппа1 Типе Арргохппабоп БсЬетев Гог Епс!)с!еап Тгаче1- шд Ба!еятап апс! ОсЬег Оеотегпс РгоЫетв.
Уоигла1 о!'гЬе АСМ, 45(5):753- 782, 1998. [22] Бащееч Агога апс! Сагзгеп 1лпс!. Нап1певя оГ Арргохппасюпв. 1п ОоПс Б. НосЬЬашп, есЬсог, Арргах!таг!оп А 1догсйтя ~ог !с1Р Нап? РгоЫетя, радев 399- 446. Р%8 РпЬИвЫпд Сотрапу, 1997. [23] Зачес! А. Ая1ат. А Бппр1е Воппс$ оп гЬе Ехресгес) НеьдЬг оГ а Капс!от!у Вш!с В)лагу БеагсЬ Тгее. ТесЬтса1 Керогс ТК2001-387, ОаггпюпгЬ Со11еде Оерагстепг оГ Согорпсег Бссепсе, 2001.
[24] М1!сЬа!! 3. Ага!1аЬ. А1доПйтз апс1 ТЬеогу о!' Сотригаг1оп Напс!Ьоо?с. СКС Ргеяв, 1999. [25] О. Апя!е1!о, Р. Сгеясепх1, О. ОатЬов1, Ч. Капп, А. МагсЬеп1-Брассате1а апс! М. Ргосаяд Сотр1ех!гу апс! Арргох!таг!опс СотЬспагог!а! Орг!т!ха!!оп РгоЫетя алс! ТЬе!г Арргох!таЬ!11гу Ргорегг1ек Брппдег-Чег! ад, 1999. 1260 Библиография [44] Ве!а Во!!оЬав. Валс!от Бгар)гк Аеас!ет1с Ргевя, 1985. [45] 3. А. Вопс!у апд ЬЬ д. К. Мопу. Огар!с Тбеогу илй Арр!1саг!оля. Атепсап Е1яеч!ег, 1976.
[46] 6111ев Вгаввап! апс! Рап1 Вгаг!еу. А!дог!йт1свг Т!сеогу алЫ Ргасйсе. Ргепс1сеНа!1, 1988. [47) О!1!ея Вгаввагс1 апс! Рап1 Вгаг1еу. гияс!отел!а!в о1 А1дог1йт1св. Ргепбсе НаП, 1996. [48] К1сЬап$ Р. Вгепс. Ап 1тргочес! Мопсе Саг!о Расгопкагюп А!допйгп. В1Т, 2012):176-184, 1980.
[49] Маг1с К. Вгоч и. Тбе Ала!ув1в о!'а Ргасг1са1 алс1 №аг1у Орг1та1 Рпопгу Диеие. РЫ) йегб, Сотрпсег дс1епсе ПераПтепд ЯгапГогс1 Ышчегя)гу, 1977. ТесЬшса! Кероп дТАХ-С8-77-600. [50) Маг)с К. Вго юп. 1тр!етепсабоп апс! Апа!ув!в оГ Впюппа1 лиепе А!допйтя. 51АМ./оигла1 ол Сотриплд, 713):298-319, 1978. [51) У.Р.
ВпЬ!ег, Н.%. Ьепягга, 1г., апс! Саг! Ротегапсе. Расгоппд шгедегя чпСЬ йе пшпЬег йеЫ в1ече. 1п А.К. 1.епвсга апс! Н."чч'. Ьепвпп, 1г., ес!1согв, Тбе Оече1ортелс о! йе МитЬег г!е1В В!ече, чо1шпе 1554 оГЬесгиге №гев и Майетаг1св, радев 50-94. Ярппдег-Чег!ад, 1993. [52] Ь Ьавгепсе Саггег апс! Маг!с Х. %едтап. Ушчегва! С!аваев оГ НаяЬ Рппсгюпя. .1оигла1 о!' Сотригег алс! Буягет Яс!елсея, 18(2):143 — 154, 1979.
[53] Вегпагс! СЬакеПе. А Мтппшп Ярапшпд Тгее А1допйт ч 1й 1пчегяе-Ас1сегтапп Туре Согпр!ехду. 1оигла1 о!' йе АСМ, 47(б):1028-1047, 2000. [54] 1ояерЬ СЬепуап апс1 ТогЬеп Надегпр. А Капс!от!лес! Махппшп-Р!очг А1допйгп. ЯАМ.1оигла1 ол Сотрийлд, 24(2):203-226, 1995.
[55] ЮояерЬ СЬепуап апс! д. Х. МаЬевЬюап'. Апа!ув1я оГ Рге!!оч~ Р,яЬ А!допСЬгпя Рог Махппшп Хепчог!с Р1очс 31АМ уоигла1 ол Сотристд, 18(6):1057 — 1086, 1989. [56] Вопя Ч. СЬег1сая1су апс1 Апс)гечг Ч. Оо!6Ьегд. Оп 1тр1егпепсшд сЬе РпяЬ-ге1аЬе! Мейос! Гог йе Махппшп Р1оч~ РгоЫет. А1дог1йт1са, 1914):390-410, 1997. [57] Вопя Ч. СЬег1саяв!су, Апс!гею Ч.
Сю!с!Ьегд апс! Тотаяк Кас!х1!с. 8ЬоПев! райя а!допГЬтя: ТЬеогу апс! ехрептепга! еча!па!!оп. Майетайса! Ргодгатт1лд, 7312):129-174, ! 996. ]58] Вопя Ч. СЬег1савв1сУ, Апс)геныч Ч. Сго!6Ьегд апс) Сга18 81!чегвге!и. Впс)се!в, НеаРЯ, Ь1яся Апс! Мопосопе Рпопсу Япепея. ЯАМ.Уоигла1 ол Сотрийлд, 28(4):1326- 1346, 1999. [59) Н. СЬегпо!Т. А гпеаяпге оГ аяутрсос1с ейс1епсу Гог сев!я оГ а ЬуросЬея!я Ьаяес) оп йе япп оГоЬяегчас!опв. Алла!в оТМайетаг1са1 Вгайвг!св, 23:493 — 507, 1952.
Библиография 1261 [60] Кас !.а1 СЬппд. Е!етелгату РтоЬаМ!1гу ТЬеоту и41Ь БгосЬаяг!с Ргосеяяек Брппдег-Чег! ад, ! 974. [61] Ч. СЬчаса1. А Огеес!у Неппябс !ог йе Бес-Сочеппд РгоЫепс. МагЬетаг!ся о1" Орегаг(оля ЯевеагсЬ, 4(3):233-235, 1979. [62] Ч. СЬчаса1. Етеаг Ртодгаттслд. %.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
