Otimização de algoritmos

Quem quer ser milionário?

Maneiras de se tornar rico de uma forma mais rápida: ganhar na mega-sena, ser um jogador de futebol, receber uma herança, estudar matemática… Estudar matemática!? Sim, ela pode ser um atalho para você se tornar milionário, mas para isso você terá de resolver um dos problemas que fazem parte dos denominados problemas do milênio. Um deles envolve uma matéria que aprendemos no ensino fundamental: os números primos.

Crédito da imagem: http://goo.gl/sVMvrg

Crédito da imagem: http://goo.gl/sVMvrg

Por volta de 300 a.c., Euclides formulou os primeiros teoremas sobre os números primos: 1. Há infinitos números primos e 2. Todo número maior do que um pode ser decomposto em um produto de números primos. Desde então o tema se tornou objeto de fascínio dos matemáticos, que procuram encontrar um padrão de distribuição desses números: 1, 3, 5, 7, 11, 13, 17, 19, 23… que, em uma observação rápida, já se mostra não ser trivial. Famosos matemáticos como Eratóstenes, Fermet, Euler publicaram estudos importantes sobre a distribuição de números primos, mas sem uma conclusão definitiva sobre o assunto. Riemann, orientado em seu doutorado por Gauss, formulou a hipótese de Riemann que é um dos sete seis (um deles já foi resolvido, mas o ator recusou o prêmio) problemas do milênio para cuja a solução (a prova da hipótese ou sua refutação) o Instituto Clay de Matemática oferece um prêmio de um milhão de dólares.

Ok! Mas qual a utilidade de se encontrar o padrão nessa distribuição? O que ela pode mudar em minha vida além de me tornar milionário? Ao provar a hipótese de Riemann a segurança da maior parte das empresas, órgãos governamentais e das pessoas estaria comprometida. O motivo? O RSA, que é o método de criptografia mais utilizado no mundo, utiliza chaves de criptografia que são geradas pelo produto de dois números primos gigantescos.

A utilização de números primos para a geração das chaves foi proposital. A fatoração para acha-los é um problema P vs NP, outro na lista dos problemas do milênio.  O problema P vs NP consiste em determinar se uma solução que pode ser verificada rapidamente (NP) possa também ser resolvida rapidamente (P), ou seja, se P = NP ou P ≠ NP. Exemplo prático disto no problema da fatoração: quais são os dois números primos que geram o número 13.717.421? Você consegue resolver isso de forma rápida sem consultar o Google? Provavelmente não (ao menos que você seja o personagem do filme O Cubo) . Porém, sabendo que o números 3.607 e 3.803 são os números primos que geraram este número basta realizar a multiplicação para verificar isso de forma rápida. Computacionalmente, também não temos um algoritmo que resolva o problema de forma rápida, ou seja, em tempo polinomial (a não ser em um computador quântico teórico), ou seja, atualmente o problema da fatoração, base da criptografia RSA, é um problema P ≠ NP.

Voltamos agora para falar novamente da hipótese de Riemann. Caso a hipótese seja comprovada, teremos um algoritmo de distribuição dos números primos que, ao ser usado, possibilitará a redução da complexidade do problema fatorial para polinomial (P = NP) e, consequentemente, não estaremos mais seguros mas, pelo menos, alguém estará milionário.

Fontes:
http://pt.wikipedia.org/wiki/Problemas_do_Pr%C3%A9mio_Millennium
http://www.repositorio.ufpe.br/handle/123456789/7361
http://pt.wikipedia.org/wiki/Teorema_fundamental_da_aritm%C3%A9tica
http://pt.wikipedia.org/wiki/A_quest%C3%A3o_P_versus_NP
http://blog.mhavila.com.br/2010/08/16/p-versus-np-continua-sem-solucao-comprovada/
http://csis.bits-pilani.ac.in/faculty/murali/netsec-09/seminar/refs/atharvasrep.pdf
http://paginapessoal.utfpr.edu.br/rwprobst/formacao-academica/curriculo/primos.pdf
http://pt.wikipedia.org/wiki/RSA

Anúncios

Dell Studio XPS – Um Review

Meu perfil e necessidades: Além de nerd e hardcore eu também sou exigente. Preciso de uma máquina potente pois faço mestrado em otimização de algoritmos, gosto de jogar e, vira e mexe, edito fotos grandes e vídeos maiores ainda.

Meu dia-adia inclui atividades como compilar um algoritmo que faz uso intenso da CPU para cálculos e deixar ele executando durante horas a fio, para medir seu desempenho, melhorar ele e colocar para rodar outra vez. Para vocês terem uma idéia, vejam o gráfico abaixo do uso do meu PC durante uma dessas brincadeiras (com mais de seis horas de duração):

Deu pra perceber que o sistema passa por maus bocados, certo? O sistema de refrigeração tem de ser bom o bastante para aguentar essa carga, os componentes tem que trabalhar bem entre sí… entre outras coisas… Por exemplo, é comum eu também deixá-lo ligado (fazendo downloads, por exemplo) por dias (ou semanas) sem interrupção – e eu espero que ela não perca desempenho por causa disso.

