Alex Florentino

O Problema P Versus NP

1. Introdução

A Matemática não é uma ciência pronta e acabada conforme muitas pessoas poderiam pensar, pelo contrario existe uma quantidade significativa de trabalhos sendo produzidos que exploram tanto conhecimentos antigos aplicados para novos problemas como novos conhecimentos matemáticos aplicados para antigos problemas.

Clay Mathematics Institute é uma instituição privada estabelecida por um bem sucedido homem de negocio e sua esposa em 1998, nos  EUA  com a missão de “Desenvolver e disseminar o conhecimento matemático”, e para comemorar o inicio de um novo milênio o Clay Institute criou um concurso chamado “Millennium Problems” que é composto por sete problemas matemáticos, que são listados a seguir :

1. Conjectura de Birch e Swinnerton-Dyer

2. Conjectura Hodge

3. Equações de Navier-Strokes

4. P vs NP

5. Conjectura de Poincaré

6. Hipótese Riemann

7. Teoria de Yang-Mills

Cada um destes 7 problemas tratam de temas de grande relevância para a matemática moderna todos eles já eram conhecidos a anos, mais ninguém tinha sido capaz de prova-los.

Como incentivo o Clay Institute oferece um prêmio de um milhão de dólares para cada problema resolvido.

Uma curiosidade desta lista de sete problemas é complexidade envolvida até mesmo para entender a questão, na verdade acredito que mesmo um professor de matemática experiente pode ter grande dificuldade para entender todos eles.

Com base nesses dados autor desta obra teve iniciativa de escolher o problema que trata P vs NP como tema , este problema tem um aspecto prático para o homem moderno e uma possível solução pode ter conseqüência no dia-a-dia homem moderno.

Por isso esse texto tenta de maneira simples e não formalista enunciar a questão P vs NP, numa tentativa de tornar claro a todos do que se trata o problema e suas implicações.

Um aspecto interessante do problema P versus NP, é que ele esta relacionado não só a matemática, mas também a computação.

2. P versus NP

Complexidade computacional é um ramo da ciência da computação que visa classificar problemas computacionais de acordo com o nivel de dificuldade do problema.

A complexidade é medida conforme, independentemente do algoritmo, qual é quantidade necessarias de recursos, mas especificamente de tempo que é necessário para executar um algoritmo.

Para se realizar esta medida são coletados dados de uma execução básica, com menor entrada de dados possível, do algoritmo que resolve dado problema, com base neste tempo analiza se este tempo cresce de forma exponencial ou polinômial, caso o tempo cresça de forma polinomial a solução é considerada rápida de outra forma ela é considerada lenta.

É necessário notar que mesmo um algoritmo que cresce em tempo exponencial e portanto é considerado rápido, com uma entrada significativa pode levar um tempo realmente grande para ser executado, então, portanto entenda que o rápido citado pode não significar o rápido do senso comum.

Digamos que em um computador a soma de dois algarismos, 7 + 3, seja realizado com apenas duas operação básica do processador do computador, então:

A soma acima precisa de 2n operações(não é exatamente 2n operações, valor utilizado apenas para uma simplificação), onde n é número de algarismos das parcelas, para ser realizada computacionalmente, o que significa dizer que o tempo gasto para processar uma operação de adição computacionalmente tem um crescimento representado por uma função polinomial, normalmente é expresso por O(n) passos.

Outro exemplo de um algoritmo que é executado em tempo polinomial é o algoritmo da multiplicação requer operações , ou seja, a complexidade é de O() passos.

Com as informações acima podemos definir : Um algoritmo de tempo polinomial é um algoritmo que resolve o problema para todas as entradas possíveis em um tempo polinomial, os algoritmos de soma e multiplicação são exemplos destes tipos de algoritmos.

A partir disso dizemos que: a classe P de problemas é o conjunto de todos os problemas polinomiais [PF].

Podemos definir também de maneira informal, o que é um problema chamado razoável(feasible problem) : um problema é dito razoável [PF] :

Se for possível em tempo polinomial verificar se uma suposta solução é realmente uma solução para o problema. [PF]

Como exemplo somar dois números é um problema razoável, pois dado dois números e o soma deles é fácil verificar se a soma esta realmente correta, na verdade essa verificação também pode ser feita em tempo polinomial.

Vamos chamar este conjunto de problemas de NP(Non nondeterministic polynomial), é evidente que na verdade a classe P esta inserida dentro de NP, pois todo problema que pode ser resolvido em tempo polinomial pode também ser verificado em um tempo polinomial.

Então a questão P = NP poderia ser lida assim:

É verdade que todo problema cujas repostas podem ser checadas em tempo polinomial também podem ser resolvidos em tempo polinomial?

Quem conseguir resolver a questão P = NP, na verdade estará respondendo a esta pergunta. Dito assim o problema parece mais fácil do que realmente é, e também não parece ter uma implicação prática.

Um exemplo da relevância do problema é na criptografia, pois os principais algoritmos de criptografias atuais que são utilizados nas transações seguras da internet(SSL), baseiam-se na decomposição em fatores primos de números absurdamente grandes, números com mais 200 algarismos, pois atualmente não se tem conhecimento de um algoritmo que possa decompor em fatores primos números tão grande em um tempo razoável, ou seja, o algoritmo que soluciona o problema de decomposição em fatores tem um custo exponencial.

Uma conseqüência da prova de que realmente P = NP, seria que todos os algoritmos de criptografia baseado na decomposição em fatores primos estariam realmente em perigo.

Uma outra conseqüência de uma possível demonstração afirmativa P = NP teria repercusão na própria matemática e lógica, pois afirmaria que é computacionalmente possível a construção de um algoritmo capaz de provar qualquer teorema matemático.

A questão P = NP , já foi tratada pelos melhores matemáticos do mundo por varias décadas, e parece que nada de definitivo foi realmente provado sobre o tema, mas William I. Gasarch conduziu uma pesquisa com os melhores cientistas da computação e matemáticos do mundo sobre o tema, a maioria acha que na verdade P é diferente NP.

3. Referência

[PF]. Paulo Feofiloff http://www.ime.usp.br/~pf/

1. http://www.claymath.org

2. http://www.claymath.org/millennium/P_vs_NP/

3. STEPHEN COOK, http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf

4. http://www.cs.umd.edu/~gasarch/papers/poll.pdf

Arquivos do Sun Tech Day 2009

As palestras do Sun Tech Day 2009 podem ser baixadas em : 

http://developers.sun.com/events/techdays/presentations/2009/saopaulo.jsp

PHP Zend Framework - Instalando

Nos últimos 2 anos o desenvolvimento WEB vem mudando muito, na minha opinão melhorando muito, uns dos motivos disso foi o surgimento do framework Ruby On Rails que mudou a maneira de pensar de muita gente pois mesmo sendo um framework MVC completo consegue manter a simplicidade e rapidez no desenvolvimento, ao contrario da maioria dos frameworks web java com seus excesso de XML e configurações.

Umas das vantages de Ruby on Rails sobre PHP é a elegância  e modulariedade das aplicações feita em ROR , ao contrario do PHP que utilizado sem um bom conhecimento de arquitetura de software pode resultar em uma aplicação muito difícil de manter.

Uma maneira que se encontrou para melhorar a qualidade de sites feitos PHP foi a criação do Zend Framework, projeto liderado pela Zend principal mantenedora do PHP.

ZendFramework esta no mercado a um bom tempo  e se mostrou excelente, é feito utilizando OOP e padrões de desenvolvimento, além de contar com uma documentação razoável , por isso é a minha escolha quando o assunto é framework PHP.

1. Baixando

Acesse http://zendframework.com e faça o download da versão mais recente, neste tutorial utlizarei a versão 1.9 Beta.

2. Configurando

Para quem esta começando essa é uma parte muito importante, pois é necessario configurar o Zend Framework corretamente para conseguir trabalhar de forma “pacifíca” com o framework PHP.

o primeiro passo é descompactar o arquivo baixado no item 1 e copiar este novo diretorio ,por exemplo, para C:\ZendFramework-1.9.0b1 de modo que fique parecido com a estrutura abaixo.

agora vá para seu php.ini normalmente no c:\windows e modifique seu arquivo para que fique parecido :

basicamente descomentar o include_path caso esteja comentado e adicionar um novo path para library do diretório do Zend Framework.

Falta ainda duas coisas, adicionar dois executaveis no path para isso, clique com botão direito no icone meu computador no desktop -> Advanced System settings -> aba Advanced -> Environment variables(variaveis de ambiente), escolha a variavel Path, e adicione no final o endereço completo do executavel PHP na sua maquina e endereço completo zf.bat(presenta na pasta bin, do Zend Framework), exemplo abaixo :

Pronto, agora para testar , abra o prompt de comando e execute.

zf show version

pronto, se  como resposta do comando acima, conseguiu a resposta abaixo, o ZendFramework esta instalado corretamente e pronto para ser usado.

Observação : os procedimentos para alterar a variavel de ambiente, PATH,  funcionou em um Windows XP, já no Windows Vista, mesmo reiniciando, não funcionou. Para funcionar copiei o conteúdo do diretorio bin do diretorio do Zend Framework para pasta c:\windows, o copiei também o executavel e dlls do php para basta c:\windows, depois disso funcionou, talvez não seja a melhor solução, mais fica registrado a dica.

3. Criando sua primeira aplicação

Basta ir para Document Root do apache,ou seja, o diretorio onde fica seus sites no apache e por linha de comando execute.

zf create project sample1

agora acesse http://localhost/sample1/public/

e deverá encontrar esta tela.

é onde sua aplicação Zend FrameWork deve estar rodando.

em futuros posts pretendo cobrir outros topicos deste fantastico FrameWork!

Rsync - Atualizando seu site de maneira inteligente

RSYNC é um software feito para aqueles que tem necessidade de transferir arquivos de um local para outro, exemplo da sua pasta local de desenvolvimento para seu servidor WEB.

Ele tem varias vantagens sobre fazer isso por FTP, pois ele utiliza varias tecnicas para saber realmente quais arquivos enviar.

É comum como desenvolvedor PHP fazer pequenas alterações em site com varios arquivos , o problema que na hora de atualizar o site do cliente, acabo enviando todos os arquivos novamente, não seria muito mais inteligente enviar somente os arquivos que realmente foram alterados ? o Rsync trata isso.

Para instala-lo no linux é bem simples basta :

apt-get install rsync

para instala-lo no windows, você precisa baixar a versão compilada para esta plataforma em  :

http://sourceforge.net/projects/sereds/files/cwRsync/1.2.4/cwRsync_1.2.4_Installer.zip/download

Logo após a instalação realizada, eu precisei copiar todo o conteúdo da pasta

C:\Program Files\cwRsync\bin

para a pasta do c:\windows, com isso conseguimos executar rsync pelo prompt de comando.

Agora o comando que sempre utilizo para atualizar meus sites, rodando sempre do diretorio raiz do meu site:

rsync  --exclude ".svn" --exclude "conecta.php" --exclude "*.swp" --exclude="nbproject" -e ssh -Prvzc .  userreomote@host:/path/remote

com isso minhas atualizações ficaram mais rapidas.

Meu Primeiro Evento Ruby On Rails

Participei do meu primeiro evento Ruby On Rails, conforme minhas expectativas o evento foi bom, valeu apena o dinheiro e o tempo investido.

O Evento foi o Ruby e Rails no mundo Real 2009 confesso que o termo “mundo real” ficou mais no nome do que nas palestras.

1. Criando um Instant Messenger usando Rails

Palestra foi razoavel, falou sobre Jabber e XMPP de forma bem rapido afinal não da para apresentar um tema deste em 1 hora.

2. Ruby, Rails e empreendedorismo

Essa palestra sobre empreendedorismo ficou muito solta no evento, mais gostei, na verdade sempre gosto deste tema.

3. Ruby Desktop

Eu particularmente não gostei deste assunto, Ruby para Desktop ? é bom ter uma idéia sim, mas se vc realmente precisa desenvolver para desktop(windows) é melhor usar Delphi(.Net), ou java!

4. Outsorcing, ou como trabalhar para empresas gringas

Na minha opinião a melhor apresentação, salvou o evento e deu mais sentido no termo “Mundo Real” no nome do evento.

5. GlassFish on Rails: Escalabilidade e Confiabilidade

Palestra muito rapida, sobre um tema pesado! mais foi uma palestra e pesquisando na web você descobre que rodar sua aplicação no JRails + Glassfish pode ser uma boa saida.

6. Só os imaturos não testam

Uma das melhores palestras, Com bastante exemplos de utilização de testes e sobre a evolução dos desenvolvedores.

7. O que é e como funciona o RubyLearning

Uma palestra informativa sobre o projeto e como funciona, gostei!

8. Ruby, muito mais do que reflexivo!

Apresentada pelo Fabio Kung, realmente muito boa apresentação! Ele mostrou tecnicas para manipulação da linguagem usando ParseTree, ele deu exemplo de como usar essa ferramenta gerar métricas de qualidade do seu código.

Em resumo foi um bom evento, e compensou o investimento(R$50)
os organizadores estão de parabéns.

Css Framework

Se você já teve que montar um layout de um site com css usando tableless, você já deve saber como essa simples tarefa pode se torna um pesadelo para um iniciante.

É comum problemas, uma propriedade funciona na versão 7 do IE outra não.

Com base nisso esta surgindo o idéia de CSS Framework, basicamente eles fornecem toda essa infra-estrutura de CSS para você, como por exemplo definir fontes padrões, e claro montar o layout, ou grid do seu site.

Abaixo irei explicar como utilizar o Blue Print CSS e construir uma estrutura basica de um site, header, footer e menu esquerdo.

1. Faça o download do framework em http://www.blueprintcss.org/

2. Descompacte o arquivo e copie a pasta blueprint para o diretorio raiz do seu site, neste exemplo irei utilizar c:\trabalho\site1

3. Vamos carregar o nosso framework em nosso site

index.html

<!DOCTYPE html PUBLIC "-/W3c/DTD HTML 4.01/EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<link rel="stylesheet" href="blueprint/screen.css" type="text/css" media="screen,projection">
<link rel="stylesheet" href="blueprint/print.css" type="text/css" media="print">
<!--[uf IE]>
<link rel="stylesheet" href="blueprint/ie.css" type="text/css" media="screen, projection">
<![endif]-->
</head>
<body>
</body>
</html>

pronto o nosso CSS Framework esta instalando agora vamos começar a usa-lo.

4. Definindo o nosso layout completo:

<!DOCTYPE html PUBLIC "-/W3c/DTD HTML 4.01/EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<link rel="stylesheet" href="blueprint/screen.css" type="text/css" media="screen,projection">
<link rel="stylesheet" href="blueprint/print.css" type="text/css" media="print">
<!--[uf IE]>
<link rel="stylesheet" href="blueprint/ie.css" type="text/css" media="screen, projection">
<![endif]-->
</head>
<div id="container">
<h1> Aqui é conteúdo do header. </h1>
<hr>
<h2 class="alt"> Simples teste </h2>
<hr>

<div class="span-15 prepend=1 colborder">
<p> Um simples texto para conteúdo </p>
</div>

<div class="span-7 last">
<ul>
<li><a href="#"> MENU 1 </a></li>
<li><a href="#"> MENU 2 </a></li>
</ul>
</div>
<hr>
<p> Um simples rodapé </p>

</div>
<body>
</body>
</html>

é essa uma estrutura basica de um layout em html, bom com isso já é possivel ter uma ideia do framework, mais é necessario um aprofundamento maior para entender toda logica do framework.

Baixe os arquivos utilizados acima junto com framework AQUI.

Autenticação com ruby on rails - restful authentication + OpenID

Todo programador  já deve ter escrito varios e varios sistemas onde exista a necessidade de proteger algumas paginas, qual é a solução mais comum ? escrever mais uma vez código para login de usuario, acabando por duplicar código entre projetos.

Outro efeito ruim disso é que acaba duplicando informações de acesso de usuarios, exemplo cada sistema tem sua própria base de dados de usuario, para resolver(ou tentar) este problema foi criado OpenID.

O funcionamento do OpenID, em linhas gerais, é o seguinte: usuario é dono de uma url digamos http://ualex.myopenid.com e  este usuario deseja logar no meu sistema que suporta autenticação por OpenID, ele simplesmente digita sua url na tela de login do meu sistema e logo depois é direcionado para um OpenID provider, neste caso myopenid.com, no site do OpenID provider o usuario digita sua  senha e comprova que é dono da URL, logo após isso ele é redirecionado para minha aplicação e continua navegando normalmente.

Parece complicado não é ?  OpenID tem uma especificação bem clara e existe varios frameworks em varias liguagens para tratar o processo de autenticação, existe até frameworks para criar seu próprio OpenID Provider, este útil para centralizar autenticação de usuarios de aplicações web dentro de uma empresa.

Neste tutorial irei aproveitar aplicação construida no post sobre restful authentication para implementar autenticação por OpenID, vamos la.

1. Instalar a biblioteca openid-ruby

gem install ruby-openid

2. Instalar o plugin open_id_authentication

git clone git://github.com/rails/open_id_authentication.git vendor/plugins/open_id_authentication

3. Criar as migrations do open_id_authentication

rake open_id_authentication:db:create

4. Criar uma migration para alterar nossa tabela users

ruby script\generate migration add_identity_url_for_users

Nossa nova migration irá conter :

class AddIdentityUrlForUsers < ActiveRecord::Migration
def self.up
add_column :users, :identity_url, :string
end

def self.down
remove_column :users, :identity_url
end
end

5. Alterar nosso controller Session para permitir autenticação por OpenID ou por password

Com certeza essa é umas das partes mais “complicadas” do processo, você irá precisar fazer as seguintes alterações no seu controller session(criado pelo restful_authentication).

def create
if using_open_id?
open_id_authentication()
else
password_authentication()
end
end

def open_id_authentication
authenticate_with_open_id do |result, identity_url|
if result.successful?
if @current_user = User.find_by_identity_url(identity_url)
success_login()
else
failed_login "Sorry, no user by that identity URL exists (#{identity_url})"
end
else
failed_login result.message
end
end
end

def success_login
session[:user_id] = @current_user.id
redirect_to(root_url)
flash[:notice] = "Sucesso"
end

def  failed_login(message)
flash[:notice] = message
redirect_to(new_session_url)

end

def password_authentication
logout_keeping_session!
user = User.authenticate(params[:login], params[:password])
if user
# Protects against session fixation attacks, causes request forgery
# protection if user resubmits an earlier form using back
# button. Uncomment if you understand the tradeoffs.
# reset_session
self.current_user = user
new_cookie_flag = (params[:remember_me] == "1")
handle_remember_cookie! new_cookie_flag
redirect_back_or_default('/')
flash[:notice] = "Logged in successfully"
else
note_failed_signin
@login       = params[:login]
@remember_me = params[:remember_me]
render :action => 'new'
end
end

altere seu arquivo conforme o código acima.

6. Adicionando a opção OpenID na tela de login

vamos adicionar em nossa tela de login um field para usuario entrar com sua url, e caso esta url estiver presente autenticar por OpenID.

//arquivo: sessions/new.html.erb
<p><%= label_tag "OpenID URL" %>
<p><%= text_field_tag 'openid_identifier' %></p>

7. Alterar nossa view para permitir o cadastro de nossa url de autenticação

adicione o novo field identity_url para quando o usuario estiver no processo de signup, ele possa entrar com a OpenID url.

//arquivo: users/new.html.erb

<p><%= label_tag 'Identity url' %><br/>
<%= f.text_field :identity_url %></p>

8. Corrigindo um  detalhe para torna nosso site mais seguro

//arquivo models/user.rb

attr_accessible :login, :email, :name, :password, :password_confirmation, :identity_url

note foi adicionado o :identity_url no final da listagem.

9. Finalizando

Pronto, se você chegou até aqui é hora de testar, para criar um OpenID(free) acesse o http://www.myopenid.com e faça o seu cadastro, uma dica é utilize o rails 2.2 e tentei inicialmente o rails 2.1.1 mais existe uma incompatibilidade entre os frameworks nessa versão.

Autenticação com ruby on rails - restful authentication

1. Criando novo projeto de exemplo

 rails -d mysql todo

2. gerando um scaffold simples, com o propósito demonstrar como funciona restful authentication

 ruby script\generate scaffold todo descricao:text prazo:date feito:boolean

vamos criar também nosso banco de dados para isso não se esqueça de configurar seu arquivo config\database.yml (development)

 rake db:create

e executa nossa migration para ele criar a tabela todos:

 rake db:migrate

agora é um bom momento para você startar sua aplicação e fazer alguns testes:

 ruby script/server

3. Baixando restful authentication

no diretorio raíz do seu do seu projeto

 git clone git://github.com/technoweenie/restful-authentication.git vendor/plugins/restful_authentication

para rodar esse comando você irá precisar instalar um cliente git

4. Rodar um generate que irá criar uma estrutura de autenticação em nosso projeto

 ruby script\generate authenticated user sessions

Este generate irá criar o user model para você que nada mais é que sua tabela de usuarios
e também irá criar o controlador sessions, que será usado para login e logout.

novamente precisamos executar uma migration para atualizar nosso banco de dados

 rake db:migrate

e precisamos incluir o modulo AuthenticatedSystem em nosso application controler (app\controllers\application.rb) para que a nossa infra-estrutura de autenticação fique disponivel para nossa aplicação.

 include AuthenticatedSystem

5. vamos alterar  no nosso controller todo para pedir autenticação,
para isso basta adicionar a linha:

 before_filter :login_required , :except => [:index]

lembre se para cadastrar um novo usuario http://localhost:3000/signup

Pronto esta feito! implementamos nosso sistema de autenticação.

Reset da senha do mysql

Por um acaso já aconteceu de você esquecer a senha de root do mysql, para corrigir é muito simples basta iniciar o servidor mysql com a opção –skip-grant-tables e logo apoós logar sem senha e dar um update na tabela user, exemplo.

mysqld-nt.exe --skip-grant-tables

c:> mysql

use mysql

update user set password='' where user='root' and host='localhost'

pronto com isso você remove o password do root para o localhost.

Deployment com Ruby On Rails - Capistrano

Como desenvolvedor sempre surge a tarefa do deployment, ou seja, colocar o seu trabalho para rodar, no mundo web existe várias formas de fazer isso,  exemplo se o site for em PHP, é comum a utilização de FTP, SFTP e RSYNC.  Por outro lado se for java(JSP e Servlet) essa pode não ser uma medida eficiente já que normalmente envolve parar e iniciar o tomcat.

Mas independente da tecnologia,  essa é uma terefa rotineira e repetitiva então é razoável automatiza-la, é comum nesse aspecto a utlização de shell scripts, .bat etc.

No mundo ruby on rails temos uma ferramenta muito boa para fazer isso é o : CAPISTRANO que automatiza essa tarefa, de forma muito elegante.

basicamente para utiliza-lo, você precisa seguir alguns passos básicos.

1. Instalar o capistrano atráves do GEM

gem install -y capistrano

2. Capification é basicamente criar alguns arquivos modelos no seu projeto Ruby On Rails , basta ir para raiz do seu projeto e digitar:

capify .

3. Algumas configurações basicas no arquivo config/deploy.rb

set :application, "seuprojeto"
set :repository,  "https://urlseurepositorio/svn"
set :deploy_to, "/pathnoseuservidor/#{application}"
set :user, "userssh"
role :app, "servidorapp"
role :web, "servidorapp"
role :db,  "servidorapp", :primary => true

Arquivo bem simples, e para quem já criou script de deploy na mão, é bem simples de entender.

4. Criar o arquivo script/spin, esse arquivo é que você colocar o comando para reiniciar sua aplicação no caso como eu uso Passenger, basta :

touch /pathyourproject/current/tmp/restart.txt

faça um commit das alterações.

5. Vamos criar a estrutura basica no nosso servidor

cap deploy:setup

6. E por último fazer um release

cap deploy:update //(copia os última versão do servidor de código fonte)
cap deploy:start //(faz o release, e se for caso reinicia a aplicação)

pronto em questões de minutos usando o Capistrano você automatiza o deployment do seu projeto,
eu já fiz shell script para fazer isso e também já usei o Apache Ant e digo uma coisa o
Capistrano é uma solução elegante para essa tarefa.