Objetivo Aprender e ensinar análise de algoritmos em condições extremas de temperatura ambiente.
Código MCTA003-13(BC1435). TPI 4-0-4. Recomendações Algoritmos e Estruturas de Dados; Matemática Discreta. Horário 3ª as 19hs e 5ª as 21hs na 301-3. Ementa Conceitos básicos. Análise de Complexidade: melhor caso, caso médio e pior caso, estudo de caso. Relações de recorrência. Complexidade de Problemas: limitantes para a Complexidade de um problema, classes de problemas, intratabilidade.
Referências [+]
- DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algoritmos. [518.1 DASa]
- MANBER, Udi. Introduction to algorithms: a creative approach. [005.73 MANBin]
- CORMEN, Thomas H et al. Algoritmos : Teoria e prática [005.1 CORa]
Bibliografia básica
TRÊS PROVAS. Confira as datas na programação ao lado.
Links
- Jeff Erickson, Algorithms, Etc.
- 15 Sorting Algorithms in 6 Minutes
- Provas antigas
- The Algorithm: Idiom of Modern Science by Bernard Chazelle
- Animações de algoritmos de ordenação
- Analysis of Algorithms Home Page, maintained by Philippe Flajolet and Helmut Prodinger.
- The Art of Computer Programming
- Algorithms is a featured book on Wikibooks
- Relevant Algorithm Animations/Visualizations (in Java) based on the textbook "Algorithms in C++" by Robert Sedgewick
- Soluções de exercícios do livro do Cormen aqui
- Pessimal algorithms and Simplexity analysis, Broder e Stolfi.
- sobre o problema P=NP, email do prof. Jorge Stolfi (UNICAMP).
- 16/02 -- comparação assintótica de funções: notação o e O.
- 18/02 -- comparação assintótica de funções: notação Omega Theta; funções chão e teto. Notas de aula
- 23/02 -- Equações de recorrência. Soluções assintóticas de recorrências. notas de aula [html] [pdf]
- 25/02 -- número de comparações na busca binária e no Merge-Sort notas de aula
- 01/03 -- Exercícios
- 03/03 -- prova
- 08/03 -- Problema computacional, solução, instâncias, complexidade de tempo e de espaço, pior caso, melhor caso, caso médio. Exemplos com busca em lista linear e busca binária. notas de aula
- 10/03 -- Exemplos análise de pior caso e caso médio.
- 15/03 -- Pior caso do Quicksort notas de aula
- 17/03 -- Caso médio do Quicksort notas de aula
- 22/05 -- Ordenação: limitante inferior para ordenação por comparação notas de aula. Counting-Sort.
- 24/03 -- Seleção notas de aula
- 29/03 -- III Semana do CMCC.
- 31/03 -- Heap notas de aula
- 05/04 -- aula de exercícios
- 07/04 -- prova
- 12/04 -- P e NP.
- 14/04 -- Redução de problema de busca para problema de decisão; redução polinomial entre problemas de decisão. notas de aula
- 19/04 -- Exemplos de redução polinomial.
- 21/04 -- feriado
- 26/04 -- NP-completude. notas de aula
- 28/04 -- Aula de exercícios
- 03/05 -- prova
- 05/05 -- prova sub
-----------------------Lista 1-----------------------
-----------------------Lista 2-----------------------
-----------------------Lista 3-----------------------
-----------------------Lista 4-----------------------
-----------------------Lista 5-----------------------
-----------------------Lista 6-----------------------