:!: Página descontinuada, provavelmente o material não é mais acessível.

====== Análise e Desenvolvimento de Algoritmos (2008/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-15.10, Sala 107, [[http://www.inf.ufrgs.br/cei/nscad/images/stories/mapa_2006.jpg|prédio 43425]].\\
**Consultas:** Ad hoc.\\
**Detalhes:** Vê o [[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 data da prova 1: 07/05 :!:
  * {{p01a.pdf|Prova antiga}} com {{sp01a.pdf|solução}} para preparação disponível!

===== Materiais =====

  * Página da disciplina em [[2007-1|2007/1]]
  * [[http://www.inf.ufrgs.br/pos/ppgc/comuns/disciplinas/sumulas/cmp155.html|Página da disciplina no PPGC]].
  * {{CA-Notas-2561.pdf|Notas de aula}}




































==== Aulas ====

^ No. ^ Data   ^ Tópicos ^ Notas ^  Exercícios  ^  Leitura ^
|   1  | 10/03 | Administrativa, Introdução.          |  p.1-19,A.1,A.2  |           |  TV1,2.1 |
|   2  | 12/03 | Notação para classes de funções.     |  p.A.3,19-29     |  1.1-1.6  |  TV2.3  |
|   3  | 17/03 | Análise de complexidade pessimista.  |  p.31-48         |           |     |
|   4  | 19/03 | Análise de complexidade pessimista.  |  p.31-48         |  2.1-2.4  |  TV3  |
|   5  | 24/03 | Complexidade média.                  |  A.5,p.48-58     |           |  TV4  |			 
|   6  | 26/03 | Complexidade média.                  |  p.59-67         |  2.1-2.7  |  TV4  |		
|   7  | 31/03 | Métodos: Divisão e conquista.        |  p.111-118       |  {{E01.pdf|T1}}                  |  TV5.3  |	
|   8  | 02/04 | Métodos: Divisão e conquista.        |  p.119-120       |                                  |  TV5.3  |		
|   9  | 07/04 | Métodos: Divisão e conquista.        |  p.121-125       |  {{E02.pdf|E1}}, {{S02.pdf|S1}}  |  TV5.3  |		
|  10  | 09/04 | Métodos: Programação dinâmica.       |  p.93-95,100-101,106-112 |    |  TV5.2  |		
|  11  | 14/04 | Métodos: Programação dinâmica.       |  p.95-99,106-113  |   |  TV5.2  |
|  12  | 16/04 | Métodos: Programação dinâmica.       |  p.104-105       |    |  TV5.2  |
|      | 21/04 | //Feriado//: [[wppt>Tiradentes]]     |                  |    |         |             
|  13  | 23/04 | Métodos: Algoritmos gulosos.         |  p.73-83         |  {{E03.pdf|E2}},{{S03.pdf|S2}}  |  TV5.1  |
|  14  | 28/04 | Métodos: Algoritmos gulosos.         |  p.84-92         |  3.1,3.2  |  TV5.1  |
|  15  | 30/04 | Métodos: Backtracking.               |                  |    | {{http://www.jstor.org/sici?sici=0025-5718(197501)29%3A129%3C121%3AETEOBP%3E2.0.CO%3B2-L&cookieSet=1|Artigo}}   |
|  16  | 05/05 | Métodos: Backtracking.               |  p.137-151       |    |    |
|  17  | 07/05 | **Prova**                            |    |  {{P01c.pdf|P}}, {{SP01c.pdf|S}}  |    |
|  18  | 12/05 | Classes de complexidade.             |  p.171-180       |    |  TV7.1,7.2   |
|  19  | 14/05 | Classes de complexidade.             |                  |    |  TV7.3  |
|  20  | 19/05 | Classes de complexidade.             |  p.181-198       |    |    |
|  21  | 21/05 | Classes de complexidade.             |  p.199-208       |    |    |
|      | 26/05 | //[[http://semac.inf.ufrgs.br|Semana academica]]//  |   |    |    |
|      | 28/05 | //[[http://semac.inf.ufrgs.br|Semana academica]]//  |   |    |    |
|  22  | 02/06 | Métodos: Aproximação.                |  p.151-170       |    |  A3.1.1-3,A2.1.1  |
|  23  | 04/06 | Métodos: Aproximação.                |  p.151-170       |    |    |
|  24  | 09/06 | Métodos: Aproximação.                |  p.151-170       |    |    |
|  25  | 11/06 | Métodos: Busca local.                |                  |    |    |
|  26  | 16/06 | Métodos: Busca local.                |                  |    |    |
|  27  | 18/06 | Métodos: Busca local.                |                  |    |    |
|      | 23/06 | //Sem aula//                         |                  |    |    |
|      | 25/06 | //Sem aula//                         |                  |    |    |
|  28  | 30/06 | Apresentação dos trabalhos.          |                  |    |    |
|  29  | 02/07 | Apresentação dos trabalhos.          |                  |    |    |
|  30  | 07/07 | Apresentação dos trabalhos.          |                  |    |    |
| | | | | | |
|      | 10/07 | Término oficial das aulas.  | | | |

Livros: TV=Toscani/Veloso. A=Ausiello.



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

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