Pasárgada

Eu quero caminhar sem rumo
até que bem cansado eu chegue
em lugar nenhum e volte pra casa
pra esperar por amanhã e dormir.

Algoritmos Genéticos

Hoje um belo dia de sol de sábado vamos falar um pouco sobre Algoritmos Genéticos. O nome é bonito e a idéia é bem empolgante vamos lá.

Um jardim no mosteiro

Século XIX e Gregor Mendel um religioso que gostava de ervilhas professor da uma faculdade estudava como as características passavam nas gerações de ervilhas caracteríticas como cor das flores tamanho formato das ervilhas etc.

Ele criou o que conhecemos hoje como Genética em seu trabalho com plantas sugeriu a idéia dos genes e das mutações entre os pais para a geração dos decendentes.

Só os melhores sobrevivem

Baseado nas idéias de Darwin e de Mendel os Algoritmos genéticos simulam um esquema de evolução entre as respostas possíveis para um problema. A idéia é colocar várias respostas possíveis em um ambiente de competição onde as respostas mais próximas da ideal tem mais chance de procriar e seu descendentes serão respostas melhores ao problema.

Tá e como se faz genes no computador?

Lembra do problema do cacheiro viajante? (é aquele do cara que vai em várias cidades e o objetivo é achar o menor caminho passando por todas elas uma única vez) Um A.G. para isto poderia ser feito da seguinte forma:

O nosso indivíduo tem em seus genes a ordem na qual as cidades devem ser visitadas a soma dos percursos é inversa a adaptabilidade dele ao ambiente assim quanto menor o percurso mais adaptado ele estará.

1. Produzimos uma geração inicial aleatória com vários indivíduos
2. Escolhemos os melhores indivíduos e eles cruzam (é, eles fazem isso mesmo que vc está pensando)
3. Depois os filhos herdam metade do caminho das cidades de cada um dos seus genitores
4. Esses filhos devem ter leves mutações que proporcionem algo aleatório nas novas gerações.
5. E aí os filhos crescem os pais morrem e aqui entra mais um detalhe alguns membros das gerações anteriores se muito bem adaptados podem sobreviver para cruzar com a nova geração (é os coroas ricos também são pegadores!).

E isso se repete até que se encontre um valor satisfatório. Algo do tipo a distância a ser percorrida deve ser menor que X.

Não vou me estender muito mais. Quer entender AG de verdade? Visite http://www.gta.ufrj.br/~marcio/genetic.html ou http://www.din.uem.br/ia/geneticos/ para demonstrações visuais (com applets e código fonte) e um monte de experimentos com Inteligênica artificial, Vida artificial e Bioinformática sugiro o site do Israelense Ariel Dolan em http://www.aridolan.com/ muito legal!

Eu gosto do Orkut e daí?

Comentário Interno:
Um contato do orkut recém adicionado me livrou de um certo dilema (epicamente ético) agradecimentos vão para a Flávia que faz CC na UFS.

O dia em que Creusa parou a Unit

É eu até acho que isso não é o tipo de coisa que anda se dizendo por aí, mas ontem 01/11/05 no bloco A umas 100 pessoas corriam por um espaço para ver a personagem da novela América apanhar gritando a cada pancada que a mulher tomava. A reunião do diretório acadêmico de informática (DAInfo) do qual faço parte teve que ser transferida para o outro bloco por causa do barulho. Eu fico apenas imaginando como aquilo vai estar na sexta feira quando vai passar o último capítulo da tal novela...
Ai ai ai esse povo me mata de vergonha....

Calc. Numérico: Interpolação

Como eu havia prometido aí vai a segunda parte do estudo de cálculo numérico

INTERPOLAÇÂO!!

Primeiro pra que serve isso? Imagine que você mediu experimentalmente algo daí você quer ter uma idéia de qual o valor para uma determinada entrada que você não mediua ai..., tá bom tá bom vamos a um exemplo.
Você está subindo uma montanha e a cada digamos 200 metros você vê o quanto do seu nariz está congelado. Você vai ter algo do tipo:

medicao Altura %congelada do nariz
x1 7000 0
x2 7200 5
x3 7400 22
x4 7600 37
x5 7800 58

