Упражнения 4.1

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

4.1.2. Возможны ли ситуации, когда алгоритм А оказался бы лучше алгоритма PRIM?

4.1.3. Преобразование двоичных чисел в десятичные (полное построение). Разработайте полностью алгоритм, преобразующий двоичные числа в десятичные и наоборот. Можно ограничиться преобразованием целых чисел.

4.1.4. Треугольник Паскаля (полное построение). Разработайте полностью алгоритм, строящий первые W строк треугольника Паскаля. Если вам это необходимо, можете найти определение (и краткую историю) этого треугольника в книге [56], стр. 52.

**4.1.5. Алгоритм А (разработка). Восполните явно все отсутствующие подалгоритмы в алгоритме А.

***L4.1.6. Агентство безопасности Ас осуществляет патрулирование. Оно имеет п патрульных автомобилей и обслуживает т клиентов. Ас знает, сколько нужно времени для проверки учреждения каждого из клиентов и сколько нужно времени для проезда от каждого из клиентов к любому другому. По очевидным соображениям секретности Ас любит менять схемы патрулирования. Оплата патрульных служащих почасовая.

Постройте полностью алгоритм для этой задачи. Привлеките любую дополнительную информацию, которая, по вашему мнению, необходима.

*4.1.7. Целочисленное умножение (полное построение). Постройте алгоритм, вычисляющий произведение двух целых чисел, используя только три операции: сложение, удвоение и деление иа 2.

4.1.8. Покажите явно, что среднее время Т(М) прогона подпрограммы PRIM равно О(М).

*4.1.9. Алгоритм проверки т цикл (разработка, правильность). Разработайте алгоритм, проверяющий, содержит ли произвольная сеть цикл. Докажите правильность алгоритма.

**4.1.10. Алгоритм проверки свойств дерева (разработка, правильность). Разработайте алгоритм, определяющий, является ли произвольная сеть деревом. Докажите правильность алгоритма,

**4.1.11. Алгоритм построения остовного дерева (наискорейигий подъем). Всегда ли следующая процедура находит остовное дерево Т минимального веса в сети G?

Algorithm EXCHANGE (ПЕРЕСТАНОВКА). Нужно найти остовное дерево Т минимального веса на взвешенной связной сети G, имеющей М вершин и N ребер.

Шаг 0. [Инициализация] Set Т произвольное остовное дерево для G; and пусть ребрами G, не входящими в Т, будут ei, ва,... е.

Шаг 1. [Проверка каждого ребра, не входящего в Т\ For i ч- 1 to do шаг 2 od; and STOP.

Шаг 2. [Перестановка ребра с максимальным весом] Пусть f - ребро с максимальным весом в единственном цикле в T+et; set Т=Т+е~[.

4.2. Проверка программ

Существует три аспекта проверки программы: (1) на правильность, 2) на эффективность реализации и (3) на вычислительную сложность. Вместе взятые, эти проверки направлены на получение экспериментального ответа на вопросы: работает ли алгоритм? Насколько хорошо он работает?

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

Проверка эффективности реализации направлена на отыскание способов заставить правильную программу работать быстрее или расходовать меньше памяти. Чтобы улучшить программу, пересматриваются результаты этапа реализации в процессе построения алгоритма.

Проверка вычислительной слохшости сводится к экспериментальному анализу сложности алгоритма или к экспериментальному сравнению двух или более алгоритмов, решающих одну и ту же задачу. Кроме того, проверки этого типа применяются для дополнения теоретического анализа алгоритма. Если теоретический анализ слишком трудно провести, необходимо все уле накопить некоторый вычислительный опыт работы с этим алгоритмом. Этот опыт можно использовать, например, для предсказания продолжительности работы программы на определенном наборе входных данных. Результаты экспериментального анализа редко оказываются исчерпывающими, и не следует выходить за разумные пределы в их интерпретации.

Проверка правильности

Предположим, что у нас есть программа, которая получает правильные результаты для нескольких простых вариантов входных данных 1). Задача состоит в том, чтобы проверить ее так, чтобы ею можно было пользоваться с уверенностью. Далее мы сообщим несколько принципов, которые должны быть представлены в любом плане проверки.

) Многие программисты сказали бы, что такая программа «отлажена», а не «проверена». Некоторые пользуются этими двумя словами вперемежку. Остальные называют «Проверкой» процесс отыскания ошибок, а «отладкой» процесс локализации и устранения- их. Мы различаем три типа проверки, а термин «отладка» применяем для проверки правильности.

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

Планируйте проверку программы в процессе ее разработки. Думайте о том, как можно проверить каждый модуль и какие следует использовать для этого данные, еще в процессе его написания.

Кроме того, планируйте наперед предполагаемые изменения программы в будущем. Задайтесь вопросом: какие изменения вероятнее всего придется сделать? Здоровая забота об универсальности программы поможет избежать дорогостоящих переделок целых сегментов написанной программы.

Локальные проверки. Ряд простых тестов или проверок может быть выполнен вручную:

1. Проверяйте соответствие между оператором алгоритма или блок-схемы и его реализацией в программе. Медленно пройдите по всем операторам программы и попытайтесь представить себе назначение каждого из них и его связь с алгоритмом или блок-схемой.

2. Проделайте локальные проверки описаний всех переменных, изменяя все вхождения переменной, имя которой было изменено, проверьте соответствие размерностей массивов, вставьте операторы отладки или печати. Делайте все изменения сразу же, как только они осознаны, или по крайней мере отмечайте их, иначе их легко забыть.

3. Проверка на недопустимые значения. В каждом операторе, если это возможно, рассмотрите возможность появления недопустимого значения некой переменной и постарайтесь определить, из-за чего это могло бы произойти. Убедитесь, что все переменные инициализируются правильно, например, при каждом вызове подпрограммы или процедуры. Убедитесь, что индексы никогда не могут принимать значения, слишком малые либо слишком большие. Кроме того, проверьте, чтобы недопустимые значения не могли быть внесены извне в подпрограмму или процедуру.

4. Проверка на бесконечные циклы. Попытайтесь определить, существует ли путь, по которому программа могла бы попасть в бесконечный цикл.

Проверка всех частей программы. Руководствуйтесь следуюшлм критерием. Проверяйте до тех пор, пока каждый присутствующий в программе оператор не будет давать правильного результата. В частности, проверьте каждую ветвь и каждое условие ошибки хотя бы раз. Попытайтесь проверить возможно больше различных путей через программу. Заметьте, что программы со cтpyкfypoй дерева имеют гораздо mTibuie путей, чем программы со сложными структурами цикЭЮв.