|
Disciplina:
DCC585: Estruturas de Dados Fundamentais
Professores
responsáveis: Roberto
da Silva Bigonha ou Mariza A. S. Bigonha
Carga Horária: 30 horas
Créditos: 2
Pré-Requisitos: Não há um pré-requisito formal.
Tipo: Optativa
Objetivos
Ementa
Tipos
abstratos de dados, complexidade de algoritmos, lista lineares, arvores.
Programa
1. TIPOS ABSTRATOS DE DADOS
1.1 Tipo Abstrato de Dados
1.2 Abstração de Dados
1.3 Implementação de Abstração de Dados e
de Tipo Abstrato de Dados
2. COMPLEXIDADE DE ALGORITMOS
2.1 Complexidade de Tempo e de Espaço
2.2 Notação O para Complexidade
2.3 Pesquisa Sequencial: pior, melhor caso
e caso médio
2.4 Função de Complexidade Assintótica
2.5 Classes de Problemas
2.6 Problemas Trataveis e Intrataveis
2.7 Operações com Notação O
2.8 Técnicas de Análise de Algoritmos
2.9 Análise de um Programa
2.10 Função de Custo de Algoritmos
Recursivos
2.11 Equação de Recorrência;cia
2.12 Algoritmos Recursivos
2.13 Recursivos X Iterativos
2.14 Algoritmos de Tentativa e Erro
2.15 Algoritmo do Passeio do cavalo
2.16 Análise do Algoritmo
3. LISTAS LINEARES
3.1 Conceito de Listas Lineares
3.2 Implementação com Arranjos
3.3 Implementação de Listas com Apontadores Versão
Pascal e Java
3.4 Uso de Nodo-Cabeça
3.5 Aplicação: Inversão de Lista
Caminhamento em Sentido Duplo
3.6 Classificação no Vestibular
3.7 Implementação de Listas com Cursores
3.8 Listas Duplamente Encadeadas Listas Circulares Listas Duplamente Encadeadas
3.9 Inserção e Remoção de Nodos
3.10 Implementação de Listas Duplamente Encadeadas
3.11 Conceito de Pilhas Exemplos de Uso de
Pilhas: Editor de Texto
3.12 Implementação com Arranjos
3.13 Implementação do Tipo
Pilha em Pascal e Java
3.14 Implementação
de Pilhas com Apontadores
3.15 Conceito de Filas Implementação de
Filas com Arranjos
3.16 Implementação de Filas com apontadores
4. ÁRVORES
4.1 Árvores Binárias Árvores Binárias
Estendidas
4.2 Representação
4.3 Aplicação Propriedades de Árvores Binárias
4.4 Caminhamentos em Árvore: Central,
Pré-Ordem e Pós-Ordem
4.5 Algoritmos de Caminhamento Recursivos e
4.6 Não-Recursivos
Bibliografia Principal
1. N. Ziviani Projeto de Algoritmos com Implementação em Pascal e C, Editora Pioneira, 1992 (capítulos 1 a ?).
2. N. Wirth, Algoritmos e Estruturas de Dados, Prentice-Hall do Brasil
Ltda, 1989 (capítulos 3 e ??).
3. R. Sedgewick, Algorithms in C++,
Addison-Wesley, 1992 (capmtulo 17 - Pesquisa Digital).
Bibliografia Suplementar
1. Jayme Luiz Szwarcfiter e Lilian
Markenzon, Estruturas de Dados e seus Algoritmos, 2a Edição, Editora LTC, 1994.
2. A.V. Aho, J.E. Hopcroft and J.D.
Ullman, J.D, Data Structure and Algorithms, Addison-Wesley, 1983.
3. S. Baase, Computer Algorithms --
Introduction to Design and Analysis, Second Edition, Addison-Wesley, 1988.
4. Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures
Sixth Printing - Computer Science Press, Inc., 1976.
5. D. Knuth, The Art of Computer Programming, Volume 1: Fundamental
Algorithms, Addison-Wesley, Second Edition, 1973.
6. D. Knuth, The Art of Computer Programming, Volume 3: Sorting and
Searching, Addison-Wesley, Second Edition, 1973.
7. R. Sedgewick, Algorithms, Second Edition, Addison-Wesley, 1988.
8. N. Wirth, Algorithms and Data
Structures, Prentice-Hall, 1986.
9. Katheleen Jensen and Niklaus Wirth,
Pascal: User Manual and Report, Springer-Verlag, 1974
(MASB-10/07/2012)
|
