Programa

Matemática Discreta

Licenciatura Bolonha em Engenharia de Telecomunicações e Informática

Programa

Estudo da indução matemática. Teoria de números elementar. Algoritmos de Euclides e Saunderson. Pequeno Teorema de Fermat. Teorema chinês dos restos. Polinómios. Transformada de Fourier discreta (DFT) e seu cálculo eficiente (FFT). Aplicações à Criptografia RSA. Análise da eficiência de programas imperativos no pior caso e no caso médio. Determinação de formas fechadas de somatórios de termos elementares. Funções geradoras. Resolução de equações às diferenças lineares. Grafos, subgrafos, ciclos e circuitos. Digrafos e redes. Grafos planares. Coloração de grafos. Autómatos finitos determinísticos e não determinísticos; linguagens regulares, expressões regulares e gramáticas regulares. Autómatos de pilha. Linguagens e gramáticas livres de contexto. Lemas de bombagem. Correção de programas. Cálculo de Hoare para correção parcial e total de programas imperativos. Correção total de algoritmos de pesquisa e ordenação.