Informa??es da Disciplina

 Preparar para impressão 
Júpiter - Sistema 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/2016 Desativação: 31/12/2019

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-first search, breadth-first 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), suffix arrays. Optional topics: B trees, LZW algorithm for text compression, memory management (garbage collection).
 
 
Avaliação
     
Método
Critério
Média ponderada de provas e exercícios.
Norma 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

Créditos | Fale conosco
© 1999 - 2019 - Superintendência de Tecnologia da Informação/USP