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!
Today é Hoje! setembro 30, 2008
Posted by kit15 in Uncategorized.Tags: cormen, teoria da computação, teoria da vida, teoria do caos
1 comment so far
Por onde inciar um blog?
Melhor, o que postar primeiro?
Muitos preferem começar escrevendo da sua vida! Outros já começam “esculachando” e outros.. outros não fazem nada, são folgados! Mas, optamos por não fazer nada!
De modo geral, este blog será de grande valia para “computeiros” (pessoas que, com certeza, não trabalham em “puteiros”, a não ser que este seja informatizado), envolvendo teoria da computação e algoritmos. Também, pessoas que gostam de brincar com teoria do caos, métodos numéricos, modelagem matemática, resolução de problemas, teoria da vida. Ops… Teoria da vida?
Pois é, alguns posts serão grandes teorias discutidas e construídas a anos pelo autor e/ou co-autor do blog. Teorias que envolvem qualquer coisa, mas puramente descrevem e explicam algum padrão na sociedade ou critica alguma coisa. Talvez em algum dia mais ensolarado, poderá haver coisas diferentes!
Porém, o trabalho principal deste blog é para computeiros, vamos brincar com Teoria da Computação e muitos algoritmos/problemas “cabulosos”. Quem não viu análise e projeto de algoritmos, complexidade de algoritmos, teoria da computação ou qualquer disciplina que usa o livro do Cormen (principalmente) ou do Manber (talvez) com aquela grande quantidade de exercícios com estrelas * ???? (Parece classificação de Hotel, só que Binária!).
Assim, tentaremos colocar grande parte dos exercícios do livro do Cormen resolvidos por nós e, com os algoritmos implementados em Java. É claro, que terá erros, mas whatever… Então, se vc é um caboco preguiçoso, com certeza, vai adorar tudo isto. Mas se vai usar como uma consulta, poderá gostar, como também vai: “malditos fdps que fizeram o treco errado!”, por outro lado, uma leva vai só dizer “malditos fdps que colocaram isto na net.”
Gotcha!
