Estruturas e Complexidade de Algoritmos
2024/2 - Turma 0300
Ementa
Estudo e análise de estruturas de dados avançadas, pesquisa, ordenação, hash e grafos, bem como complexidade de algoritmos, envolvendo classes de problemas, notações para complexidade, soluções heurísticas e força-bruta.
Competências
* Identificar problemas que tenham solução algorítmica;
* Resolver problemas usando ambientes de programação;
* Compreender e explicar as dimensões quantitativas de um problema;
* Reconhecer a importância do pensamento computacional no cotidiano e sua aplicação em circunstâncias apropriadas e em domínios diversos;
* Identificar e analisar requisitos e especificações para problemas específicos e planejar estratégias para suas soluções.
Objetivos
OBJTIVO GERAL
Proporcionar ao aluno uma visão geral das estruturas de dados e suas complexidades, bem como a aplicação na resolução de problemas algorítmicos.
OBJETIVOS ESPECÍFICOS
* Apresentar a utilização de algoritmos complexos para resolução de problemas algorítmicos;
* Implementar algoritmos de classificação de dados em memória e externos, conhecendo sua complexidade.
* Implementar algoritmos de pesquisa de dados em memória, conhecendo sua complexidade.
Programa
Árvores binárias de busca balanceadas
Árvores B
Análise e complexidade de algoritmos
Algoritmos de Ordenação de Dados
Algoritmos de Pesquisa de Dados
Tabelas Hashing
Algoritmos para problemas básicos em grafos.
Metodologia
* Aulas expositivas apresentando o assunto de forma lógica e estruturada através de exemplos práticos, com foco no incentivo da participação do aluno por meio de discussões, comentários e verificações em experimentos práticos;
* São apresentados problemas, estimulando o acadêmico a buscar soluções satisfatórias, comparando com a realidade os conhecimentos teóricos adquiridos;
* Para fixar os conteúdos são apresentados trabalhos individuais, como lista de exercícios, ao final das aulas expositivas, e para a troca de conhecimentos e experiências entre os acadêmicos serão realizados trabalhos relacionando os assuntos discutidos nas aulas com questões práticas;
Web Aula: 03 aulas online serão disponibilizadas em um sistema web, compostas por recursos didáticos - como textos, apresentações e vídeos - e atividades individuais ou em grupo, seguindo as determinações da Portaria MEC nº 2.117, de 06 de dezembro de 2019.
Avaliação
O aluno será avaliado ao longo do semestre letivo em duas avaliações de grau, a saber:
* Grau Um (G1, com peso 1), composta por:
- Trabalhos: 4,0
- Prova individual, com conteúdo do primeiro bimestre letivo: 6,0
* Grau Dois (G2, com peso 2), composta por:
- Trabalhos: 4,0
- Prova individual, com conteúdo do segundo bimestre letivo: 6,0
A Média Parcial (MP) será a média ponderada entre G1 e G2: MP = (G1 + 2 x G2) / 3.
Será aprovado o aluno que alcançar a MP igual ou superior a 6,0 (seis).
O aluno, com ou sem aprovação, que desejar aumentar a sua MP e atingir frequência mínima de 75%, terá direito de realizar a prova de Exame Final (EF).
Para o aluno que fizer a prova de EF, a Média Final (MF) será a média ponderada entre MP (peso um) e EF (peso dois). Logo: MF = (MP + EF x 2) / 3.
Para os alunos que não realizarem a prova de EF a MF será igual a MP.
Será aprovado o aluno que alcançar a MF igual ou superior a 6,0 (seis) e atingir, no mínimo, 75% de frequência.
Bibliografia
Básica
DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algoritmos. Porto Alegre: AMGH, 2010. 9788563308535. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788563308535/. Acesso em: 08 abr. 2022.
SWARCFITER, Jayme Luiz. Estrutura de dados e seus algoritmos. 2. ed. Rio de Janeiro: LTC, 1994.
TOSCANI, Laira Vieira; VELOSO, Paulo A. S. Complexidade de algoritmos: análise, projeto e métodos. 3. ed. Porto Alegre : Bookman, 2012. E-book. [Minha Biblioteca]. Disponível em: https://integrada.minhabiblioteca.com.br/reader/books/9788540701397. Acesso em: 7 abr. 2022.
Complementar
BOAVENTURA NETTO, Paulo Oswaldo. Grafos: teoria, modelos, algoritmos. 5. ed. São Paulo: E. Blücher, 2011.
PUGA, Sandra; RISSETTI, Gerson. Lógica de programação e estrutura de dados: com aplicações em Java. 2. ed. São Paulo: Pearson, 2016. E-book. [BV Pearson]. Disponível em: https://plataforma.bvirtual.com.br/Acervo/Publicacao/447. Acesso em: 30 mar. 2022.
RABUSKE, Márcia Aguiar. Introdução à teoria dos grafos. Florianópolis: Ed. UFSC, 1992.
SERPA, Matheus da S.; RODRIGUES, Thiago N.; ALVES, Ítalo C.; et al. Análise de algoritmos. Porto Alegre: SAGAH, 2021. E-book. [Minha Biblioteca]. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9786556901862/. Acesso em: 8 abr. 2022.
TERADA, Routo. Desenvolvimento de algoritmos e estruturas de dados. São Paulo: McGraw-Hill, 1991.
Material Digital
https://ulbra-to.br/graphlive/
https://ulbra-to.br/estruturasdedados/
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/
https://www.youtube.com/playlist?list=PLxZdKEtmy3GRhETjatYq9v3O8VVt3YrNb