Daí você quer saber como estava o seu nariz a 7500m de altura. Você deve interpolar o 7500 aí e ver como é horrível subir uma montanha sem o agasalho adequado.
O primeiro método de interpolação será a

Interpolação polinomial
Neste método vamos criar um polinômio de grau n-1 onde n é o número de medições que você fez. No nosso caso há 5 medições ou seja Polinômio de grau 4. E como você vai achar este magnífico "polinômio que descreve o congelamento dos narizes em grandes altitudes"? Primeiro vamos ver o formato dele. Já que é de grau 4 o nosso polinômio deve ser algo do tipo:

a1 + b1x1 + c1x1^2 + d1x1^3 +e1x1^4 = 0

Certo? Daí você com toda a paciência do mundo vai para cada ponto medido substituir x do polinômio pelo que você mediu e isso deve dar igual a o teu y também medido daí você vai obter 5 equações polinomiais:

a1 + b1x1 + c1x1^2 + d1x1^3 +e1x1^4 = y1
a1 + b1x2 + c1x2^2 + d1x2^3 +e1x2^4 = y2
a1 + b1x3 + c1x3^2 + d1x3^3 +e1x3^4 = y3
a1 + b1x4 + c1x4^2 + d1x4^3 +e1x4^4 = y4
a1 + b1x5 + c1x5^2 + d1x5^3 +e1x5^4 = y5

Daí resolva o sistema linear acima e Tchan Ram! vc tem o "polinômio que modela o congelamento de narizes em grandes altitudes".

Primeira Competição em TopCoder

Olá para todo mundo, ante-ontem participei pela primeira vez de uma competição oficial do TopCoder. São 3 problemas um valendo 250 outro 500 e outro 1000 pontos fiz o de 250 rapidin o de 500 fiz mas percebi que tinha um erro resolvi passar para o de 1000 e voltar ao de 500 depois.
O de 1000 era relativamente fácil mas, tempo é que foi um problema (da próxima vez começo pelo de 1000), quando faltava apenas 3 min pra acabar o tempo tive uma iluminação !-) e descobri o erro do de 500 voltei para ele mas já não dava mais tempo.
Você sabia que o método replaceAll da classe String do Java pega ? e * como caracteres curinga? é nem eu, aí já viu né.
O pior é que depois que as respostas são enviadas tem 15 min. onde os outro competidores podem examinar o seu código se eles acharem algo errado você perde os pontos daquela questão e ele ainda ganha uns pontins por ter achado. Resumindo perdi os pontos da minha questão de 500 pontos.
No final das contas ganhei uns pontos pela questão de 250 e agora estou no rank (estou em 37º de 55 brasileiros e em 2129º de 3767 no geral) a posição não é das melhores mas foi minha primeira competição ué! A próxima será na quinta-feira(03/11).

ps.: No grupo onde competi fiquei na frente de um chinês e um indiano só precisava ter um argentino pra tirar uma onda ahahuhhauhu ;-)

Calc. Numérico: Sistemas Lineares

Olá! Andei meio distante em? Bom hoje vamos falar um pouco sobre cálculo numérico vamos dar uma olhada em dois assuntos muito interessantes: o primeiro é resolução de sistemas lineares o segundo será interpolação.

Sistemas lineares

Sistemas lineares serão modelados como um conjunto de equações do tipo

ax + by + cz = k

dx + ey + fz = m

gx + hy + iz = n

Você já deve ter visto um desses por aí não?

Eliminação Gaussiana

O primeiro método numérico que vem é Eliminação Gaussiana (é sério o Gauss era muito brabo o cara era um gênio mesmo!).

O objetivo da eliminação Gaussiana é representando os S.L. (apelido para sistema linear) como matrizes operar essa matriz para obter uma matriz triangular, algo do tipo:

a b c k

0 e f m

0 0 i n

Que voltando para o S.L. vamos ter a última equação com:

uma variável = valor

daí é só ir substituindo nas outras equações o resultado da anterior. Muito facim facim né não?

Aí você diz: “não né não e esse passe de mágica aí da matriz pra matriz triangular?” Ok, vamos ver mais de perto como se faz isso.

