====== Análise e Desenvolvimento de Algoritmos (2012/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.//
===== Informações gerais =====

**Professores:** Marcus Ritt\\
**Carga horária:** 60 h (em 30 aulas de 2h)\\
**Créditos:** 4\\
**Súmula:** Complexidade de algoritmos. Cálculo de complexidade. Métodos básicos de construção de algoritmos. Classes de complexidade. Algoritmos aproximativos.\\
**Horário/Sala:** Seg/Qua 13.30, sala 111.\\
**Consultas:** Seg 15.30-17.00.\\
**Detalhes:** Ver a [[http://ppgc.inf.ufrgs.br/index.php?option=com_content&view=category&layout=blog&id=81&Itemid=73|página no PPGC]].

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

   * Nova versão da notas de aula disponível
   * Definição do projeto atualizado.
===== Resultados =====
  * [[2012-1-Notas|Notas]]
  * [[2012-1-Freq|Frequência]]

===== Materiais =====

  * Página da disciplina em [[2011-1|2011/1]], [[2010-1|2010/1]], [[2008-1|2008/1]] e [[2007-1|2007/1]]
  * {{:cmp155:notas-4227.pdf|Notas de aula}} (atualizado 16/5/2012).


==== Aulas ====

^  No.  ^  Data  ^ Tópicos ^  Cap.((Capítulo nas notas de aula))  ^  Exercícios  ^  Soluções ^ Leitura  ^
|  1 | 05/03 | Administrativa, Introdução. Notação assintótica.     |   1,2 |  {{e01b.pdf|E1}}  |  {{s01b.pdf|S1}}  | KT1-3 |
|  2 | 07/03 | Notação assintótica. Análise de complexidade.        |   1,2 |                   |                  | KT1-3 |
|  3 | 12/03 | Divisão e conquista.                                 |     6 |                   |                  | KT5   |
|  4 | 14/03 | Divisão e conquista.                                 |     6 |                   |                  | KT5   |
|  5 | 19/03 | Divisão e conquista.                                 |     6 |  {{e02b.pdf|E2}}  |  {{s02bv1.pdf|S2}}  | KT5   |
|  6 | 21/03 | Algoritmos gulosos.                                  |     4 |                   |                  | KT4   |
|  7 | 26/03 | Algoritmos gulosos.                                  |     4 |                   |                  | KT4   |
|  8 | 28/03 | Algoritmos gulosos.                                  |     4 |  {{e03b.pdf|E3}}  |  {{s03bv1.pdf|S3}}                | KT4   |
|  9 | 02/04 | Programação dinâmica.                                |     5 |                   |                  | KT6   |
| 10 | 04/04 | Programação dinâmica.                                |     5 |                   |                  | KT6   |
| 11 | 09/04 | Programação dinâmica.                                |     5 |                   |                  | KT6   |
| 12 | 11/04 | Backtracking, Branch-and-bound.                      |     7 |  {{e04av1.pdf|E4}}  |  {{s04a.pdf|S4}}  |       |
| 13 | 16/04 | Backtracking, Branch-and-bound.                      |     7 |                   |                  |       |
| 14 | 18/04 | [[Network flow|Fluxos em redes (aula a distância).]]   |  14.1 |                   |                  | KT7   |
| 15 | 23/04 | Fluxos em redes.                                     |  14.1 |                   |                  | KT7   |
| 16 | 25/04 | Fluxos em redes.                                     |  14.1 |                   |                  | KT7   |
| 17 | 30/04 | Emparelhamentos.                                     |  14.2 |                   |                  |       |
| 18 | 02/05 | Emparelhamentos.                                     |  14.2 |                   |                  |       |
| 19 | 07/05 | Emparelhamentos.                                     |  14.2 |                   |                  |       |
| 20 | 09/05 | Algoritmos randomizados.                             |       |  {{e05a.pdf|E5}}  |  {{s05a.pdf|S5}}  | KT13  |
| 21 | 14/05 | Algoritmos randomizados.                             |       |                   |                  | KT13  |
| 22 | 16/05 | Algoritmos randomizados.                             |       |                   |                  | KT13  |
|    | 21/05 | //[[http://semac.inf.ufrgs.br|Semana academica]]//   |       |                   |                  |       |
|    | 23/05 | //[[http://semac.inf.ufrgs.br|Semana academica]]//   |       |                   |                  |       |
| 23 | 28/05 | Algoritmos randomizados.                             | 15    |                   |                  | KT13  |
| 24 | 30/05 | Teoria da complexidade.                              | 16-19 |                   |                  | KT8,  |
| 25 | 04/06 | Teoria da complexidade.                              | 16-19 |                   |                  | KT8,9 |
| 26 | 06/06 | Teoria da complexidade.                              | 16-19 |  {{e06a.pdf|E6}}  |  {{s06a.pdf|S6}}  | KT8,9 |
| 27 | 11/06 | Apresentação dos trabalhos.                          |       |                   |                  |       |
| 28 | 13/06 | Apresentação dos trabalhos.                          |       |                   |                  |       |
| 29 | 18/06 | Apresentação dos trabalhos.                          |       |                   |                  |       |
| 30 | 25/06 | **Prova**                                            |       |  {{p01g.pdf|P}}   |  {{sp01g.pdf|SP}}  |       |
|    | 27/06 | Prova de recuperação.                                |       |                   |                  |       |
|    |       |                                                      |       |                   |                  |       |
|    | 14/07 | Término oficial das aulas.                           |       |                   |                  |       |
 
Livros: TV=Toscani/Veloso. A=Ausiello, KT=Kleinberg/Tardos.



==== Avaliação ====

A nota final é composto pela nota obtido na solução dos exercícios (1/3), a nota do projeto (1/3) e a nota da prova (1/3). Informações sobre o projeto: {{:cmp155:pf20121.pdf|aqui}}.

==== Bibliografia ====
<html>
<!-- BEGIN BIBLIOGRAPHY Bibliografia -->                                             
<!--                                                                                 
    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 -s unsortlist Bibliografia.bib Bibliografia.html -->
<ul class="bib2xhtml">                                                                                     

<!-- Authors: Sanjeev Arora and Boaz Barak -->
<li><a name="Arora.Barak/2009">Sanjeev</a> Arora and Boaz Barak.
<cite>Computational Complexity: A Modern Approach</cite>.       
Cambridge University Press, 2009.</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.
<a href="http://projects.csail.mit.edu/clrs"><cite>Introduction to
  Algorithms.</cite></a>
The MIT Press, 2nd edition, 2001.</li>

<!-- Authors: Michael R Garey and David S Johnson -->
<li><a name="Garey.Johnson/1979">Michael</a>&nbsp;R. Garey and David&nbsp;S.
  Johnson.
<a href="http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness"><cite>Computers and intractability: A guide to
  the theory of NP-completeness</cite></a>.
Freeman, 1979.</li>

<!-- Authors: E Horowitz and S Sahni -->
<li><a name="Horowitz.Sahni/1984">E</a>.&nbsp;Horowitz and S.&nbsp;Sahni.
<cite>Fundamentals of Computer Algorithms</cite>.
Computer Science Press, 1984.</li>

<!-- Authors: Laira Vieira Toscani and Paula A S Veloso -->
<li><a name="Toscani.Veloso/2005">Laira</a>&nbsp;Vieira Toscani and
  Paula A.&nbsp;S. Veloso.
<a href="http://www.inf.ufrgs.br/~laira/"><cite>Complexidade de
  Algoritmos</cite></a>.
Editora Sagra Luzzatto, 2a edition, 2005.</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: Bernhard H Korte and Jens Vygen -->
<li><a name="Korte/2005">Bernhard</a>&nbsp;H. Korte and Jens Vygen.
<a href="http://www.or.uni-bonn.de/~vygen/co.html"><cite>Combinatorial
  optimization theory and algorithms</cite></a>.
Springer, 4th edition, 2008.
INF 65.012.122 K85c.</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>

<!-- 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: S Dasgupta and C Papadimitriou and U Vazirani -->
<li><a name="Dasgupta.etal/2009">S</a>.&nbsp;Dasgupta,
  C.&nbsp;Papadimitriou, and U.&nbsp;Vazirani.
<cite>Algoritmos</cite>.
McGraw-Hill, 2009.</li>

</ul>

<!-- END BIBLIOGRAPHY Bibliografia -->

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