Рассмотрено и утверждено
на заседании кафедры математики, ТиМОМ
протокол от 01.01.2001 г.
зав. кафедрой _________________
Задания к зачёту по дисциплине «Компьютерная алгебра»
3 курс, направление подготовки «Математика. Прикладная математика»,
6 семестр, уч. г., ОДО
ПЕРЕЧЕНЬ СТАНДАРТНЫХ ПРОГРАММ НА ЯЗЫКЕ PASCAL:
1. Сложение огромных чисел по алгоритму удвоения разрядности (20 баллов).
Вход: два огромных двоичных числа в виде строк двоичных цифр.
Результат: строка цифр двоичного представления суммы чисел.
2. Умножение больших чисел по алгоритму удвоения разрядности (20 баллов).
Вход: два огромных двоичных числа в виде строк двоичных цифр.
Результат: строка цифр двоичного представления произведения чисел.
3. Возведение малого числа в малую степень по алгоритму быстрого возведения в степень без перевода степени в двоичную систему счисления (10 баллов).
Вход: два малых числа: х – основание и y – показатель степени.
Результат: целое число x y .
4. Линейное разложение НОД(a, b) (5 баллов).
Вход: два малых числа a и b.
Результат: запись вида a×x+b×y = НОД(a, b) .
5. Генератор простых чисел в заданном диапазоне на основе ТЕОРЕМЫ ФЕРМА (10 баллов).
Вход: два натуральных числа (границы диапазона).
Результат: простое число или 0, если простых чисел в диапазоне нет.
6. Сложение, умножение и деление двух многочленов с целыми коэффициентами (5 баллов).
Вход: два целых массива: коэффициенты двух многочленов.
Результат: четыре целых массива – коэффициенты суммы, произведения, частного и остатка.
Все программы должны иметь дружелюбный интерфейс (т. е. подсказывать пользователю какие данные вводить), “защиту от дурака” (т. е. проверять правильность введённых данных) и выдавать правильные результаты в реальном времени.
Нестандартные семестровые задачи по дисциплине “Компьютерная алгебра”
1. Написать программу, вычисляющую 
= для заданного i: 0 £ i £ 2007 (15 баллов).
2. Написать программу вычисления выражения x 200 (x – огромное целое число), использующую минимальное количество умножений (20 баллов).
3. Написать программу, вычисляющую заданное количество членов разложения функции f(x) = в ряд Маклорена (20 баллов).
4. Написать программу, вычисляющую производную заданного не очень большого порядка от функции f(x) = (20 баллов).
5. Написать программу, вычисляющую интеграл 
, где a, b, n, m – заданные не очень большие натуральные числа (30 баллов).
6. Написать программу, проверяющую, разложим ли на множители данный многочлен с целыми коэффициентами (30 баллов).
7. Написать программу, переводящую заданное огромное число из десятичной записи в двоичную (20 баллов).
8. Написать программу, обыгрывающую пользователя в крестики-нолики на поле 8´8 (20 баллов).
9. Написать программу, определяющую, делится ли заданное своими десятичными цифрами огромное натуральное число на 13 (15 баллов).
10. Написать нерекурсивную процедуру, генерирующую все подмножества множества {1, 2, … , n} (10 баллов).
11. Во множестве {1, 2, … , n} пользователь загадывает любое подмножество. Напишите программу, задающую такие вопросы пользователю (допускающие только ответы “да” и “нет”), что загаданное им подмножество будет отгадано за наименьшее число вопросов (30 баллов).
12. Написать программу, выводящую линейное разложение НОД(a1 , … , an ) нескольких (n > 2) заданных целых чисел. (10 баллов).
ТРЕБОВАНИЯ К ЗАЧЕТУ ПО КУРСУ “ КОМПЬЮТЕРНАЯ АЛГЕБРА”
I. Не иметь долгов по семестровому заданию.
II. Знать основные определения и формулировки результатов по курсу.
III. Иметь представление о следующих основных способах представления данных в ЭВМ: бит, байт, массив, структура, список. Уметь приводить примеры их использования в программах.
IV. Уметь решать следующие стандартные задачи:
1. Перевести число 100110 из десятичной системы счисления в двоичную.
2. Перевести число из двоичной системы счисления в десятичную.
3. Выполнить арифметические действия в двоичной системе:
+ – ´
10112
Упорядочить по ключу: 178, 94, 33, 152, 89, 17.
4. Вычислить по алгоритму быстрого возведения в степень x100.
5. Объяснить, как представляются целые числа и производятся сложение и умножение в 4-х разрядной ЭВМ.
6. Найти НОД(333, 144) и НОК[333, 144].
7. Найти линейное разложение НОД(33, 14).
8. Выполнить сложение огромных чисел 58+39 на 4-х разрядной ЭВМ.
9. Выполнить умножение больших чисел 58´39 на 8-ми разрядной ЭВМ.
10. Вычислить (x5–2x3+1)×(x–1)2 – (x5+2x3+1)×(x+1)2.
11. Найти НОД и НОК многочленов x3+3×x2–1, 2×x2–x (используя в вычислениях только многочлены с целыми коэффициентами).
12. Найти линейное разложение НОД(x3+x, 3x2–2x–5) (используя в вычислениях только многочлены с целыми коэффициентами).
13. Упорядочить лексикографически мономы многочлена
x+x2y–2xyz+3x2z–6xz+y –xy2z2+8y2z–9yz2+z–20.
14. Найти базис фактор-пространства F4 / L(e1 , e2 ), где e1 = (2; –2; 1; –1), e2 = (1; 1; –1; 2).
15. Найти базис Грёбнера-Ширшова для порождающих идеал в F[x, y, z] многочленов f(x, y, z) = x×y+1, g(x, y) = y×z – x, h(x, y, z) = y2 + z.
16. Раскодировать по алгоритму RSA с параметрами p = 5, q = 7, e = 11 сообщение 2, 5, 7.
17. Найти все неприводимые многочлены степени 4 над полем F2 .
18. Для заданной схемы кодирования из F24 в F27
(a1 ; a2 ; a3 ; a4 ) ® (a1 ; a2 ; a3 ; a4 ; a1+a3 ; a2+a4 ; a3+a2 )
найдите кодирующую и проверочную матрицы, минимальное расстояние и число исправляемых ошибок.
19. Декодируйте сообщение 
= (1, 1, 1, 1, 1, 1, 1) для схемы кодирования из предыдущей задачи.
К. ф.-м. н., доцент
