Skip to content

Algoritmos e Estrutura de Dados Avançado

1º sem 2024

Ementa

Revisão sobre Estrutura de Dados. Linguagens de máquina e linguagem de montagem Assembly. Análise de Complexidade Assintótica. Noções básicas de Ordenação: InsertionSort, MergeSort, Quicksort e Heapsort. Filas de prioridade. Heaps esquerdistas e heaps binomiais. Estruturas de dicionário: acesso direto, transformação de chave, funções Hash. Colisões e Transbordamento. Hashing para Arquivos Extensíveis. Estruturas balanceadas e auto-ajustáveis. Árvore AVL, Vermelho-Preto, B, B+ e de espalhamento. Estruturas multidimensionais. Estruturas de dados aplicadas em banco de dados espaciais. Árvore Point-Quad e Polygon-Quad. Árvore R. Tries. Trie R-Way. Trie Ternária. Árvore PATRICIA. Arquivos Invertidos. Compressão de Textos em Linguagem Natural, Codificação RLE. Codificação de Huffman Usando Bytes, Huffman Adaptativo, Codificação de Lempel-Ziv.

Referências

  • Adaptive Huffman coding. (2023). In Wikipedia. https://en.wikipedia.org/w/index.php?title=Adaptive_Huffman_coding
  • Algoritmos e Estruturas de Dados 2. (n.d.). Retrieved February 21, 2024, from https://www.youtube.com/playlist?list=PL5TPkym335qz6i9AYI5CMuxIXRO03JtWj
  • Alves, R. (2010). Árvores B. Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Norte, IFRN. https://docente.ifrn.edu.br/robinsonalves/disciplinas/estruturas-de-dados-nao-lineares/ArvBrl.pdf
  • Artero, M. A., & Scheffer, V. C. (2018). Algoritmos e lógicas de programação. EDE.
  • Árvore Patricia. (2022). In Wikipédia, a enciclopédia livre. https://pt.wikipedia.org/w/index.php?title=%C3%81rvore_Patricia
  • Árvore ternária de busca. (2024). In Wikipédia, a enciclopédia livre. https://pt.wikipedia.org/w/index.php?title=%C3%81rvore_tern%C3%A1ria_de_busca
  • Assis, G. T. de. (2018). Introdução à Estrutura de Dados Espaciais & QuadTree. Universidade Federal de Ouro Preto, UFOP. http://www.decom.ufop.br/guilherme/BCC203/geral/ed2_introducao-estruturas-dados-espaciais_victor.pdf
  • Bentley, J. L., & Sedgewick, R. (1997). Fast algorithms for sorting and searching strings. Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 360–369. http://webhotel4.ruc.dk/~keld/teaching/algoritmedesign_f08/Artikler/04/Bentley99.pdf
  • Boeres, M. C. S. (2018). Hashing (Tabela de Dispersão). IFF. http://www2.ic.uff.br/~boeres/slides_ed/ed_TabelaHash.pdf
  • Bueno, M. (2009). Árvores Trie e Patricia. Universidade Católica de Pernambuco, UNICAP. https://marciobueno.com/arquivos/ensino/ed2/ED2_06_Trie_Patricia.pdf
  • Cayres, C. E. (2017). Estrutura de dados. EDE.
  • Chiossi, T. C. dos S. (2010). Compressão de Dados—Lempel-Ziv. Unicamp. https://www.ic.unicamp.br/~thelma/gradu/MC326/2010/Slides/Aula03c-compressao-Lempel-Ziv.pdf
  • Codificação de Huffman. (2019). In Wikipédia, a enciclopédia livre. https://pt.wikipedia.org/w/index.php?title=Codifica%C3%A7%C3%A3o_de_Huffman
  • Codificação run-length. (2021). In Wikipédia, a enciclopédia livre. https://pt.wikipedia.org/w/index.php?title=Codifica%C3%A7%C3%A3o_run-length
  • Conci, A. (2014). Solid modeling em C. G. Universidade Federal Fluminense, UFF. http://profs.ic.uff.br/~aconci/Solidos.pdf
  • Cormen, T. H. (2012). Algoritmos—Teoria e Prática. GEN LTC.
  • Day-Stout-Warren Algorithm Explained. (n.d.). S. M. Unlisted. Retrieved February 21, 2024, from http://www.smunlisted.com/day-stout-warren-dsw-algorithm.html
  • Feofiloff, P. (2019). Filas Priorizadas. IME-USP. https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/priority.html
  • Feofiloff, P. (2022). Tries (árvores digitais). IME-USP. https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/tries.html
  • Fernandes, C. G. (2020). Árvores esquerdistas e heaps binomiais. IME-USP. https://www.ime.usp.br/~cris/aulas/20_2_323/slides/aula07.pdf
  • Fonseca, M. S. P. (2015). Processamento de Cadeias de Caracteres. Universidade Tecnológica Federal do Paraná, UTFPR. https://pessoal.dainf.ct.utfpr.edu.br/maurofonseca/lib/exe/fetch.php?media=cursos:if63c:if63ced_10_cadeias.pdf
  • Fortes, R. (2014). Análise de Algoritmos. Universidade Federal de Ouro Preto, UFOP. http://www.decom.ufop.br/reinaldo/site_media/uploads/2014-01-bcc202/aulas/aula_04_-analise_de_algoritmos(parte_1)_(v1).pdf
  • Freire, A. da S. (2018). Compressor de Ziv e Lempel. USP. https://edisciplinas.usp.br/mod/resource/view.php?id=2423088
  • Grupo de Estudos em Haskell da UFABC :: Grupo de Estudos de Haskell—UFABC. (n.d.). Retrieved February 21, 2024, from https://haskell.pesquisa.ufabc.edu.br/
  • Guedes, A. L. P. (2023). Análise de Algoritmos. UFPR. https://www.inf.ufpr.br/andre/Disciplinas/CI1165-2023-2/
  • Guerra, R. (2014). Árvore AVL. Universidade Federal de Rio Grande, FURG. https://youtu.be/3zmjQlJhBLM
  • Htay, M. M. (2006). The DSW Algorithm. Radford University. https://sites.radford.edu/~mhtay/ITEC360/webpage/Lecture/06_p2.pdf
  • Inverted Index. (2018, May 30). GeeksforGeeks. https://www.geeksforgeeks.org/inverted-index/
  • Kleinberg, J., & Tardos, É. (2013). Algorithm Design. Pearson. https://www.google.com.br/books/edition/Algorithm_Design/ROiUngEACAAJ
  • Knuth, D. E. (1997). The art of computer programming. Pearson Education.
  • Kumar, C. (Director). (2017, May 18). Dynamic Huffman coding “Abracadabra.” https://www.youtube.com/watch?v=h5_ix_DnOtU
  • Leftist Tree / Leftist Heap—GeeksforGeeks. (n.d.). Retrieved February 21, 2024, from https://www.geeksforgeeks.org/leftist-tree-leftist-heap/
  • Listas invertidas. (2013). In Wikipédia, a enciclopédia livre. https://pt.wikipedia.org/w/index.php?title=Listas_invertidas
  • LZW. (2023). In Wikipédia, a enciclopédia livre. https://pt.wikipedia.org/w/index.php?title=LZW
  • Machusak, E. (2003). The Notorious PM Quadtree. http://www.cs.umd.edu/~meesh/420/ContentBook/FormalNotes/PMQuadtree/pm_quadtree_local.pdf
  • Manacero Jr., A. (2007). Árvores Balanceadas. Unesp. https://www.dcce.ibilce.unesp.br/~aleardo/cursos/ed2/arvbalanc.pdf
  • Nikander, J. (2019). Data structures and algorithms for geometric models 2. Aalto University. https://mycourses.aalto.fi/pluginfile.php/926315/mod_folder/content/0/data%20structures%20and%20algorithms%202.pdf?forcedownload=1
  • Pei, J. (2008). R-Tree. Simon Fraser University, SFU. https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf
  • Roberts, E. (1997). Programming Abstractions in C: A Second Course in Computer Science. Addison Wesley.
  • Roman, N. T., & Nunes, F. L. S. (2017). Complexidade Assintótica. USP. https://edisciplinas.usp.br/mod/resource/view.php?id=2197531&forceview=1
  • Rovai, K. R. (2018). Algoritmos e estrutura de dados. EDE. http://cm-kls-content.s3.amazonaws.com/201801/INTERATIVAS_2_0/ALGORITMOS_E_ESTRUTURA_DE_DADOS/U1/LIVRO_UNICO.pdf
  • Rovai, K. R., Scheffer, V. C., & Artero, M. A. (2020). Algoritmos e programação estruturada. EDE.
  • Santana, G. A., Silva, N. dos S., & Mozer, M. (2018). Linguagens de programação e estruturas de dados. EDE.
  • Santos, C. (2010). Compressão de Dados Multimídia. https://docplayer.com.br/3862431-Compressao-de-dados-multimidia.html
  • Scheffer, V. C. (2024). Algoritmos de Ordenação.
  • Scheffer, V. C., & Artero, M. A. (2018). Algoritmos e técnicas de programação. EDE.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms. Addison-Wesley Professional.
  • Souza, J. F. de. (2010). Strings (Compressão). Universidade Federal de Juiz de Fora, UFJF. https://docplayer.com.br/3862587-Strings-compressao-estrutura-de-dados-ii-jairo-francisco-de-souza.html
  • Souza, J. F. de. (2012a). Hashing para Arquivos Extensíveis. Universidade Federal de Juiz de Fora.
  • Souza, J. F. de. (2012b). Hashing—Resolução de Colisões. Universidade Federal de Juiz de Fora.
  • Tanenbaum, A. S. (2013). Cap. 7—O nível de linguagem de montagem. In Organização Estruturada de Computadores. Pearson.
  • Tomaschewski Netto, G. (2019). Hashing. Universidade Federal de Pelotas, UFPEL. http://netto.ufpel.edu.br/lib/exe/fetch.php?media=aed2:hashing.pdf
  • Trie. (2018). In Wikipédia, a enciclopédia livre. https://pt.wikipedia.org/w/index.php?title=Trie
  • Vitter, J. S. (2001). External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33(2), 209–271. https://doi.org/10.1145/384192.384193
  • Ziviani, N. (2014). Compressão de Textos. Universidade Federal de Minas Gerais, UFMG. https://homepages.dcc.ufmg.br/~nivio/cursos/ri14/transp/text-compression.pdf

Repositório

https://github.com/efurlanm/teaching/tree/main/aed/



Last edited: 2024-11-17