Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013), страница 9

Аналогично массивы передаются с помощью передачи указателя, а не целого массива, и изменения отдельных злементов массива видимы для вызывающей процедуры. Инструкция гезвгп немедленно возвращает управление в точку вызова в вызываюшей процедуре. В большинстве случаев инструкция ге1нгп получает значение для возврата вызываюшей процедуре. Наш псевдокод отличается от многих языков программирования тем, что мы допускаем возврат нескольких значений одной инструкцией гезнгп. Булевы операторы "и" и "или" вычисляются сокращенно (яЬоп с(гсшбпй).

Это означает, что при вычислении выражения "х и у" сначала вычисляется значение выражения х. Если это значение ложно (Ельке), то все выражение не может быть истинным, и значение выражения у не вычисляется. Если же выражение х истинно (ткыв), то для определения значения всего выражения необходимо вычислить выражение у. Аналогично в выражении "х или у" величина у вычисляется только в том случае, если выражение х ложно.

СокраШенные операторы позволяют составлять такие логические выражения, как "х ф мп. и х.1' = у"„не беспокоясь о том, что произойдет при попытке вычислить выражение х.1, когда х равно хц., Ключевое слово еггог указывает на ошибку, произошедшую из-за неверных условий при вызове процедуры. За обработку ошибки отвечает вызывающая процедура„а потому мы не указываем, какие действия должны быть предприняты. Упражнения 2.1.1 Используя рис.2.2 в качестве образца, проиллюстрируйте работу процедуры 1ызнктюн-8окт по сортировке массива А = (31,41,59,26,41,58). Гзаеа 2.

Приступаем к изучению 21.г Перепишите процедуру!нзпкт~ом-Яокт для сортировки в невозрастающем по- рядке вместо неубывающего. г.1.З Рассмотрим задачу поиска. Вход. Последовательность из и чисел А = (аы аз,..., а„) и значение ю. Выход. Индекс з, такой, что о = А[з), или специальное значение ыпа если и в А отсутствует. Составьте псевдокод линейного поиска, при работе которого выполняется сканирование последовательности в поисках значения о. Докажите корректность алгоритма с помощью инварианта цикла. Убедитесь, что выбранный инвариант цикла удовлетворяет трем необходимым условиям.

2.1.4 Рассмотрим задачу сложения двух и-битовых двоичных целых чисел, хранящихся в и-элементных массивах А и В. Сумму этих двух чисел необходимо занести в двоичной форме в (и+ 1)-элементный массив С. Приведите строгую формулировку задачи и составьте псевдокод для сложения этих двух чисел. 2.2. Анализ влгорнтмов Анализ заключается в том, чтобы предсказать требуемые для его выполнения ресурсы.

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

Строго говоря, в модели КАМ следует точно определить набор инструкций и время их выполнения, однако это утомительно и мало способствует пониманию принципов разработки и анализа алгоритмов. С другой стороны, нужно соблюдать осторожность, чтобы не исказить модель КАМ. Например, что будет, если в ВАМ встроена команда сортировки? В этом случае сортировку можно выпол- вб Часть я Основы нять с помощью всего одной команды процессора. Такая модель нереалистична, поскольку настоящие компьютеры не имеют подобных встроенных команд, а мы ориентируемся именно на их устройство.

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

Также предполагается, что существует верхний предел размера слова данных. Например, если обрабатываются входные данные с максимальным значением п, обычно предполагается, что целые числа представлены с1яп битами для некоторой константы с > 1. Требование с > 1 обусловлено тем, что в каждом слове должно храниться одно из и значений, что позволит индексировать входные элементы. Кроме того, предполагается, что с — это конечная константа, поэтому объем слова ие может увеличиваться до бесконечности. (Если бы это было возможно, в одном слове можно было бы хранить данные огромных объемов и осуществлять над ними операции в рамках одной элементарной команды, что нереально.) В реальных компьютерах содержатся команды, не упомянутые выше, которые представляют "серую область" модели ВАМ.

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

Сдвиг битов на lс позиций влево эквивалентен его умножению на 2". Таким образом, на этих компьютерах 2" можно вычислить с помощью одной элементарной инструкции, сдвинув целое число 1 на lс позиций влево; при этом 14 не должно превышать количество битов компьютерного слова. Мы попытаемся избегать таких "серых областей" модели ВАМ, однако вычисление 2" будет рассматриваться как элементарная операция, если й — достаточно малое целое положительное число.

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

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

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