Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [ 108 ] [109] [110] [111] [112] [113] [114] [115] [116] [117]

ки X и s. Каковы эти величины по сравнению с истинными средним и дисперсией равномерно распределенной случайной переменной? Поиторите для 25, 50 и 100 случайных чисел.

6.3.13. Равномерно распределенные случайные переменные, опредеяенные на каждом из следующих замкнутых и открытых интервалов, по существу, эквивалентны: [О, 1], (О, 1], [О, 1), (О, 1). Почему?

6.3.14. Является ли интервал машинного генератора случайных чисел (например, для алгоритма LCM) действительно непрерьшным интервалом [О, 1)?

*L6.3.15. Алгоритм NRN (реализация). Запрограммируйте алгоритм NRN, используя свой генератор случайных чисел в качестве процедуры RANN, при значениях п=10 и 20. Выполните с вашей программой некоторые эксперименты, чтобы убедиться, что она дает нормально распределенные случайные числа. Воспользуйтесь для контроля таблицами нормального распределения.

6.3.16. Докажите теорему 6.3.4.

**L6.3.17. Тест хи-квадрат. Он часто применяется для того, чтобы взять выборку случайной переменной и задаться вопросом: какое распределение скрывается под этой выборкой? В общем виде ответ на этот вопрос должен носить вероятностный характер. Существует много тестов, призванных облегчить получение ответа на подобные вопросы. Известно, что наилучшим является тест хи-квадрат (х-тест). Изучите этот тест и научитесь им пользоваться. Обсуждение ряда таких статистических тестов можно найти в разд. 3.3 книги Кнута [57].

*6.3.18. В упр. 2.4 был получен ряд общих результатов относительно средних и дисперсий дискретных случайных переменных. Убедитесь, что эти результаты верны и для непрерывных случайных переменных.

*6.3.19. Пусть X и К - две независимые случайные переменные. Пусть {Х, . . . , Х„} - выборка из п наблюденных значений X, а {Yi, . . . , Y„} - выборка из п наблюденных значений Y. Найдите несмещенную оценку для Е [Z], где Z=XY.

6.3.20. Генераторы случайных чисел. Ни одни из коммерческих генераторов случайных чисел не содержит шага 1 с циклом DO, присутствующим в алгоритмах MS, LCM и NRN. Какая процедура применяется для генерации последовательности случайных чисел в генераторе, реализованном на вашей машине?

L6.3.21. Эктоненциально распределенные случайные числа. Используйте процедуру, построенную в этом разделе, для генерации нескольких экспоненциально распределенных случайных чисел. Примите >.= L Сравните теоретическую функцию распределения с распределением частот, полученным экспериментально.

6.3.22. Вычислите среднее и дисперсию через X для экспоненциально распределенной случайной переменной.

***6.3.23. Алгоритм PNRN (доказательство). Докажите правильность алгоритма PNRN. Указание: (а) обратите внимание иа то, что (Vi, V.) - случайная точка, равномерно распределенная внутри единичного круга (if S<1 на шаге 2); (б) воспользуйтесь полярными координатами S=R (квадрат расстояния от начала координат); (в) вычислите вероятность того, что -2 In 5<:л при 0<r<L

*L6.3.24. Алгоритм PNRN (проверка). Реализуйте алгоритм PNRN и примените его для генерации случайных чисел с распределением Л/(О, 1). Сравните теоретическую функцию распределения с экспериментальным распределением частот.

**L6.3.25. Алгоритм PNRN (проверка, анализ). Проведите сравнительную проверку времени, затрачиваемого на получение нормально распределенных случайных чисел, с помощью алгоритмов PNRN и NRN. Проанализируйте различие с учетом сложности обращений к программам, генерирующим равномерно распределенные-числа и вычисляющим квадратные корни и логарифмы на вашей машине.

*ь6.3.26. Тасовка карт (полное построение). Проведите полное построение алгоритма, моделирующего тасовку колоды карт.



Глава 7. Дополнительные замечания и ссылки

Цель этой главы - привлечь внимание к материалу, дополняющему содержание этой книги. Она не должна служить исчерпывающей библиографией. Мы попытались найти хорошие, легко читаемые источники по вопросам, которые заинтересуют читателя.

В этой главе две части. Первая - аннотированная библиография, упорядоченная по главам и разделам. Вторая - алфавитный список (по фамилиям авторов) работ, упомянутых в первой части. Где возможно, мы предпочитали цитировать учебники более или менее элементарного уровня вместо трудных журнальных статей. Для обозначения уровня- работы использовались следующие сокращения:

Е: элементарные,

I: промежуточного уровня,

А: трудные,

VA: очень трудные.

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

Глава 1. Полное построение алгоритма

Не существует «официального» определения термина «полное построение алгоритма». Похоже, что большинство специалистов в области вычислительной математики находят приемлемым перечень, данный в конце разд. 1.1.

Хорошим введением в математические машины и формальную теорию вычислений является книга [89]. Более обширным и немного более трудным введением является [72].

Хотя некоторые пуристы признают в качестве описания алгоритма только полную программу в кодах, мы думаем, что полусловесные пошаговые описания, использованные здесь (см. приложение А), и некоторое прозаическое обсуждение очень полезны (и часто необходимы) для основательного понимания работы алгоритма. Многим людям трудно вникать непосредственно в программу, если даже она хорошо документирована.

Естественно было бы полагать, что идея математической модели является наиболее фундаментальным понятием в прикладной мате-



матике. Несмотря на это, мы не смогли найти хорошего элементарного обсуждения этой темы, ориентированного на применение вычислительной техники.

Считается, что первоначальная формулировка задачи коммивояжера принадлежит Мерриллу М. Флуду (Колумбийский университет, 1937 г.). Она возникла в связи с выбором маршрутов для школьных автобусов. К середине 50-х годов в литературе по исследованию операций начали появляться журнальные статьи, посвященные этой задаче, и она широко изучается до сих пор. Хотя для задачи не известны алгоритмы, полиномиальные в худшем случае, существует ряд впечатляющих эвристических и точных (но экспоненциальных в худшем случае) процедур ее решения. Ссылки на некоторые из них даны в разд. 4.4. В [63] описаны некоторые практические приложения задачи коммивояжера.

Хорошее общее обсуждение реализации, отладки и документации дано в [99]. В качестве учебника по «стилю программирования» см. [54].

Несмотря на то что для многих людей полиномиально-экспоненциальный критерий сложности кажется вполне очевидным, до середины 60-х годов он, по-видимому, не находил широкого применения. Первая явная его формулировка, которую мы нашли, содержится в [22]. Обозначения «0-большое» и «о-малое» стали популярными в ряде математических дисциплин. Подробное обсуждение можно найти в гл. 1 книги [56].

Глава 2. Некоторые основные приемы и алгоритмы

2.1. Структурное программирование сверху-вниз и правильность программ

Предмет структурного программирования сверху-вниз нов и противоречив. Среди программистов он, кажется, быстро завоевывает признание, хотя пока далеко не всеобщее. Литература по структурному программированию растет экспоненциально. Для дальнейшего изучения мы бы рекомендовали [70]. Эта достаточно основательная книга содержит краткий исторический обзор предмета. Можно также посмотреть специальные выпуски двух популярных журналов [12], [17].

Более глубокое изложение материала содержится в [16].

2.2. Сети

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [ 108 ] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0015