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)

 

>>Alairm ::: Comunicação<<
>>Técnicas Avançadas para Desenvolvimento de Software<< >>Engenharia de Software<< >>Análise de Sistemas<< >>Métodos e Ferramentas da Computação<< >>Regulamento<< >>Página Inicial<< >>Disciplinas do CEI<< >>Professores  da Especialização em Informática<< DCC/UFMG >>Universidade Federal de Minas Gerais<< >>Desenvolvimento de Aplicações Distribuídas e Móveis<<