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 [2019/12/16 11:01] 127.0.0.1 Edição externa |
cmp601:homepage [2022/08/22 17:02] (Actual) |
||
|---|---|---|---|
| Linha 1: | Linha 1: | ||
| - | ====== CMP 601: Algorithms and Theory of Computation (2019/2) ====== | + | ====== 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, 112, building 43425.\\ | + | **Time and room:** Tue/Thu 10.30, 108/43413.\\ |
| - | **Consultation hours:** Wed 15.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 ===== | ||
| - | * First exam: Aug 23, 2018. The exam will take 2.5 hours. | + | * First lecture: Tue, Jun 14. |
| ===== Results ===== | ===== Results ===== | ||
| - | |||
| ===== 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]], [[:cmp601:2016-2|2016/2]], and [[:cmp601:2018-1|2018/1]]. | + | * 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-10619.pdf|Lecture notes}} (in Portuguese, updated 19/9/2019). | + | * {{:cmp155:notas-11959.pdf|Lecture notes}} (in Portuguese, updated Junho 2022). |
| ==== Lectures ==== | ==== Lectures ==== | ||
| - | ^ No. ^ Data ^ Topics ^ Chap. in\\ notes ^ Exercises ^ Solutions ^ Reading ^ | + | ^ No. ^ Date ^ Topics ^ Chap. in\\ notes ^ Exercises ^ Solutions ^ Reading ^ |
| - | | | | ** Algorithms ** | | | | | | + | | | | ** Algorithms ** | | | | | |
| - | | 1 | 13/08 | Administrativa. Introduction. | 1 | | | 1.1 | | + | | 1 | 14/06 | Administrativa. Introduction. | 1 | | | 1.1 | |
| - | | 2 | 15/08 | Representative problems. | | | | 1.2 | | + | | | 16/06 | //Corpus Cristi// | | | | | |
| - | | 3 | 20/08 | Basics of algorithm analysis. | 2 | | | 2 | | + | | 2 | 21/06 | Basics of analysis and representative problems. | | | | 1.2 | |
| - | | 4 | 22/08 | Graph algorithms 1 | | | | 3.[12],4.4 | | + | | 3 | 23/06 | Basics of analysis and representative problems. | 2 | | | 2 | |
| - | | | 23/08 | **Pre-semester exam.** | | | | | | + | | | 24/06 | Qualification exam algorithms (8.30, AUD-0) | | {{eqa20221.pdf|E}} | {{seqa20221.pdf|S}} | | |
| - | | 5 | 27/08 | Graph algorithms 2. | | | | 3.[3-6] | | + | | | 24/06 | Qualification exam theory (13.30, 109, 43413) | | | | | |
| - | | 6 | 29/08 | Graph algorithms 3. | | {{q0120192.pdf|Q1}} | {{sq0120192.pdf|S1}} | | | + | | 4 | 28/06 | Graph algorithms 1. | | | | 3.[123],4.4 | |
| - | | 7 | 03/09 | Greedy algorithms 1. | 4 | | | 4.[12] | | + | | 5 | 30/06 | Graph algorithms 2. | | | | 3.[46] | |
| - | | 8 | 05/09 | Greedy algorithms 2 | 4 | | | 4.5 | | + | | 6 | 05/07 | Graph algorithms 3. | | {{q0120221.pdf|E1}} | {{sq0120221.pdf|S1}} | 3.5 | |
| - | | 9 | 10/09 | Greedy algorithms 3 | 4 | {{q0220192.pdf|Q2}} | {{sq0220192.pdf|S2}} | 4.9 | | + | | 7 | 07/07 | Greedy algorithms 1. | 4 | | | 4.[12] | |
| - | | 10 | 12/09 | Divide-and-conquer 1 | 5 | | | 5.[123] | | + | | 8 | 12/07 | Greedy algorithms 2. | 4 | | | 4.5 | |
| - | | 11 | 17/09 | Divide-and-conquer 2 | 5 | | | 5.[45] | | + | | 9 | 14/07 | Greedy algorithms 3. | 4 | | | 4.9 | |
| - | | 12 | 19/09 | Divide-and-conquer 3 | 5 | {{q0320192.pdf|Q3}} | {{sq0320192.pdf|S3}} | 5.6 | | + | | 10 | 19/07 | Divide-and-conquer algorithms 1. | 5 | {{q0220221.pdf|E2}} | {{sq0220221.pdf|S2}} | 5.[123] | |
| - | | 13 | 24/09 | Dynamic programming 1 | 6 | | | 6.[12] | | + | | 11 | 21/07 | Divide-and-conquer algorithms 2. | 5 | | | 5.[45] | |
| - | | 14 | 26/09 | Dynamic programming 2 | 6 | | | 6.[45] | | + | | 12 | 26/07 | Divide-and-conquer algorithms 3. | 5 | | | 5.6 | |
| - | | | | ** Theory of computation ** | | | | | | + | | 13 | 28/07 | Dynamic programming 1. | 6 | {{q0320221.pdf|E3}} | {{sq0320221.pdf|S3}} | 6.[12] | |
| - | | 15 | 01/10 | Theory: TBD | | | | | | + | | 14 | 02/08 | Dynamic programming 2. | 6 | | | 6.[45] | |
| - | | 16 | 03/10 | Theory: TBD | | | | | | + | | 15 | 04/08 | Dynamic programming 3. | 6 | {{q0420221.pdf|E4}} | {{sq0420221.pdf|S4}} | 6.[67] | |
| - | | 17 | 08/10 | Dynamic programming 3 | 6 | {{q0420192.pdf|Q4}} | {{sq0420192.pdf|S4}} | 6.[67] | | + | | | | ** Theory of computation ** | | | | | |
| - | | 18 | 10/10 | Theory: TBD | | | | | | + | | 16 | 09/08 | Theory 1: Introduction -- Noncomputability | | | | | |
| - | | | 15/10 | //Semana acadêmica// | | | | | | + | | 17 | 11/08 | Theory 2: Introduction -- Intractability | | | | | |
| - | | | 17/10 | //Semana acadêmica// | | | | | | + | | 18 | 16/08 | Theory 3: Introduction -- NP-complete problems | | | | | |
| - | | 19 | 22/10 | Theory: TBD | | | | | | + | | 19 | 18/08 | Theory 4: Turing Machines | | | | | |
| - | | 20 | 24/10 | Theory: TBD | | | | | | + | | 20 | 23/08 | Theory 5: Undecidability | | | | | |
| - | | 21 | 29/10 | Theory: TBD | | | | | | + | | 21 | 25/08 | Theory 6: Reducibility | | | | | |
| - | | 22 | 31/10 | Theory: TBD | | | | | | + | | 22 | 30/08 | Theory 7: Time Complexity I | | | | | |
| - | | 23 | 05/11 | Theory: TBD | | | | | | + | | 23 | 01/09 | Theory 8: Time Complexity II | | | | | |
| - | | 24 | 07/11 | Theory: TBD | | | | | | + | | 24 | 06/09 | Theory 9: Time Complexity III | | | | | |
| - | | 25 | 12/11 | Theory: TBD | | | | | | + | | 25 | 08/09 | Theory 10: Time Complexity IV | | | | | |
| - | | 26 | 14/11 | Theory: TBD | | | | | | + | | 26 | 13/09 | Theory 11: Exercises | | | | | |
| - | | 27 | 19/11 | Theory: TBD | | | | | | + | | 27 | 15/09 | Theory 12: Space Complexity I | | | | | |
| - | | 28 | 21/11 | Theory: TBD | | | | | | + | | | 20/09 | //Revolução Farroupilha// | | | | | |
| - | | 29 | 26/11 | Theory: TBD | | | | | | + | | 28 | 22/09 | Theory 13: Intractability | | | | | |
| - | | 30 | 28/11 | Theory: TBD | | | | | | + | | | 27/09 | //Semana Acadêmica// | | | | |
| - | | | 10/12 | Prova de recuperação. | | | | | | + | | | 29/09 | //Semana Acadêmica// | | | | |
| - | | | 20/12 | **Post-semester exam.** | | | | | | + | | 29 | 04/10 | Theory 14: Exercises | | | | | |
| - | | | 11/01 | Official end of lecture period 2019/2. | | | | | | + | | 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 ==== | ||
cmp601/homepage.1576504887.txt.gz · Esta página foi modificada pela última vez em: 2019/12/16 11:01 por 127.0.0.1
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
