MAC0323  Algoritmos Estruturas de Dados II

Por | Em

Até 2014 se chamou MAC0323 Estruturas de Dados.

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.

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

RESPONSÁVEIS:  Arnaldo Mandel, Carlos Eduardo Ferreira, Cristina Gomes Fernades, Paulo Feofiloff, Yoshiharu Kohayakawa.

PRÉ-REQUISITOS:  MAC0121 e MAC0216.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS:  8 horas, 4 créditos-aula e 2 créditos-trabalho.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM:  Média ponderada de provas e exercícios.

BIBLIOGRAFIA BÁSICA: 

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

OBSERVAÇÃO:  Disciplina obrigatória no currículo do BCC.

 

[Veja dados da disciplina no JúpiterWeb]

Alguns oferecimentos da disciplina: 2013/1, 2012/1, 2008/1, 1998/1, 1999/1, 1999/1, 2001/1, 2008/1, 2012, 2013, 2014, 2015.