Além disso, gosto de testar softwares e acabo brincando bastante com máquinas virtuais, o que também exige um sistema estável.

Então, minha máquina precisa REALMENTE ser muito potente, estável e confiável.

A história: Sempre gostei de montar minhas próprias máquinas. O pessoal do Fórum do Clube do Hardware sabe. É uma espécie de passatempo para mim e o resultado final é sempre mais vantajoso, pois, via de regra, termina com uma máquina muito mais potente do que uma “pronta” de marca pelo mesmo preço.

Entretanto, essa atividade acaba sempre consumindo bastante tempo: pesquisa de configurações, benchmarks, pesquisa de preços, espera pela entrega das peças, a montagem em sí, testes com o computador montado, o período de configurações e estabilização da configuração… Dependendo da máquina a brincadeira pode durar entre semanas e alguns meses até se atingir o resultado esperado. E desta vez, tempo era um luxo que eu não possuía.

No começo eu estava decidido a montar minha própria máquina, mas durante as pesquisas acabei decidindo dar uma chance às maquinas prontas, e comecei a estudá-las… E no fim acabei escolhendo (e comprando) um Dell Studio XPS, o que foi uma surpresa até para mim, mas que valeu a pena.

A venda: Fiz todo o processo online, na comodidade da minha mesa. No Site da Dell você pode comparar e personalizar o modelo inicial do PC escolhido por você (o que é muito legal!) e tirar dúvidas com os atendentes via telefone ou chat. Claro que eu escolhi o chat. São todos muito atenciosos e você tem, inclusive, a opção de falar sempre com a mesma pessoa, para manter o histórico da conversa.

Depois de personalizar minha máquina (pela enésima vez em vários dias) entrei no chat para tirar algumas dúvidas e fechei a conta por lá mesmo, passando alguns dados e o cartão de crédito.

Isso mesmo: não precisei preencher nenhum formulário. Comprei na base da conversa, literalmente. Foi uma experiência bastante positiva e tudo, PC, entrega e monitor de 24″ de LED, não saiu por mais de R$ 4 mil. Também vieram vários softwares originais, como o prórpio Windows 7, Office Home n Student, Roxio DVD burner e muitos outros, já incluso no preço.

Depois da compra, o processo de pós venda também foi muito bom: pelo site pude acompanhar o status da máquina, a cada passo da entrega, desde o processo de montagem, até o transporte, passando pelo aeroporto, países e locais por onde o brinquedo passou.

Ela veio muito bem embalada, num pacote intuitivo de abrir e bonito também, bem acabado, com uma boa lógica para desempacotar. Mesmo alguém não nerd não teria problemas para montar a máquina, apesar de a Dell oferecer uma opção para que um profissional vá até sua casa, monte o computador novo e migre os dados do seu PC antigo para você. Mamão com açucar.

Outro ponto que me ajudou a escolher foi a garantia: um ano e três meses à domicílio e mais dois anos na assistência técnica. Os mais “micreiros” podem falar: “ah, mas pra garantia valer você vai ter que ficar 3 anos sem dar upgrade na máquina. Impossível.” Errado. A Dell trabalha com o modelo de arquitetura aberta: eu posso, à qualquer momento, abrir minha máquina e fazer modificações sem perder a garantia. Show de bola né?

Sem falar no design: a máquina é muito bonita (tendo em vista que eu não sou grande fã de cases com neon e derivados, mas que até compraria um case mod do R2D2). Ela é branca, com um painel preto na frente e um “porta trecos” em cima, próximo das duas portas usb frontais e da saída para fones de ouvido e microfone. Ela é, inclusive, bonita até por dentro. Dêem uma olhada na galeria abaixo:

Este slideshow necessita de JavaScript.

O veredito: Sim, a máquina vale muito a pena. É muito estável e parruda e até hoje NUNCA travou, mesmo rodando várias aplicações pesadas ao mesmo tempo (e vários jogos também). Isso só acontece em máquinas com peças de ótima qualidade em que os componentes trabalhem muito bem juntos. E esse resultado você só obtem depois de pesquisas, testes e trabalho duro. A Dell está de parabéns em ter conseguido montar um computador potente e com um belo design ao mesmo tempo.

Então, caso você leitor precise de uma máquina para rodar os jogos mais exigentes, programar, editar vídeos ou fotos, eu recomendo um Dell Studio XPS!

Maiores detalhes:

Meu objetivo aqui foi criar um relato para aqueles que querem uma máquina parruda, mas sem muita dor de cabeça ou trabalho. Não vou postar resultados de testes, como 3D Mark e similares, pois acho que não vai agregar muito mais além dos fatos que eu já mencionei: sou um usuário hard core, uso meu processador, memória e placa de vídeo ao máximo para testar a otimização de algoritmos pesados de cálculo e empacotamento de sólidos.

Também gosto de jogar, e jogos como Star Craft II, The Sims Medieval, Crysis, Civilization 5, Ragnarok, Diablo II e vários outros rodam muito bem na minha máquina.

Atualmente estou editando uma foto de 2GB no photoshop, que nem faz cócegas no desempenho e recentemente renderizei um vídeo full HD de alguns GB com duração de 5min que também rodou suavemente na máquina. Processei o render com um algoritmo mixto, usando a placa de vídeo e processador. O resultado: um uso equilibrado de ambos, sem penalizar muito o desempenho geral da máquina. Dêem uma olhada no gráfico abaixo:

Configuração do sistema:

A configuração abaixo é a mesma que veio quando eu comprei o PC da Dell, exceto pelos sistemas operacionais (só o Windows veio de fábrica), o segundo monitor e o sistema de som surround, que eu já tinha.

Sistemas Operacionais (sem contar os da máquina virtual): Windows 7 Home Premium (principal / dia-a-dia) | Mac OS X Snow Leopard | Ubuntu 11.04
Processador: Intel Core I7 860
Memória RAM: 4GB DDR 3 a 1333mhz
HD: 2TB em RAID 0 (2x1TB SATA 3Gb/s 7200rpm HDDS)
Placa de Vídeo: nVidia GeForce GTX 260 | Monitor 1: Dell de 24″ Wide Full HD de LED | Monitor 2: Sansung de 17″
Placa de Rede: Aqui são duas. Uma Broadcom NetLink para Gigabit / Ethernet e uma DW1525 para wireless com suporte aos procolos 802.11a até 802.11n
Som: Realtech 5.1, com qualidade profissional | Caixas de Som: 5.1 c/ sub-woofer
Portas USB: Duas frontais, 8 traseiras.
Leitor de Cartões: Sim. Todos os modelos.
Leitor / Gravador de CDs e DVDs: Sim. Não peguei com leitor de BD pois ainda acho muito caro e sem necessidade (para mim), mas quem quiser pode adquirir já de fábrica.

No mais, dêem uma olhada no site para mais informações.

A Cauda Longa para as Instituições Bancárias

Nota do autor:

Recentemente (para ser mais preciso, hoje) publiquei o artigo inaugural na minha nova coluna sobre usabilidade no Dicas-L. O artigo se chama “A Cauda Longa para a Usabilidade”.

Apesar do tema ter sido usado lá primeiro a verdade é que este artigo (a Cauda Longa para as Instituições Bancárias) foi escrito antes, com alguns dias de antecedência. Ele surgiu quando, em uma conversa sobre a inteligência competitiva das organizações surgiu a pergunta: “como os bancos poderiam se adequar melhor aos clientes do futuro?”.

Na mesma hora o texto abaixo surgiu em minha cabeça, pronto e acabado. Reproduzo-o aqui pois considerei ser uma visão interessante sobre como os bancos farão negócio no futuro.

Também usei a Cauda Longa como tema no Dicas-L pois considero o assunto  interessantíssimo, de extrema relevância na sociedade atual e por acreditar que ainda falta muito a ser explorado sobre isso.

Agora o artigo de verdade:

Basicamente, o resultado da Cauda Longa é a máxima personalização dos produtos e serviços, levando a uma adequação perfeita das necessidades dos usuários. Em ultima instância, seria como voltar a fabricar tudo sob medida para os consumidores (atendendo os desejos destes) mas com grande vantagem econômica para os produtores (maximização do lucro, economia com estoque e sobras de produção).

Hoje os bancos continuam calculando riscos e oferecendo serviços baseados em grandes grupos de consumidores: classes A, B, C, D e E, por exemplo. Entretanto, os clientes obteriam muito mais vantagens se fossem separados em nichos mais específicos levando em consideração mais variáveis, como histórico de compras, local de residência, etc. E, com clientes obtendo mais vantagens e consumindo mais serviços bancários, os Bancos também lucrariam mais.

Uma indústria que já se beneficia desta segmentação é a de seguros automotivos. O seguro é fortemente baseado em nichos bastante específicos (embora ainda possa melhorar muito) e utiliza centenas de variáveis para calcular o preço de uma apólice (distância percorrida diariamente, local de residência, local de trabalho, tipo de alarme, faixa etária, modelo do veículo, cor, etc, etc).

O seguro conseguiu atingir este alto grau de personalização pois utiliza vários processos automatizados para calcular os preços, utilizando inclusive técnicas estatísticas, de calculo diferencial e integral, álgebra, etc.

Os bancos, por outro lado, ainda continuam calculando taxas de juros para empréstimo e de risco levando em conta grandes tendências e grupos com milhões de pessoas e fazendo análises de risco manualmente.

Por que a taxa de um empréstimo para uma mulher de 25 anos que mora no Distrito federal e quer comprar uma TV tem que ser a mesma de um homem de 30 anos que mora em Santa Catarina e quer comprar um iPad para trabalhar? A renda dos dois é a mesma, o valor do empréstimo é o mesmo, mas os perfis são outros, históricos de compra diferentes e o objetivo final do empréstimo também.

Com a cauda longa seria possível criar taxas diferenciadas para atrair perfis diferentes de clientes com um preço quase zero, pois a segmentação seria feita a partir de um questionário e as variáveis analisadas e calculada pelo computador, diminuindo em muito o trabalho braçal da análise de riscos, por exemplo.