Computer Algebra

Code:

M342

Acronym:

M342

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2013/2014 - 1S

Active?	Yes
Web Page:	https://moodle.up.pt/course/view.php?id=519
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:CC	0	Plano de estudos de 2008 até 2013/14	3	-	7,5	-	202,5
L:M	33	Plano de estudos a partir de 2009	3	-	7,5	-	202,5
M:CC	2	PE do Mestrado em Ciência de Computadores	1	-	7,5	-	202,5
			2

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. Aritmética de inteiros
1.1. Teoria de Conjuntos (axiomas, relações de ordem, relações de equivalência)
1.2. Números (inteiros, racionais, reais, complexos e outros)
1.3. Algoritmo de divisão (domínios Euclideanos)
1.4. Algoritmo de Euclides para inteiros
1.5. Aplicações (aritmética modular, equações diofantina linear)

2. Aritmética de polinómios a uma indeterminada
2.1. Domínios integrais (corpo de frações, irreducibilidade, ideais primos)
2.2. Anéis de polinómios (séries de potências, polinómios irredutiveis, Eisenstein)
2.3. Algoritmo de Karatsuba
2.4. Aplicação à multiplicação de inteiros (Algoritmo de Schönhage-Strassen)
2.5. Algoritmo de Euclides para polinómios
2.6. Aplicação à teoria de códigos corretores de erros (códigos cíclicos, RSA, algoritmo de Sudan)

3. Aritmética de polinómios a várias indeterminadas
3.1. Séries de potências a várias indeterminadas
3.2. Breve introdução à geometria algébrica
3.3. Ordem monomial
3.4. Algoritmo de divisão para polinómios a várias indeterminadas
3.5. O Lema de Dickson
3.6. Polinómios S
3.7. Bases de Gröbner e Algoritmo de Buchberger
3.8. Aplicações

Mandatory literature

000040121. ISBN: 0-387-94680-2
000053864. ISBN: 0-521-64176-4

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. Furthermore should the students hand in two python programming homework-assignment and shall write two testes.

keywords

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

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation	Weight (%)
Teste	85,00
Trabalho escrito	15,00
Total:	100,00

Calculation formula of final grade

Two quizzes will be held during the semester. Furthermore the students will have  to hand-in two homework assignments  during the semester.

Each of the items counts as follows:

1º homework assignment = 1 value

2º homework assignment = 2 values

1º quiz = 8 values

2º quiz = 9 values

The final grade is the sum of the grades  of the two tests and the two homework assignments.

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 part of the final grade (tests or hand-in assignments).