Análise de Algoritmos

Referências:
[KT05] Kleinberg, J., & Tardos, É. (2005). Algorithm Design (1st ed.). Boston: Addison-Wesley.
[CLRS09] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). Cambridge: MIT Press.
[HF04] Harel, D., & Feldman, Y. A. (2004). Algorithmics: The Spirit of Computing (3rd ed.). Harlow: Addison-Wesley.
[T98] Taylor, R. G. (1998). Models of Computation and Formal Languages. New York: Oxford University Press.

Algoritmo de Gale-Shapley
Exemplo de binary search
Big-O cheat sheat
Grafos
Algoritmos gulosos
Divisão e conquista
Programação dinâmica
NP e intratabilidade
Teoria da computação
Distâncias: algoritmos aproximativos
Distâncias: algoritmos randomizados
Extra: IA

Trabalho…

  1. (GABRIEL) Trabalho de análise de algoritmo, em Latex
    23/03 Trabalho 1
    Questao 1. Disserte sobre algoritmos aproximativos.
    Questao 2. Disserte sobre algoritmos randomizados.
    Comente sobre:
  2. A motivação por tras destes algoritmos
  3. Sua importância para a computação
  4. Suas principais características,
  5. Algumas das tecnicas para projetar estes tipos de algoritmos
  6. As diferenças deste tipo de algoritmo para outros tipos vistos em aula.
  7. Apresente um exemplo de algoritmo aproximativo e comente
  8. Em linhas gerais, sua analise de complexidade.

30/03 Trabalho 2 – algoritmo
Questao 1. Disserte sobre analise de algoritmos.
Sua resposta deve englobar os seguintes temas: tratabilidade, complexidade assintotica, notação Big O, e classes de função.
Para cada tema, explique: o conceito, comente sobre sua importancia, e apresente exemplos.

Questao 2. Disserte sobre tecnicas de projeto de algoritmos.
Sua resposta deve abordar as seguintes tecnicas: A) algoritmos gulosos, B) divisão e conquista, e C) programação dinâmica.
Diferenças entre as técnicas.
Situações de uso (em quais situações é mais indicada em relação aos demais).
Idéia geral de cada técnica.
Discuta a importância para a computação.
Características principais.
Forma de analisar algoritmos usando essas técnicas.
Cite exemplos de algoritmos que usam essas técnicas e que estejam alinhados com o tema se dua pesquisa.