NP-Completo? O Problema de Catar Mulher. Outubro 2, 2008
Posted by kit15 in teoria da vida.Tags: algoritmos, mulher, np-completo
add a comment
Um computeiro está acostumado a tratar de diversos problemas no dia-a-dia. Quem nunca ouviu falar dos seguintes problemas, ou até mesmo se deparou com o maldito?!
- Problema da mochila: é dada uma mochila com capacidade W, uma coleção de n itens, cada um com valor c e peso w. Assim, o problema é maximizar o valor carregado, ou seja, quantos itens levar para maximizar o valor, respeitando o limite de peso da mochila W. (Este é muito simples de resolver, porém a solução não cabe aqui, causa overflow!);
- Problema do Caixeiro Viajante: Um maldito andarilho tem uma bicicleta e uma grande quantidade de cidades para visitar, donde existem diversas rotas possíveis, cada uma com um custo associado (nº de pedaladas). A idéia é, então, fazer com que o maldito passe por todas as cidades uma única vez gastando o menor número possível de pedaladas, menor custo possível, e volte a sua cidade de origem. Como eu não sou andarilho, prefiro não propor a solução. Quem sabe, mais tarde?!
Bem.. chega destes problemas simples e fácil de serem resolvidos. Vamos abordar algo realmente interessante e que até o momento não existe solução adequada, o PROBLEMA DE CATAR MULHER.
Vaga pela rede um monte de textos e referências esdruxulas ensinando como minimizá-lo ou resolvê-lo, inclusive material pago com citações de vários usuários felizes. Vale lembrar que não vendemos CD’s, nem E-BOOKs ensinando como resolvê-lo, nem existe um monte de comentários de pessoas “felizes” que compraram e se deram bem!
Nosso propósito é específico e resume em:
- Mostrar diversas estratégias computacionais para resolver o problema (recursão, iteração, programação dinâmica, estratégia gulosa, magia negra! Ops.. magia negra está fora do escopo, mas vamos falar de oráculo e o que se segue);
- Chegar em um consenso de que o problema, afinal, pode ou não ser resolvido?! Interessa-se soluções polinomiais!
- Se sim, mostrar qual estratégia utilizar, independente da instância do problema.
No mais, esperamos chegar a alguma conclusão sobre este problema após todas estas abordagens!
GOTCHA!
Sincronia em Sistemas Dinâmicos! Outubro 1, 2008
Posted by kit15 in teoria do caos.Tags: sincronia, sistemas dinâmicos
add a comment
Sistemas dinâmicos, em linhas gerais, são sistemas que variam com o passar do tempo e estão definidos mediante uma equação diferencial. Não estamos interessados em sistemas dinâmicos por si só (e.g. um sistema massa-mola), mas em sincronia em sistemas dinâmicos.
O que vem a ser sincronia? Talvez, algo como iniciar no mesmo tempo; terminar no mesmo tempo; ou que gasta o mesmo tempo. Na verdade, depende do que vc quer que seja sincronizado. Então, whatever…
O propósito é descrever alguns exemplos legais de sistemas dinâmicos que apresentam sincronia. Alguns ou todos foram retirados do livro Sistemas Dinâmicos (Monteiro, 2002, editora livraria da Física) e são expressos a seguir:
- Seja dois relógios de pêndulo atrasados segundos um em relação ao outro e presos na mesma parede. Após um certo intervalo de tempo, depende do quanto estão atrasados, ambos entram em sincronia e passam a marcar o mesmo segundo.
- Seja uma leva de pessoas reunidas em um determinado local. Quando uma delas ou um pequeno grupo começam a bater palmas, “todas” as outras batem palmas também;
- Mulheres acondicionadas no mesmo ambiente, após um certo período de tempo, começam a ter o ciclo menstrual igualado, isto é, passando a menstruar no mesmo tempo;
No momento, como a memória é boa, lembro-me só destes exemplos. Mas, acredito existirem diversos outros fenômenos que possuem tal característica, porém ainda não descritos ou explicados/provados.
No mais, comecem a perceber o mundo a sua volta, pois muita coisa boba, para alguns vale um artigo científico e para outros, ainda será muita coisa boba!
GOTCHA!
