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
|