====== Algoritmos avançados (INF 5016/CMP 588) (2021/1) ======

//Beware of bugs in the above code; I have only proved it correct, not tried it. (Donald Knuth)//

:!: Bem-vindo.

===== Informações gerais =====

**Carga horária:** 60 h (em 30 aulas de 2h)\\
**Créditos:** 2+2\\
**Súmula:** Algoritmos, estruturas de dados e técnicas algoritmicas avançadas: algoritmos randomizados, algoritmos de aproximação, algoritmos parametrizados.\\
**Turma:** U.\\
**Horário/Sala:** Seg/Qua 13.30, Zoom.\\
**Consultas:** No discord ([[https://discord.gg/UD6TdJby|Convite]]).\\
**Detalhes:** Vê o {{pea-inf05016.pdf|programa}} e [[https://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp588|página da PPGC]].

===== Resultados =====

  * [[2021-1-Trabalhos|Trabalhos]]
  * [[2021-1-Notas|Notas]]
  * [[2021-1-Freq|Frequência]]

===== Notícias =====

  * 29 de agosto: Nova versão das Notas de aula publicada.
  * 26 de agosto: Material do Lab 2 é disponível.
  * 26 de agosto: Nova versão das Notas de aula publicada.
  * 11 de agosto: Página atualizada.
  * 9 de agosto: Material da terceira aula é disponível.
  * 5 agosto: nova versão das Notas de aula publicada.

===== Materiais =====

  * Página da disciplina em [[inf05016:2017-1|2017/1]], [[inf05016:2015-2|2015/2]], [[inf05504:2014-2|2014/2]], [[inf05504:2013-2|2013/2]], [[inf05504:2012-2|2012/2]], [[inf05504:2011-2|2011/2]], [[inf05504:2010-2|2010/2]] e [[inf05504:2009-1|2009/1]].
  * {{inf05016:notas-11595.pdf|Notas de aula}} (atualizado 29/8/2021).
  * Algumas [[http://www.cs.princeton.edu/~wayne/cs423/demos.html|demonstrações]] de algoritmos.
  * [[inf05504:dicas|Dicas]] para os trabalhos experimentais.

===== Aulas =====

^ No. ^ Data   ^ Tópicos                           ^ Notas pág.   ^  Exercícios  ^  Soluções   ^ Leitura ^
|   1 | 02/08 | 📢 [[inf05016:aula1|Algoritmo de Dijkstra e Heaps binários.]]  |     5-15 |   |   | KT2.5,C6   |
|   2 | 04/08 | [[inf05016:lab-dijkstra|Laboratório 1 (Dijkstra).]]            |          |   |   |            |
|   3 | 09/08 | 📢 [[inf05016:aula3|Fast marching method e A*.]]               |    42-48 |   |   |            |
|   4 | 11/08 | 📢 [[inf05016:lab-dijkstra|Laboratório 2 (Dijkstra).]]         |          |   |   |            |
|   5 | 16/08 | [[inf05016:aula5|Árvores geradoras mínimas e arborescências]]  |          |   |   | KT4        |
|   6 | 18/08 | 📢 [[inf05016:lab-dijkstra|Laboratório 3 (Dijkstra).]]         |          |   |   |            |
|   7 | 23/08 | [[inf05016:aula7|Fluxos em redes 1.]]                          |    49-57 |   |   | KT7.{1,2}  |
|   8 | 25/08 | 📢 [[inf05016:lab-mca|Laboratório 4 (Arborescências).]]        |          |   |   |            |
|   9 | 30/08 | [[inf05016:aula9|Fluxo em redes 2.]]                           |    57-59 |   |   | KT7.{2,3}  |
|  10 | 01/09 | 📢 [[inf05016:lab-mca|Laboratório 5 (Arborescências).]]        |          |   |   |            |
|  11 | 06/09 | [[inf05016:aula11|Fluxo em redes 3.]]                          |    60-69 |   |   | KT7.4      |
|  12 | 08/09 | 📢 [[inf05016:lab-mca|Laboratório 6 (Arborescências).]]        |          |   |   |            |
|  13 | 13/09 | [[inf05016:aula13|Emparelhamentos 1.]]                         |    70-74 |   |   | KT7.5,K19  |
|  14 | 15/09 | 📢 [[inf05016:lab-fluxo|Laboratório 7 (Fluxos).]]              |          |   |   |            |
|     | 20/09 | [[wppt>Revolução Farroupilha]]                                 |          |   |   |            |
|  15 | 22/09 | [[inf05016:aula15|Emparelhamentos 2.]]                         |    74-83 |   |   | K20        |
|  16 | 27/09 | 📢 [[inf05016:lab-fluxo|Laboratório 8 (Fluxos).]]              |          |   |   |            |
|  17 | 29/09 | [[inf05016:aula1719|Emparelhamentos 3.]]                       |    84-87 |   |   | K20        |
|  18 | 04/10 | 📢 [[inf05016:lab-fluxo|Laboratório 9 (Fluxos).]]              |          |   |   |            |
|  19 | 06/10 | [[inf05016:aula1719|Emparelhamentos 4.]]                       |    84-87 |   |   | K20        |
|     | 11/10 | //Sem aula//                                                   |          |   |   |            |
|  20 | 13/10 | 📢 [[inf05016:lab-matching|Laboratório 10 (Emparelhamentos).]]   |        |   |   |            |
|  21 | 18/10 | [[inf05016:aula21|Randomização 1.]]                            |  129-138 |   |   | MU1,KT13.2 |
|  22 | 20/10 | 📢 [[inf05016:lab-matching|Laboratório 11 (Emparelhamentos).]]  |         |   |   |            |
|  23 | 25/10 | [[inf05016:aula23|Randomização 2.]]                            |  138-146 |   |   | C31.8      |
|  24 | 27/10 | 📢 [[inf05016:lab-matching|Laboratório 12 (Emparelhamentos).]]  |         |   |   |            |
|  25 | 01/11 | [[inf05016:aula25|Hashing 1.]]                                  |    89-95 |   |   | KT13.6,C11 |
|  26 | 03/11 | 📢 [[inf05016:lab-primes|Laboratório 13.]]                      |          |   |   |            |
|  27 | 08/11 | [[inf05016:aula27|Hashing 2.]]                                  |    95-98 |   |   | KT13.6,C11 |
|  28 | 10/11 | 📢 [[inf05016:lab-primes|Laboratório 14.]]                      |          |   |   |            |
|     | 15/11 | [[wppt>Proclamação da República]]                               |          |   |
|  29 | 17/11 | [[inf05016:aula29|Aproximação.]]                                |   99-108 |   |   |            |
|  30 | 22/11 | ** Prova **                                                     |          |  {{p01g.pdf|P}}  |  {{sp01g.pdf|SP}}   |            |
|     |       | Provas de recuperação (a serem combinadas).  |     |   |   |            |
|     |       |                                         |          |   |   |            |
|     | 04/12 | Término oficial das aulas.              |          |   |   |            |

Livros: KT=Kleinberg/Tardos. K=Kozen, C=Cormen, et al.,V=Vazirani, MU=Mitzenmacher/Upfal
📢: Sessão interativa.

===== Bibliografia =====

<html>
<!-- BEGIN BIBLIOGRAPHY livros -->                                                                                                                  
<!--                                                                                                                                                
    DO NOT MODIFY THIS BIBLIOGRAPHY BY HAND!  IT IS MAINTAINED AUTOMATICALLY!                                                                       
    YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED!                                                                                          
-->                                                                                                                                                 
<!-- Generated by: /home/ritt/arch/share/bin/bib2xhtml-mod -s unsortlist livros.bib livros.html -->                                                 
<ul class="bib2xhtml">                                                                                                                              

<!-- Authors: Juraj Hromkovivc -->
<li><a name="Hromkovic/2001">Juraj</a> Hromkovic.
<cite>Algorithmics for hard problems</cite>.
Springer, 2001.
INF 65.012.122 H873a.</li>

<!-- Authors: Thomas H Cormen and Charles E Leiserson and Ronald L Rivest and
  Clifford Stein -->
<li><a name="Cormen.etal/2001">Thomas</a>&nbsp;H. Cormen, Charles&nbsp;E.
  Leiserson, Ronald&nbsp;L. Rivest, and Clifford Stein.
<cite>Introduction to Algorithms.</cite>
The MIT Press, 2nd edition, 2001.</li>

<!-- Authors: G Ausiello and P Crescenzi and G Gambosi and V Kann and A
  Marchetti Spaccamela and M Protasi -->
<li><a name="Ausiello.etal/1999">G</a>.&nbsp;Ausiello, P.&nbsp;Crescenzi,
  G.&nbsp;Gambosi, V.&nbsp;Kann, A.&nbsp;Marchetti-Spaccamela, and M.&nbsp;Protasi.
<a href="http://www.nada.kth.se/~viggo/approxbook"><cite>Complexity and
  approximation &ndash; Combinatorial Optimization Problems and their
  Approximability Properties</cite></a>.
Springer-Verlag, 1999.</li>

<!-- Authors: Jon Kleinberg and Eva Tardos -->
<li><a name="Kleinberg.Tardos/2005">Jon</a> Kleinberg and &Eacute;va
  Tardos.
<cite>Algorithm design</cite>.
Addison-Wesley, 2005.</li>

<!-- Authors: Michael Mitzenmacher and Eli Upfal -->
<li><a name="Mitzenmacher.Upfal/2005">Michael</a> Mitzenmacher and
  Eli Upfal.
<cite>Probability and Computing: Randomized Algorithms and Probabilistic
  Analysis</cite>.
Cambridge University Press, 2005.</li>

<!-- Authors: Rajeev Motwani and Prabhakar Raghavan -->
<li><a name="Motwani.Raghavan/1995">Rajeev</a> Motwani and
  Prabhakar Raghavan.
<cite>Randomized Algorithms</cite>.
Cambridge University Press, 1995.</li>

<!-- Authors: Rolf Niedermeier -->
<li><a name="Niedermeier/2002">Rolf</a> Niedermeier.
Invitation to fixed-parameter algorithms.
Habilitationsschrift, Universit&auml;t T&uuml;bingen, WSI f&uuml;r Informatik, Germany,
  September 2002.</li>

<!-- Authors: Dexter Kozen -->
<li><a name="Kozen/1991">Dexter</a> Kozen.
<cite>The design and analysis of algorithms</cite>.
Springer, 1991.</li>

<!-- Authors: Christos H Papadimitriou and Kenneth Steiglitz -->
<li><a name="Papadimitriou.Steiglitz/1982">Christos</a>&nbsp;H.
  Papadimitriou and Kenneth Steiglitz.
<cite>Combinatorial optimization: Algorithms and complexity</cite>.
Prentice-Hall, Dover edition, 1982.</li>

</ul>

<!-- END BIBLIOGRAPHY livros -->
</html>


<html>
<a href="http://www2.clustrmaps.com/counter/maps.php?url=http://www.inf.ufrgs.br/~mrpritt" id="clustrMapsLink"><img width=1 src="http://www2.clustrmaps.com/counter/index2.php?url=http://www.inf.ufrgs.br/~mrpritt" style="border:1px solid;" alt="Locations of visitors to this page" title="Locations of visitors to this page" id="clustrMapsImg" onError="this.onError=null; this.src='http://clustrmaps.com/images/clustrmaps-back-soon.jpg'; document.getElementById('clustrMapsLink').href='http://clustrmaps.com'" />
</a>
</html>