Esta é uma disciplina de 4 créditos, e portanto ela possui (4/2)*16 = 32 encontros planejados, dos quais 28 são Aulas e 4 são Avaliações Parciais (observação). Adicionalmente, poderá ser realizada também uma Avaliação Final. Cada AP cobrirá em torno de 7 aulas, e a solução de cada prova será apresentada na última meia-hora da própria data de aplicação. Na tabela a seguir estão as datas e descrições de cada encontro.
A disciplina está dividida em 4 partes:
A parte 1 é a motivação da disciplina: nela são apresentados 2 problemas evidentemente relevantes, em cujos processos de solução nós aproveitamos para evidenciar a importância de 2 maneiras específicas de organizar dados. A ideia é convencer o aluno de que cada parte do conteúdo possui relevância prática, embora a disciplina não comporte o tempo necessário para detalhar uma aplicação para cada assunto. Além disso, são apresentados programas de computador para resolver os 2 problemas em questão, de forma a deixar clara a viabilidade da implementação do conteúdo apresentado.
O foco da parte 2 são as estruturas encadeadas, que são então utilizadas para representar vários Tipos Abstratos de Dados, incluindo grafos.
Findas as partes 1 e 2, com grande foco na programação das estruturas, a parte 3 introduz a análise de tempo e memória de algoritmos, além de tratar de conteúdos relacionados, como a manutenção da ordem entre os elementos de um dicionário.
A última parte da disciplina reune os elementos introduzidos anteriormente na apresentação de estruturas de dados mais elaboradas.
| Aula | Data | Descrição |
|---|---|---|
| 01 | 18/08 | Introdução à Disciplina; O Problema da Avaliação de Expressões Aritméticas. |
| 21/08 | Semana Acadêmica da Computação | |
| 25/08 | Semana Acadêmica da Computação | |
| 02 | 28/08 | O TAD Pilha e Implementação via Vetor |
| 03 | 01/09 | Programa para Avaliação de Expressões Aritméticas |
| 04 | 04/09 | O Problema das Distâncias em um Grafo Não-Ponderado; Matrizes de Adjacência. |
| 05 | 08/09 | O TAD Fila e Implementação via Vetor |
| 06 | 11/09 | Programa para Cálculo de Distâncias em Grafo Não-Ponderado |
| * | 15/09 | AP1 e Solução da Prova |
| 07 | 18/09 | O TAD Lista e Implementação via Vetor |
| 08 | 22/09 | Estrutura Encadeada e Implementação de Pilhas e Filas |
| 09 | 25/09 | Implementação de Listas via Estrutura Encadeada |
| 10 | 29/09 | O TAD Deque e Estruturas Duplamente Encadeadas |
| 11 | 02/10 | Implementação de Listas via Estrutura Duplamente Encadeada |
| 12 | 06/10 | Representação de Grafos por Listas de Adjacências |
| 13 | 09/10 | Ordenação Topológica de Grafos Direcionados Acíclicos |
| * | 13/10 | AP2 e Solução da Prova |
| 14 | 16/10 | Introdução às Notações Assintóticas O, Ω e Θ |
| 15 | 20/10 | Complexidade Assintótica de Algoritmos e Análise dos Algoritmos Anteriores |
| 16 | 23/10 | Introdução à Análise Amortizada de Complexidade |
| 17 | 27/10 | Dicionários e Implementação via Vetor ou Estrutura Encadeada |
| 18 | 30/10 | Busca Binária e uso na Implementação de Dicionários |
| 19 | 03/11 | Recursão e Aplicações: Busca Binária, Busca Linear, etc. |
| 20 | 06/11 | Árvores Binárias de Busca e uso na Implementação de Dicionários |
| * | 10/11 | Encontros Universitários 2017 |
| * | 13/11 | AP3 e Solução da Prova |
| 21 | 17/11 | Árvores AVL – Parte 1 / 2 |
| 22 | 20/11 | Árvores AVL – Parte 2 / 2 |
| 23 | 24/11 | Tabelas de Dispersão ("hash tables") – Parte 1 / 3 |
| 24 | 27/11 | Tabelas de Dispersão ("hash tables") – Parte 2 / 3 |
| 25 | 01/12 | Tabelas de Dispersão ("hash tables") – Parte 3 / 3 |
| 26 | 04/12 | Filas de Prioridades e Montes ("heaps") Binários |
| 27 | 08/12 | Algoritmos para Montes Binários |
| 28 | 11/12 | Construção de Montes em Tempo Linear e Ordenação por Monte ("heapsort") |
| * | 15/12 | AP4 e Solução da Prova |
| * | 18/12 | AF |
| 22/12 | Notas da AF |