Ferramentas de Utilizador
cmp601:homepage
Diferenças
Esta página mostra as diferenças entre as duas revisões da página.
| Ambos os lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
|
cmp601:homepage [2018/04/10 12:55] marcus [General information] |
cmp601:homepage [2022/08/22 17:02] (Actual) |
||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| - | ====== CMP 601: Algorithms and Theory of Computation (2018/1) ====== | + | ====== 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.// | //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 ===== | ===== General information ===== | ||
| Linha 9: | Linha 10: | ||
| **Summary:** Theory of Computation: Models of computation. Limitation of formal systems. Complexity theory. | **Summary:** Theory of Computation: Models of computation. Limitation of formal systems. Complexity theory. | ||
| Algorithms: Analysis of algorithms. Main techniques for designing algorithms.\\ | Algorithms: Analysis of algorithms. Main techniques for designing algorithms.\\ | ||
| - | **Time and room:** Tue/Thu 10.30, upper lecture hall, [[https://www1.ufrgs.br/infraestrutura/geolocation/index.php?verb=pan&building=1885|building 43413 (67)]].\\ | + | **Time and room:** Tue/Thu 10.30, 108/43413.\\ |
| - | **Consultation hours:** Thu 14.30, room 216.\\ | + | **Consultation hours:** By appointment.\\ |
| - | **Details:** On the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601/|homepage of the course at PPGC]]. | + | **Details:** On the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601|homepage of the course at PPGC]].\\ |
| + | **Note:** The course will be split during the semester into two courses. | ||
| ===== News ===== | ===== News ===== | ||
| - | * Introduction: Mar 6, 2018. | + | * First lecture: Tue, Jun 14. |
| - | * First exam: Mar 13, 2018. The exam will take 2.5 hours. | + | |
| - | * Second exam: Jun 28, 2018. The exam will take 2.5 hours. | + | |
| ===== Results ===== | ===== Results ===== | ||
| - | |||
| - | * [[2018-1a-Notas|Results]] of the first qualification exam. | ||
| - | * [[2018-1b-Notas|Results]] of the second qualification exam. | ||
| - | * [[2018-1c-Notas|Results]] of the course. | ||
| - | |||
| ===== Additional material ===== | ===== Additional material ===== | ||
| * Homepage of CMP155 (Análise e Desenvolvimento de Algoritmos) in [[:cmp155:2011-1|2011/1]], [[:cmp155:2010-1|2010/1]], [[:cmp155:2008-1|2008/1]] and [[:cmp155:2007-1|2007/1]]. | * Homepage of CMP155 (Análise e Desenvolvimento de Algoritmos) in [[:cmp155:2011-1|2011/1]], [[:cmp155:2010-1|2010/1]], [[:cmp155:2008-1|2008/1]] and [[:cmp155:2007-1|2007/1]]. | ||
| - | * Homepage of CMP601 in [[:cmp601:2015-1|2015/1]], and [[:cmp601:2016-2|2016/2]]. | + | * Homepage of CMP601 in [[:cmp601:2020-2|2020/2]], [[:cmp601:2020-1|2020/1]], [[:cmp601:2019-1|2019/2]], [[:cmp601:2018-1|2018/1]], [[:cmp601:2016-2|2016/2]], and [[:cmp601:2015-1|2015/1]]. |
| - | * {{:cmp155:notas-4227.pdf|Lecture notes}} (in Portuguese, updated 16/5/2012). | + | * {{:cmp155:notas-11959.pdf|Lecture notes}} (in Portuguese, updated Junho 2022). |
| - | * {{:cmp601:exq20162a.pdf|Some comments}} on the qualification exam. | + | |
| ==== Lectures ==== | ==== Lectures ==== | ||
| - | ^ No. ^ Data ^ Tópicos ^ Notas pág. ^ Exercícios ^ Soluções ^ Leitura ^ | + | ^ No. ^ Date ^ Topics ^ Chap. in\\ notes ^ Exercises ^ Solutions ^ Reading ^ |
| - | | | | ** Algorithms ** | | | | | | + | | | | ** Algorithms ** | | | | | |
| - | | 1 | 06/03 | Administrativa. Introduction. | | | | | | + | | 1 | 14/06 | Administrativa. Introduction. | 1 | | | 1.1 | |
| - | | 2 | 08/03 | Representative problems. | | | | | | + | | | 16/06 | //Corpus Cristi// | | | | | |
| - | | | 13/03 | Pre-semester exam. | {{q0520181.pdf|Q1}} | {{sq0520181.pdf|SQ1}} | | | | + | | 2 | 21/06 | Basics of analysis and representative problems. | | | | 1.2 | |
| - | | 3 | 15/03 | Basics of algorithm analysis | | | | | | + | | 3 | 23/06 | Basics of analysis and representative problems. | 2 | | | 2 | |
| - | | 4 | 20/03 | Graph algorithms 1 | | | | | | + | | | 24/06 | Qualification exam algorithms (8.30, AUD-0) | | {{eqa20221.pdf|E}} | {{seqa20221.pdf|S}} | | |
| - | | 5 | 22/03 | Graph algorithms 2 | | | | | | + | | | 24/06 | Qualification exam theory (13.30, 109, 43413) | | | | | |
| - | | 6 | 27/03 | Graph algorithms 3 | | | | | | + | | 4 | 28/06 | Graph algorithms 1. | | | | 3.[123],4.4 | |
| - | | 7 | 29/03 | Greedy algorithms 1 | {{q0120181.pdf|E1}} | | | | | + | | 5 | 30/06 | Graph algorithms 2. | | | | 3.[46] | |
| - | | 8 | 03/04 | Theory: Introduction | | | | | | + | | 6 | 05/07 | Graph algorithms 3. | | {{q0120221.pdf|E1}} | {{sq0120221.pdf|S1}} | 3.5 | |
| - | | 9 | 05/04 | Theory: Introduction | | | | | | + | | 7 | 07/07 | Greedy algorithms 1. | 4 | | | 4.[12] | |
| - | | 10 | 10/04 | Greedy algorithms 2 | | | | | | + | | 8 | 12/07 | Greedy algorithms 2. | 4 | | | 4.5 | |
| - | | 11 | 12/04 | Greedy algorithms 3 | | | | | | + | | 9 | 14/07 | Greedy algorithms 3. | 4 | | | 4.9 | |
| - | | 12 | 17/04 | Divide-and-conquer 1 | | | | | | + | | 10 | 19/07 | Divide-and-conquer algorithms 1. | 5 | {{q0220221.pdf|E2}} | {{sq0220221.pdf|S2}} | 5.[123] | |
| - | | 13 | 19/04 | Divide-and-conquer 2 | | | | | | + | | 11 | 21/07 | Divide-and-conquer algorithms 2. | 5 | | | 5.[45] | |
| - | | 14 | 24/04 | Divide-and-conquer 3 | | | | | | + | | 12 | 26/07 | Divide-and-conquer algorithms 3. | 5 | | | 5.6 | |
| - | | 15 | 26/04 | Dynamic programming 1 | | | | | | + | | 13 | 28/07 | Dynamic programming 1. | 6 | {{q0320221.pdf|E3}} | {{sq0320221.pdf|S3}} | 6.[12] | |
| - | | | 01/05 | [[wppt>Dia do Trabalhador]] | | | | | | + | | 14 | 02/08 | Dynamic programming 2. | 6 | | | 6.[45] | |
| - | | 16 | 03/05 | Dynamic programming 2 | | | | | | + | | 15 | 04/08 | Dynamic programming 3. | 6 | {{q0420221.pdf|E4}} | {{sq0420221.pdf|S4}} | 6.[67] | |
| - | | 17 | 08/05 | Dynamic programming 3 | | | | | | + | | | | ** Theory of computation ** | | | | | |
| - | | | | ** Theory of computation ** | | | | | | + | | 16 | 09/08 | Theory 1: Introduction -- Noncomputability | | | | | |
| - | | 18 | 10/05 | Theory: TBD | | | | | | + | | 17 | 11/08 | Theory 2: Introduction -- Intractability | | | | | |
| - | | 19 | 15/05 | Theory: TBD | | | | | | + | | 18 | 16/08 | Theory 3: Introduction -- NP-complete problems | | | | | |
| - | | 20 | 17/05 | Theory: TBD | | | | | | + | | 19 | 18/08 | Theory 4: Turing Machines | | | | | |
| - | | 21 | 22/05 | Theory: TBD | | | | | | + | | 20 | 23/08 | Theory 5: Undecidability | | | | | |
| - | | 22 | 24/05 | Theory: TBD | | | | | | + | | 21 | 25/08 | Theory 6: Reducibility | | | | | |
| - | | 23 | 29/05 | Theory: TBD | | | | | | + | | 22 | 30/08 | Theory 7: Time Complexity I | | | | | |
| - | | | 31/05 | [[wppt>Corpus Christi]] | | | | | | + | | 23 | 01/09 | Theory 8: Time Complexity II | | | | | |
| - | | 24 | 05/06 | Theory: TBD | | | | | | + | | 24 | 06/09 | Theory 9: Time Complexity III | | | | | |
| - | | 25 | 07/06 | Theory: TBD | | | | | | + | | 25 | 08/09 | Theory 10: Time Complexity IV | | | | | |
| - | | 26 | 12/06 | Theory: TBD | | | | | | + | | 26 | 13/09 | Theory 11: Exercises | | | | | |
| - | | 27 | 14/06 | Theory: TBD | | | | | | + | | 27 | 15/09 | Theory 12: Space Complexity I | | | | | |
| - | | 28 | 19/06 | Theory: TBD | | | | | | + | | | 20/09 | //Revolução Farroupilha// | | | | | |
| - | | 29 | 21/06 | Theory: TBD | | | | | | + | | 28 | 22/09 | Theory 13: Intractability | | | | | |
| - | | 30 | 26/06 | Theory: TBD | | | | | | + | | | 27/09 | //Semana Acadêmica// | | | | |
| - | | | 28/06 | Post-semester exam. | | | | | | + | | | 29/09 | //Semana Acadêmica// | | | | |
| - | | | 05/07 | Prova de recuperação. | | | | | | + | | 29 | 04/10 | Theory 14: Exercises | | | | | |
| - | | | 14/07 | Official end of lecture period 2018/1. | | | | | | + | | 30 | 06/10 | Theory 15: Exercises | | | | | |
| + | | | 20/10 | Official end of lecture period 2022/2. | | | | | | ||
| ==== Evaluation ==== | ==== Evaluation ==== | ||
| See the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601/|homepage of the course at PPGC]]. | See the [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601/|homepage of the course at PPGC]]. | ||
| + | |||
| + | ==== Material ==== | ||
| + | |||
| + | * Template ([[http://www.inf.ufrgs.br/~mrpritt/ca/answers.tex|LaTeX]],[[http://www.inf.ufrgs.br/~mrpritt/ca/answers.pdf|PDF]]) for exercise lists. | ||
| ==== Bibliography ==== | ==== Bibliography ==== | ||
| <html> | <html> | ||
| - | <!-- BEGIN BIBLIOGRAPHY Bibliografia --> | + | <!-- BEGIN BIBLIOGRAPHY Bibliografia --> |
| - | <!-- | + | <!-- |
| - | DO NOT MODIFY THIS BIBLIOGRAPHY BY HAND! IT IS MAINTAINED AUTOMATICALLY! | + | DO NOT MODIFY THIS BIBLIOGRAPHY BY HAND! IT IS MAINTAINED AUTOMATICALLY! |
| - | YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED! | + | YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED! |
| - | --> | + | --> |
| <!-- Generated by: /home/ritt/arch/share/bin/bib2xhtml -s unsortlist Bibliografia.bib Bibliografia.html --> | <!-- Generated by: /home/ritt/arch/share/bin/bib2xhtml -s unsortlist Bibliografia.bib Bibliografia.html --> | ||
| - | <ul class="bib2xhtml"> | + | <ul class="bib2xhtml"> |
| <!-- Authors: Sanjeev Arora and Boaz Barak --> | <!-- Authors: Sanjeev Arora and Boaz Barak --> | ||
| <li><a name="Arora.Barak/2009">Sanjeev</a> Arora and Boaz Barak. | <li><a name="Arora.Barak/2009">Sanjeev</a> Arora and Boaz Barak. | ||
| - | <cite>Computational Complexity: A Modern Approach</cite>. | + | <cite>Computational Complexity: A Modern Approach</cite>. |
| - | Cambridge University Press, 2009.</li> | + | Cambridge University Press, 2009.</li> |
| <!-- Authors: Thomas H Cormen and Charles E Leiserson and Ronald L Rivest and | <!-- Authors: Thomas H Cormen and Charles E Leiserson and Ronald L Rivest and | ||
| - | Clifford Stein --> | + | Clifford Stein --> |
| - | <li><a name="Cormen.etal/2001">Thomas</a> H. Cormen, Charles E. | + | <li><a name="Cormen.etal/2001">Thomas</a> H. Cormen, Charles E. |
| Leiserson, Ronald L. Rivest, and Clifford Stein. | Leiserson, Ronald L. Rivest, and Clifford Stein. | ||
| <a href="http://projects.csail.mit.edu/clrs"><cite>Introduction to | <a href="http://projects.csail.mit.edu/clrs"><cite>Introduction to | ||
cmp601/homepage.1523375758.txt.gz · Esta página foi modificada pela última vez em: 2018/04/10 12:55 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
