MAC0385  Estruturas de Dados Avançadas

Por | Em

OBJETIVOS:  Familiarizar estudantes com estruturas de dados amplamente utilizadas no cotidiano que não são estudadas em disciplinas usuais. Produzir uma biblioteca com implementações da maioria das estruturas de dados estudadas.

PROGRAMA RESUMIDO:  LCA, estruturas de dados temporais, cinéticas, sucintas, árvores de segmentos, otimalidade dinâmica, árvores splay, grafos dinâmicos.

PROGRAMA:  Serão escolhidos tópicos da seguinte lista: 1. Ancestral comum mais próximo, ancestral de nível, árvores de segmentos. 2. Estruturas de dados temporais: persistência e retroatividade. 3. Estruturas de dados cinéticas. 4. Conjectura da otimalidade dinâmica. 5. Conexidade em grafos dinâmicos. 6. Busca de padrão em textos gigantes. 7. Estruturas de dados sucintas. 8. Hierarquia de memória.

RESPONSÁVEIS:  Cristina Gomes Fernandes, Jose Coelho de Pina Junior.

PRÉ-REQUISITOS:  MAC0323.

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

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM:  Média ponderada das notas obtidas nas implementações e entrevistas.

BIBLIOGRAFIA BÁSICA: 

  • Peter Brass. Advanced Data Structures, Cambridge University Press, 2008.
  • Yan S. Couto, Algoritmos em Sequências, Trabalho de Conclusão de Curso, IME­USP, 2016.
  • Yan S. Couto, Estrutura de Dados Persistentes, Dissertação de Mestrado, IME­USP, 2019.
  • Erik D. Demaine, John Iacono, and Stefan Langerman, Retroactive Data Structures, Transactions on Algorithms, Volume 3, Issue 2, May 2007, Article No. 13.
  • James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, 38(1):86–124, 1989.
  • Dan Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, EBL­Schweitzer. Cambridge University Press, 1997.
  • Donald Knuth, The Art of Computer Programming, Sorting and Searching, Vol. 3, Third Edition, Reading, Massachusetts: Addison­Wesley, 2011.
  • Dinesh P. Mehta and Sartaj Sahni (Editors), Handbook on Data Structures and Applications, Chapman & Hall/CRC, 2004.
  • Pat Morin, Open Data Structures: An Introduction, UBC Press; 31st ed. edition (September 19, 2013).
  • Gabriel de Russo e Carmo, O Problema da Conectividade Dinâmica em Grafos, Trabalho de Conclusão de Curso, IME­USP, 2018.

OBSERVAÇÃO:  Disciplina optativa nos currículos do BCC.

 

[Veja dados da disciplina no JúpiterWeb]