Disciplina Curricular

Algoritmos em Estruturas Discretas AEDis

Mestrado Bolonha em Matemática e Aplicações e Computação - MMA 2006

Peso

6.0 (para cálculo da média)

Pré-requisitos

Objectivos

Os algoritmos em estruturas discretas têm desempenhado um importante papel em muitas aplicações em áreas da ciências da computação e, por conseguinte, constituem uma importante componente da formação em algoritmia. Esta unidade curricular tem como principal objectivo a análise de diversos algoritmos eficientes para a pesquisa de padrões em textos, árvores e grafos. Os alunos deverão desenvolver competências teóricas e práticas. Na componente teórica serão estudadas estruturas de dados avançadas e algoritmos para pesquisa de padrões, por pesquisa online, utilizando árvores e grafos. Na componente prática os alunos irão desenvolver aplicações eficientes para pesquisas de padrões em sequências biológicas ou para a construção de estruturas de dados para recuperação de informação.

Programa

1. Estruturas de dados avançadas i. B-Trees ii. Binomial Heaps iii. Fibonacci Heaps 2. Algoritmos online i. Knut-Moris-Pratt ii. Real-time string matching iii. Shift-And iv. Match-count and FFT v. Método Karp-Rabin 3. Algoritmos em Árvores i. Arrays de sufixos ii. Árvores de sufixos iii. Maior Substring Comum iv. Estruturas Máximas Repetidas v. Linearização de strings circulares vi. Análise Amortizada vii. Algoritmo de Ukkonen 4. Algoritmos em Grafos i. Procura de padrões simples ii. Cálculo de distâncias iii. Contagem de árvores iv. Contagem de sub-grafos 5. Aplicações i. Biologia Computacional ii. Recuperação de Informação