MAC0323: Ementa oficial
Esta é a ementa oficial da disciplina
MAC0323 (Estruturas de Dados).
Confira no
Sistema Júpiter
e
no antigo
catálogo do IME.
A ementa está um pouco desatualizada.
Objetivos
Estudo das diversas estruturas de dados, sua manipulação e suas aplicações.
Programa
-
Listas ligadas: listas simples, duplas, circulares, ortogonais e matrizes.
-
Alocação dinâmica de memória.
-
Pilhas e filas.
-
Árvores: implementação, algoritmos de busca, inserção e remoção.
-
Árvores binárias de busca, árvores balanceadas: AVL, rubro-negras, B-árvores.
-
Representação de conjuntos.
-
Estruturas abstratas de dados, encapsulamento.
-
Exemplos de aplicações de estruturas de dados.
Carga horária
Créditos Aula: 4
Créditos Trabalho: 2
Carga Horária Total: 120h
Tipo: Semestral
Ativação: 1/1/2003
Critério de avaliação
Média ponderada de provas e exercícios.
Bibliografia
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
"Introduction to Algorithms",
2nd ed., McGraw-Hill, 2001.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
"Algoritmos - Teoria e Prática",
Campus, 2002.
-
J.L. Szwarcfiter, L. Markenzon,
"Estruturas de Dados e seus Algoritmos",
Livros Técnicos e Científicos, 1994.
-
D.E. Knuth, "The Art of Computer Programming",
vols. 1 e 3, Addison-Wesley, 1973.
-
N. Wirth,
"Algorithms and Data Structures",
Prentice Hall, 1986.
-
A.V. Aho, J.E. Hopcroft, J.D. Ullman,
"Data Structures and Algorithms",
Addison-Wesley, 1983.
-
A.V. Aho, J.D. Ullman,
"Foundations of Computer Science",
Computer Science Press, 1992.
-
Y. Langsam, M.J. Augenstein, A.M. Tenenbaum,
"Data Structures Using C and C++", Prentice Hall, 1996.
Pré-Requisitos
MAC0122 (Princípios de Desenvolvimento de Algoritmos)
MAC0323: nova ementa, a partir de 2015
MAC0323 (Algoritmos e Estruturas de Dados II)
Objetivos
Apresentar estruturas de dados e algoritmos amplamente utilizados
e discutir sua implementação e seu desempenho.
Programa resumido
-
Tipos abstratos de dados
e suas implementações.
-
Tabelas de símbolos:
árvores de busca balanceadas,
tabelas de espalhamento (hashing).
-
Grafos:
busca em profundidade,
busca em largura.
-
Processamento de texto:
expressões regulares,
busca de padrões,
compressão de dados.
Programa
-
Tipos abstratos de dados
e suas implementações.
Análise da complexidade de tempo e espaço
(pior caso, caso médio, análise amortizada,
estimativas empíricas).
-
Tabelas de símbolos:
árvores de busca balanceadas,
tabelas de espalhamento (hashing),
tries ternárias de busca.
-
Grafos:
busca em profundidade,
busca em largura,
caminhos mínimos (algoritmo de Dijkstra),
ordenação topológica,
componentes fortes.
-
Processamento de texto:
expressões regulares e autômatos,
busca de padrões
(algoritmo KMP,
algoritmo de Rabin-Karp),
compressão de dados
(códigos de Huffman),
vetores de sufixos.
-
Tópicos opcionais:
árvores B,
algoritmo LZW de compressão de texto,
gerenciamento de memória (coleta de lixo).
Avaliação: Método
-
Aulas expositivas e laboratório de programação.
Avaliação: Critério
- Média ponderada de provas e exercícios.
Bibliografia
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
"Introduction to Algorithms", 3rd ed.,
McGraw-Hill, 2001.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
"Algoritmos", 3a. ed.,
Elsevier, 2013.
-
P. Morin,
"Open Data Structures: An Introduction",
AU Press, 2013.
URL: http://opendatastructures.org/
-
E.S. Roberts,
"Programming Abstractions in C: a Second Course in Computer Science",
Addison-Wesley, 1997.
-
R. Sedgewick,
"Algorithms in C", 3rd. ed.,
Addison-Wesley, 1998.
-
R. Sedgewick, K. Wayne,
"Algorithms", 4th. ed.,
Addison-Wesley, 2011.
Pré-requisitos
-
MAC0122 (Algoritmos e Estruturas de Dados I)
(atual Princípios de Desenvolvimento de Algoritmos)
