Detalhes
TEORIA DE COMPLEXIDADE I
Nome da Disciplina: TEORIA DE COMPLEXIDADE I
Carga Horária: 60
Créditos: 4
Disciplina Regular: Sim
EMENTA
Análise de Algoritmos. Métodos de Análise de Algoritmos. Teoria da Complexidade dos Algoritmos. Modelos computacionais, Ω, ω ; Crescimento de funções: notações O, o, ω e θ. Somatórios e outras ferramentas matemáticas. Design e Análise de Algoritmos por Indução. A indução como método para projeto de algoritmos. Cálculo da complexidade de algoritmos recursivos. Problemas do tipo “dividir para conquistar”. Prova Matemática da correção de algoritmos. Algoritmos envolvendo sequências e conjuntos. Busca binária. Insertionsort. Selectionsort. Mergesort. Heapsort. Quicksort. Cotas inferiores para problemas de ordenação e busca cujos algoritmos envolvem comparação entre elementos. Radix sort. Bucket sort. Programação Dinâmica. Método Guloso.
BIBLIOGRAFIA
AHO, A. V.; HOPCROFT, J. E.; ULLMAN, J. D. Data Structures and Algorithms. Reading: Addison-Wesley, 1982.
AHO, A. V.; ULLMAN, J. D. Foundations of Computer Science. 1st Ed. New York: W. H. Freeman and Company, 1992.
CORMEN, T.; LEISERSON, C.; RIVEST, R.; STEIN, C. Introduction to Algorithms. New York: MIT Press, 2004.
KNUTH, D. E.. The Art of Computer Programming. Vol 1, Fundamental Algorithms; Vol 2, Seminumerical Algorithms; Vol 3, Sorting and Searching. Reading: Addison-Wesley, 1997.
MANBER, U. Introduction to Algorithms: A Creative Approach. Boston: Addison Wesley, 1989.
HOROWITZ, E.; SAHNI S. Fundamentals of Computer Algorithms. Rockville: Computer Science Press, 1984.
GAREY, M.; JOHNSON, D. Computers and Intractability: a guide to the theory of NP-completeness. New York: Freeman, 1979.
PAPADIMITRIOU, C. H. Computational Complexity. Reading: Addison-Wesley, 1993.
SEDGEWICK, R. Algorithms. Reading: Addison-Wesley,1983.
ZIVIANI, N. Projeto de Algoritmos com Implementação em Pascal e C. 2a. Ed. São Paulo: Thomson, 2004.
AHO, A. V.; ULLMAN, J. D. Foundations of Computer Science. 1st Ed. New York: W. H. Freeman and Company, 1992.
CORMEN, T.; LEISERSON, C.; RIVEST, R.; STEIN, C. Introduction to Algorithms. New York: MIT Press, 2004.
KNUTH, D. E.. The Art of Computer Programming. Vol 1, Fundamental Algorithms; Vol 2, Seminumerical Algorithms; Vol 3, Sorting and Searching. Reading: Addison-Wesley, 1997.
MANBER, U. Introduction to Algorithms: A Creative Approach. Boston: Addison Wesley, 1989.
HOROWITZ, E.; SAHNI S. Fundamentals of Computer Algorithms. Rockville: Computer Science Press, 1984.
GAREY, M.; JOHNSON, D. Computers and Intractability: a guide to the theory of NP-completeness. New York: Freeman, 1979.
PAPADIMITRIOU, C. H. Computational Complexity. Reading: Addison-Wesley, 1993.
SEDGEWICK, R. Algorithms. Reading: Addison-Wesley,1983.
ZIVIANI, N. Projeto de Algoritmos com Implementação em Pascal e C. 2a. Ed. São Paulo: Thomson, 2004.
VOLTAR

Nome da Disciplina: TEORIA DE COMPLEXIDADE I
Carga Horária: 60
Créditos: 4
Obrigatória: Sim
EMENTA
Análise de Algoritmos. Métodos de Análise de Algoritmos. Teoria da Complexidade dos Algoritmos. Modelos computacionais, Ω, ω ; Crescimento de funções: notações O, o, ω e θ. Somatórios e outras ferramentas matemáticas. Design e Análise de Algoritmos por Indução. A indução como método para projeto de algoritmos. Cálculo da complexidade de algoritmos recursivos. Problemas do tipo “dividir para conquistar”. Prova Matemática da correção de algoritmos. Algoritmos envolvendo sequências e conjuntos. Busca binária. Insertionsort. Selectionsort. Mergesort. Heapsort. Quicksort. Cotas inferiores para problemas de ordenação e busca cujos algoritmos envolvem comparação entre elementos. Radix sort. Bucket sort. Programação Dinâmica. Método Guloso.
BIBLIOGRAFIA
AHO, A. V.; HOPCROFT, J. E.; ULLMAN, J. D. Data Structures and Algorithms. Reading: Addison-Wesley, 1982.
AHO, A. V.; ULLMAN, J. D. Foundations of Computer Science. 1st Ed. New York: W. H. Freeman and Company, 1992.
CORMEN, T.; LEISERSON, C.; RIVEST, R.; STEIN, C. Introduction to Algorithms. New York: MIT Press, 2004.
KNUTH, D. E.. The Art of Computer Programming. Vol 1, Fundamental Algorithms; Vol 2, Seminumerical Algorithms; Vol 3, Sorting and Searching. Reading: Addison-Wesley, 1997.
MANBER, U. Introduction to Algorithms: A Creative Approach. Boston: Addison Wesley, 1989.
HOROWITZ, E.; SAHNI S. Fundamentals of Computer Algorithms. Rockville: Computer Science Press, 1984.
GAREY, M.; JOHNSON, D. Computers and Intractability: a guide to the theory of NP-completeness. New York: Freeman, 1979.
PAPADIMITRIOU, C. H. Computational Complexity. Reading: Addison-Wesley, 1993.
SEDGEWICK, R. Algorithms. Reading: Addison-Wesley,1983.
ZIVIANI, N. Projeto de Algoritmos com Implementação em Pascal e C. 2a. Ed. São Paulo: Thomson, 2004.
AHO, A. V.; ULLMAN, J. D. Foundations of Computer Science. 1st Ed. New York: W. H. Freeman and Company, 1992.
CORMEN, T.; LEISERSON, C.; RIVEST, R.; STEIN, C. Introduction to Algorithms. New York: MIT Press, 2004.
KNUTH, D. E.. The Art of Computer Programming. Vol 1, Fundamental Algorithms; Vol 2, Seminumerical Algorithms; Vol 3, Sorting and Searching. Reading: Addison-Wesley, 1997.
MANBER, U. Introduction to Algorithms: A Creative Approach. Boston: Addison Wesley, 1989.
HOROWITZ, E.; SAHNI S. Fundamentals of Computer Algorithms. Rockville: Computer Science Press, 1984.
GAREY, M.; JOHNSON, D. Computers and Intractability: a guide to the theory of NP-completeness. New York: Freeman, 1979.
PAPADIMITRIOU, C. H. Computational Complexity. Reading: Addison-Wesley, 1993.
SEDGEWICK, R. Algorithms. Reading: Addison-Wesley,1983.
ZIVIANI, N. Projeto de Algoritmos com Implementação em Pascal e C. 2a. Ed. São Paulo: Thomson, 2004.