Professor responsável

Paulo Fonseca

Local & horário

• Seg 10-12h: Sala E124 / Lab G03
• Qua 08-10h: Sala E124

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

• 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. 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.

Ética acadêmica

Os alunos/equipes devem fazer seus próprios trabalhos, compreender o que fizeram e ser capazes de explicar os seus raciocínios sem ajuda externa.

É permitido estudar código de terceiros, mas não é permitido copiar partes significativas destes e apresentar como se fosse trabalho próprio. Também cabe aos alunos/equipes zelar pelo sigilo dos seus trabalhos. Em caso de cópias, as notas dos trabalhos ou provas idênticos serão zerados, independente de quem tenha copiado.

No caso de trabalhos em equipe, todos devem contribuir igualmente e conhecer em detalhes todo o trabalho.

O plágio e a fraude acadêmica não contribuem para o processo educacional e não serão tolerados.

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 fudamentalmente informativo e não-vinculativo, podendo ser modificado a qualquer altura à discrição do professor responsável 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 pelo professor responsável.
3. Quaisquer dúvidas e/ou divergências deverão ser esclarecidas o mais brevemente possível com o professor responsável.
4. Documentos de referência:
   • Regimento da UFPE
   • Calendário acadêmico UFPE 2016
   • Resolução n° 04/1994 - Estabelece normas complementares de avaliação de aprendizagem e controle da frequência nos Cursos de Graduação
   • Manual acadêmico UFPE 2016

Projeto	Descrição	Entrega
Projeto 1		14/10/2016
Projeto 2		03/12/2016

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)