Estrutura de Dados I (IM468)

Estruturas de Dados I

Informações

Código: IM468

Pré-requisito:

Programação Estruturada

Ementa

Complexidade de algoritmos e notação assintótica. Listas lineares, simplesmente encadeadas, duplamente encadeadas e circulares. Pilha e Fila. Algoritmos de ordenação. Árvores binárias, árvores binárias de busca, árvores balanceadas: AVL e rubro-negras. Listas de prioridades.

Objetivos

Ao final da disciplina o aluno deve:

(a) Interpretar o problema e identificar a estrutura de dados adequada para este;

(b) Analisar a complexidade de operações de todas das estruturas de dados abordadas na ementa;

(c) Aplicar as estruturas de dados de forma eficiente no desenvolvimento de algoritmos.

Conteúdo Programático

Sumario

1. Introdução
2. Listas
3. Pesquisa e Ordenação
4. Árvores

Tópicos de Aula

01. Introdução

• Introdução;
• Complexidade de Algoritmos;
• Complexidades de Pior Caso, Caso Médio e Melhor Caso;
• Notações Assintóticas;
• Recursividade.

02. Listas

• Listas Lineares, Busca Linear;
• Busca Binária;
• Pilhas e Filas;
• Alocação Encadeada;
• Listas Simplesmente Encadeadas;
• Listas Duplamente Encadeadas; *Listas Circulares.

03. Pesquisa e Ordenação

Algoritmos de Ordenação e suas respectivas complexidades:

• Bolha;
• Seleção;
• Inserção;
• Quicksort;
• Mergesort;
• E outros.

04. Árvores

• Árvores e Árvores Binárias, algoritmos de busca;
• Árvores Binárias de Busca;
• Árvores Balanceadas e seus algoritmos de busca e inserção: Árvores AVL, Árvores Graduadas e * Árvores Rubro-Negras;
• Listas de Prioridades e Algoritmos;
• Heap e Heapsort.

Referencia Bibliográfica

Bibliografia Básica

1. CORMEN, T.H., LEISERSON, C.E., Rivest, R.L., Stein, C. – “Algoritmos: Teoria e Prática.” 3ª Ed., Elsevier, 2012.
2. SZWARCFITER, J.L., MARKENZON, L. – “Estruturas de Dados e Seus Algoritmos.” 2ª Ed., LTC, Rio de Janeiro, 2004.
3. LUCCHESI C.L., KOWALTOWSKI. T. – “Estruturas de Dados e Técnicas de Programação.” Instituto de Computação – UNICAMP, 2003. Available at http://www.ic.unicamp.br/~tomasz/mc202/edtp.pdf, Accessed on Sep 15, 2015.

Bibliografia Complementar

1. SCHILDT, H. – “C Completo e Total”, Makron Books, 1997.
2. VELOSO P., SANTOS C., AZEREDO P., FURTADO A. – “Estruturas de Dados”, Ed. Campus, 1984.
3. ZIVIANI, N. – “Projeto de Algoritmos com implementações em Pascal e C”, 5a.edição, Ed Pioneira, 2001.
4. GUIMARÃES A. M. – “Algoritmos e Estruturas de Dados”, 1a Ed., LTC, 1994.
5. TERADA R. – “Desenvolvimento de Algoritmos e Estruturas de Dados”, 1a Ed., Makron Books, 1991.

Postado em 18/11/2013 - 07:39 - Atualizado em 14/08/2023 - 22:38