Í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:2015-1
Tabela de Conteúdos
CMP 601: Algorithms and Theory of Computation (2015/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: Leila Ribeiro, 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: Seg/Qua 13.30, room 102.
Consultation hours: Seg 13.30, sala 201
Details: Ver a homepage of the course at PPGC.
News
- Introduction: Mar 2, 2015.
- First exam: Mar 4, 2015. The exam will take 2.5 hours.
- Second exam: Jul 6, 2015. The exam will take 2.5 hours.
Results
- Resultados do primeiro exame de qualificação.
- Resultados do segundo exame de qualificação.
- Resultados da disciplina.
Additional material
- Lecture notes (in Portuguese, updated 16/5/2012).
Lectures
Aulas
| No. | Data | Tópicos | Notas pág. | Exercícios | Soluções | Leitura | |
|---|---|---|---|---|---|---|---|
| Introduction & pre-semester exam | |||||||
| 1 | 02/03 | Administrativa, Introduction. | |||||
| 04/03 | Pre-semester exam. | ||||||
| 09/03 | Evaluation of exam | ||||||
| 11/03 | Evaluation of exam | ||||||
| Theory of computation | |||||||
| 2 | 16/08 | Proof techniques and structural induction | |||||
| 3 | 18/08 | The Turing machine: motivation, importance | |||||
| 4 | 23/03 | Universal TMs, multi-tape TMs | |||||
| 5 | 25/03 | Primitive recursive functions | |||||
| 6 | 30/03 | Primitive recursive functions, exercises | |||||
| 7 | 01/04 | Partial recursive functions | |||||
| 8 | 06/04 | Equivalence of TMs and partial recursive functions | |||||
| 9 | 08/04 | Equivalence of TMs and partial recursive functions | |||||
| 10 | 13/04 | The halting problem, reductions, Rice's theorem | |||||
| 11 | 15/04 | O-notation, introduction to complexity theory, nondeterminism | |||||
| 12 | 20/04 | The Church-Turing thesis (a distância) | |||||
| 13 | 22/04 | Languages and problems, classes P and NP, NP-completeness | |||||
| 14 | 27/04 | The Cook-Levin theorem | |||||
| 15 | 29/04 | More NP-complete problems | |||||
| Algorithms | |||||||
| 16 | 04/05 | Introduction and representative problems | |||||
| 17 | 06/05 | Basics of algorithm analysis | |||||
| 18 | 11/05 | Basics of algorithm analysis | |||||
| 19 | 13/05 | Graph algorithms | |||||
| 20 | 18/05 | Graph algorithms | |||||
| 21 | 20/05 | Graph algorithms | E1 | S1 | |||
| 22 | 25/05 | Greedy algorithms | |||||
| 23 | 27/05 | Greedy algorithms | |||||
| 24 | 01/06 | Greedy algorithms | |||||
| 25 | 03/06 | Divide-and-conquer | Prazo lista 1 | ||||
| 08/06 | Sem aula | ||||||
| 10/06 | Sem aula | ||||||
| 15/06 | Sem aula | E2 | S2 | ||||
| 26 | 17/06 | Divide-and-conquer | |||||
| 27 | 22/06 | Divide-and-conquer | |||||
| 28 | 24/06 | Dynamic programming | E3 | S3 | Prazo lista 2 | ||
| 29 | 29/06 | Dynamic programming | |||||
| 30 | 01/07 | Dynamic programming | Prazo lista 3 | ||||
| 06/07 | Prova de recuperação. | ||||||
| 11/07 | Término oficial das aulas. |
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/2015-1.txt · Esta página foi modificada pela última vez em: 2016/02/24 09:22 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
