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 (Juiz Online ou Questionários), 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. Linguagem de Programação: Java

A disciplina adotará a linguagem Java (JDK 11 ou superior). - Por que mudar de C/C++? Java tem maior foco no mercado, possui suporte nativo à orientação a objetos (facilitando grandes projetos industriais) e introduz o aluno ao ecossistema da Máquina Virtual (JVM). - Ferramentas Genéricas: Solicitamos configurar IDEs modernas como IntelliJ IDEA ou VSCode para as práticas orientadas em aula. As submissões serão feitas através de um Juiz Online (Online Judge) para correção automatizada.

5. Módulos da Disciplina e Objetivos

Módulo 1: Fundamentos e Árvores de Pesquisa

• Revisar complexidade matemática, lidar com espalhamento (Hash) e introduzir a busca hiérarquica em profundidade e largura (BST).

Módulo 2: Árvores Balanceadas e Memória Secundária

• Garantir a eficiência no pior caso (AVL, Rubro-Negra), explorar filas de prioridade (Heaps) e indexar dados massivos em disco (Árvores B/B+).

Módulo 3: Introdução e Percursos em Grafos

• Modelar problemas do mundo real em redes estruturadas e realizar percursos baseados em otimização de busca (BFS/DFS) e conexões de custo mínimo (Árvore Geradora Mínima).

Módulo 4: Caminhos Mínimos e Algoritmos Gulosos

• Resolver problemas de roteamento determinando rotas ótimas (Dijkstra, Bellman-Ford, Floyd-Warshall) e analisar cenários de alocação de recursos (Coloração de Grafos).

Módulo 5: Fluxo Máximo em Redes e Avançados

• Maximizar o transporte de itens através de gargalos (Ford-Fulkerson) e estudar classes de caminhos rigorosos (Grafos Eulerianos e Hamiltonianos).

6. Avaliação

Componente	Pontos	Descrição
Prova 1	35	Árvores e Estruturas Hierárquicas
Prova 2	35	Grafos e Algoritmos
TP 1	7	Indexação (Árvores)
TP 2	7	Otimização (Grafos)
Listas	16	Juiz Online ou Questionários

Bibliografia Principal: - KNUTH, Donald E. The Art of Computer Programming. - CORMEN, Thomas H. Algoritmos: teoria e prática. - GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de dados e algoritmos em JAVA.