Para cada item que você queira zerar calcule um multiplicador baseado no elemento da diagonal principal da matriz. (Ãhn?? agora você viajou né não?). Vamos ver um exemplo:

Eu quero zerar o d vou usar o a por que ele está na diagonal principal daí

Mult = d/a

Aí para a linha toda eu faço

item_da_linha2 = (item_da_linha1*mult)- item_da_linha2

é só isso até zerar tudo o que precisar.

Decomposição L.U.

A idéia da Decomposição L.U. é muito parecida com a da Eliminação Gaussiana a diferença aqui será que não vamos nos preocupar com os termos independentes na matriz (k,m e n no exemplo anterior) e para isso depois de feitos os passos da Eliminação Gaussiana vamos fazer umas continhas, coisa pouca eu garanto ;-).

A*X = B

Bonito né? Sim e daí? Tá tá eu explico A = matriz com os coeficientes das variáveis no S.L. no nosso exemplo

a b c

d e f

g h i

X = Matriz coluna com as variáveis do S.L.

x

y

z

B = matriz coluna dos termos independentes

k

m

n

A matriz A será decomposta em matriz L e matriz U (olha aí você num queria saber por quê esse nome?)

U será a matriz A depois de passar por Eliminação Gaussiana que você já sabre fazer.

A matriz L será uma matriz muito interessante triangular superior com 1s na digonal principal e preenchida com os mults usados na Eliminação Gaussiana de A daí L =

1 0 0

m 1 0

m m 1

Põe tudo no liquidificador e... ops receita errada, Voltando como L*U =A

L*U*X=B

Vamos chamr U*X de Y ok? Por quê? Pro quê sim ué!

Daí

L*Y=B

Vamos agora calcular a matriz coluna Y

Y1

Y2

Y3

Ora faça você as contas! Multiplique L pela matriz coluna Y e encontre os resultados comparando o resultado com B.

Agora ache X com U e Y lembre:

U*X = Y

Pivotamento

Pivotamento é o seguinte para garantir boas operações no cálculo do mult e nas operações com linhas da matriz o ideal é que o maior número da matriz seja o seu pivô(pivô é o elemento da diagonal principal que você usa para calcular o mult). Assim você pode trocar uma linha com outra para gaantir que o maior pivô esteja na diagonal principal sempre que for fazer essas operções. No caso do Pivotamento completo você poderá também trocar colunas cuidado!!! ao trocar colunas você também está trocando a ordem das variáveis do seu S.L. então você deve alterar teu vetor X das variáveis de acordo com as trocas que você faça. No caso da Decomposição L.U. a troca de linhas também é perigosa pois você deve trocar os valores da matriz B de acordo!

Métodos Iterativos

Vamos passar agora a métodos iterativos que não darão necessariamente respostas exatas

Método iterativo de Gauss-Jacobi

Antes de começar para este método você precisa de uma condição muito especial. Em cada equação deve haver uma variável cujo coeficiente seja maior que a soma dos outros dois. E isso é importante mesmo! Depois disso selecione para cada variável uma equação que a represente você deve selecionar a variável da equação que tem o maior índice e isolar essa variável. Daí você vai ter coisinhas como

x = (k-by-cz)/a

y = (m-dx-fz)/a

z = (n-gx-hy)/a

Chuta valores para x y e z vai calculando x y e z usando o valor da iteração anterior na atual e pronto.

E isso não para não é?Para sim, calcule o erro de cada variável como sendo (X0-X1)/X1 o erro da iteração será o maior dos erros quando ele chegar ao limiar que você gosta, retire do fogo e deixe descansar por uma hora em local seco e ventilado ops... receita errada de novo ^^.

Método Iterativo de Gauss-Seidel

Faça o mesmo, mas numa mesma iteração se você já calculou x use esse valor no cálculo de y e de z. Oxe e é só isso? É só isso que que você quer mais? Eu eim!

Não vou passar para interpolação hoje não!

Aí já tem coisa demais.

Fica pra o próximo artigo.

Grandíssimas novidades

Olá pra todo mundo depois de uma semana sem atualizações tenho muitas novidades, a primeira é estou estudando no ITP(Instituto de Tecnologia e Pesquisa) da Unit (pense num cara empolgado!) depois que algo estiver acontecendo eu falo mais sobre isso, segunda novidade agora eu tenho internet de banda larga (êêêê :)) o que acaba com as minhas desculpas para não atualizar o blog :-/ com mais frequencia.

