Tulio Faria

Olá pessoal,

essa semana apresentei na faculdade mais um trabalho interessante. Era sobre chegar a uma solução razoável para o problema do caixeiro viajante.

O problema do caixeiro viajante é um dos problemas chamados de NP-Completo, cujo a complexidade é dada como grande.

O problema consiste em um caixeiro viajante que tem N cidades a visitar, todas as cidades possuem ligação entre si e quer-se descobrir a melhor ordem de visita das cidades voltando ao ponto inicial, com a menor distância e sem passar mais de uma vez por cidade.

Achar a solução para esse problema com poucas cidades não é tão dificil, por exemplo, com 4 cidades, há a possibilidade de 4! soluções, ou seja, 24 soluções. A medida que aumentamos o número de cidades inviabilizamos o uso de força bruta (testar todas as possibilidades) pelo o fato do número de soluções aumentar.

O algoritmo genético se espelha na natureza para resolver um determinado problema. Assim sendo, no problema do caixeiro viajante, temos uma população composta por soluções aleatórias para o problema. Desta soluções, pegamos uma porcentagem das melhores e as usamos para gerar as demais. E podemos também fazer algumas mutações para evitar da população ser formada somente por clones .

Na solução do problema feita em Java por mim, eu tenho uma população de 10 soluções geradas aleatoriamente. A cada evolução eu ordeno essas soluções deixando os melhores primeiro. Eu determinei uma taxa de mortalidade de 50%, ou seja, vou pegar os 5 piores e substituir pelo cruzamento dos 5 melhores. Esse cruzamento também é aleatório, sendo que escolho duas soluções pai de forma aleatória, tento copiar seus “genes”, e ao final completo o que não foi possível ser copiado com “genes” aleatórios (mutação). Na implementação, as distâncias entre cidades é dada por uma matriz de adjacência de 8×8 (8 cidades).

O código completo do Algorítmo Genético implementado em Java.

A implementação não garante uma solução ótima, mas tende a ser uma solução razoável na maioria das vezes.

Bom é isso, até a próxima pessoal!

Olá pessoal,

estou meio sumido, mas não sei se todos sabem, último ano de faculdade, trabalhos a mil, projeto final de curso e muito serviço deixam qualquer um louco…rs…

Neste post vou falar sobre uma técnica que foi o tema proposto em um trabalho na faculdade: Esteganografia (Steganography), que é a arte de esconder uma mensagem em outra, ou no meio digital, esconder um arquivo em outro.

O primeiro trabalho que foi proposto foi esconder um texto em um texto (HIT - Hide in Text). Foi o que mais deu trabalho, pois não há nada na internet falando sobre isso nem mesmo no Google . A técnica que desenvolvi não deve ser tão inovadora, mas resolveu o problema, com a restrição do texto “cobaia”, que irá abrigar (esconder) a mensagem, tem que ser muito, mas muito grande!

O que fiz foi trocar todos os espaços do texto pelos caracteres 0, 32 e 160 (códigos ASCII). Simples né? Mais ou menos…

Tive que fazer uma conversão de cada caracter ASCII da mensagem a ser escondida nesses 3 caracteres. Ou seja, haja espaços para conseguir esconder uma mensagem nem tão grande.

A implementação foi feita em ANSI C. Os fontes dos arquivos podem ser baixados aqui:

• Esconder texto
• Ler texto oculto

A implementação do HIP - Hide in Picture me consumiu um pouco mais de tempo, já que eu teria que ler sobre como funciona o formato BMP. Desta vez a implementação foi em PHP , por falta de tempo mesmo…

Os fontes podem ser encontrados aqui:

• Esconder texto (PHP)
• Ler texto oculto (PHP)

O link para o demo online.

Bom pessoal, até a próxima!

Olá pessoal,

hoje me deparei com a Kombi dos Correios tocando a minha campainha, mas não lembrava de ter comprado nada cuja a previsão de chegada fosse hoje.

Havia chegado isso:

Na mesma hora fiquei me perguntando, que diabos vinha a ser aquilo (What the hell is this?), mas caiu a ficha que poderia ser os livros que comprei no Amazon.com chegando (pasmem) 10 dias antes do previsto.

E não é que era mesmo:

