====== Análise e Desenvolvimento de Algoritmos (2010/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:** Luciana Buriol, 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 116, [[http://www.inf.ufrgs.br/cei/nscad/images/stories/mapa_2006.jpg|prédio 43425]].\\
**Consultas:** Seg 15.30.\\
**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 =====
  * 8/3/2010: Primeiro dia de aula.


===== Resultados =====
  * [[Notas]]
===== Materiais =====

  * Página da disciplina em [[2008-1|2008/1]] e [[2007-1|2007/1]]
  * {{Notas-3319.pdf|Notas de aula}} (atualizado dia 2/7/2010).
  * Definição do [[T2|segundo trabalho prático]]
  * [[TF|Apresentações trabalho final]]

===== Aulas =====

^ No. ^ Data   ^ Tópicos ^ Notas  ^  Exercícios  ^  Leitura  ^
|   1  | 08/03 | Administrativa, Introdução.          |  p.1-19,A.1,A.2   |                               |  TV1,2.1  |
|   2  | 10/03 | Notação para classes de funções.     |  p.A.3,19-29      |  1.1-1.6                      |  TV2.3    |
|   3  | 15/03 | Análise de complexidade pessimista.  |  p.31-48          |                               |           |
|   4  | 17/03 | Análise de complexidade pessimista.  |  p.31-48          |  2.1-2.4                      |  TV3      |
|   5  | 22/03 | Complexidade média.                  |  A.5,p.48-58      |                               |  TV4      |			 
|   6  | 24/03 | Complexidade média.                  |  p.59-67          |  2.1-2.7                      |  TV4      |		
|   7  | 29/03 | Métodos: Divisão e conquista.        |  p.111-118        |                               |  TV5.3    |	
|   8  | 31/03 | Métodos: Divisão e conquista.        |  p.119-120        |                               |  TV5.3    |		
|   9  | 05/04 | Métodos: Divisão e conquista.        |  p.121-125        |                               |  TV5.3  |		
|  10  | 07/04 | Métodos: Programação dinâmica.       |  p.93-95,100-101,106-112 |                        |  TV5.2    |		
|  11  | 12/04 | Métodos: Programação dinâmica.       |  p.95-99,106-113  |                               |  TV5.2    |
|  12  | 14/04 | Métodos: Programação dinâmica.       |  p.104-105        |                               |  TV5.2    |
|  13  | 19/04 | Métodos: Algoritmos gulosos.         |  p.73-83          |                               |  TV5.1    |
|      | 21/04 | //Feriado//: [[wppt>Tiradentes]]     |                   |                               |           |             
|  14  | 26/04 | Métodos: Algoritmos gulosos.         |  p.84-92          |  3.1,3.2                      |  TV5.1    |
|  15  | 28/04 | Classes de complexidade.             |  p.179-189        |                               |  TV7.1,7.2, AB 1  |
|  16  | 03/05 | Classes de complexidade.             |  p.189-206        |                               |  TV7.3, AB 2,3    |
|  17  | 05/05 | Classes de complexidade.             |  p.207-218        |  {{:cmp155:e04.pdf|EC}}       |           |
|  18  | 10/05 | **Prova**                            |                   |  {{:cmp155:p01d.pdf|P}}, {{:cmp155:sp01d.pdf|S}}  |           |
|  19  | 12/05 | Métodos: Backtracking e Branch&Bound  |  p.137-151       |                               |           |
|  20  | 17/05 | Métodos: Algoritmos randomizados.    |                   |                               |           |
|  21  | 19/05 | Métodos: Algoritmos randomizados.    |                   |                               |           |
|      | 24/05 | //[[http://semac.inf.ufrgs.br|Semana academica]]//  |    |                               |           |
|      | 26/05 | //[[http://semac.inf.ufrgs.br|Semana academica]]//  |    |                               |           |
|  22  | 31/05 | Métodos: Fluxos em redes.            |                   |                               |           |
|  23  | 02/06 | Métodos: Fluxos em redes.            |                   |                               |           |
|  24  | 07/06 | Métodos: Emparelhamentos.            |                   |                               |           |
|  25  | 09/06 | Métodos: Emparelhamentos.            |                   |                               |           |
|  26  | 14/06 | Métodos: Aproximação.                |  p.151-170        |                               |  A3.1.1-3,A2.1.1  |
|  27  | 16/06 | Métodos: Aproximação.                |  p.151-170        |                               |           |
|  28  | 21/06 | Apresentação dos trabalhos.          |                   |                               |           |
|  29  | 23/06 | Apresentação dos trabalhos.          |                   |                               |           |
|  30  | 28/06 | Apresentação dos trabalhos.          |                   |                               |           |
|      | 07/07 | Prova de recuperação.                |                   |                               |           |
| | | | | | |
|      | 17/07 | Término oficial das aulas.  | | | |

Livros: TV=Toscani/Veloso. A=Ausiello, AB=Arora/Barak.

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