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: MAC0385 - Estruturas de Dados Avançadas
Advanced Data Structures

Créditos Aula: 4
Créditos Trabalho: 2
Carga Horária Total: 120 h
Tipo: Semestral
Ativação: 01/01/2023 Desativação:

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.
 
Familiarize students with broadly and commonly used data structures that are not studied in usual courses. Design a library with implementations of most of the data structures studied.
 
 
Docente(s) Responsável(eis)
55029 - Cristina Gomes Fernandes
91267 - Jose Coelho de Pina Junior
 
Programa Resumido
LCA, estruturas de dados temporais, cinéticas, sucintas, árvores de segmentos, otimalidade dinâmica, árvores splay, grafos dinâmicos.
 
LCA, temporal, kinetic, and succinct data structures, segment trees, dynamic optimality, splay trees, dynamic graphs.
 
 
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.
 
Topics from the ones below will be selected: 1. Lowest common ancestor, level ancestor, segment trees. 2. Temporal data structures: persistence and retroactivity. 3. Kinetic data structures. 4. Dynamic optimality conjecture. 5. Connectivity in dynamic graphs. 6. Pattern search in huge texts.
 
 
Avaliação
     
Método
Implementação de várias das estruturas de dados abordadas na disciplina. Entrevistas para apresentação das implementações.
Critério
Média ponderada das notas obtidas nas implementações e entrevistas.
Norma de Recuperação
Não há recuperação.
 
Bibliografia
     
Bibliografia Básica: 

1. Yan S. Couto, Algoritmos em Sequências, Trabalho de Conclusão de Curso, IME-­USP, 2016.

2. Yan S. Couto, Estrutura de Dados Persistentes, Dissertação de Mestrado, IME­-USP, 2019. 

3. Erik D. Demaine, John Iacono, and Stefan Langerman. Retroactive Data Structures, Transactions on Algorithms, Volume 3, Issue 2, May 2007, Article No. 13. 

4. Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. EBL­Schweitzer. Cambridge University Press, 1997. 

5. Gabriel de Russo e Carmo, O Problema da Conectividade Dinâmica em Grafos, Trabalho de Conclusão de Curso, IME­-USP, 2018.

Bibliografia Complementar: 

1. Peter Brass. Advanced Data Structures, Cambridge University Press, 2008. 

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

3. Donald Knuth, The Art of Computer Programming, Sorting and Searching, Vol. 3, Third Edition, Reading, Massachusetts: Addison­Wesley, 2011. 

4. Dinesh P. Mehta and Sartaj Sahni (Editors). Handbook on Data Structures and Applications, Chapman & Hall/CRC, 2004. 

5. Pat Morin, Open Data Structures: An Introduction, UBC Press; 31st ed. edition (September 19, 2013).
 

Clique para consultar os requisitos para MAC0385

Clique para consultar o oferecimento para MAC0385

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