Disciplina Curricular
Elementos de Matemática Finita EMF
Licenciatura Bolonha em Matemática Aplicada e Computação - LMAC 2006
Contextos
Grupo: LMAC 2006 > 1º Ciclo > Tronco Comum
Período:
Peso
6.0 (para cálculo da média)
Objectivos
Introduzir os alunos as tecnicas e aplicações elementares da matematica em estruturas finitas. Os alunos aprendem a linguagem dos algoritmos e as estruturas que lhes estão associadas : problemas de contagem, de classificação e de optimizaçã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.
Metodologia de avaliação
A avaliação de conhecimentos nesta cadeira será por avaliação contínua nas aulas práticas, complementada com Testes e Exame Final.