Programa

Elementos de Matemática Discreta

Licenciatura Bolonha em Engenharia Informática e de Computadores - Taguspark

Programa

Estudo da indução matemática. Teoria intuitiva dos conjuntos, das relações e das funções. Relações de ordem. Reticulados. Grafos, subgrafos, ciclos e circuitos. Digrafos e redes. Grafos planares. Coloração de grafos. 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. 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.