|
|
| 3° período | |||
| Código: BiSuCOM.542 |
Nome da disciplina: Projeto e Análise de Algoritmos |
||
| Carga horária total: 60 h |
Abordagem metodológica: Teórica |
Natureza: Obrigatória |
|
| Carga horária teórica: 60 h |
Carga horária prática: Nenhuma |
||
| Ementa: Fundamentos matemáticos para Projeto e Análise de Algoritmos. Conceitos em complexidade computacional. Prova de corretude algorítmica baseada em indução matemática. Contagem de tempo de execução. Notação assintótica. Tempo de execução com notação assintótica. Comparação de performance algorítmica. Recorrência algorítmica. Divisão e conquista. Análise de complexidade em algoritmos de ordenação iterativa e recorrente: Bubble Sort, Selection Sort, Insertion Sort, Quick sort e Merge Sort. Análise de recorrência com métodos da substituição, iterativo, árvore de recursão e teorema mestre. Redução entre problemas. Classes de problemas P, NP, NP-Completo e NP-Difícil. |
|||
|
Objetivo(s): Objetivo Geral: Aplicar os fundamentos matemáticos e as técnicas de análise de algoritmos para criar projetos eficientes de algoritmos avaliando sua complexidade computacional. Objetivos Específicos: Utilizar conceitos de complexidade computacional para justificar a escolha de algoritmos por meio da sua eficiência. Implementar algoritmos de ordenação e comparar suas performances com base na notação assintótica. Calcular o tempo de execução de algoritmos utilizando notações como O, Ω e Θ. Demonstrar a corretude de algoritmos por meio de indução matemática. Classificar problemas de acordo com as classes P, NP, NP-Completo e NP-Difícil. Selecionar e utilizar diferentes métodos de análise de recorrência para delimitar a complexidade de algoritmos. Traçar estratégias de divisão e conquista para elaborar soluções eficientes em problemas computacionais. |
|||
|
Bibliografia básica: SIPSER, Michael. Introdução à teoria da computação. 2. ed. São Paulo: Cengage Learning, 2007. 459 p. ISBN 9788522104994. Acervo: 004 S617i. LITNZMAYER, Carla Negri; MOTA, Guilherme Oliviera. Análise de Algoritmos e Estrutura de Dados. 1. ed. São Paulo: Independente, 2023. 425 p. Disponível em <http://professor.ufabc.edu.br/~carla.negri/cursos/materiais/Livro-Analise.de.Algoritmos.pdf>. Acesso em: 6 de Setembro de 2024. ARAÚJO, Graziela Santos de. Estruturas de dados: Algoritmos, análise de complexidade e implementações em Java e C++. 1. ed. São Paulo: Pearson, 2010. 433 p. ISBN 9788576058816. Disponível em <https://pergamum.ifmg.edu.br/acervo/5018315>. Acesso em: 6 de Setembro de 2024. |
|||
|
Bibliografia complementar: MANZANO, José Augusto. Algoritmos: Lógica para desenvolvimento de programação de computadores. 26. ed. São Paulo: Érica, 2012. 328 p. ISBN 9788536502212. Acervo: 005.1 M296a. CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford; MARQUES, Arlete Simile. Algoritmos: Teoria e prática. 1. ed. Rio de Janeiro: Elsevier, 2012. 926 p. ISBN 9788535236996. Acervo: 005.1 A394. DOBRUSHKIN, V. A.. Métodos para análise de algoritmos. 1. ed. Rio de Janeiro: LTC, 2012. 659 p. ISBN 9788521620662. Acervo: 005.1 D634m. GERSTING, Judith L.. Fundamentos Matemáticos para a Ciência da Computação: Um tratamento moderno de matemática discreta. 5. ed. Rio de Janeiro: LTC, 2004. 597 p. ISBN 9788521614227. Acervo: 004.0151 G383f. ZIVIANI, Nívio. Projeto de algoritmos: Com implementações em PASCAL e C. 3. ed. São Paulo: Cengage Learning, 2011. 639 p. ISBN 9788522110506. Acervo: 005.1 Z82p. |
|||