Uma nova era se aproxima
Vou mudar a estratégia de postagem normalmente tem um parágrafo sobre mim e depois algo muito mais interessante sobre computação, pois agora vou separar as coisas vou sempre fazer dois posts um com o texto legal e o outro com o texto chato sobre mim, assim vc só lê o que achar interessante. Tá tá bom não é naa de grandioso e inovador mas é mudança né?

Mr. Sandman
Andei pesquisando e vou comprar nem que seja scaneada a coleção do Sandman história em quadrinho que fez sucesso no Brasil no fim da década de 90 e início da década de 00 (é assim que se diz?) ou se pode-se dizer assim no fim do século XX ahuhuaha.
Na seção links tem um link para um site brasileiro sobre o sandman e os perpétuos eles são: Sonho, Morte, Destino, Desejo, Destruição, Desepero e Delírio. Só pra ter uma idéia: "Há muito é dito que os Perpétuos são uma família de sete entes conceituais, descritos como "idéias envoltas em algo semelhante à carne"".

Feivest
Neste sábado vai acontecer a Feira do Vestibular como fugurinha carimbada do evento e vou estar lá pela manhã se bem que tossindo como estou nem sei se vai dar muito certo...

Orkut
Obrigado ao pessoal no orkut os comentários sobre a interpretação do álbum BE do Pain of Salvation e vocês podem comentar aqui também ;) não paga não.

Té mais...

Pain of Salvation (Parte 2)

Continuando sobre o Álbum BE do Pain of Salvation

Como não podia faltar uma música sobre a incapacidade do homem contra morte, a brevidade da vida e tudo mais muito interessante nesta é a ajuda dada pelos trechos "A Scene in Brown and Yellow" onde dá uma cor a cada verso o que ajuda a compor o clima da música um trecheio rápido:

...

They tell me that your pain is gone

Where you are now

Well, you left it here

...

A Scene in White and Grey:

...

Life seems too small when Death takes its toll

I need something to blame for this pain

A próxima é algo como um canto de escravos americanos sabe como é? É quase uma prece por auxilio de Deus legal... legal...

...

Oh Lord

Won't you help me find the way

When I'm lost and lead astray

Oh Lord

...

Uma música que é das melhores do CD é a do Mr. Money um cara que tem tudo que o dinheiro pode comprar e na verdade trata o dinheiro como um Deus e aí o que acontece com ele? alguém criou o dinheiro para ser de seu uso e o dinheiro o destruiu uma relação bem pertinente com o Deus que criou os homens para se entender e foi esquecido destruído pelos homens. E essa merece um bloco maior o Deus Dinheiro falando com o Mr. Money sugerindo dar a ele tudo inclusive a imortalidade e ele cego aceita veja:

...

Dea Pecuniae:

“If you're looking for fulfillment

A Kingdom and a Crown

A Paradise of Free Rides

I am here...

...to let you down

I'll get you the sexy cars

And a taste of divinity

A glimpse of the Stars

Immortality

But then Vanity

Will leave you dried and scarred

(Mr. Money: That's right, oh, give it to me!)

Here's to Me! (Mr. Money: Oh baby, baby)

Here's to Me! (Mr. Money: You'll take care of me)

Here's to Me!

To me “

...

Cada música melhor que a outra uma das músicas com maior apelo emocional é Vocari Dei nela ouvimos pessoas orando ou falando diretamente com Deus perguntando coisas como por que há tanto mal, tanta violência no mundo, além disso, pedidos como aprender a voar pedem desculpa, pedem favores, choram é muito interessante talvez tão ou mais interessante é que a Banda compôs a música mas a letra, o que as pessoas dizem, é real! Eles colocaram no site um número de telefone onde uma secretaria eletrônica estava ligada e pediram que os visitantes ligassem para o número para falar com Deus algo do tipo “Se você pudesse deixar um recado na secretária eletrônica de Deus o que você diria?”.

Faixa 10

Fala sobre a grande besteira que estamos fazendo com o mundo a decadência do homem que criou o dinheiro para ser seu escravo, sua ferramenta, destuído por sua própria criação pela sua ganância veja um pedacinho:

