AEDs III - 25/04/2011

Na aula passada falamos vários paradigmas de mapeamento
de algoritimos paralelos, (ex: deadlock, barreira e variáveis de condição)

Nessa aula vamos falar de alguns problemas práticos de programação,
para análise:

CONCEITO:
Problemas NP Completo
são problemas para os quais não existe uma solução barata de ser computada, mas sim soluções de tentativa e erro.
Estes problemas são conhecidos por possuírem complexidade O(n!) ou superior.
Vamos citar abaixo dois casos deste tipo de problema, e então discutir possíveis soluções.

Prob 1: Passeio do Cavalo, neste problema deve-se descobrir se é ou não possível para a peça de chadrês "Cavalo"
        sair de uma posição (x,y) em um tabuleiro de tamanho NxN caminhar por todos os quadrados do tabuleiro
        e então retornar para a posição original.
	Para solucionar este problema deve-se ter:
	--> Um conjunto de regras de caminhamento, para impedir a repetição do mesmo caminho.
	--> E um modo de verificar se a solução foi cumprida.

Prob 2: O Problema da mochila. Dada uma mochila de espaço X, e um conjunto de itens cada um com um tamanho e cada um com um valor,
        deve-se descobrir qual a maior soma de valores que podem ser colocadas dentro da mochila.
        Neste problema também deve-se ter:
        --> Um conjunto de regras de colocação de objetos, para não repetir os mesmo conjuntos.
        --> E um modo de descobrir a solução, no caso é uma comparação um a um do valor de cada caso.

  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

CONCEITO:
Algoritmo Guloso:
Um algoritimo guloso é aquele que ao processar uma pequena fração do problema,
assumi que uma grande parte do problema foi solucionada.
A principio parece confuso, mas a verdade é que é só um nome complicado para uma coisa que usamos o tempo todo
quase sem perceber. Para esclarecer segue um exemplo abaixo:

Em problemas de ordenação, poderíamos tentar por tentativa e erro verificar cada vetor possível e ver se ele está ordenado ou não,
ou poderíamos de uma maneira mais normal, e eficiênte simplismente ordenar um a um cada peça do vetor.
Repare que quando nós colocamos a antes de b no vetor, pois a<b, eu elimino nesse pequeno processamento, um grande
conjunto de possibilidades, ou seja todas àquelas possibilidades onde a se encontraria depois de b.
Isto é portanto um algoritimo guloso, que com um pequeno processamento, utilizando-se de uma propriedade conhecida do problema
elimina um grande número de possibildades de solução, aproximando-se mais rápido da única solução verdadeira.

CONCEITO:
Programacao dinâmica é a capacidade de um programa de escolher em tempo de execução o melhor método para continuar o processamento.
Isso é então um programa que possuí duas funções que resolvem um mesmo problema, mas as vezes uma solução é mais eficiente
que a outra.
Se o programa recebe um conjunto muito grande de entradas para ser processado ele realiza testes com as primeiras entradas,
e decide medindo os tempos qual das duas soluções está se mostrando mais eficiênte e então à utiliza pelo resto do processamento.

// A aula terminou abruptamente logo depois dessa definição, o professor disse que continuaria a falar disso na próxima aula,
// após a prova.