Упражнения

Раздел 1.2

1. а. Предполагая существование алгоритма возводящего целое число в степень многократным умножением, используйте обозначение О (определение 1.2.1), чтобы оценить время вычисления функции

b. Если алгоритм F вычисляет умножая сначала 2 на 3, затем результат на 4, затем новый результат на 5 и так до , то чему равно время вычисления функции

(Указание. В обеих частях упражнения воспользуйтесь тем, что число цифр в произведении двух чисел либо равно сумме числа цифр в сомножителях, либо на 1 больше этой суммы.)

2. Для суммы первых кубов имеет место формула

Пользуясь О-обозначениями, оцените в терминах простой функции от

a. число базисных (битовых) операций, необходимых для выполнения вычислений в левой части этого равенства;

b. число базисных (битовых) операций, необходимых для выполнения вычислений в правой части этого равенства.

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

где представляет число простых чисел, меньших, чем для больших частное аппроксимирует

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

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

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

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

Упражнения по программированию

Раздел 1.2

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

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

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

2. Установив формат звеньев, напишите процедуры, которые будут (а) инициализировать доступное пространство, т.е. образовывать односвязный список (связанный через поле ссылки) и возвращать указатель, указывающий на первое звено в этом списке (для нашего проекта достаточно 300 звеньев); брать звено из доступного пространства для использования в вычислениях; возвращать звено

в доступное пространство, если оно более не нужно; определять длину, т.е. число звеньев, любого списка.

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

4. Покажите, что если — два длинных целых числа, таких, что , то [Указание. Покажите, что так что и для определения каждого - требуется не более умножений.]

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

6. Пусть — полином от v переменных с целыми коэффициентами; через обозначим его степень по Ниже мы будем обозначать через полином при любом значении v. Индукцией по v определим две нормы следующим образом: если , то поскольку — целое число. положим (наибольший коэффициент) и (сумма коэффициентов).

a. Покажите, что .

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

b. вычислять их сумму за время

с. вычислять их произведение за время

Литература

Flanders Н. Scientific Pascal. Reston, VA, 1984.

Forsythe G.E., Malcolm M.A., Moler C.B. Computer methods for mathematical computations. Prence-Hall, Englewood Cliffs, NJ, 1977.

Horowitz E., Sahni S. Fundamentals of data structures. Computer Science Press, Rockville, MD, 1976.

Knuth D. The art of computer programming. Vol. 2: Seminumerical algorithms. Addison-Wesley, Reading, MA, 1981. [Имеется перевод предыдущего издания: Кнут Д. Искусство программирования для ЭВМ. Т. 2. - М.: Мир. 1977.]

Pavelle R., Rothstein М., Fitch J. Computer algebra. Scientific American. 136-152, December 1981.

Petricle S.R. (ed.) Proceedings of the 2nd symposium on symbolic and algebraic manipulation. Association for Computing Machinery, New York, NY, 1971.