Programa

Elementos de Matemática Discreta

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

Programa

Teoria de números elementar Aritmética modular. Divisibilidade, máximo divisor comum, algoritmo de Euclides. Factorização e primalidade, teorema de Euler. Teorema chinês dos restos. Relações de equivalência e de congruência. Corpos finitos. Motivação: criptografia (RSA), teoria algorítmica de números. Algoritmia e correcção de programas Introdução à linguagem de programação Mathematica. Procedimento versus algoritmo. Análise da eficiência de programas imperativos no pior caso. Notação assintótica. Somatórios, formas fechadas, perturbação da soma, indução finita. Correcção parcial e total de programas, condições invariantes, expressões variantes. Pré-condição e pós-condição. Cálculo de Hoare para correcção de programas imperativos. Motivação: análise e verificação de algoritmos sobre matrizes, pesquisa e ordenação. Grafos Grafos, caminhos e ciclos. Árvores. Problema do percurso mínimo, algoritmo de Dijkstra e sua análise, soluções distribuídas (Chandy-Misra). Grafos dirigidos, fluxos e cortes. Teorema do fluxo máximo, algoritmo de Ford-Fulkerson. Motivação: optimização, problemas de encaminhamento em redes. Funções geradoras Função geradora de uma sucessão. Propriedades. Coeficientes binomiais. Função geradora de uma variável aleatória discreta, momentos. Análise de recorrências. Teorema da expansão racional. Resolução de equações lineares às diferenças. Motivação: problemas de contagem, análise de algoritmos recursivos.