Jupiterweb

Informações da Disciplina

Preparar para impressão

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação

Instituto de Matemática e Estatística

Ciência da Computação

Disciplina: MAC0323 - Algoritmos e Estruturas de Dados II

Algorithms and Data Structures II

Créditos Aula:	4
Créditos Trabalho:	2
Carga Horária Total:	120 h
Tipo:	Semestral
Ativação:	01/01/2020	Desativação:

Objetivos

Apresentar estruturas de dados e algoritmos amplamente utilizados e discutir sua implementação e seu desempenho.

Present widely used data structures and algorithms and discuss their implementation and performance.

Docente(s) Responsável(eis)

	91288 - Carlos Eduardo Ferreira
	55029 - Cristina Gomes Fernandes
	26472 - Paulo Feofiloff
	88134 - Yoshiharu Kohayakawa

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.

Abstract data types and their implementations. Symbol tables: balanced search trees, hash tables. Graphs: depth-first search, breadth-first search. Text processing: regular expressions, pattern matching, data compression.

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).

Abstract data types and their implementations. Time and space complexity analysis (worst case, average case, amortized analysis, empirical estimates). Symbol tables: balanced search trees, hash tables, ternary search tries. Graphs: depth- rst search, breadth- rst search, shortest paths (Dijkstra's algorithm), topological sort, strong components. Text processing: regular expressions and automata, pattern matching (KMP algorithm, Rabin-Karp algorithm), data compression (Huffman codes), su x arrays. Optional topics: B trees, LZW algorithm for text compression, memory management (garbage collection).

Avaliação

Método

Média ponderada de provas e exercícios.

Critério

A média ponderada tem que ser maior ou igual a 5 para aprovação.

Norma de Recuperação

1 prova de recuperação.

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, 3ª ed., Elsevier, 2013.
P. Morin, Open Data Structures: An Introduction, AU Press, 2013.
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.

Clique para consultar os requisitos para MAC0323

Clique para consultar o oferecimento para MAC0323