Análise de Algoritmos

Professor Dr. Gabriel de Oliveira Ramos.

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

Exercícios:

prova

Trabalhos:

  1. Trabalho de análise de algoritmo, em Latex, data: 23/03 Trabalho 1
    Questão 1. Disserte sobre algoritmos aproximativos.
    Questão 2. Disserte sobre algoritmos randomizados.
    Comente sobre: a motivação por trás destes algoritmos; Sua importância para a computação; Suas principais características; Algumas das técnicas para projetar estes tipos de algoritmos; As diferenças deste tipo de algoritmo para outros tipos vistos em aula; Apresente um exemplo de algoritmo aproximativo e comente; Em linhas gerais, sua analise de complexidade.
Trabalho1_ProfGabriel_v1

2. Trabalho 2: Data: 30/03.
Questão 1. Disserte sobre analise de algoritmos. Sua resposta deve englobar os seguintes temas: tratabilidade, complexidade assintótica, notação Big O, e classes de função. Para cada tema, explique: o conceito, comente sobre sua importância, e apresente exemplos.

Questão 2. Disserte sobre técnicas de projeto de algoritmos. Sua resposta deve abordar as seguintes técnicas: 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). Ideia 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 de sua pesquisa.

Trabalho2_ProfGabriel_v2

A turma com o professor Gabriel: