Programa

Elementos de Matemática Finita

Licenciatura Bolonha em Matemática Aplicada e Computação

Programa

1.Números Inteiros: recorrências; princípio de indução finita; divisibilidade; algoritmo de Euclides; primos e factorização; aritmética modular. 2.Funções: sobrejecções, injecções, bijecções; contagem; princípio do pombal; princípio da dupla contagem; função de Euler; palavras e selecções; selecções ordenadas; permutações. 3.Conjuntos: números binomiais; selecções não-ordenadas; combinatória de conjuntos finitos; princípio de inclusão-exclusão; função de Mobius; configurações ou ?designs?. 4.Partições: partições de conjuntos; relações de equivalência; distribuições e números multinomiais; partições de um número inteiro; classificação de permutações. 5.Aplicações: iteradas de funções ? pontos fixos, órbitas periódicas e não periódicas, partições do intervalo, matriz de transição de Markov; construções de ?designs? e códigos; quadrados latinos; factorização e criptografia 6.Algoritmos: análise de eficiência de algoritmos; comparação de algoritmos; a notação O, o e ~; introdução a algoritmos de ordenação. 7.Grafos: valência, caminhos e ciclos; problemas de coloração de vértices; algoritmo ?glutão?; árvores; algoritmos de ordenação e de procura; problema do caminho mais curto. 8.Grafos bipartidos e problemas de emparelhamento: coloração de arestas e quadrados latinos; transversais em famílas de conjuntos finitos. 9.Grafos dirigidos, redes e fluxos: fluxos e cortes; o problema do fluxo máximo. 10.Aplicações: sistemas dinâmicos e grafos; optimização recursiva; introdução à programação dinâmica.