collapse Sobre o curso

Professor responsável

Paulo Fonseca paulofonseca at cin.ufpe.br

Local & horário

  • Seg 13-15h: Sala B020
  • Qua 15-17h: Lab. Grad 3

Pré-requisitos

Não existem requisitos formais mas sugere-se fortemente que os alunos já tenham cursado IF672CC (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

A nota será calculada como a média das notas de duas unidades. Em cada unidade a nota será calculada com base em projetos feitos em duplas da seguinte forma:

  1. 50% pela implementação
  2. 50% pela apresentação do algoritmo

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 2013 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 2012 link to PDF
Show Programação
Show Material
show Trabalhos