Programação das aulas
Segundo semestre de 2023
Agosto
Setembro
Outubro
Novembro
1 de novembro (Aula 15):
Busca de padrão
Tries e árvores de sufixos compactadas
Construção quadrática da árvore de sufixos
Vetor de sufixos e longest common prefix (LCP)
Slides
[
pdf
].
Leitura recomendada:
Secs 4.1, 4.2, 2.1, 2.2 do
TCC do Marco Alves de Alcântara
.
6 de novembro (Aula 16):
Construção dos vetores estendidos de LCP
Construção dos vetores de sufixos e de LCP a partir da árvore de sufixos
Árvore cartesiana: construção em tempo linear
Slides
[
pdf
].
Leitura recomendada:
Secs 2.3, 2.5 e 4.3.1 do
TCC do Marco Alves de Alcântara
. Sobre treaps e árvores cartesianas, veja este
site
.
Tarefa 8:
Implementação da construção linear do vetor de LCPs estendidos e da busca eficiente com vetor de sufixos e LCPs.
8 de novembro (Aula 17):
Construção linear da árvore de sufixos a partir dos vetores de sufixos e LCP
Construção linear do vetor LCP do vetor de sufixos
Slides
[
pdf
].
Leitura recomendada:
Secs 4.3 e 2.4 do
TCC do Marco Alves de Alcântara
.
Tarefa 9:
Implementação da construção linear da árvore de sufixos a partir dos vetores de sufixo e LCP, e da busca eficiente com árvore de sufixos. Construção linear do vetor de sufixos e LCP da árvore de sufixos.
13 de novembro (Aula 18):
Construção linear dos vetores de sufixos
Slides
[
pdf
].
Tarefa 10:
Implementação da construção linear do vetor de sufixos e da construção linear do vetor LCP a partir do vetor de sufixos.
15 e 20 de novembro:
feriados.
22 de novembro (Aula 19):
Otimalidade dinâmica: geometria de buscas em ABBs
Estratégia gulosa
Slides
[
pdf
].
Leitura recomendada:
Aula 5
do curso do Demaine.
27 de novembro (Aula 20):
Delimitações inferiores para OPT(X)
Árvores Tango
Slides
[
pdf
].
Leitura recomendada:
aula 6
do curso do Demaine e o artigo
The geometry of binary search trees
29 de novembro (Aula 21):
Estruturas de dados implícitas, sucintas e compactas
Tries binárias sucintas - rank
Tries binárias sucintas - select
Slides
[
pdf
].
Leitura recomendada:
Parte da
aula 17
do curso do Demaine. Leia também a entrada da wiki sobre
succinct data structure
.
Dezembro