Упражнения

о 1.4 Приведите содержимое массива id после выполнения каждой операции union при использовании алгоритма быстрого поиска (программа 1.1) для решения задачи связности для последовательности 0-2, 1-4, 2-5, 3-6, 0-4 и 1-3. Укажите также количество обращений программы к массиву id для каждой вводимой пары.

о 1.5 Выполните упражнение 1.4, но используйте алгоритм быстрого объединения (программа 1.2).

о 1.6 Приведите содержимое массива id после выполнения каждой операции union для случаев использования алгоритма взвешенного быстрого объединения применительно к примерам, соответствующим рис. 1.7 и 1.8.

t> 1.7 Выполните упражнение 1.4, но используйте алгоритм взвешенного быстрого объединения (программа 1.3).

О 1.8 Выполните упражнение 1.4, но используйте алгоритм взвешенного быстрого объединения с сжатием пути делением пополам (программа 1.4).

1.9 Определите верхнюю границу количества машинных инструкций, требующихся для обработки Л/соединений TV объектов при использовании профаммы 1.3. Например, можно предположить, что для выполнения оператора присваивания С++ всегда требуется выполнение менее с инструкций, где с - некоторая фиксированная константа.

1.10 Определите минимальное время (в днях), которое потребовалось бы для выполнения быстрого поиска (программа 1.1) для решения задачи с 10 объектов и 10 вводимых пар на компьютере, который может выполнять инструкций в секунду. Примите, что при каждой итерации внутреннего цикла for должно выполняться не менее 10 инструкций.

1.11 Определите максимальное время (в секундах), которое потребовалось бы для выполнения взвешенного быстрого объединения (программа 1.3) для решения задачи с 10 объектов и 10 вводимых пар на компьютере, который может выполнять 10 инструкций в секунду. Примите, что при каждой итерации внешнего цикла while должно выполняться не более 100 инструкций.

1.12 Вычислите среднее расстояние от узла до корня в худшем случае в дереве, построенном алгоритмом взвешенного быстрого объединения из 2 узлов.

1> 1.13 Нарисуйте схему подобную рис. 1.10, но содержащую восемь узлов, а не девять.

о 1.14 Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения (программа 1.3) создает путь длиной 4.

1.15 Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения с сжатием пути делением пополам (программа 1.4) создает путь длиной 4.

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

о 1.17 Выполните упражнение 1.4, но используйте алгоритм взвешенного быстрого объединения с полным сжатием пути (упражнение 1.16).

1.18 Приведите последовательность вводимых пар, для которой алгоритм взвешенного быстрого объединения с полным сжатием пути (см. упражнение 1.16) создает путь длиной 4.

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

1.20 Измените программу 1.3, чтобы в ней для принятия решения, нужно ли устанавливать id[i] = j или id[j] = i, вместо веса использовалась высота деревьев (самый длинный путь от любого узла до корня). Экспериментально сравните этот вариант с программой 1.3.

1.21 Покажите, что лемма 1.3 справедлива для алгоритма, описанного в упражнении 1.20.

1.22 Измените программу 1.4, чтобы она генерировала случайные пары целых чисел в диапазоне от О до Л- 1 вместо того, чтобы считывать их из стандартного ввода, и выполняла цикл до тех пор, пока не будет выполнено N- 1 операций union. Выполните программу для значений N = 10 \0\ 10 и 10 и выведите общее количество ребер, генерируемых для каждого значения N.

1.23 Измените программу из упражнения 1.22, чтобы она выводила в виде графика количество ребер, требующихся для соединения 7V элементов, при 100<7V< 1000.

1.24 Приведите приближенную формулу для определения количества случайных ребер, требующихся для соединения 7V объектов, как функции 7V.

1.4 Перспектива

Каждый из алгоритмов, рассмотренных в разделе 1.3, кажется определенным усовершенствованием предыдущего, но, вероятно, процесс был искусственно упрощен, поскольку разработка самих этих алгоритмов уже была выполнена рядом исследователем в течение многих лет (см. раздел используемой литературы). Реализации просты, а задача четко определена, поэтому мы можем оценить различные алгоритмы непосредственно, экспериментальным путем. Более того, мы можем подкрепить эти исследования, количественно сравнив производительность алгоритмов (см. главу 2). Не все задачи, рассмотренные в этой книге, столь же хорошо проработаны, как эта, и мы обязательно встретимся с алгоритмами, которые трудно сравнить, и с математическими задачами, которые трудно решить. Мы стремимся принимать объективные научно обоснованные решения в отношении используемых алгоритмов, изучая свойства реализаций на примере их выполнения применительно к реальным данным, полученным из приложений, или случайным тестовым наборам данных.

Этот процесс - прототип того, как различные алгоритмы решения фундаментальных задач рассматриваются в данной книге. Когда это возможно, мы предпринимаем те же основные шаги, что и при рассмотрении алгоритмов объединения-поиска, описанных в разделе 1.2, часть из которых перечислена ниже:

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

Тщательная разработка краткой реализации для простого алгоритма.

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

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

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

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

Что еще важнее, по мере повышения вычислительных возможностей компьютеров и приложений разрыв между быстрыми и медленными алгоритмами увеличивается. Новый компьютер может работать в 10 раз быстрее и может обрабатывать в 10 раз больше данных, чем старый, но при использовании квадратичного алгоритма, наподобие быстрого поиска, новому компьютеру потребуется в 10 раз больше времени для выполнения новой задачи, чем требовалось старому для выполнению старой! Вначале это утверждение кажется противоречивым, но его легко подтвердить простым тождеством {\QN)/ 10= 10Л, как будет показано в главе 2. По мере того как вычислительные мощности увеличиваются, позволяя решать все более сложные задачи, важность использования эффективных алгоритмов также возрастает.

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

Упражнения

1.25 Предположите, что взвешенное быстрое объединение используется для обработки в 10 раз большего количества соединений на новом компьютере, который работает в 10 раз быстрее старого. На сколько больше времени потребуется для выполнения новой задачи на новом компьютере по сравнению с выполнением старой задачи на старом компьютере?

1.26 Выполните упражнение 1.25 для случая использования алгоритма, для которого требуется выполнение Л инструкций.