BCC202 - Estruturas de Dados I - 2020-1

Carga horária da disciplina: 6 horas/aula


Professor(es) em 2020-1

Turma 21 Professor:
Amanda Sávio Nascimento e Silva - www | e-mail

Horários:
Segunda-feira (10h10 - 11h50)
Segunda-feira (15h20 - 17h00)
Quarta-feira (10h10 - 11h50)

Turma 22 Professor:
Amanda Sávio Nascimento e Silva - www | e-mail

Horários:
Segunda-feira (10h10 - 11h50)
Segunda-feira (13h30 - 15h10)
Quarta-feira (10h10 - 11h50)

Objetivos

O aluno deverá conhecer conceitos associados a tipos abstratos de dados e métodos de pesquisa e ordenação de interesse teórico e prático.
Deverá também adquirir a capacidade de utilizar esses recursos pra desenvolvimento de programas, utilizando conceitos de modularização e abstração de dados.
Deverá ainda ser capaz de comparar estratégias de implementação do ponto de vista da complexidade dos algoritmos envolvidos, usando a notação $O$.

Ementa

Recursividade; conceitos básicos de análise assintótica de algoritmos; tipos abstratos de dados; estruturas de dados: listas, pilhas, filas de prioridade e árvores binárias; algoritmos de ordenação por comparação de chaves: seleção, inserção, bolha, shellsort, quicksort, mergesort, heapsort; algoritmos de ordenação em tempo linear: counting sort, radix sort e bucket sort; e algoritmos de pesquisa: simples, binária, árvores binárias de busca e hashing.

Conteúdo Programático

- Revisão de alocação dinâmica de memória
- Recursividade
- Noções de análise de complexidade de algoritmos:
- Conceitos
- Medidas de avaliação: tempo e espaço
- Análise assintótica: notação O, Omega e Theta
- Hierarquia de funções e classes de problemas
- Tipos de dados abstratos
- Estruturas de Dados
- Listas
- Pilhas
- Filas
- Filas de prioridade
- Árvores
- Algoritmos
- Métodos de ordenação por comparação: Selection Sort, Insertion Sort, Bubblesort, Shellsort, Quicksort, Heapsort e Mergesort
- Métodos de ordenação em tempo linear: Counting Sort, Radix Sort e Bucket Sort
- Métodos de pesquisa: Simples, Binária, Árvores Binárias e AVL e Hashing

Bibliografia

- ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Pascal e C. 3. ed. rev. e ampl. São Paulo: Cengage Learning, c2011. xx, 639 p. ISBN 9788522110506.
- CELES,Waldemar; CERQUEIRA,Renato; RANGEL,Jose Lucas. Introdução a Estruturas de Dados: com técnicas de programação em C.. Rio de Janeiro: Elsevier 2004. 293 p.
- CORMEN, Thomas H. Algoritmos: teoria e prática. Rio de Janeiro: Campus, 2002. xvii, 916 p.

Bibliografia complementar

- KLEINBERG, Jon; TARDOS, Eva. Algorithm design. Boston: Pearson/Addison-Wesley, c2006. xxiii, 838 p.
- KNUTH, Donald Ervin. The art of computer programming. Upper Saddle River: Addison Wesley, c2005. v.
- GOODRICH, Michael T.; TAMASSIA, Roberto; COPSTEIN, Bernardo. Projeto de algoritmos: fundamentos, análise e exemplos da internet. Porto Alegre: Bokman, 2004. 696 p.
- DROZDEK, Adam. Estrutura de dados e algoritmos em C++. São Paulo: Cengage Learning, c2002. xviii, 574 p.
- TENENBAUM, Aaron M; LANGSAM, Yedidyah; AUGENSTEIN, Moshe. Estruturas de dados usando C. São Paulo: Makron Books, 1995. 884 p.

Departamento de Computação  |  ICEB  |  Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro  |  CEP 35400-000  |  Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692  |  decom@ufop.edu.br