Professor responsável

• Paulo Fonseca

Horário e sala

Aulas

• Terça-feira 13h-15h (Lab Grad 3)
• Quinta-feira 15h-17h (Lab Grad 5)

Ementa

• Conceitos básicos
  1. Alfabetos cadeias e sub-cadeias
  2. Distâncias entre cadeias
• Casamento de padrões (String matching)
  1. String matching exato
     (Métodos de janela deslizante, métodos semi-numéricos, paralelismo binário (bit-parallelism)
     
  2. String matching aproximado
     (Métodos baseados em matriz de distância, Mátodos baseados em máquinas de estado, paralelismo binário)
     
• Indexação
  1. Árvores de sufixos
     (Representação e construção, string matching, aplicações)
     
  2. Arrays de sufixos
     (Representação e construção, string matching, aplicações)
     
• Compressão de texto
  1. Codificação de Huffman
  2. Fatoração de Lempel-Ziv

Bibliografia

1. M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994.
2. Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge Univ Press, 1997.
3. James Storer. Data compression: methods and theory Computer Science Press, 1988.

Avaliação

Dois projetos práticos de programação e, havendo necessidade, uma prova final escrita.

Frequência

• A frequência a pelo menos 75% das aulas e avaliações parciais é obrigatória, respeitados o turno e o horário previstos para a disciplina. Será realizada chamada.
não é obrigatória.

Inscreva-se já no canal oficial de comunicação entre alunos, professores e monitores da disciplina (apenas para alunos matriculados com e-mail do CIn)