Planeamento

Aulas Teóricas

Elementos da teoria dos números

Existência e unicidade do máximo divisor comum. Algoritmo de Euclides.

Elementos da teoria dos números

Algoritmo de Saunderson (Euclides extendido).

Divisores de um número.

Elementos da teoria dos números

Equações diofantinas.

Elementos da teoria dos números

Congruências. Aplicação ao resto da divisão de grandes números.

Elementos da teoria dos números

Pequeno Teorema de Fermat. Aplicações.

Elementos da teoria dos números  

Teorema de Bachet.

Existência de inversos. Fórmula de Voronoy.

Elementos da teoria dos números

Teorema Chinês do Resto.

Criptografia

RSA.

Elementos da teoria dos números

Teorema Chinês do Resto, parte II

Criptografia.

RSA, parte II

TESTE

Teste 1

Somatórios

Método da perturbação da soma

Somatórios

Cálculo finito. Somatórios relativos a polinómios.

''Falling powers positivos''.

Somatórios

Cálculo finito. Somatórios relativos a sucessões exponenciais e telescópicas.

''Falling powers'' negativos e soma por partes (transformação de Abel).
Fórmula de Euler-MacLaurin.

Funções geradoras

Contagens. Coeficientes binomiais. Princípio de inclusão-exclusão.

Funções geradoras

Aplicações à resolução de equações às diferenças finitas.

TESTE

Teste 2.

Funções geradoras

Aplicações à resolução de equações às diferenças finitas e à determinação de fórmulas fechadas de somatórios. Complexidade de algoritmos de ordenação.

Grafos

Introdução ao estudo dos grafos. Conceitos introdutórios.

Grafos

Atalhos eulerianos e circuitos hamiltonianos.

Grafos

Grafos planares.

Grafos

Algoritmos de Kruskal e Dijkstra.

Grafos

Algoritmo de Ford-Fulkerson.

Autómatos

Autómatos determinísticos e não determinísticos. Linguagens regulares.

Autómatos

Lema da bombagem.

Autómatos

Gramáticas.

TESTE

Teste 3.

Autómatos

Autómatos de pilha e linguagens livres de contexto, hierarquia de Chomsky.