Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 16
Текст из файла (страница 16)
В этой области ведутся активные исследования, и вероятностные алгоритмы удалось с успехомприменить во многих областях48 .Упражнение 1.21.С помощью процедуры smallest-divisor найдите наименьший делитель следующих чисел:199, 1999, 19999.Упражнение 1.22.Бо́льшая часть реализаций Лиспа содержат элементарную процедуру runtime, которая возвращает целое число, показывающее, как долго работала система (например, в миллисекундах).Следующая процедура timed-prime-test, будучи вызвана с целым числом n, печатает n и проверяет, простое ли оно.
Если n простое, процедура печатает три звездочки и количество времени,затраченное на проверку.(define (timed-prime-test n)(newline)(display n)(start-prime-test n (runtime)))(define (start-prime-test n start-time)(if (prime? n)(report-prime (- (runtime) start-time))))(define (report-prime elapsed-time)(display " *** ")(display elapsed-time))Используя эту процедуру, напишите процедуру search-for-primes, которая проверяет на простоту все нечетные числа в заданном диапазоне.
С помощью этой процедуры найдите наименьшиетри простых числа после 1000; после 10 000; после 100 000; после 1 000 000. Посмотрите, скольковремени затрачивается на каждое простое число. Поскольку алгоритм проверки имеет порядок√роста Θ( n), Вам следовало бы ожидать, что проверка на простоту чисел, близких к 10 000,48 Одно из наиболее впечатляющих применений вероятностные алгоритмы получили в области криптографии.Хотя в настоящее время вычислительных ресурсов недостаточно, чтобы разложить на множители произвольное число из 200 цифр, с помощью теста Ферма проверить, является ли оно простым, можно за несколькосекунд. Этот факт служит основой предложенного в Rivest, Shamir, and Adleman 1977 метода построенияшифров, которые «невозможно» взломать.
Полученный алгоритм RSA (RSA algorithm) стал широко используемым методом повышения секретности электронных средств связи. В результате этого и других связанныхсобытий исследование простых чисел, которое раньше считалось образцом «чистой» математики, изучаемымисключительно ради самого себя, теперь получило важные практические приложения в таких областях, каккриптография, электронная передача денежных сумм и хранение информации.68Глава 1. Построение абстракций с помощью процедур√занимает в 10 раз больше времени, чем для чисел, близких к 1000.
Подтверждают ли это Ваши√замеры времени? Хорошо ли поддерживают предсказание n данные для 100 000 и 1 000 000?Совместим ли Ваш результат с предположением, что программы на Вашей машине затрачиваютна выполнение задач время, пропорциональное числу шагов?Упражнение 1.23.Процедура smallest-divisor в начале этого раздела проводит множество лишних проверок:после того, как она проверяет, делится ли число на 2, нет никакого смысла проверять делимостьна другие четные числа. Таким образом, вместо последовательности 2, 3, 4, 5, 6 . . .
, используемой для test-divisor, было бы лучше использовать 2, 3, 5, 7, 9 . . . . Чтобы реализовать такоеулучшение, напишите процедуру next, которая имеет результатом 3, если получает 2 как аргумент, а иначе возвращает свой аргумент плюс 2. Используйте (next test-divisor) вместо (+test-divisor 1) в smallest-divisor. Используя процедуру timed-prime-test с модифицированной версией smallest-divisor, запустите тест для каждого из 12 простых чисел,найденных в упражнении 1.22.
Поскольку эта модификация снижает количество шагов проверкивдвое, Вы должны ожидать двукратного ускорения проверки. Подтверждаются ли эти ожидания?Если нет, то каково наблюдаемое соотношение скоростей двух алгоритмов, и как Вы объяснитето, что оно отличается от 2?Упражнение 1.24.Модифицируйте процедуру timed-prime-test из упражнения 1.22 так, чтобы она использовалаfast-prime? (метод Ферма) и проверьте каждое из 12 простых чисел, найденных в этом упражнении. Исходя из того, что у теста Ферма порядок роста Θ(log n), то какого соотношения времениВы бы ожидали между проверкой на простоту поблизости от 1 000 000 и поблизости от 1000?Подтверждают ли это Ваши данные? Можете ли Вы объяснить наблюдаемое несоответствие, еслионо есть?Упражнение 1.25.Лиза П.
Хакер жалуется, что при написании expmod мы делаем много лишней работы. В концеконцов, говорит она, раз мы уже знаем, как вычислять степени, можно просто написать(define (expmod base exp m)(remainder (fast-expt base exp) m))Права ли она? Стала бы эта процедура столь же хорошо работать при проверке простых чисел?Объясните.Упражнение 1.26.У Хьюго Дума большие трудности в упражнении 1.24. Процедура fast-prime? у него работаетмедленнее, чем prime?. Хьюго просит помощи у своей знакомой Евы Лу Атор. Вместе изучаякод Хьюго, они обнаруживают, что тот переписал процедуру expmod с явным использованиемумножения вместо того, чтобы вызывать square:(define (expmod base exp m)(cond ((= exp 0) 1)((even? exp)(remainder (* (expmod base (/ exp 2) m)(expmod base (/ exp 2) m))m))1.3.
Формулирование абстракций с помощью процедур высших порядков69(else(remainder (* base (expmod base (- exp 1) m))m))))Хьюго говорит: «Я не вижу здесь никакой разницы». «Зато я вижу, — отвечает Ева. — Переписав процедуру таким образом, ты превратил процесс порядка Θ(log n) в процесс порядка Θ(n)».Объясните.Упражнение 1.27.Покажите, что числа Кармайкла, перечисленные в сноске 47, действительно «обманывают» тестФерма: напишите процедуру, которая берет целое число n и проверяет, правда ли an равняется aпо модулю n для всех a < n, и проверьте эту процедуру на этих числах Кармайкла.Упражнение 1.28.Один из вариантов теста Ферма, который невозможно обмануть, называется тест Миллера–Рабина (Miller-Rabin test) (Miller 1976; Rabin 1980).
Он основан наальтернативной формулировкеМалой теоремы Ферма, которая состоит в том, что если n — простое число, а a — произвольноеположительное целое число, меньшее n, то a в n − 1-ой степени равняется 1 по модулю n. Проверяя простоту числа n методом Миллера–Рабина, мы берем случайное число a < n и возводимего в (n − 1)-ю степень по модулю n с помощью процедуры expmod. Однако когда в процедуре expmod мы проводим возведение в квадрат, мы проверяем, не нашли ли мы «нетривиальныйквадратный корень из 1 по модулю n», то есть число, не равное 1 или n − 1, квадрат которогопо модулю n равен 1. Можно доказать, что если такой нетривиальный квадратный корень из 1существует, то n не простое число. Можно, кроме того, доказать, что если n — нечетное число, неявляющееся простым, то по крайней мере для половины чисел a < n вычисление an−1 с помощьютакой процедуры обнаружит нетривиальный квадратный корень из 1 по модулю n (вот почемутест Миллера–Рабина невозможно обмануть).
Модифицируйте процедуру expmod так, чтобы онасигнализировала обнаружение нетривиального квадратного корня из 1, и используйте ее для реализации теста Миллера–Рабина с помощью процедуры, аналогичной fermat-test. Проверьтесвою процедуру на нескольких известных Вам простых и составных числах. Подсказка: удобныйспособ заставить expmod подавать особый сигнал — заставить ее возвращать 0.1.3. Формулирование абстракций с помощью процедурвысших порядковМы видели, что процедуры, в сущности, являются абстракциями, которые описывают составные операции над числами безотносительно к конкретным числам.
Например,когда мы определяем(define (cube x) (* x x x))мы говорим не о кубе какого-то конкретного числа, а о способе получить куб любогочисла. Разумеется, мы могли бы обойтись без определения этой процедуры, каждый разписать выражения вроде(* 3 3 3)(* x x x)(* y y y)70Глава 1. Построение абстракций с помощью процедури никогда явно не упоминать понятие куба. Это поставило бы нас перед серьезнымзатруднением и заставило бы работать только в терминах тех операций, которые оказались примитивами языка (в данном случае, в терминах умножения), а не в терминахопераций более высокого уровня. Наши программы были бы способны вычислять кубы,однако в нашем языке не было бы возможности выразить идею возведения в куб.
Однаиз тех вещей, которых мы должны требовать от мощного языка программирования — этовозможность строить абстракции путем присвоения имен общим схемам, а затем прямоработать с этими абстракциями. Процедуры дают нам такую возможность. Вот почемувсе языки программирования, кроме самых примитивных, обладают механизмами определения процедур.Но даже при обработке численных данных наши возможности создавать абстракции окажутся сильно ограниченными, если мы сможем определять только процедуры,параметры которых должны быть числами. Часто одна и та же схема программы используется с различными процедурами. Для того чтобы выразить эти схемы как понятия,нам нужно строить процедуры, которые принимают другие процедуры как аргументылибо возвращают их как значения.
Процедура, манипулирующая другими процедурами, называется процедурой высшего порядка (higher-order procedure). В этом разделепоказывается, как процедуры высших порядков могут служить в качестве мощного механизма абстракции, резко повышая выразительную силу нашего языка.1.3.1. Процедуры в качестве аргументовРассмотрим следующие три процедуры. Первая из них вычисляет сумму целых чиселот a до b:(define (sum-integers a b)(if (> a b)0(+ a (sum-integers (+ a 1) b))))Вторая вычисляет сумму кубов целых чисел в заданном диапазоне:(define (sum-cubes a b)(if (> a b)0(+ (cube a) (sum-cubes (+ a 1) b))))Третья вычисляет сумму последовательности термов в ряде111+++ ...1 · 3 5 · 7 9 · 11который (очень медленно) сходится к π/849 .111π= 1 − + − + .
. ., мы обя4357заны Лейбницу. В разделе 3.5.3 мы увидим, как использовать его как основу для некоторых изощренныхвычислительных трюков.49Этим рядом, который обычно записывают в эквивалентной форме1.3. Формулирование абстракций с помощью процедур высших порядков71(define (pi-sum a b)(if (> a b)0(+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))Ясно, что за этими процедурами стоит одна общая схема. Большей частью они идентичны и различаются только именем процедуры, функцией, которая вычисляет терм,подлежащий добавлению, и функцией, вычисляющей следующее значение a. Все этипроцедуры можно породить, заполнив дырки в одном шаблоне:(define (hимяi a b)(if (> a b)0(+ (hтермi a)(hимяi (hследующийi a) b))))Присутствие такого общего шаблона является веским доводом в пользу того, чтоздесь скрыта полезная абстракция, которую только надо вытащить на поверхность.
Действительно, математики давно выделили абстракцию суммирования последовательности (summation of a series) и изобрели «сигма-запись», напримерbXf (n) = f (a) + . . . + f (b)n=aчтобы выразить это понятие. Сила сигма-записи состоит в том, что она позволяет математикам работать с самим понятием суммы, а не просто с конкретными суммами —например, формулировать общие утверждения о суммах, независимые от конкретныхсуммируемых последовательностей.Подобным образом, мы как проектировщики программ хотели бы, чтобы наш языкбыл достаточно мощным и позволял написать процедуру, которая выражала бы самопонятие суммы, а не только процедуры, вычисляющие конкретные суммы. В нашемпроцедурном языке мы можем без труда это сделать, взяв приведенный выше шаблон ипреобразовав «дырки» в формальные параметры:(define (sum term a next b)(if (> a b)0(+ (term a)(sum term (next a) next b))))Заметьте, что sum принимает в качестве аргументов как нижнюю и верхнюю границы a иb, так и процедуры term и next.
Sum можно использовать так, как мы использовали былюбую другую процедуру. Например, с ее помощью (вместе с процедурой inc, котораяувеличивает свой аргумент на 1), мы можем определить sum-cubes:(define (inc n) (+ n 1))(define (sum-cubes a b)(sum cube a inc b))Глава 1. Построение абстракций с помощью процедур72Воспользовавшись этим определением, мы можем вычислить сумму кубов чисел от 1 до10:(sum-cubes 1 10)3025С помощью процедуры идентичности (которая просто возвращает свой аргумент) длявычисления терма, мы можем определить sum-integers через sum:(define (identity x) x)(define (sum-integers a b)(sum identity a inc b))Теперь можно сложить целые числа от 1 до 10:(sum-integers 1 10)55Таким же образом определяется pi-sum50 :(define (pi-sum a b)(define (pi-term x)(/ 1.0 (* x (+ x 2))))(define (pi-next x)(+ x 4))(sum pi-term a pi-next b))С помощью этих процедур мы можем вычислить приближение к π:(* 8 (pi-sum 1 1000))3.139592655589783Теперь, когда у нас есть sum, ее можно использовать в качестве строительного блокапри формулировании других понятий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
