![]() Материал был изложен не в рамках одной лабораторной работы, а в цикле из семи лабораторных:
Подобное изложение должно поспособствовать более качественному усвоению материала. Каждая лабораторная работа включает в себя цель, теоретическую часть с подробным описанием идей и примерами, контрольные вопросы и список практических заданий. В седьмой лабораторной работе по окончанию изучения курса «длинной» арифметики предложены темы для исследований. Схема сдачи лабораторной работы выглядит следующим образом:
Все примеры и процедуры, реализующие алгоритмы «длинной» арифметики в лабораторных работах написаны на С++. Обзор лабораторной работы №1. В данной лабораторной работе происходит ознакомление с «длинной» арифметикой, необходимостью ее применения, и рассмотрены алгоритмы сложения, вычитания и сравнения двух длинных чисел. Первоначально предполагается изучить метод представления длинных чисел, и только потом перейти непосредственно к их сложению, вычитанию и сравнению. В лабораторной работе приведены примеры для наглядной иллюстрации изложенных идей. Алгоритм сложения двух длинных чисел имитирует привычное сложение «в столбик». Этот алгоритм очень прост и эффективен. В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется программно реализовать алгоритмы сложения, вычитания и сравнения «длинных» чисел. Язык реализации может быть произвольным. Обзор лабораторной работы №2. В данной лабораторной работе происходит ознакомление с алгоритмами умножения длинных чисел. В начале излагается идея умножения двух длинных чисел «в столбик», описывается сложность и недостатки приведенного алгоритма. Далее описывается более эффективный метод, известный как метод Карацубы, его преимущество над предыдущим. Следующим этапом в этой лабораторной является алгоритм умножения длинного числа на цифру, его описание и описание получаемого результата. В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется программно реализовать алгоритмы умножения двух длинных чисел и умножение длинного числа на цифру. Язык реализации может быть произвольным Обзор лабораторной работы №3. В данной лабораторной работе происходит ознакомление с алгоритмами, возведения в квадрат длинных чисел. В начале излагается общая идея возведения в степень длинных чисел, затем метод возведения в квадрат умножением, его сложность. Следующим этапом является метод Карацубы: приводятся его преимущества и недостатки. Далее предлагается изучить метод «треугольника» возведения в квадрат, являющийся модификацией метода Карацубы. В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется программно реализовать алгоритм возведения длинного числа в квадрат методом «треугольника». Язык реализации может быть произвольным. Обзор лабораторной работы №4. В данной лабораторной работе происходит ознакомление с алгоритмами вычисления остатка длинных чисел. Первоначально приводятся общие сведения и необходимость применения данной процедуры. Далее предлагается изучить алгоритм деления «лесенкой», а именно: деление длинного числа на короткое и деление двух длинных чисел с вычислением остатка. Также здесь приведен недостаток процедуры, отвечающей за «длинное» деление ее сложность и область применения. В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется реализовать процедуры деления длинного числа на короткое и деления двух длинных чисел с вычислением остатка. Язык реализации может быть произвольным. Обзор лабораторной работы №5. В данной лабораторной работе происходит ознакомление с алгоритмами модулярного умножения. Первоначально изложены основные идеи и процедуры умножения и возведения в квадрат длинного числа по модулю. Затем предлагается изучить метод Монтгомери. Здесь приводится его сложность, преимущества и недостатки, а также процедуры умножения и возведения в квадрат по модулю, но уже с использованием операции Монтгомери. В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется реализовать процедуры умножения длинного числа по модулю, возведения в квадрат по модулю и умножения Монтгомери длинных чисел. Язык реализации может быть произвольным. Обзор лабораторной работы №6. В данной лабораторной работе происходит ознакомление с алгоритмами возведения длинного числа в степень. Первоначально предлагается изучить идею бинарного алгоритма возведения в степень, его преимущества над алгоритм возведения в степень В путем В-1 умножения. Далее этот же метод, но с использованием операции Монтгомери. Затем в лабораторной работе приводится обобщение бинарного алгоритма, а именно: k-арный алгоритм возведения в степень и k-арный алгоритм возведения в степень по модулю. Здесь приведены сложности этих алгоритмов, а также их преимущества и недостатки. Следующим этапом является вычисление степени с помощью заранее заготовленной таблицы: табличный алгоритм возведения в степень по модулю, к-арный табличный алгоритм возведения в степень и k-арный табличный алгоритм возведения в степень по модулю. Также как и для предыдущих примеров приведены сложности этих алгоритмов. В конце теоретической части предлагается изучить алгоритм одновременного вычисления произведения степеней. В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется реализовать процедуры бинарного алгоритма возведения в степень, бинарного алгоритма возведения в степень с использованием операции Монтгомери, k-арного алгоритма возведения в степень и бинарного алгоритма одновременного вычисления произведения степеней. Язык реализации может быть произвольным. Обзор лабораторной работы №7. В данной лабораторной работе происходит ознакомление с алгоритмами вычисления обратного по модулю. Первоначально приводятся общие сведения и необходимость применения данной процедуры. Далее предлагается изучить расширенный алгоритм Евклида, а также алгоритмы вычисления обратного С = A-1(mod В) и z = -a-1 (mod 2m). В конце лабораторной работы требуется ответить на контрольные вопросы и выполнить практические задания. Контрольные вопросы подразумевают знание материала изложенного в этой лабораторной работе. В качестве практических заданий требуется реализовать процедуры расширенного алгоритма Евклида, вычисления обратного С = A-1(mod В), вычисления z = -a-1 (mod 2m). Язык реализации может быть произвольным. | |
Просмотров: 420 | Добавлено: 10.03.2015, 04:20 |