Professor responsável

Paulo Fonseca paulofonseca at cin.ufpe.br

Local & horário

  • Seg 08-10h: Sala D004
  • Qua 10-12h: Sala D004

Pré-requisitos

Não existem requisitos formais mas sugere-se fortemente que os alunos já tenham cursado IF672cc/ec (Algoritmos). Espera-se que o alunos tenha familiaridade com o desenho, análise e implementação de estruturas de dados básicas e algoritmos como de ordenação e busca.

Ementa (tentativa)

  • 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 básica

  1. Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge Univ Press, 1997. link
  2. M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994. link

Avaliação

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

Observações

  1. Esta página tem objetivo de facilitar a comunicação e a organização do curso e será feito esforço para manter a informação aqui contida correta e atualizada. Entretanto, o conteúdo desta página tem caráter informativo e não-vinculativo, podendo ser modificado a qualquer altura à discrição dos professores responsáveis ou atendendo a restrições materiais e humanas, no melhor interesse dos objetivos didáticos e acadêmicos, bem como da observância às regras instituicionais.
  2. Sobrepõem-se às informações aqui contidas qualquer comunicado em contrário emitido publicamente em sala de aula pelos professores responsáveis.
  3. Quaisquer dúvidas e/ou divergências deverão ser esclarecidas o mais brevemente possível com os professores responsáveis.
  4. Documentos de referência:
    • Regimento da UFPE link
    • Calendário acadêmico UFPE 2014 link to PDF
    • Resolução n° 04/1994 - Estabelece normas complementares de avaliação de aprendizagem e controle da frequência nos Cursos de Graduaçãolink to document
    • Manual acadêmico UFPE 2014 link to PDF
Projeto Descrição Entrega
Projeto 1 (v2 atualizado em 19/11/2014) 30/11/2014
Projeto 2 22/02/2015