Álgebra Computacional

Código:

M342

Sigla:

M342

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

Ocorrência: 2015/2016 - 1S

Ativa?	Sim
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:M	33	Plano de estudos a partir de 2009	3	-	7,5	-	202,5

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Introdução de conceitos básicos da Álgebra Computacional, com algumas aplicações à Geometria (referência às bases de Gröbner), à Criptografia (sistema RSA) e à Integração Simbólica.

Resultados de aprendizagem e competências

Espera-se que o estudante apreenda alguns conceitos básicos da Álgebra Computacional.

Modo de trabalho

Presencial

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

Espera-se que os estudantes tenham bons conhecimentos em pelo menos 4 dos seguintes tópicos: Álgebra Linear, Álgebra, Cálculo, noções básicas de programação e noções básicas de análise/complexidade de algoritmos.

Programa

[0.] Introdução/motivação
  Uma introdução ao GAP
   Generalidades sobre o GAP
   Instruções básicas
   Funções GAP
   Exemplos

[1.] Motivação
   A cifra RSA (rudimentos)
   Exemplos usando o GAP

I *Algoritmos aritméticos básicos*

[2.] Algoritmos Fundamentais
   Inteiros
   Polinómios
   Multiplicação
   Divisão com resto

[3.] Algoritmo de Euclides
   Domínios euclideanos
   O algoritmo estendido de Euclides
   Custo computacional do algoritmo estendido de Euclides
   (Não) unicidade do máximo divisor comum

[4.] Aplicações do algoritmo de Euclides
   Aritmética Modular
   Inversos modulares
   Exponenciação modular
   Equações diofantinas lineares
   Frações contínuas (e aproximação diofantina)

[5.] Avaliação e interpolação
   Mudança de representação
   Avaliação e interpolação
   Teorema chinês dos restos
   Cálculo (modular) de um determinante

[6.] Multiplicação rápida
   Algoritmo de Karatsuba

II *Tópicos de Álgebra Computacional*

[7.] Integração simbólica
   Preliminares
     Decomposição em frações parciais
     A resultante
   Factorização livre de quadrados
   Álgebra diferencial
   Método de Hermite
   Algoritmo de integração de Rothstein, e Trager

[8.] Bases de Gröbner
   Motivação
      Ideais de polinómios
   Ordens monomiais
   Divisão com resto
   Bases de Gröbner
   Ideais de monómios e Teorema da base de Hilbert
   Bases de Gröbner e S-polinómios
   O algoritmo de Buchberger

[9.] Tópicos de teoria dos números computacional
   Testes de primalidade
     Pseudoprimos de Fermat
     Números de Carmichael
     Pseudoprimos fortes
   Algoritmos de factorização
     “Trial division”
     Método de Factorizaçãao de Fermat
     Método p − 1 de Pollard
   Criptografia
     Rudimentos de criptografia de chave pública
     O sistema RSA

Bibliografia Obrigatória

Gathen Joachim von zur; Modern computer algebra. ISBN: 0-521-82646-2

Métodos de ensino e atividades de aprendizagem

1. Aulas teóricas: exposição da matéria e apresentação de exemplos pelo docente.
2. Aulas teórico-práticas: resolução de exercícios pelos estudantes com apoio do docente.
3. Além das horas de apoio tutorial, haverá um horário regular de atendimento para apoio e esclarecimento de dúvidas.
4. Além da bibliografia indicada, são disponibilizados online slides com notas das aulas.

Software

GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra

Palavras Chave

Ciências Físicas > Matemática > Algoritmos
Ciências Físicas > Matemática > Álgebra

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	100,00
Total:	100,00

Obtenção de frequência

A única condição para obtenção de frequência é a inscrição na unidade curricular.

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

Ao longo do semestre (nas horas de OT, em datas a anunciar) serão realizados N conjuntos de exercícios. Aquele em que o estudante obtiver a classificação mais baixa não conta para efeito da sua classificação final: a classificação correspondente aos exercícios é a soma das classificações obtidas nos N-1 conjuntos de exercícios mais bem classificados. A classificação correspondente aos exercícios pode ser usada no exame, nos termos descritos a seguir.

O exame final consiste de duas partes, correspondendo a primeira aos conjuntos de exercícios e podendo, por solicitação do estudante, ser classificada com a classificação correspondente aos exercícios. Tem a cotação de 15 valores. A segunda parte tem a cotação de 5 valores.

Em épocas subsequentes (época de recurso, incluindo melhoria de nota, ou época especial) não é dada a possibilidade de usar a classificação correspondente aos exercícios.

Avaliação especial (TE, DA, ...)

Qualquer tipo de avaliação especial poderá revestir uma das seguintes formas: exclusivamente uma prova oral; uma prova oral e uma prova escrita, ambas com caráter eliminatório; somente uma prova escrita. A opção por uma das alternativas compete exclusivamente aos docentes responsáveis pela unidade curricular.

Melhoria de classificação

Para quem tenha obtido aprovação no ano letivo de 2014/2015, a melhoria de nota pode ser tentada exclusivamente através de exame.

Observações

Artigo 13º do Regulamento Geral para Avaliação dos Discentes de Primeiros Ciclos, de Ciclos de Estudos Integrados de Mestrado e de Segundos Ciclos da U.Porto, aprovado em 19 de Maio de 2010 (cf. http://www.fc.up.pt/fcup/documentos/documentos.php?ap=3&ano=2011): "A fraude cometida na realização de uma prova, em qualquer das suas modalidades, implica a anulação da mesma e a comunicação ao órgão estatutariamente competente para eventual processo disciplinar."