Í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
Tabela de Conteúdos
CMP 601: Algorithms and Theory of Computation (2022/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, 108/43413.
Consultation hours: By appointment.
Details: On the homepage of the course at PPGC.
Note: The course will be split during the semester into two courses.
News
- First lecture: Tue, Jun 14.
Results
Additional material
- Lecture notes (in Portuguese, updated Junho 2022).
Lectures
| No. | Date | Topics | Chap. in notes | Exercises | Solutions | Reading |
|---|---|---|---|---|---|---|
| Algorithms | ||||||
| 1 | 14/06 | Administrativa. Introduction. | 1 | 1.1 | ||
| 16/06 | Corpus Cristi | |||||
| 2 | 21/06 | Basics of analysis and representative problems. | 1.2 | |||
| 3 | 23/06 | Basics of analysis and representative problems. | 2 | 2 | ||
| 24/06 | Qualification exam algorithms (8.30, AUD-0) | E | S | |||
| 24/06 | Qualification exam theory (13.30, 109, 43413) | |||||
| 4 | 28/06 | Graph algorithms 1. | 3.[123],4.4 | |||
| 5 | 30/06 | Graph algorithms 2. | 3.[46] | |||
| 6 | 05/07 | Graph algorithms 3. | E1 | S1 | 3.5 | |
| 7 | 07/07 | Greedy algorithms 1. | 4 | 4.[12] | ||
| 8 | 12/07 | Greedy algorithms 2. | 4 | 4.5 | ||
| 9 | 14/07 | Greedy algorithms 3. | 4 | 4.9 | ||
| 10 | 19/07 | Divide-and-conquer algorithms 1. | 5 | E2 | S2 | 5.[123] |
| 11 | 21/07 | Divide-and-conquer algorithms 2. | 5 | 5.[45] | ||
| 12 | 26/07 | Divide-and-conquer algorithms 3. | 5 | 5.6 | ||
| 13 | 28/07 | Dynamic programming 1. | 6 | E3 | S3 | 6.[12] |
| 14 | 02/08 | Dynamic programming 2. | 6 | 6.[45] | ||
| 15 | 04/08 | Dynamic programming 3. | 6 | E4 | S4 | 6.[67] |
| Theory of computation | ||||||
| 16 | 09/08 | Theory 1: Introduction – Noncomputability | ||||
| 17 | 11/08 | Theory 2: Introduction – Intractability | ||||
| 18 | 16/08 | Theory 3: Introduction – NP-complete problems | ||||
| 19 | 18/08 | Theory 4: Turing Machines | ||||
| 20 | 23/08 | Theory 5: Undecidability | ||||
| 21 | 25/08 | Theory 6: Reducibility | ||||
| 22 | 30/08 | Theory 7: Time Complexity I | ||||
| 23 | 01/09 | Theory 8: Time Complexity II | ||||
| 24 | 06/09 | Theory 9: Time Complexity III | ||||
| 25 | 08/09 | Theory 10: Time Complexity IV | ||||
| 26 | 13/09 | Theory 11: Exercises | ||||
| 27 | 15/09 | Theory 12: Space Complexity I | ||||
| 20/09 | Revolução Farroupilha | |||||
| 28 | 22/09 | Theory 13: Intractability | ||||
| 27/09 | Semana Acadêmica | |||||
| 29/09 | Semana Acadêmica | |||||
| 29 | 04/10 | Theory 14: Exercises | ||||
| 30 | 06/10 | Theory 15: Exercises | ||||
| 20/10 | Official end of lecture period 2022/2. |
Evaluation
See the homepage of the course at PPGC.
Material
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.txt · Esta página foi modificada pela última vez em: 2022/08/22 17:02 (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
