Planeamento

Aulas Teóricas

Introdução

Indução matemática. Somatórios e produtórios.

Equações às diferenças finitas

Cálculo de somatórios pelo método das perturbações direto e indireto.

Equações às diferenças finitas

Funções geradoras e suas aplicações. Soma dos termos de uma sucessão através do método da função geradora da sucessão.

Equações às diferenças finitas

Resolução das equações às diferenças finitas pelo método das funções geradoras.

Equações às diferenças finitas

Resolução das equações às diferenças finitas pelo método das funções geradoras.

Equações às diferenças finitas

Cálculo finito e suas aplicações ao cálculo de somatórios.

Equações às diferenças finitas

Complexidade de algoritmos de ordenação: Mergesort e Quicksort.

Transformada de Fourier discreta e introdução à FFT.

Elementos da teoria dos números

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

Elementos da teoria dos números

Equações diofantinas.

TESTE 1

Teste.

Elementos da teoria dos números

Resolução de congruências.

Elementos da teoria dos números

Reescrita (com congruências). Critérios de divisibilidade.

Elementos da teoria dos números

Teorema chinês do resto.

Elementos da teoria dos números

Teoria elementar dos números primos.

Elementos da teoria dos números

Aplicações à criptografia: Método de encriptação de chave pública --- RSA.

Autómatos finitos

Autómatos finitos determinísticos e não determinísticos.

Lema de Pumping.

TESTE 2

Teste.

Autómatos finitos

Gramáticas, gramáticas livres de contexto e gramáticas regulares. Expressões regulares.

Hierarquia de Chomsky.

Autómatos finitos

Aplicação dos autómatos não determinísticos à conversão de expressões e gramáticas regulares em autómatos determinísticos.

Grafos

Conceito elementares sobre grafos: grafos, digrafos, redes, pseudografos, multigrafos. Isomorfismos entre grafos. Aplicações dos grafos.

Grafos

Problemas de transportes.

Grafos eulerianos e hamiltonianos. Teoremas sobre grafos eulerianos, atravessáveis e hamiltonianos.

Grafos

Conectividade. Árvores de cobertura de um grafo. Algoritmo de Kruskal. 

Método do caminho crítico: PERT.

Grafos

Conectividade. Caminho mínimo num grafo. Algoritmo de Dijkstra.

Grafos

Campeonatos.

Grafos

Fluxos em redes. Algoritmo de Ford e Fulkerson.

 

Grafos

Grafos planares (teoremas de Euler). Transportes (teorema de Robbins).

TESTE 3

Teste.