Professor responsável
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
- Alfabetos cadeias e sub-cadeias
- Distâncias entre cadeias
- Casamento de padrões (String matching)
- String matching exato
(Métodos de janela deslizante, métodos semi-numéricos, paralelismo binário (bit-parallelism)
- String matching aproximado
(Métodos baseados em matriz de distância, Mátodos baseados em máquinas de estado, paralelismo binário)
- String matching exato
- Indexação
- Árvores de sufixos
(Representação e construção, string matching, aplicações)
- Arrays de sufixos
(Representação e construção, string matching, aplicações)
- Árvores de sufixos
- Compressão de texto
- Codificação de Huffman
- Fatoração de Lempel-Ziv
Bibliografia básica
- Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge Univ Press, 1997.
- M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994.
Avaliação
Dois projetos práticos de programação e, havendo necessidade, uma prova final escrita.
Observações
- 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.
- Sobrepõem-se às informações aqui contidas qualquer comunicado em contrário emitido publicamente em sala de aula pelos professores responsáveis.
- Quaisquer dúvidas e/ou divergências deverão ser esclarecidas o mais brevemente possível com os professores responsáveis.
- Documentos de referência: