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

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