Disciplina
Algoritmos em Estruturas Discretas
Área
Área Científica de Metodologia e Tecnologias da Programação > Algoritmos
Activa nos planos curriculares
MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Ciência da Computação > Algoritmos em Estruturas Discretas
MBiotec 2008 > MBiotec 2008 > 2º Ciclo > Eusysbio > Algoritmos em Estruturas Discretas
MMA 2006 > MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Metodologia e Tecnologia da Programação > Algoritmos em Estruturas Discretas
MEBiom 2006 > MEBiom 2006 > 2º Ciclo > Opções > Opção 2 > Algoritmos em Estruturas Discretas
Nível
60% Exame + 40% Projectos (2 pequenos projectos)
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
3.0 h/semana
1.5 h/semana
105.0 h/semestre
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
Metodologia de avaliação
60% Exame + 40% Projectos (2 pequenos projectos)
Pré-requisitos
na
Componente Laboratorial
na
Princípios Éticos
na
Componente de Programação e Computação
na
Componente de Competências Transversais
na
Bibliografia
Principal
Algorithms on strings Trees, and Sequences
Secundária
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Combinatorial Pattern Matching Algorithms in Computational Biology Using Perl and R
Berthier de Araújo Neto Ribeiro, Ricardo Baeza-Yates.
Addison Wesley Longman Publishing