Disciplina: Estrutura de Dados Fundamentais E
Código: DCCxxx
Professor responsável: Roberto da Silva Bigonha
Carga horária: 30 horas-aula
Créditos: 2
Tipo: Optativa

Objetivos
Esta disciplina visa capacitar o aluno com relação às principais estruturas de dados.

Ementa
Tipos abstratos de dados, complexidade de algoritmos, lista lineares, árvores.

Programa
TIPOS ABSTRATOS DE DADOS:

· Tipo Abstrato de Dados
· Abstração de Dados
· Implementação de Abstração de Dados e de Tipo Abstrato de Dados

COMPLEXIDADE DE ALGORITMOS:

· Medidas de Tempo de Execução
· Complexidade de Tempo e de Espaço
· Notação O para Complexidade
· Pesquisa Sequencial: pior, melhor caso e caso médio
· Função de Complexidade Assintótica
· Classes de Problemas
· Problemas Tratáveis e Intratáveis
· Operações com Notação O
· Técnicas de Análise de Algoritmos
· Análise de um Programa
· Função de Custo de Algoritmos Recursivos
· Equações de Recorrência
· Algoritmos Recursivos
· Recursivos X Iterativos
· Algoritmos de Tentativa e Erro
· Algoritmo do Passeio do cavalo
· Análise do Algoritmo

LISTAS LINEARES:

· Conceito de Listas Lineares Implementação com Arranjos Implementação de Listas com Apontadores Versão Pascal e Java Uso de Nodo-Cabeça
· Aplicação: Inversão de Lista Caminhamento em Sentido Duplo Classificação no Vestibular
· Implementação de Listas com Cursores Listas Duplamente Encadeadas Listas Circulares Listas Duplamente Encadeadas
· Inserção e Remoção de Nodos Implementação de Listas Duplamente Encadeadas
· Conceito de Pilhas Exemplos de Uso de Pilhas: Editor de Texto Implementação com Arranjos Implementação do Tipo
· Pilha em Pascal e Java Implementação de Pilhas com Apontadores
· Conceito de Filas Implementação de Filas com Arranjos Implementação de Filas com apontadores

ÁRVORES:

· Árvores Binárias Árvores Binárias Estendidas Representação Aplicação Propriedades de Árvores Binárias
· Caminhamentos em Árvore: Central, Pré-Ordem e Pós-Ordem Algoritmos de Caminhamento Recursivos e
· Não-Recursivos

Bibliografia
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 (capítulo 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.

3. Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures Sixth Printing - Computer Science Press, Inc., 1976.

4. D. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley, Second Edition, 1973.

5. D. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, Second Edition, 1973.

6. R. Sedgewick, Algorithms, Second Edition, Addison-Wesley, 1988.

7. N. Wirth, Algorithms and Data Structures, Prentice-Hall, 1986.
Katheleen Jensen and Niklaus Wirth, Pascal: User Manual and Report, Springer-Verlag, 1974

<< voltar