лежат между 1 и 1 ООО ООО. Можно задать вопрос: не влияет ли заметно диапазон весов ребер на длительность прогнозов? По-видимому, не влияет. Это заключение согласуется с доводами из разд. 4.1 и с элементарной теорией вероятности, но убедительнее всего экспериментальное доказательство. Были проведены прогоны с весами от 1 до 100 и с весами от 1 до 10". Отличие средних длительностей прогонов было только в третьем десятичном знаке (что уже объяснимо системной неточностью).

Теперь проверим анализ сложности из разд. 4.1. Первой целью будет определение среднего времени прогона Для сети с М вершинами.

Сколько следует прогнать случайных сетей с М вершинами, чтобы получить достаточно надежное среднее значение? Подходящий размер выборки будет определен экспериментально (с неявньм использованием закона больших чисел) ). Начнем с М=50, так как при меньших значениях М прогоны столь коротки, что ошибка в третьем десятичном знаке составляет заметную часть общего времени прогона. Теперь выполним прогоны для переменного числа полных случайных сетей с 50 вершинами. Мы прогоняли от 25 до 200 случайных сетей и зафиксировали среднее около 0.034 с на сеть для всех размеров выборки. Это указывает на то, что среднее значение устанавливается быстро. Исключительно для уверенности и в предположении, что, возможно, большие значения М могли бы потребовать больших размеров выборки, мы обычно вслед за этим пользуемся для проверки выборкой из 100 случайно сгенерированных полных сетей. Если бы прогон стоил заметно дороже, мы не могли бы быть столь предусмотрительными.

Рассмотрим значение М=75. Прежде чем выполнять прогон 100 сетей с 75 вершинами, проверим предсказания разд. 4.1. Если подпрограмма PRIM требует времени, пропорционального М, и если сети с 50 вершинами потребовали в среднем времени 0.034 с, то сети с M=75 вершинами должны потребовать в среднем около (75/50)(0.034)= =0.076 с.Испытание 100 сетей с 75 вершинами дает экспериментальное среднее 0.075 с.

При M=100 среднее время прогона должно быть приблизительно вчетверо больше, чем при УИ=50 (почему?). Следовательно, мы ожидаем, что среднее будет приблизительно равно 0.136 с. Экспериментальный прогон 100 сетей дает среднее 0.129 с.

В самом деле, оказывается, что подпрограмма PRIM требует времени, пропорционального М. Теперь построим функцию, предсказывающую длительность прогона. Пусть Т{М) обозначает среднюю продолжительность прогона при использовании подпрограммы PRIM для сети с М вершинами. Так как Т{М)=0{М), можно явно записать Т{М)=АМ-\-ВМ+С, где А, В, С - константы, которые предстоит определить экспериментально.

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

Требуется, чтобы кривая Т{М) проходила через три экспериментальных точки:

М=50 Г(М)=0.034 М=75 Г (М)=0.075 М = 100 Г (М)=0.129

Так как каждая из этих точек лежит на кривой Т{М), должны выполняться следующие три уравнения:

(50)М+(50)В+С=0.034 (75)М-Ь(75)В-ЬС=0.075 (100)М-Ь(100)В+С=0.129

Эта система линейных уравнений легко решается относительно коэффициентов А, В, С. Получаем

Л = 1.04(10-!) 5=3.4(10-*) С=9.0(10-=)

так что

Г(М)=((1.04(10-П)М2+((3.4(10-*))М-9.0(10-*)

Теперь рассмотрим M = 150. Воспользовавшись этим уравнением, мы могли бы предсказать среднюю продолжительность прогона Т(150)=0.276 с для сети со 150 вершинами. Мы получили экспериментальное значение 0.284; таким образом, относительная ошибка составляет 8/284=0.028, или около 3%.

Уместно сделать некоторые замечания относительно этой ошибки. Процедура, когда данные в некотором диапазоне аппроксимируют какой-либо кривой, а затем эту кривую используют для предсказания значений за пределами этого диапазона, называется экстраполяцией. Экстраполяция полиномами опасна. Небольшие ошибки в данных могут слегка изменить значения коэффициентов полинома. Эти маленькие ошибки в коэффициентах приводят к гораздо большим ошибкам, как только аргумент полинома выходит за пределы интервала аппроксимации. Экспериментальные значения Т{М) подвержены ошибкам в третьем десятичном знаке по причинам, обсуждавшимся раньше. «Слишком маленькая» ошибка в 2.8% легко могла бы подскочить из-за изменений в наблюдаемых последних десятичных знаках. Хорошее элементарное обсуждение экстраполяции и ошибок, которые вносятся в нее, можно найти в книге [43].

Упражнения 4.2

4.2.1. Счетчики операторов (проверка). Измените подпрограмму PRIM так, чтобы она печатала общее число выполненных операторов при отыскании ОДМВ. Для случайных входных данных найдите средние значения для операторов с кратностями выполнения А, В, С ч D т рис, 4,1.7,

4.2.2. Счет при игре в кегли (построение алгоритма). Постройте алгоритм подсчета очков при игре в кегли. Используйте стандартные правила относительно ударов, очередности, расположения и т. д. Запрограммируйте и проверьте ваш алгоритм.

*L4.2.3. Простые числа (полное построение, сравнительная проверка). Полностью постройте алгоритм, выдающий все простые .числа от 2 до некоторого введенного N. Вы могли бы воспользоваться литературой, чтобы найти два таких алгоритма и провести их сравнительные испытания.

*4.2.4. Относительные величины времени шполнения (анализ). Найдите приближенные значения относительных величин времени выполнения для различных тниов операторов на имеющейся в вашем распоряжении вычислительной машине. Выразите эти величины в единицах, равных времени выполнения оператора присваивания вида А=1.0. Затем, например, вы могли бы обнаружить, что выполнение простого присваивания для индексированной переменной, например А(1)=1.0, требует две такие единицы. Будьте осторожны. Эта задача не так проста, как кажется.

*L4.2.5. Головоло.мка «8» (реализация и проверка). Реализуйте и проверьте алгоритм отхода назад для головоломки «8», описанной в р.агд. 3.3.

*4.2.6. Интерполяция и экстраполяция (проверка программы). Определите и противопоставьте «интерполяцию» и «экстраполяцию». Что из них кажется надежнее? Можете воспользоваться книгой по численному анализу (например, [43]).

*4.2.7. Приблшюение по методу наименьших квадратов (проверка программы). Просмотрите книгу по численному анализу и изучите материал об аппроксимации данных кривыми по методу наименьших квадратов. Сравните эту процедуру с использованием интерполирующих и экстраполирующих полиномов (см. упр. 4.2.6).

*L4.2.8. Полиномиальная аппроксимация данных (проверка программы). Закодируйте подпрограмму РЯШ и продолжите ее проверку. Является ли полином Т(М) из этого раздела удовлетворительным аппроксимирующим полиномом (см. упр. 4.2.6)? Ддя имеющейся в вашем распоряжении машины необходимо заново вычислить А, В и С. Почему? Насколько сильно могут отличаться длительности отдельных прогонов от средней длительности? Попробуйте, используя метод наименьших квадратов (см. упр. 4.2.7), получить аппроксимацию квадратичным полиномом. Каков аппроксимирующий полином при методе наименьших квадратов по сравнению с Т(М)?

L4.2.9. Алгоритм PRIM (разработка и реализация). Реализуйте алгоритм PRIM, используя ссязянные списки. Срасните трудоемкость измененной версии программы с трудоем1состью программы на рис. 4,2.1.

L4.2;10. М1югис наблюдали, что большинство программ, по-видимому, затрачивает большую часть времени на выполнение малой части операторов в программе. Соберите несколько старых программ и, применив метод профилей, проверьте справедливость этого наблюдения.

L4.2.11. Проверьте сложность либо программы KNIGHT (разд. 2.1), либо эвристики, описанной в упр. 2.1.2.

4.2.12. Как можно было бы изменить и дополнить обсуждение в этом разделе, если бы расход памяти рассматривался как важнейший фактор?

4.3. Документация и обслуживакие Общее обсуждение

Одним из показателей квалификации программиста является степень понимания им всего процесса программирования. При этом важный и часто упускаемый из виду аспект состоит в передаче другим npoi раммистам деталей данной программы.