Álgebra Computacional

Código:

M342

Sigla:

M342

Áreas Científicas
Classificação	Área Científica
OFICIAL	Matemática

Ocorrência: 2013/2014 - 1S

Ativa?	Sim
Página Web:	https://moodle.up.pt/course/view.php?id=519
Unidade Responsável:	Departamento de Matemática
Curso/CE Responsável:	Licenciatura em Matemática

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
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

Língua de trabalho

Português

Objetivos

Introdução a alguns aspetos computacionais de álgebra nomeadamente nas operações elementares de alguns sistemas de números e de anéis de polinómios a uma ou a várias indeterminadas. Durante o semestre os alunos vão aprender alguns algoritmos eficientes para multiplicar e/ou dividir nesses estruturas algébricos. Os algoritmos de Schönhage-Strassen, de Karatsuba  e de Buchberger vão ser tratados.

Resultados de aprendizagem e competências

É  esperado que o aluno aprende alguns aspectos computacionais de álgebra.

 

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

M141 Álgebra Linear I

M142 Álgebra Linear II

CC101 Introdução à Programação

M241 Álgebra I

 

Programa

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, corpo dos números racionais, matrizes
3.8. Aplicações

Bibliografia Obrigatória

000040121. ISBN: 0-387-94680-2 (Matéria sobre as bases de Gröbner e geometria algébrica)
000053864. ISBN: 0-521-64176-4 (Important para a matéria do início do semestre)

Bibliografia Complementar

000041470. ISBN: 978-0-387-97971-7 hbk (introdução alternativa às bases de Gröbner)

Métodos de ensino e atividades de aprendizagem

Em três horas semanais será exposto a teoria que é trabalhado em 1,5+0,5 horas de aulas práticas. Os alunos deverão entregar dois trabalhos de programação em Python e deverão escrever dois testes.

Palavras Chave

Ciências Físicas > Matemática > Matemática computacional > Sistemas computacionais
Ciências Físicas > Matemática > Algoritmos

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Teste	85,00
Trabalho escrito	15,00
Total:	100,00

Fórmula de cálculo da classificação final

Durante o semestre realizar-se-ão dois testes e os alunos deverão entregar dois trabalhos.

A cotação dos testes e dos trabalhos é

1º trabalho = 1 valor

2º trabalho = 2 valores

1º teste = 8 valores

2º teste = 9 valores

A classificação final é a soma das classificações obtidos nos dois testes e nos dois trabalhos.

Provas e trabalhos especiais

Entrega do 1º trabalho: 7.10.2013 (cotação: 1 valor)

Realização do 1º teste: 4.11.2013 (cotação: 8 valores)

Entrega do 2º trabalho: 25.11.2013 (cotação: 2 valores)

Realização do 2º teste:: 16.12.2013 (cotação: 9 valores)

Melhoria de classificação

O alunos que pretendem melhorar a classificação final podem fazer um exame na época do recurso.

Não existe a possibilidade de melhorar só a classificação duma parte da avaliação distribuída (i.e. trabalhos e teste).