Disciplina

Área

Área Científica de Metodologia e Tecnologias da Programação > Algoritmia

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

Componente Laboratorial

Princípios Éticos

Componente de Programação e Computação

Componente de Competências Transversais

Bibliografia

Principal

Algorithms on strings Trees, and Sequences

Dan Gusfield

1997

Cambridge press


Secundária

Introduction to Algorithms

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

2002

The MIT Press


Combinatorial Pattern Matching Algorithms in Computational Biology Using Perl and R

Gabriel Valiente

2009

CRC Press


Modern Information Retrieval

Berthier de Araújo Neto Ribeiro, Ricardo Baeza-Yates.

1999

Addison Wesley Longman Publishing