MENU: [ Avisos | Informações Gerais | Regras | Trabalhos | Plano de Atividades ]
Última atualização em 05/09/2018 (trabalhos e plano de atividades).
Leia toda esta página no início do semestre: ela contém informações essenciais, como as regras para solicitação de segunda chamada e para o cálculo da nota na disciplina.
Esta página está em contínua construção. Por favor, entre em contato comigo caso você precise de alguma informação adicional, ou caso acredite ter encontrado um erro aqui. Obrigado!
Nesta disciplina aprende-se as técnicas clássicas para a eficiente manipulação de dados em programas de computador. Uma descrição mais detalhada é fornecida mais abaixo.
Informações importantes sobre a disciplina, como ementa e bibliografia, podem ser encontradas na atual regulamentação da disciplina. Parte dessas informações está também no PPC do curso de Matemática Industrial.
Todas as atividades da disciplina já têm data estimada no plano de atividades. Se você percebeu um choque de datas importantes com outra disciplina, ou se você já sabe que não poderá fazer uma das nossas provas na data prevista, por favor me comunique o quanto antes!
As aulas da disciplina não seguirão livro algum de forma exata, mas, àqueles que desejarem uma sugestão de livro para estudar, eu recomendo o muito bom Estruturas de Dados e Seus Algoritmos, de Jayme Szwarcfiter e Lilian Markenzon, que contém todo o conteúdo que veremos e o apresenta em nível adequado a esta disciplina. Um livro mais avançado, mais abrangente e que também contempla a disciplina posterior de Construção e Análise de Algoritmos, é o Algoritmos, de Cormen, Leiserson, Rivest e Stein.
Esteja atento, desde o início do semestre, às regras para solicitação de segunda chamada e para o cálculo da nota da disciplina.
A minha sugestão para a obtenção de um bom desempenho na disciplina é (1) acompanhar as aulas com atenção, tirando dúvidas o quanto antes, e (2) fazer os exercícios com regularidade. Caso você possua uma dúvida no horário da aula, o ideal é tirá-la na própria ocasião, para que os demais alunos também se beneficiem das explicações. Esteja, porém, à vontade para me contactar fora das aulas.
Segunda chamada: consulte as regras para a solicitação de prova de segunda chamada.
Provas (8 pontos): AP1 (2,5 pontos), AP2 (2,5 pontos) e AP3 (3 pontos).
Trabalhos (2 pontos): 4 trabalhos (0,5 ponto cada).
A aprovação na disciplina seguirá a regra da universidade (Regimento Geral, artigo 114):
| Nota | ≥ 7 | 7 > média ≥ 4 | < 4 |
|---|---|---|---|
| Situação | Aprovado | AF | Reprovado |
Deque Ilimitado (especificação no SIGAA).
... POR DEFINIR ...
... POR DEFINIR ...
... POR DEFINIR ...
Dentro do Período Letivo 2018.2, esta disciplina possui 48 datas reservadas, já descontados os feriados (4) e recessos (1). Dessas datas, 6 estão reservadas para eventos acadêmicos (SAC, Encontros Universitários e Semana da Matemática Industrial), 39 para aulas e 3 para provas. Além disso, para o Período de Avaliações Finais, está prevista a AF da disciplina. Na tabela a seguir estão descritas todas essas atividades.
O conteúdo da disciplina é o seguinte:
INTRODUÇÃO E REVISÃO (3 aulas): introdução à disciplina, revisão sobre ponteiros, alocação dinâmica de memória.
VETORES E TIPOS ABSTRATOS DE DADOS (9 aulas, mais AP1 e correção): pilhas, filas, deques (1º trabalho), conjuntos (e iteradores) e dicionários, todos implementados via vetor. Esses TADs mostram como programas de computador tipicamente precisam manipular dados, e as implementações via vetor mostram maneiras eficientes de manipulação dessa fundamental estrutura.
LISTAS ENCADEADAS (6 aulas): listas simplesmente encadeadas, duplamente encadeadas, circulares e com sentinelas. Essas estruturas apresentam maneiras alternativas pelas quais os TADs estudados anteriormente podem ser implementados.
COMPLEXIDADE DE ALGORITMOS (3 aulas, mais AP2 e correção): notações assintóticas O, Ω e Θ, complexidade de algoritmos em geral e complexidade dos algoritmos estudados até então.
TABELAS DE DISPERSÃO (4 aulas): funções de dispersão, encadeamento externo, endereçamento aberto e redimensionamento de tabelas de dispersão.
ÁRVORES E MEMÓRIA SECUNDÁRIA (9 aulas): busca binária, árvores binárias, percursos em árvores binárias, árvores balanceadas (AVL) e árvores B.
FILAS DE PRIORIDADE (3 aulas, mais AP3): montes ("heaps") binários e ordenação por monte ("heapsort").
| Aula | Data | Descrição |
|---|---|---|
| 01 | 06/08 (seg) | Introdução à Disciplina; Introdução a Ponteiros |
| 02 | 08/08 (qua) | Aritmética de Ponteiros; Percurso de Vetor via Ponteiros |
| 03 | 10/08 (sex) | Percurso de Vetor via Ponteiros x Indexado; Alocação Dinâmica |
| * | 13/08 (seg) | SAC |
| 15/08 (qua) | Feriado Municipal: Nossa Senhora da Assunção | |
| * | 17/08 (sex) | SAC |
| 04 | 20/08 (seg) | Solução de um Problema de Avaliação de Expressões Aritméticas |
| 05 | 22/08 (qua) | Programação da Avaliação de Expressões Aritméticas |
| 06 | 24/08 (sex) | Introdução a Tipos Abstratos de Dados; Pilhas: Operações, Variações e Uso |
| 07 | 27/08 (seg) | Implementação de Pilha via Vetor em C; Polimorfismo Paramétrico em C++ |
| 08 | 29/08 (qua) | Implementação de Pilhas Genéricas em C++; Introdução a Filas |
| 09 | 31/08 (sex) | Implementação de Fila via Vetor |
| 10 | 03/09 (seg) | Conjuntos Dinâmicos: Introdução e Início de Implementação via Vetor |
| 11 | 05/09 (qua) | Continuação da Implementação de Conjunto via Vetor; Percurso via Iteradores |
| 07/09 (sex) | Feriado Nacional: Independência do Brasil | |
| 12 | 10/09 (seg) | Dicionários e Implementação via Vetor |
| 13 | 12/09 (qua) | Listas Encadeadas; Implementação de Pilha via Lista Encadeada |
| 14 | 14/09 (sex) | Implementação de Fila via Lista Encadeada |
| * | 17/09 (seg) | AP1 - Até Dicionários via Vetor |
| 15 | 19/09 (qua) | Correção da AP1; Entrega das provas corrigidas (tentativa) |
| 16 | 21/09 (sex) | Implementação de Deque via Lista Duplamente Encadeada |
| 17 | 24/09 (seg) | Implementação de Conjunto via Lista Encadeada |
| 18 | 26/09 (qua) | Iteradores em Lista Encadeada |
| 19 | 28/09 (sex) | Busca e Remoção em Listas Circulares e Listas com Sentinelas |
| 20 | 01/10 (seg) | Introdução às Notações Assintóticas O, Ω e Θ |
| 21 | 03/10 (qua) | Complexidade Assintótica de Algoritmos |
| 22 | 05/10 (sex) | Complexidade dos Algoritmos Estudados até aqui |
| 23 | 08/10 (seg) | Introdução às Tabelas de Dispersão; Encadeamento Externo |
| 24 | 10/10 (qua) | Funções de Dispersão |
| 12/10 (sex) | Feriado Nacional: Dia de Nossa Senhora Aparecida | |
| 15/10 (seg) | Recesso Escolar: Dia do Professor | |
| * | 17/10 (qua) | AP2 - Até notação assintótica e a complexidade dos algoritmos |
| 25 | 19/10 (sex) | Correção da AP2; Entrega das provas corrigidas (tentativa) |
| 26 | 22/10 (seg) | Endereçamento Aberto |
| * | 24/10 (qua) | Encontros Universitários 2018 |
| * | 26/10 (sex) | Encontros Universitários 2018 |
| * | 29/10 (seg) | Semana da Matemática Industrial - SEMI |
| * | 31/10 (qua) | Semana da Matemática Industrial - SEMI |
| 02/11 (sex) | Feriado Nacional – Dia de Finados | |
| 27 | 05/11 (seg) | Redimensionamento de Tabelas de Dispersão |
| 28 | 07/11 (qua) | Busca Binária e Aplicações |
| 29 | 09/11 (sex) | Introdução a Árvores Binárias |
| 30 | 12/11 (seg) | Inserção e Percursos em Árvores Binárias |
| 31 | 14/11 (qua) | Remoção em Árvores Binárias; Árvores n-árias |
| 32 | 16/11 (sex) | Introdução a Árvores Balanceadas e AVL |
| 33 | 19/11 (seg) | Inserção em Árvores AVL |
| 34 | 21/11 (qua) | Remoção em Árvores AVL |
| 35 | 23/11 (sex) | Filas de Prioridades e Montes ("heaps") Binários |
| 36 | 26/11 (seg) | Algoritmos para Montes Binários |
| 37 | 28/11 (qua) | Construção de Montes em Tempo Linear e Ordenação por Monte ("heapsort") |
| 38 | 30/11 (sex) | Árvores B (1/2) |
| 39 | 03/12 (seg) | Árvores B (2/2) |
| * | 05/12 (qua) | AP3 - Até heapsort |
| * | 07/12 (sex) | Entrega das provas corrigidas (tentativa) |
| 10/12 (seg) | ||
| * | 12/12 (qua) | Avaliação Final |
| * | 13/12 (qui) | Último dia para AFs: Provas são possíveis até esta data - não viajar antes! |
| * | 14/12 (sex) | Notas Finais da Disciplina |
Para fins de registro, também é possível acessar a versão anterior do plano acima.