Computational Algebra
Code
10986
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
3.0
Teacher in charge
António José Mesquita da Cunha Machado Malheiro
Weekly hours
3
Total hours
60
Teaching language
Português
Objectives
This course is an introduction for some basic concepts of computational algebra and its applications. It is intended that students be able to:
solve elementary problems occurring in computer algebra, preferentially with the help of a computer algebra system;
understand major algorithms of computational algebra such as the euclidean algorithm, some modular algorithms, and the Karatsuba algorithm for multiplication;
understand some algorithms of experimental mathematics;
understand some algorithms used in for automated theorem provers;
ackowledge some tools of experimental mathematics and their use in modelling and discovery of mathematical results.
Prerequisites
Elementary math skills to a level of a student in a degree in science or engineering.
Subject matter
1. Introduction. Computer algebra systems.
2. Applications of the Euclidean algorithm.
3. Modular algorithms and interpolation.
4. Fast multiplication: Karatsuba''''''''s algorithm.
5. Factorization of integers and cryptography. RSA system.
6. Rewriting systems: Knuth-Bendix procedure.
7. Algorithms involving finitely presented groups.
Bibliography
1. J. Gathen e J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003
2. K.O. Geddes, S.R. Czapor e G. Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, 1992
3. C.C. Sims, Computation with finitely presented groups, Cambridge University Press, 1994
4. H. Cohen, A course in computational algebraic number theory, Springer-Verlag, 1993
Teaching method
Theoretical classes: it is taught the fundamental concepts, illustrated by numerous representative examples .
Practical lab (computer) classes where are solved exercises with the application of those concepts.
Will be made available lists of exercises, which students must solve as many as possible, before and after practical classes (individually) and in practical classes with the support of a teacher in order to overcome the remaining difficulties.
Evaluation method
ASSESSMENT REGULATION
The assessment regulation for the course Computer Algebra follows the rules established by the assessment regulation of FCTUNL, available at (http://www.fct.unl.pt/sites/default/files/Reg_Aval.pdf). Students are advised to consult it.
The evaluation will have two components:
A) written theoretical-practical evaluation, corresponding to 30% of the final grade;
B) laboratory evaluation or project, corresponding to 70% of the final grade.
The written evaluation (A) will be conducted through a single test, of two hours in the last week of classes. It is required a minimum score of 6 values in this component.
Laboratory evaluation or project consists of performing computational assignments with a regular weekly base (between 8 to 12 assignments), which correspond to 70% of the final grade. It is required a minimum score of 8 points in the laboratory evaluation or project. This is also the requirement to obtain the frequency to the discipline.
Each computational assignment consists of a small task which will be discussed with the teacher. This discussion will be done on a regular basis throughout the semester.
The final classification is obtained by the formula
TC * 0.7 + TF * 0.3
and each of the components, computational assignments (TC) and test (TF), are rated from 0 to 20, with rounding to one decimal place. The value of TC is obtained by arithmetic average of the grades of the computational assignments.
In case the student does not get approved or if he want''''s to improve its grade (requires prior registration), he can perform an exam whose classification replaces the classification of the test in the previous formula.
If the final grade is higher than 16, the student may opt to keep the final grade of 16 or do a complementary exam (oral and/or theoretico-practical project).