Í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:2020-2
Tabela de Conteúdos
CMP 601: Algorithms and Theory of Computation (2020/2)
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 online via Zoom.
Consultation hours: Any time per email or via Discord (Invitation).
Details: On the homepage of the course at PPGC.
News
- First lecture: Tue, Jan 27.
Results
Additional material
- Lecture notes (in Portuguese, updated Sep 2019).
Lectures
| No. | Data | Topics | Chap. in notes | Exercises | Solutions | Reading |
|---|---|---|---|---|---|---|
| Algorithms | ||||||
| 1 | 26/01 | Administrativa. Introduction. | 1 | 1.1 | ||
| 2 | 28/01 | Basics of analysis and representative problems. | 1.2 | |||
| 02/02 | Navegantes | |||||
| 3 | 04/02 | Basics of analysis and representative problems. | 2 | 2 | ||
| 05/02 | First qualification exam | PA1 | SPA1 | |||
| 4 | 09/02 | Graph algorithms 1. | 3.[123],4.4 | |||
| 5 | 11/02 | Graph algorithms 2. | 3.[46] | |||
| 16/02 | Carnaval | |||||
| 6 | 18/02 | Graph algorithms 3. | E1 | S1 | 3.5 | |
| 7 | 23/02 | Greedy algorithms 1. | 4 | 4.[12] | ||
| 8 | 25/02 | Greedy algorithms 2. | 4 | 4.5 | ||
| 9 | 02/03 | Greedy algorithms 3. | 4 | 4.9 | ||
| 10 | 04/03 | Divide-and-conquer algorithms 1. | 5 | E2 | S2 | 5.[123] |
| 11 | 09/03 | Divide-and-conquer algorithms 2. | 5 | 5.[45] | ||
| 12 | 11/03 | Divide-and-conquer algorithms 3. | 5 | 5.6 | ||
| 13 | 16/03 | Dynamic programming 1. | 6 | 6.[12] | ||
| 14 | 18/03 | Dynamic programming 2. | 6 | E3 | S3 | 6.[45] |
| 15 | 23/03 | Dynamic programming 3. | 6 | 6.[67] | ||
| Theory of computation | ||||||
| 25/03 | Sem aula | |||||
| 16 | 30/03 | Theory 1: Introduction – Noncomputability | ||||
| 17 | 01/04 | Theory 2: Introduction – Intractability | E4 | S4 | ||
| 18 | 06/04 | Theory 3: Introduction – NP-complete problems | ||||
| 19 | 08/04 | Theory 4: Turing Machines | ||||
| 20 | 13/04 | Theory 5: Undecidability | ||||
| 21 | 15/04 | Theory 6: Reducibility | ||||
| 22 | 20/04 | Theory 7: Time Complexity I | ||||
| 23 | 22/04 | Theory 8: Time Complexity II | ||||
| 24 | 27/04 | Theory 9: Time Complexity III | ||||
| 25 | 29/04 | Theory 10: Time Complexity IV | ||||
| 26 | 04/05 | Theory 11: Exercises | ||||
| 27 | 06/05 | Theory 12: Space Complexity I | ||||
| 28 | 11/05 | Theory 13: Intractability | ||||
| 29 | 13/05 | Theory 14: Exercises | ||||
| 30 | 18/05 | Theory 15: Exercises | ||||
| 21/05 | Second qualification exam | PA2 | SPA2 | |||
| 29/05 | Official end of lecture period 2020/2. |
⌛: material from last semester, to be updated during the semester.
Evaluation
See the homepage of the course at PPGC.
Material
- Template for exercise lists.
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/2020-2.txt · Esta página foi modificada pela última vez em: 2022/06/14 08:50 (Edição externa)
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
