Programa

Algoritmos e Modelação Computacional

Licenciatura Bolonha em Engenharia Biológica

Licenciatura Bolonha em Engenharia Biomédica

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

Programa

Programação imperativa em C++ ou JAVA. Noção de objeto, classe, polimorfismo e herança. Correção de programa imperativos. Noção de invariante e variante de um ciclo. Introdução ao estudo da eficiência de algoritmos. Notação assimptótica. Análise no pior caso e no caso médio. Algoritmos de ordenação: inserção direta, seleção direta, bubblesort, quicksort, fusão binária e heapsort. Tipos de dados abstratos: árvores e grafos. Implementações estáticas e dinâmicas. Problema da pesquisa. Tabelas de dispersão. Árvores binárias de pesquisa. Árvores de pesquisa equilibradas e B-Trees. Pesquisa de padrões: algoritmo baseado em autómatos e Knuth-Morris-Pratt. Alinhamento de Sequências. Aplicações à Bioinformática. Algoritmos sobre grafos: Pesquisa em profundidade e largura, subárvore maximal. Aplicações à Aprendizagem Automática: Redes de Bayes e neuronais. Fluxo máximo e encaminhamento de pacotes. Problemas difíceis. Classes de complexidade P e NP. Projeto adequado ao curso.