Computer Algebra

Code:

M342

Acronym:

M342

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2014/2015 - 1S

Active?	Yes
Web Page:	https://moodle.up.pt/course/view.php?id=2311
Responsible unit:	Department of Mathematics
Course/CS Responsible:	Bachelor in Mathematics

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:M	41	Plano de estudos a partir de 2009	3	-	7,5	-	202,5

Teaching language

Portuguese

Objectives

Introduction to some computational aspects of algebra in particular elementary operations of some number systems and polynomial rings in one or various variables. During the semester the students will learn some efficient algorithm to multipy and/or divide in these algebraic structures. The algorithms of Schönhage-Strassen, Karatsuba and Buchberger will be discussed.

Learning outcomes and competences

The expected outcome is that the student learns about some computational aspects of algebra.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

M141 Álgebra Linear I

M142 Álgebra Linear II

CC101 Introdução à Programação

M241 Álgebra I

 

Program

1. Short revision of integer arithmetic
1.1 Order relation
1.2 Revison of the extended Euclidean algorithm for Euclidean domains.
1.3 Applications (modular arithmetic, linear Diofantian equations)

2. Polynomial arithmetic in one variable
2.1. Revision of the properties of the ring of polynomials in one variable  (power series, irreducible polynomials, Eisenstein)
2.3. Karatsuba's algorithm
2.4. Application to integer multiplication (Schönhage-Strassen algorithm)
2.5. Euclidean algorithm for polynomials
2.6. Application to the theory of error correcting codes (cyclic codes, RSA, Sudan's algorithm)

3. Polynomial arithmetic in several variables
3.1. Power series in several variables
3.2. Short introduction to algebraic geometry
3.3. Monomial order
3.4. Division algorithm for polynomials in several variables
3.5. Dickson's lemma
3.6. S-polynomials
3.7. Gröbner basis and Buchberger's algorithm
3.8. Applications

Mandatory literature

000040121. ISBN: 0-387-94680-2

Complementary Bibliography

000041470. ISBN: 978-0-387-97971-7 hbk

Teaching methods and learning activities

The theoretical content will be lectured in two classes of 1,5 hours per week and will be worked out with the students in 1,5+0,5 hours of example classes.

keywords

Physical sciences > Mathematics > Computational mathematics > Computing systems
Physical sciences > Mathematics > Algorithms

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation	Weight (%)
Teste	100,00
Total:	100,00

Calculation formula of final grade

Two quizzes will be held during the semester.
The final grade is the average mean of the grades  of the two tests.

There is no final exam.

Classification improvement

Students who intend to imrpove their final grade can take an exam in the epoca do recurso.

There is no possibility to improve only the grade of a single test.