====== Algoritmos avançados (2009/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, 109 (Seg), Lab. 104 (Qua), [[http://www.inf.ufrgs.br/cei/nscad/images/stories/mapa_2006.jpg|prédio 43425]].\\
**Consultas:** TBD.\\
**Detalhes:** Vê o {{sy.pdf|programa}}.



Por razões técnicas, a disciplina foi dividida em duas disciplinas de dois créditos. Eles devem ser selecionados em conjunto:

  * INF05504: TÓPICOS ESPECIAIS EM COMPUTAÇÃO V
  * INF05505: TÓPICOS ESPECIAIS EM COMPUTAÇÃO VI
===== Resultados =====

  * [[2009-1-Trabalhos|Trabalhos]]
  * [[2009-1-Notas|Notas]]

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

  * Aula de laboratório no dia 03/06 na sala 103!



















===== Materias =====

  * {{Notas.pdf|Notas de aula}} (atualizado 13/6/2009)
  * Algumas [[http://www.cs.princeton.edu/~wayne/cs423/demos.html|demonstrações]] de algoritmos.
  * [[Dicas]] para os trabalhos experimentais 












==== Aulas ====

^ No.  ^ Data   ^ Tópicos                                              ^ Notas pág. ^  Exercícios  ^  Soluções   ^ Leitura ^
|  1 | 02/03 | Introdução. Heaps binários.	       |                    |   |   | KT2.5,C6  |
|  2 | 04/03 | Laboratório 1.                          |                    |   |   |           |
|  3 | 09/03 | Heaps binomiais.                        |                    |   |   | K8,C19    |
|  4 | 11/03 | Laboratório 2.                          |                    |   |   |           |
|  5 | 16/03 | Heaps Fibonacci.                        |                    |   |   | K9,C20    |
|  6 | 18/03 | Laboratório 3.                          |                    |   |   |           |
|  7 | 23/03 | Fluxo em redes 1.                       |                    |   |   | KT7.{1,2} |
|  8 | 25/03 | Laboratório 4.                          |                    |   |   |           |
|  9 | 30/03 | Fluxo em redes 2.                       |                    |   |   | KT7.{2,3} |
| 10 | 01/04 | Laboratório 5.                          |                    |   |   |           |
| 11 | 06/04 | Fluxo em redes 3.                       |                    |   |   | KT7.4     |
| 12 | 08/04 | Laboratório 6.                          |                    |   |   |           |
| 13 | 13/04 | Emparelhamentos 1.                      |                    |   |   | KT7.5,K19 |
| 14 | 15/04 | Laboratório 7.                          |                    |   |   |           |
| 15 | 20/04 | Emparelhamentos 2.                      |                    |   |   | K20       |
| 16 | 22/04 | Laboratório 8.                          |                    |   |   |           |
| 17 | 27/04 | Hashing 1.                              |                    |   |   | KT13.6,C11 |
| 18 | 29/04 | Laboratório 9.                          |                    |   |   |           |
| 19 | 04/05 | Hashing 2.                              |                    |   |   |           |
| 20 | 06/05 | Laboratório 10.                         |                    |   |   |           |
| 21 | 11/05 | Aproximação 1.                          |                    |   |   | V3        |
| 22 | 13/05 | Laboratório 11.                         |                    |   |   |           |
| 23 | 18/05 | Aproximação 2.                          |                    |   |   | V4       |
| 24 | 20/05 | Laboratório 12                          |                    |   |   |           |
|    | 25/05 | //[[http://semac.inf.ufrgs.br | Semana acadêmica]]//  |      |   |   |           |
|    | 27/05 | //[[http://semac.inf.ufrgs.br | Semana acadêmica]]//  |      |   |   |           |
| 25 | 01/06 | Randomização 1.                         |                    |   |   | MU1,KT13.2  |
| 26 | 03/06 | Laboratório 13.                         |                    |   |   |           |
| 27 | 08/06 | Randomização 2.                         |                    |   |   | C31.8     |
| 28 | 10/06 | Laboratório 14.                         |                    |   |   |           |
| 29 | 15/06 | Parametrização.                         |                    |   |   | KT10.1    |
| 30 | 01/07 | ** Prova **                             |                    |   |   |           |
|    | 08/07 | Prova de recuperação.                   |                    |   |   |           |
|    |       |                                         |                    |   |   |           |
|    | 10/07 | Término oficial das aulas.              |                    |   |   |           |
Livros: KT=Kleinberg/Tardos. K=Kozen, C=Cormen, et al.,V=Vazirani, MU=Mitzenmacher/Upfal


===== 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: Vijay V Vazirani -->
<li><a name="Vazirani/2001">Vijay</a>&nbsp;V. Vazirani.
<cite>Approximation algorithms</cite>.
Springer, 2001.</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>

</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>