...

We were stuck in this world of change, expecting it to remain - now nothing is left unstained!

No!

When there´s nothing more that we can trade, own, steal, or sell...

When there´s nothing whole because we took it apart, and just left, moved on... When there´s nothing left for us to break, use, abuse, or rape...

Then you´re free to count how much you saved!

…

Faixa 11

E a humanidade quase se destruiu por completo:

2060AD 1.2 Milion people

Pain of Salvation (Parte 1)

Olá para todo mundo

Temos novidades no NotNet a primeira é a nova seção "Estou lendo" vou colocar ali o que eu estiver lendo no momento como eu costumo ler mais de um livro ao mesmo tempo podem sempre estar esperando novidades ainda não está no formato que eu espero a idéia é que coloque os nomes dos que estou lendo e a capa do que estou dando mais atenção no momento vamos ver no que dá. Além disso, teremos agora também BlogRoll uma lista com uns links para outros blogs que eu acho interessantes o primeiro da lista é o site-blog do Silvio Meira ele é o diretor do C.E.S.A.R. (Centro de Estudos Avançados do Recife) muito legal quando eu crescer quero um blog legal assim (só que com um visual menos moderno eu acho).

Hoje eu deveria ter chegado uma hora mais cedo no trabalho para adiantar umas coisas dormi demais :-/ e praticamente cheguei no horário de sempre.

Formatei meu PC, bom meu irmão formatou por que eu mesmo num tenho mais paciência pra essas coisas, tô sem Linux por causa do Saulo que me enrolou a semana toda pra trazer o Kurumin 5.0.

Hoje não vou falar de tecnologia vou falar de Música como se eu entendesse algo sobre isso, mas como voltei a ouvir Pain of Salvation vou comentar sobre o Álbum BE que eu acredito é o mais novo deles.

Pain of Salvation

O cara que compõe as letras é o Daniel é uma banda de Prog Metal e acho que num tenho mais nada a dizer. Li uma entrevista do Daniel dizendo que este álbum BE foi lançado em escolas no país deles com o apoio do ministério da educação de lá e tudo mais. Ah! o nome da banda em todos os álbuns eles tem uma preocupação com a visão do homem da morte e da brevidade da vida daí o nome Dor da Salvação.

O álbum BE

Não vou fazer uma análise dos aspectos musicais por que isso está muito longe da minha competência, sobre as letras meu inglês ruim será minha grande ferramenta ahauhauhauha pois vamos lá, pra começar os nomes das músicas em latim não vou traduzir mesmo por que não sei as traduções.

A primeira Faixa é o surgimento de Deus muito interessante a voz de Deus é de uma criança um homem e aparentemente uma mulher ao mesmo tempo num eco incomum um efeito muito legal uma parte da letra onde Deus tenta entender de onde veio:

I was not

then I came to be

I cannot remember NOT being

...

Maybe I was formed in this silent darkness

From this silent darkness

...

I will call myself GOD

And I will spend the rest of forever

Trying to figure out who I am

...

Na idéia deles Deus cria a humanidade sua imagem e semelhança com o objetivo de observando a si próprio de fora poder entender a si mesmo.

Da segunda música:

Trying to understand myself

I created the world to be an image of myself, of my mind

...

A terceira música é o nascimento e crescimento da humanidade sua fome e curiosidade as estações do ano dão a idéia de tempo e a música tem um ritmo muito legal para ilustrar veja o refrão:

Take me to the forest, take me to the trees

Take me anywhere as long as you take me

Take me to the ocean, take me to the sea

Take me to the Breathe and BE

O "Take" durante a música é substituído por "Teach" e por "Give" no final o que dá a sensação da "evolução" do homem

1. Me leve aos locais às coisas;

2. Aprender sobre elas;

3. Tomar posse delas.

Ok já demais aqui consiga o BE do Pain of Salvation um grande álbum de uma grande Banda. Escrevo talvez mais algo sobre este CD depois...

Acesse http://www.painofsalvation.com/be/ para mais informações e para ver as letras completas além de fontes de onde partiram as idéias do conceito do Álbum.

Até qualquer dia!