Análise de Algoritmos

Notas Finais ->

Conceitos básicos

• Problema.
• Instância de um problema.
• Solução de um problema.
• Problema de otimização.
• Problema de decisão.
• Dados de entrada ("entrada") para um dado problema.
• Esquema de representação de dados de entrada.
• Algoritmo para resolver um problema.
• Função de complexidade no tempo de um algoritmo (complexidade no tempo).
• Função de complexidade no espaço de um algoritmo (complexidade no espaço).
• Ordem de uma função (exponencial, linear, logarítmica, polinomial, constante, n, n^2, n log n, etc.).
• Ordem de complexidade (no tempo ou no espaço) de um algoritmo.
• Árvore de decisão para um problema.
• Ordem de complexidade (no tempo ou no expaço) de um problema.
• Problemas polinomiais.
• Problemas de complexidade maior que polinomial.
• Problemas NP (Polinomiais Não determinísticos).
• Redutibilidade de um problema a outro (em tempo polinomial).
• Problemas NP-completos.
• Esquema para provar que um problema é NP-completo.
• Relação entre P, NP e NP-completo.

Outros tópicos abordados durante o curso

• Problema de achar o máximo e o mínimo de uma lista.
• Problema de ordenação de uma lista
• Técnicas empregadas em diversos algoritmos
• Ordem de diversos algoritmos
• Ordem de complexidade do problema
• Casos particulares do problema
• Problemas da família NP-completo
• Problema do Caixeiro Viajante
• Problema da Mochila
• Problema da Forma Normal Conjuntiva
• Problema da Bacia

Exercícios para testar os conceitos

1. O problema de achar o máximo e o mínimo de uma lista, é NP-completo? Justifique.
2. O problema de ordenar uma lista, é NP-completo? Justifique.
3. O problema de ordenar uma lista é NP? Justifique.
4. O problema de ordenar uma lista é P? Justifique.
5. Existe algum problema de complexidade maior que a polinomial? Qual? Justifique.
6. Descreva dois problemas de complexidade maior que a polinomial.
7. Descreva dois problemas de complexidade polinomial.
8. Descreva dois problemas de complexidade linear.
9. Descreva dois problemas de complexidade constante.
10. Descreva um esquema de representação dos dados de entrada para o problema de decisão de achar o maior e o menor elemento de uma lista.
11. Descreva exatamente a função de complexidade no tempo e no espaço de um algoritmo que, dado o problema anterior e a entrada que você descreveu, responda ao problema comparando os dois valores dados, m e M, com todos os valores da lista. Diga quais foram as operações consideradas na contagem da complexidade no tempo.
12. O problema da ordenação de uma lista tem complexidade O(n log n),
1. Justifique a afirmação.
2. Como pode ser, então, que o algoritmo do balde consiga ordenar em tempo O(n)?
13. Os algoritmos A1, A2, A3 e A4 tem funções de complexidade no tempo T1(n)=1,5 log n + n, T2(n)=3 n^2 + (log n)^3, T3(n)=0,001 n! + 5 n^2 + 3 e T4(n)= (1/3 n^2 - n)^n.
1. Diga quais destes algoritmos tem complexidade linear, quais O(n^2), quais polinomial e quais maior que polinomial.
2. Se tivesse que escolher entre A1 e A3, qual preferiria? Por que motivo?
14. Dê uma entrada para o problema não determinístico de uma mochila de tamanho 100, onde devem ser colocados os objetos de tamanhos e valores dados:

Tamanho do objeto	Valor do objeto
27	1.798,00
59	5.032,00
77	371,00
34	4.322,00
79	1.247,00

Escolha uma das quatro relações abaixo para mostrar a redutibilidade de um problema a outro, em tempo polinomial. O ponto mais difícil é encontrar a função de transformação das entradas de um problema em entradas do outro. Não esqueça que, depois, tem que verificar a equivalência entre as soluções "SIM" e "NÃO" de ambos os problemas. (Similar ao exercicio 9.4 do livro da Sarah Baase).

15. Mostre que o Problema do Caixeiro Viajante pode ser reduzido (em tempo polinomial) ao Problema da Mochila,
16. ... ou vice-versa.
17. Mostre que o Problema da Mochila pode ser reduzido ao problema da bacia,
18. ... ou vice-versa.


Atenção! Na prova será incluída uma questão pedindo para provar que um problema P1 é NP-completo, supondo que um outro problema dado, P2, seja NP-completo. Você poderá escolher ambos os problemas, devendo explicitar qual é o problema que supõe já estar no conjunto.
 

19. Dado o problema de calcular o número de descendentes de cada nó de uma árvore binária
• Descreva exatamente o tamanho de uma entrada do problema.
• Qual é exatamente a complexidade no tempo deste problema?
• Qual é exatamente a complexidade no espaço do problema?
• Qual é a ordem de complexidade do problema? Explique.
20. Problema 9.1 do livro de Sarah Baase
21. Problema 9.2 do livro de Sarah Baase
22. Problema 9.6 do livro de Sarah Baase
23. Problema 9.7 do livro de Sarah Baase (Difícil!)
24. Problema 9.10 do livro de Sarah Baase (Difícil!)

Grupos de Trabalho em Análise de Algoritmos

Os temas a serem apresentados se focalizam na analise de um algoritmo de ordenação. Os sete primeiros grupos analizarão os sete algoritmos do Capítulo 2 do livro de Sarah Baase. O oitavo, um algoritmo de busca lexicografica baseado no Heapsort (Referencia: Aho, Hopcroft e Ullman).

 Todos os trabalhos deverão fazer uma analise da complexidade no pior caso, complexidade média, complexidade no tempo, comparação com outros algoritmos, com o melhor caso teoricamente possível, assim como a descrição da técnica de programação utilizada.