Público
Calendário Escolar
2021
2020
Cursos de ingresso
Disciplina
Busca por Disciplinas
Busca por Turmas
Editais
Programa Unificado de Bolsas(PUB)
Edital 2020-2021
PEEG
FAQ
Matrícula Interativa
FAQ
Informações gerais
TUTORIAL - NOVA MATRÍCULA
Jupiterweb em Vídeos
Informações gerais sobre a Graduação
Acesso Restrito
Entrar
Esqueci a Senha
Primeiro Acesso
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 - 2021 - Superintendência de Tecnologia da Informação/USP