Apresentação da Disciplina: Além do Linear
1. O Legado de AED I
Em Algoritmos e Estruturas de Dados I, o foco foi construir a base do pensamento computacional estruturado. Lá, o mundo era predominantemente Linear (1D): - Vetores (Arrays): Acesso rápido, tamanho fixo. - Listas Encadeadas: Tamanho dinâmico, acesso sequencial. - Pilhas (Stacks): LIFO (Last In, First Out) - essencial para chamadas de função. - Filas (Queues): FIFO (First In, First Out) - essencial para processamento de tarefas.
Os problemas resolvidos eram diretos: “Insira X”, “Remova Y”, “Ordene Z”. A complexidade raramente explodia.
2. Bem-vindos a AED II: O Mundo Não-Linear
Conforme nossa Ementa Oficial, aqui os dados ganham complexidade e dimensões. O foco é em Estruturas de Dados Não Lineares.
Por que estudar isso?
- Hierarquia (Árvores): Como organizar dados em disco (B-Trees) ou memória (AVL) para que a busca seja \(O(\log N)\) e não \(O(N)\).
- Relacionamento (Grafos): Modelar redes sociais, rotas de GPS e dependências de software.
- Complexidade Pesada: Diferente de ordenar um vetor (\(O(N \log N)\)), muitos problemas em grafos não têm solução rápida conhecida (NP-Completo). Aprenderemos a identificar esses “problemas impossíveis” e usar aproximações ou heurísticas.
3. Estrutura dos Trabalhos Práticos
A disciplina é fortemente prática. Além das listas semanais no Juiz Online, teremos dois grandes Trabalhos Práticos (TPs) que consolidam os módulos:
TP1: Indexação e Estruturas Hierárquicas
- Objetivo: Implementar um sistema de índices (como um mini-Banco de Dados ou Buscador).
- Conteúdo: Árvores AVL, Rubro-Negra ou Árvores B.
- Desafio: Lidar com grandes volumes de dados onde a escolha da estrutura define se o programa roda em 1 segundo ou 1 hora.
TP2: Otimização em Grafos Realistas
- Objetivo: Resolver um problema de otimização em uma rede real (ex: Rotas de entregas, Alocação de horários, Rede de distribuição de água).
- Conteúdo: Caminhos Mínimos (Dijkstra), Árvore Geradora (Kruskal) ou Fluxo Máximo.
- Desafio: Modelagem. O difícil não é codar o Dijkstra, é perceber que o problema é um Dijkstra disfarçado.
4. Conteúdo Programático (Baseado na Ementa)
Unidade 1: Estruturas Hierárquicas
- Árvores Binárias de Busca (BST).
- Análise de Complexidade: Pior caso vs Caso Médio.
Unidade 2: Balanceamento e Memória Secundária
- Árvores AVL: Balanceamento rígido para leitura rápida.
- Árvores B: A base dos Sistemas de Arquivos e Bancos de Dados (SQL/NoSQL).
Unidade 3: Grafos e Otimização
- Buscas: BFS e DFS (Conectividade).
- Caminhos Mínimos: Dijkstra e Floyd-Warshall.
- Problemas Difíceis: Caixeiro Viajante (TSP), Coloração e a classe NP-Difícil.
5. Avaliação
| Componente | Pontos | Descrição |
|---|---|---|
| Prova 1 | 35 | Árvores e Estruturas Hierárquicas |
| Prova 2 | 35 | Grafos e Algoritmos |
| Trabalho Prático 1 | 7 | Implementação de Estruturas de Dados |
| Trabalho Prático 2 | 7 | Otimização em Grafos |
| Listas de Exercícios | 16 | Prática contínua no Juiz Online |
Bibliografia Principal: - CORMEN, T. H. et al. Algoritmos: Teoria e Prática. - ZIVIANI, N. Projeto de Algoritmos.