4. На выполнение микросекундной команды потребуется 1 с. На один оборот диска, выполняемый за 16 мс (при 3600 оборотах/мин), уйдет 5 ч, а на 30-миллисекундный поиск -10 ч, 2 с, требующиеся для ввода моего имени, превратятся примерно в месяц.
5. За 1 с суперкомпьютер способен выполнить 100 млн операций с плавающей точкой над 64-раэрядньши числами; мидикомпьютер может выполнить 1 млн сложений 16-разрядных целых чисел; микрокомпьютер 0.5 млн 8-разрядных команд, а Бейсик на персональном компьютере может выполнить 100 операторов. Значения времени, указанные в задаче, дают примерно одинаковую производительность для первых трех компьютеров, но "бедный Бейсик1* остается далеко позади.
6. Если не учитывать снижение быстродействия из-за очередей, то 30-миллисекунданая дисковая операция обеспечивает время выполнения запроса, равное 3 с или 1200 запросов/ч.
7. Стоимость этого изменения составляет 100 дол времени компьютера плюс 400 дол времени программиста. При экономии 10 мин в день или 16 дол в день потребуется месяц, чтобы окупить затраты. Если скорость возросла вдвое, экономия, равная 80 дол в день, окупила бы зто ускорение за неделю.
9. Даже я могу вводить цифры со скоростью 1 цифра/с, что дает 3 записи/мин или 200 записей/ч. Если служащий вводил бы данные повторно, используя знакомые ему средства, это заняло бы меньше 2 ч и стоило бы менее 50 дол. Автоматизированное решение потребовало бы программного обеспечения существенного объема (я бы тщательно поискал подходящие пакеты, прежде чем писать программу самому), а также покупки модемов. Хотя решение на высоком техническом уровне, очевидно, предпочтительней для данных большого объема, простое решение лучше для рассматриваемой задачи.
РЕШЕНИЯ К ГЛ. 7
2. В алгоритме 1 используется примерно N /6 вызовов процедуры max, в алгоритме 2 при-мерно N /2 вызовов, а в алгоритме 4 примерно 2N вызовов. В алгоритме 2Ь дополнительный объем памяти для кумулятивного массива растет линейно, а в алгоритме 3 дополнительный объем памяти для стека имеет логарифмическую зависимость, в других алгоритмах используется фиксированный объем дополнительной памяти. Алгоритм 4 пригоден
для интерактивного взаимодействия: он находит ответ за один проход по входным данным, что особенно полезно при обработке файлов на диске.
3. Замените оператор присваивания MaxSoFar :а 0 на MaxSoFar := - °°. Бели вас беспокоит использование — <», MaxSoFar := X [1] тоже можно использовать; почему?
4. Задайте начальные значения в массиве Cum так, чтобы Cum [I] = Х[1] +...+ Х[1]. Сумма элементов подвектора X [L.. .U] равна 0, если Cum [L - 1] = Cum [U]. Поэтому подвектор с суммой, наиболее близкой к 0, находится с помощью определения местоположения двух наиболее близких элементов в массиве Cum, что может быть сделано за время О (N logN) посредством сортировки массива. Это время работы с точностью до коэффициентов оптимально, так как любой алгоритм для решения этой задачи может быть также использован, чтобы решить задачу "уникальности элементов'', в которой определяется, содержит ли массив дубликаты (Добкин и Липтон показали, что для решения этой задачи требуется как раз столько времени в наихудшем случае на модели вычислений в виде дерева принятия решений).
5. Общая стоимость путешествия между пунктами I и J при линейной зависимости стоимости проезда от длины пути равна Cum [J] - Cum [I -1], где Cum - кумулятивный массив, как и выше.
