Carga horária da disciplina: 4 horas/aula

Professor(es) em 2024-2

Turma 11

Professor: Anderson Almeida Ferreira - e-mail Horários: Segunda-feira (13h30 - 15h10) Quarta-feira (13h30 - 15h10)

Objetivos

Ao final do curso espera-se que os alunos possuam os seguintes conhecimentos e habilidades:
Capacidade para fazer análise de pior e melhor caso do tempo de execução de algoritmos típicos, como algoritmos de ordenação e pesquisa, algoritmos clássicos sobre grafos, etc;
Compreensão sobre o significado da notação usada para expressar ordem de complexidade de algoritmos;
Compreensão do princípio básico de cada uma das técnicas de programação estudadas e dos casos aos quais elas se aplicam;
Habilidade para implementação dos algoritmos estudados e para aplicação dos mesmos na solução de problemas práticos.

Ementa

Medidas de complexidade, análise assintótica de complexidade e notação Big O, Little o, Omega e Theta; análise de algoritmos iterativos e recursivos; medidas empíricas de performance; estratégias de projeto de algoritmos: divisão e conquista, método guloso, programação dinâmica, backtracking, branch and bound, probabilístico, aproximado; classes de complexidade: P, NP, NP-Completo e NP-Difícil.

Conteúdo Programático

- Medidas de complexidade, análise assintótica de complexidade e notação Big O, Little o, Omega e Theta.
        - Panorama e Conceitos Básicos.
        - Medidas de Complexidade (tempo, espaço)
        - Análise Assintótica
- Análise de Algoritmos Iterativos e Recursivos
        - Teorema Mestre
- Medidas Empíricas de Performance
- Estratégias de projeto de algoritmos
        - Divisão e conquista: MergeSort, Medianas, QuickSort e Exponencial
        - Método guloso: Conceitos, Árvores Geradoras Mínimas - Prim & Kruskal, Código de Huffman, Cláusula de Horn, Problema da Mochila e Seleção de atividades
        - Programação dinâmica: Conceitos, Maior Sequência Crescente, Distância de Edição, Problema da Mochila e Multiplicação de Cadeia de Matrizes
        - Backtracking
        - Branch and bound
        - Probabilístico
        - Aproximado
- Classes de complexidade
        - Problemas de Busca - Decisão e Otimização,
        - Classe P
        - Classe NP
        - Classe NP-Completo
        - NP-Difícil
        - Redução de problemas

Bibliografia

- DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos H.; VAZIRANI, Umesh Virkumar. Algoritmos. São Paulo: McGraw-Hill, 2009.
- CORMEN, Thomas; LEISERSON, Charles; RIVEST, Ronald; STEIN, Clifford. Algoritmos: Teoria e Prática. 2. ed. Rio de Janeiro: Campus, 2002.
- SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4. ed. Upper Saddle River: Addison Wesley, 2011.

Bibliografia complementar

- HOROWITZ, Ellis; SAHNI, Sartaj. Fundamentals of computer algorithms. New-Delhi: Galgotia, 1990. ((Computer software engineering series)).
- ZIVIANI, Nivio; BOTELHO, Fabiano Cupertino. Projeto de algoritmos: com implementações em Java e C++. 1 ed. São Paulo: Cengage Learning, 2006.
- GOODRICH, Michael T.; TAMASSIA, Roberto; COPSTEIN, Bernardo. Projeto de algoritmos: fundamentos, análise e exemplos da internet. Porto Alegre: Bookman, 2004.
- KNUTH, Donald Ervin. The art of computer programming. Upper Saddle River: Addison Wesley, 2005.
- WIRTH, Niklaus. Algoritmos e estruturas de dados. Livros Técnicos e Científicos, 1999.