Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 260
Текст из файла (страница 260)
Часть Ч!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оп Напс!Ьоо?с. СКС Ргеяв, 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. Етеаг Ртодгаттслд. %. Н. Ргееспап апс! Сошрапу, 1983. [63] 'Ч. СЬчаса1, О. А. К!агпег апс1 О. Е. Кппй. Бе!ессес1 СошЫпасопа! КевеагсЬ РгоЫешв. ТесЬшса1 Кероп БТАХ-СБ-72-292, Сошрпсег Бссепсе Оерясшепс, БсапГогс! 11п!чегв!су, 1972. [64] А1ап СоЬЬасп.
ТЬе 1псппяс Согпршабопа1 О!СГссп!су оГ Рппссюпв. 1п Ртосеег1- 1лдв о(йе 1964 Солдтевв /ог йод!с, МеГЬог!о!оду, алг! йе РЬС!оворЬу о! Яс!елее, радев 24-30. Хогй-Но1!апд, ! 964. [65] Н. СоЬеп апс! Н. %. 1.епвсга, 1г. Рпша11су Тевбпд апс1 )асоЫ Бшпв. МагЬетаг!св о!' Сотригагюл, 42(165):297 — 330, ! 984. [66] О. Сопсег. ТЬе 1Лпс!шсопв В-сгее. АСМ Сотриг!лд Яигчеув, 11(2):121-137, 1979.
[67] БсерЬеп Соо1с. ТЬе Сошр1ехКу оГ ТЬеогегп Ргочспд Ргоседигев. 1п Ргосеес1!лдв о( йе ТИХ Аллиа! АСМ Бутрогдит ол ТЬеогу ос Сотриг!лд, радев 151-158, 1971. [68] 1ашев %. Соо1еу апсс 1оЬп %. Тп1сеу. Ап А1допдпп Гог йе МасЫпе Са!сп!асюп оГ Сошр1ех Роппег Бепев. МагЬетагссв о1' Сотригаггал, 19(90):297-301, 1965. [69] Ооп Соррегвппй. Мог!!Гссас!опв со йе ХсппЬег Р!е1с! Б!ече..Уоигла! ос Сгурго1- оду, 6:169-180, 1993.
[70] Ооп Соррегяпсй апс1 БЬлше1 %шодгад. Маспх Мойр!ссабоп Ч!а Апйшебс Ргодгевв!оп..Гоигла1 о! БутЬо1!с Сотригаг!ол, 9(3):251-280, 1990. [7!] ТЬогпав Н. Соппеп. Итгиа! Метогу Тот Оага-Рата!!е1 Сотриг!лд. РЬО йеяв, Оерагппепс оГ Е!есспса! Епд!пееппд апс! Сошрпсег Бссепсе, МГГ, 1992. [72] Епс Ч. Оепагйо апс1 Веппеп 1.. Рох. БЬопевс-Коше МесЬос!в: 1. КеасЫпд, Рппппд, апс! Впс1сесв. Орегаполв ЯевеагсЬ, 27(1):161 — 186, 1979.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
