Algoritmos e estruturas de dados III

Ensino Remoto Emergencial : ERE – 2020/2021

Página com informações gerais da disciplina: ementa, datas das provas, bibliografia, exercícios, etc.

AVISOS

================================

=> Resultados disponíveis neste link

=> Nova data para o trabalho 2 : 19/03/2021

=> Início dia 20/01/2021, quarta, as 15h30

=> Especificação do trabalho 2 disponível

=> Especificação do trabalho 1 disponível

=> Moodle: https://moodle.c3sl.ufpr.br/course/view.php?id=416

=> Locais dos encontros virtuais: https://bbb.c3sl.ufpr.br/b/mar-d3c-kdz 

=> Estão acesssíveis no GitHub um conjunto de Notebooks com códigos em C++ com implementação das estruturas de dados apresentadas na disciplina. Acessível no Github.

================================

MATERIAL DE AULA

1 – Exercícios (árvores BST, AVL, 2-3-4, B, RB)
2 – Exercícios (BST, AVL, 2-3-4, RB)
3 – Exercícios Trie, Heap, Hash

 Site com simulação de criação de diferentes tipos de estruturas de dados (Universidade de São Francisco, EUA)

Aulas gravadas

Modalidades e meios

Atividades síncronas: aulas por videconferência https://bbb.c3sl.ufpr.br/b/mar-d3c-kdz
Atividades assíncronas: textos, listas de exercícios e trabalhos. Calendário:
Início: 20/01/2021
Fim: 26/03/2021

Cronograma detalhado:

20/01/2021 Apresentação da disciplina Busca binária ES

27/01/2021 Tipo abstrato de dados Árvores binárias ES/EX

03/02/2021 Implementação de árvores binárias ES/ML /EX

10/02/2021 Árvore binaria de busca: ordenação, rotações, inclusão , inclusão na raiz, exclusão ES/EX/TP1 (21/02)

24/02/2021 AVL Árvore 2-3-4 ES

03/03/2021 Árvore B: inclusão, ES/EX

10/03/2021 Árvore B: exclusão Árvore B+, ISAM ES

17/03/2021 Pesquisa digital e Trie Ordenação Externa ES/TP2/ML/EX

24/03/2021 Compressão de dados ES / EX

24/03/2021 Hashing e Endereçamento aberto ES/EX

26/03/2021 Final

Legenda:
ES: Encontro síncrono (2 horas)
ML: Disponibilização pelo professor de material de leitura (tempo necessário para leitura e estudo complementar ao trabalho prático: 4 horas)
EX: Disponibilização pelo professor de exercícios (tempo necessário para realizar a tarefa: 3 horas)
TPn: Disponibilização pelo professor de trabalho prático (tempo necessário para leitura, estudo e implementação do trabalho prático: 9 horas)

Avaliação

Dois trabalhos e prova final (se necessário)

  • Trabalho 1: 21/02/2021: implementação de analisador de expressões aritméticas 
  • Trabalho 2: 18/03/2021 :17/03/2021: implementação de árvore binária indexada por uma árvore binária: https://web.inf.ufpr.br/didonet/ci1057-ere-trabalho-2/
  • Final: 26/03/2021 → uma sexta!


Cálculo da Média Parcial: t1*0.40  + t2*0.60


Cálculo da média final:
– igual à média parcial, se esta é igual ou superior a 7.0 ou inferior a 4.0,
– média aritmética entre a média parcial e a nota no exame final, caso contrário.

Será aprovado o aluno que apresentar freqüência mínima igual ou superior a 75% das aulas e obtiver média final igual ou superior a 5.0.

BIBLIOGRAFIA

Os 2 primeiros livros serão os mais utilizados durante a disciplina. Os demais também possuem material muito bom.
=> Algoritmos – Teoria e prática, Cormen, Leiserson, Rivest, Stein, Rio de Janeiro, Campus, 2002
=> Projeto de algoritmos: com implementações em Pascal e C. Nívio Ziviani. São Paulo: Pioneira, 1999
=> Algorithms in C. R. Sedgewick. Addison-Wesley, Reading, Massachusetts, 1998.
=> Estruturas de Dados e seus Algoritmos. J.L. Szwarcfiter, L. Markenzon. LTC-Livros Técnicos e Científicos, Rio de Janeiro, RJ, 1994.
=>  Data Structures and Algorithms. A.V. Aho, J.E. Hopcroft, J.D. Ullman. Addison-Wesley, Reading, Massachusetts, 1983.
=>  Algorithms and Data Structures. N. Wirth. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989)
=> Introduction to Algorithms, Cormen, Leiserson, Rivest. MIT Press, Cambridge, Massachusetts, 1996.