Algoritmos e Estruturas de Dados (AED's II)

AED's II

Objetivo do curso

O curso de Algoritmos e Estrutura de Dados II tem o objetivo de apresentar e analisar estruturas de dados mais avançadas e seus algoritmos.

Ementa

Árvores binárias de busca balanceadas: AVL, Rubro-negra e suas operações. Árvores de busca gerais: árvore B e suas variações. Introdução à teoria dos grafos: conceitos, denominações, representação, operações, Grafos Bipartidos, isomorfismo, clique, cobertura, Grafos Eulerianos, Grafos Hamiltonianos. Algoritmos em grafos: busca (BFS, DFS), árvore geradora mínima (Prim, Kruskal), caminhos mínimos (Dijkstra, Bellman-Ford, Floyd-Warshall). Técnicas de projetos de algoritmos: Backtraking, Divisão e Conquista.

Horário de Aula

• Segundas 08:40hs - 11:10hs

• Quintas 07:00hs - 09:30hs

• Sala: 120

Horário de atendimento docente

• Quartas:

  • 14:00hs - 17:00hs (síncrono)

  • Plataforma: Teams (a priori, até normalizarmos a rede elétrica)

Horário de atendimento monitor - Willian Pitter

• Terças:

  • 15:00hs - 17:00hs (síncrono)

• Quintas:

  • 15:00hs - 17:00hs (síncrono)

• Plataforma: Teams, e-mail e WhatsApp

Notas de Aula

• Aula 00 - Apresentação

• Aula 01 - Árvores AVL (inserção)

• Aula 02 - Árvores AVL (Remoção)

• Aula 03 - Árvores AVL (Exercícios)

• Aula 04 - Árvores Rubro-Negras (Inserção)

• Aula 05 - Árvores Rubro-Negras (Remoção)

• Aula 06 - Árvores Rubro-Negras (Exercício)

• Aula 07 - Introdução a Árvores B

• Aula 08 - Inserção e Remoção em Árvores B

• Aula 09 - Árvores B (Exercícios)

• Aula 10 - Variantes da árvore B

• Aula 11 - Introdução à Teoria do Grafos

• Aula 12 - Principais Conceitos e Representação Computacional

• Aula 13, 14 - Aula prática em laboratório

• Aula 15 - Operações e Características

• Aula 16 - Exercícios no laboratório

• Aula 17 - Grafos Bipartidos

• Aula 18 - Isomorfismo, clique e cobertura

• Aula 19 - Grafos Eulerianos

• Aula 20 - Grafos Eulerianos (Algoritmos)

• Aula 21 - Grafos Hamiltonianos

• Aula 22 - Revisão para P1

• Aula 23 - Prova

• Aula 24 - Busca em Largura

• Aula 25 - Busca em Profundidade

• Aula 26 - Exercícios no laboratório (Busca)

• Aula 27 - Árvores em grafos

• Aula 28 - Árvore Geradora Mínima

• Aula 29 - Árvore Geradora Mínima - Algoritmos

• Aula 30 - Exercícios no laboratório (AGM)

• Aula 31 - Caminhos mínimos - Dijkistra

• Aula 32 - Caminhos mínimos - Bellman-Ford e Floyd-Warshall

• Aula 33 - Exercícios no laboratório (Caminhos mínimos)

• Aula 34 - Backtracking

• Aula 35 - Divisão e Conquista

• Aula 36 - Exercícios no laboratório

Exercícios Revisão

1. Árvore AVL

2. Árvore RN

3. Árvores B

4. Teoria Grafos 1

5. Teoria Grafos 2

6. Busca em Grafos

7. Caminhos mínimos

8. Árvore geradora mínima

9. Backtracking, backtracking 2

10. Divisão e conquista

Testes

1. Busca em Grafos

   1. Ir e vir

   2. Chegando Junto

   3. Chefe

   4. Inversão

2. Árvore Geradora Mínima

   1. Estradas Escuras

   2. Itinerário Papai Noel

   3. Roteadores

   4. Caixa Dois

3. Caminhos Mínimos

   1. Países em Guerra

   2. Desvio de Rotas

   3. Desrugenstein

   4. Movimentos do Cavalo

4. Backtracking

   1. Labirintos

   2. Código Genético

   3. Copa Européia

   4. Polícia e Ladrão

5. D&C

   1. Calouro vence vetereano?

   2. Bolhas e Baldes

Material Auxiliar

Sistema de paginação

Exemplos Grafos

***************************

Importante

• Comece a fazer o trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar!