Índice
-
- INF 5010: Otimização combinatória
- INF 5016: Algoritmos avançados
- INF 5023: Técnicas de busca heurística.
Ferramentas de Utilizador
Barra Lateral
cmp601:homepage
Esta é uma versão antiga do documento!
Tabela de Conteúdos
CMP 601: Algorithms and Theory of Computation (2020/1)
Somebody once asked John Hopcroft about the problem of P and NP. He answered: “On Tuesdays, I try to prove that they are equal, on the rest of the week - that they are different.” I believe that he has reduced the time to try to show that they are equal to Sunday afternoons.
General information
Professors: Álvaro Freitas Moreira, Marcus Ritt
Total hours: 60 h (in 30 lectures of 2h)
Credits: 4
Summary: Theory of Computation: Models of computation. Limitation of formal systems. Complexity theory.
Algorithms: Analysis of algorithms. Main techniques for designing algorithms.
Time and room: Tue/Thu 10.30, 102, building 43425.
Consultation hours: Thu 13.30, room 216, building 43425.
Details: On the homepage of the course at PPGC.
News
- First exam: Mar 27, 2020. The exam will take 2.5 hours.
Results
Additional material
- Lecture notes (in Portuguese, updated Sep 2019).
Lectures
| No. | Data | Topics | Chap. in notes | Exercises | Solutions | Reading |
|---|---|---|---|---|---|---|
| Algorithms | ||||||
| 1 | 05/03 | Administrativa. Introduction. | 1 | 1.1 | ||
| 2 | 10/03 | Representative problems. | 1.2 | |||
| 3 | 12/03 | Basics of algorithm analysis. | 2 | 2 | ||
| 4 | 17/03 | Graph algorithms 1. | 3.[12],4.4 | |||
| 5 | 19/03 | Graph algorithms 2. | 3.[3-6] | |||
| 6 | 24/03 | Graph algorithms 3. | ||||
| 7 | 26/09 | Greedy algorithms 1. | 4 | 4.[12] | ||
| 27/03 | Pre-semester exam. | |||||
| 8 | 31/03 | Greedy algorithms 2. | 4 | 4.5 | ||
| 9 | 02/04 | Greedy algorithms 3. | 4 | 4.9 | ||
| 10 | 07/04 | Divide-and-conquer 1. | 5 | 5.[123] | ||
| 11 | 09/04 | Divide-and-conquer 2. | 5 | 5.[45] | ||
| 12 | 14/04 | Divide-and-conquer 3. | 5 | 5.6 | ||
| 13 | 16/04 | Dynamic programming 1. | 6 | 6.[12] | ||
| 21/04 | Tiradentes | |||||
| 14 | 23/04 | Dynamic programming 2. | 6 | 6.[45] | ||
| 15 | 28/04 | Dynamic programming 3. | 6 | 6.[67] | ||
| Theory of computation | ||||||
| 16 | 30/04 | Theory: TBD | ||||
| 17 | 05/05 | Theory: TBD | ||||
| 18 | 07/05 | Theory: TBD | ||||
| 19 | 12/05 | Theory: TBD | ||||
| 20 | 14/05 | Theory: TBD | ||||
| 21 | 19/05 | Theory: TBD | ||||
| 22 | 21/05 | Theory: TBD | ||||
| 23 | 26/05 | Theory: TBD | ||||
| 24 | 28/05 | Theory: TBD | ||||
| 25 | 02/06 | Theory: TBD | ||||
| 26 | 04/06 | Theory: TBD | ||||
| 27 | 09/06 | Theory: TBD | ||||
| 11/06 | Corpus Christi | |||||
| 28 | 16/06 | Theory: TBD | ||||
| 29 | 18/06 | Theory: TBD | ||||
| 30 | 23/06 | Theory: TBD | ||||
| 30/06 | Prova de recuperação. | |||||
| 10/07 | Post-semester exam. | |||||
| 15/07 | Official end of lecture period 2020/1. |
Evaluation
See the homepage of the course at PPGC.
Bibliography
- Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
- Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. Freeman, 1979.
- E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1984.
- Laira Vieira Toscani and Paula A. S. Veloso. Complexidade de Algoritmos. Editora Sagra Luzzatto, 2a edition, 2005.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation – Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999.
- Bernhard H. Korte and Jens Vygen. Combinatorial optimization theory and algorithms. Springer, 4th edition, 2008. INF 65.012.122 K85c.
- Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, dover edition, 1982.
- Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
- S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algoritmos. McGraw-Hill, 2009.
cmp601/homepage.1583326223.txt.gz · Esta página foi modificada pela última vez em: 2020/03/04 09:50 por marcus
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
