Kursthemen
-
-
Apresentação da disciplina, professor e monitor
Bibliografia: Algorithms 4th edition. Sedgewick e Wayne
Critério de Aprovação
- EPs obrigatórios. MEP é a média aritmética dos EPs
- Provas (9/5 e 27/6). MP é a média aritmética das provas
A média final é dada por (2MEP + MP)/3, caso MEP e MP sejam maiores ou iguais a 5.0.
-
- Bags, pilhas e filas.
Fundamentos de análise de algoritmos:Livro texto (Sedgewick & Wayne) cap. 1.2 e 1.3.
Exercícios recomendados: 1.3.3, 1.3.10 e 1.3.11
- análise empírica
- análise de pior caso
Capítulo 1.4 do livro texto.
-
Análise de pior caso, melhor caso, caso médio
Análise Amortizada
Tabelas de símbolos - primeiras definições
-
Implementações básicas
- lista ligada desordenada
- árvore de busca binária: busca e inserção
-
ABB:
- busca
- inserção
- altura esperada de um nó
- remoção
Treaps
-
Não haverá aula
-
Inserção em uma árvore 2-3
-
Árvores 2-3 - remoção
B-árvores
-
B-árvores: inserção e remoção
Árvores rubro-negras: definição
-
- Inserção (código e exemplos)
-
Árvores Rubro-negras (remoção)
Tabelas de símbolos - comparação das estruturas vistas
-
Hashing
Tratamento de colisões com encadeamento
-
Hashing com linear probing
Tries
Árvores de sufixo
-
Exercícios
-
Correção da prova
Grafos: definições, como implementar as arestas: matriz de adjacências, listas de adjacências, matriz de incidência.
-
Aplicações de DFS:
- conexidade
- componentes conexas
- bipartido
- aresta em circuito
Busca em largura: caminho de distância mínima.
Todo o material da aula pode ser encontrado na página do Prof. Feofiloff
https://www.ime.usp.br/~pf/algoritmos_para_grafos/
-
- Aula cancelada
-
- Digrafos: definições básicas
- Busca em profundidade: classificação de arestas (arborescência, retorno, descendente, cruzada)
- Busca de circuitos em digrafos
-
Algoritmo de Tarjan para componentes fortemente conexas.
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/strong-graphs.html
-
- Ordenação Topológica (eliminação das fontes)
- Algoritmo de Dijkstra
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/cheapestpaths.html
-
KMP
Autômatos finitos determinísticos
-
Expressões regulares: definições, exemplos.
Reconhecimento de exp. reg usando autômatos finitos não determinísticos.
-
Algoritmo para reconhecimento de expressões regulares
Geração do grafo de lambda-transições
-
Exercícios para a Segunda Prova
-
Segunda Prova
-
Códigos de Huffman
-