Não se empolgue querendo importar notebooks, iPod’s e etc. Porque a Receita Federal não cobra impostos de importação apenas de livros! Se não estou enganado, para as outras coisas adicione uns 60% no valor do produto. Aliás, se for pelo Amazon eles nem entregam caso não seja livro.

No fim das contas compensou, entre os livros que comprei está um Dicionário Oxford Advanced Learners, que no Brasil custa aproximadamente R$ 115,00, paguei um pouco mais de R$ 60,00 com frete no Amazon.

Um fato curioso é que minha encomenda apesar de ter sido feita no site americano deles, foi enviada da Alemanha:

Fica então a dica para quem não tem medo de inglês principalmente de livros.

Abraços e até a próxima!

Olá pessoal,

este é o último post de 2007. Últimos instantes de 2007. É sempre nessas horas que fazemos um balanço de tudo de positivo que ocorreu no ano e tudo que desejamos para o próximo.

Gostaria de desejar a todos vocês um excelente ano novo com muito sucesso e saúde!

Estou com muitas idéias para o blog para o próximo ano, se eu conseguir colocar grande parte delas em prática.

Abraços!

Olá pessoal,

gostaria de desejar a todos vocês um feliz natal…

Abraços!

Olá pessoal,

este post é uma propaganda

Para quem não sabe, meu irmão é DJ. Antes que digam: “Grande coisa!”, queria dizer que ele é diferente. Por quê? Simplesmente porque além de tocar ele ainda compõe.

Dia 27 de Dezembro deste ano, ele irá lançar seu primeiro EP, o Cogitum EP. Lançamento internacional no site: BeatPort.

Quem curte música eletrônica pode conferir o trabalho dele em:

www.djfulvio.com.br e www.myspace.com/deejayfulvio

Apesar de ouvir um bom e velho metal, tenho que confessar que ele manda bem

Tá feito o merchan

Abraços a todos!

Olá pessoal,

esses dias achei este cartoon, muito bom por sinal.

Link original.

Tradução:
Quadro 1: “Oi, aqui é da escola do seu filho. Nós estamos tendo um problema de computador.
Quadro 2: Mãe: “Oh, ele quebrou alguma coisa?” Telefone: “De certa forma”
Quadro 3: Telefone: “Vocês realmente deram o nome de Robert ‘); DROP TABLE students; — ? ” Mãe: “Ah sim, pequeno Bobby Tables, como o chamamos”
Quadro 4: Telefone: “Bem, nós perdemos todos os registros de alunos deste ano. Espero que vocês estejam felizes” Mão: “E eu espero que vocês tenham aprendido a sanitizar suas entradas no banco de dados”

Eu ri demais quando li… Pena que não é pra qualquer um que eu posso mostrar isso, dificilmente quem não entenda um mínimo de SQL não entenderia a história.

Aliás, achei uma excelente idéia para nomear meu filho, quando eu for ter um (quem sabe) daqui uns 20 anos! rs

Abraços a todos,

Olá pessoal,

desculpem a demora na postagem de algum material sobre a CONISLI, mas que fim de ano sempre é muito “brabo” no quesito correria :).

Quem quiser baixar os slides, aqui estão eles.
Sobre os vídeos, ainda estou apanhando para compactá-los. Mas creio que logo conseguirei

Abraços e até mais…

Olá pessoal,

entre os dias 9 e 11 de Novembro acontecerá em São Paulo (na UNICID) o  CONISLI - Congresso Internacional de Software Livre. Eu irei participar através da palestra: CakePHP - desenvolvimento web ágil com PHP.

A minha palestra acontecerá no dia 10/11 as 9:00 da manhã.

Conto com a presença de vocês, não só para a minha palestra mas também para o congresso.

Abraços,

Olá pessoal,

esta semana estava pensando sobre um assunto interessante: Minha conta do Dreamhost está vencendo a qual possibilitou eu colocar os vídeos tutoriais…
Não tão interessante assim né? rs…

Na verdade este post é para as boas almas que desejarem ajudar de alguma forma o blog… O link para doação está disponível  do lado esquerdo do blog, quem quiser doar usando o PagSeguro (do UOL) é só clicar lá… Quer ajudar de outra forma? Entre em contato comigo…

Claro que a ajuda será bem vinda tanto para o blog quanto para mim Vocês sabem como é né? Vida de universitário é uma tristeza
Abraços,