Programação
-
-
Programação das aulas, tarefas, etc.
-
-
Deque persistente com o jump pointer inspirado na notação skew binary.
-
Treap tradicional e treap funcional (persistente).
-
Pilha retroativa
-
Árvore de segmentos estática e dinâmica
-
Heap cinético
-
Splay tree e treap com split e join
-
Florestas dinâmicas com Euler tour trees
-
Vetor de sufixos e LCP: construção linear dos vetores LLCP e RLCP, busca por padrão e número de ocorrências em tempo O(|P|+log |T|), e lista de ocorrências O(|P|+log |T| + t), onde t é o número de ocorrências.
-
Construção linear da árvore de sufixos de T a partir do vetor de sufixos e vetor LCP. Busca na árvore de sufixos de um padrão P em tempo O(|T|), número de ocorrências de P em tempo O(|P|), e lista das t ocorrências de P, em tempo O(|P| + t). Construção linear do vetor de sufixos e LCP a partir da árvore de sufixos.
-
Construção em tempo linear do vetor de sufixos de um texto T e do vetor LCP a partir do vetor de sufixos.
-
-
-
A primeira parte da aula aborda o material referente à tarefa T7. Mas não menciona a versão simplificada (sem os nós de vértices). Tem um extra sobre essa tarefa numa aula posterior, que coloquei no vídeo seguinte.
-
A partir do minuto 43:53 tem uma revisão e detalhamento do que é para implementar na tarefa 7 (só que sem a simplificação).
-
A partir do instante 1:09, eu falo dos algoritmos de conversão. Continua no vídeo da aula seguinte e tem um extra numa aula mais adiante sobre a construção da árvore a partir dos dois vetores.
-
No instante 8:00 desse vídeo, eu explico de novo o algoritmo de construção da árvore Cartesiana, que vai dar o esqueleto da árvore de sufixos a partir do vetor LCP em tempo linear, da T9. A partir do instante 40:47, começa a explicação da construção linear do vetor de sufixos e do LCP em tempo linear, ambos pedidos na T10. Tem mais explicação sobre isso no vídeo seguinte.
-
Em 2021, estas eram as tarefas T10 e T11 (e a tarefa 9 da edição de 2021 é a T8, que vocês já entregaram). A T9 da edição deste ano pede mais coisas: pede também a construção dos vetores de sufixo e LCP a partir da árvore. Esse vídeo detalha mais a construção da árvore de sufixos a partir do vetor de sufixos e LCP, detalha também a busca, se bem que esse ano eu sugeri uma simplificação para determinar o número de ocorrências na árvore de sufixos (busca do predecessor e sucessor). Tem também depois uma revisão das coisas da T10.
-