Blog do Márcio d'Ávila

Provavelmente o maior problema conceitual em aberto da Ciência da Computação é chamado P versus NP, uma questão estudada na teoria da complexidade computacional, que lida com a proporção de recursos consumidos para se solucionar um problema computacional. Os principais recursos considerados são tempo (quantos passos são necessários) e espaço (quantidade de memória utilizada).

Conceituação

Segundo a teoria, a classe dos problemas computacionais P são aqueles que podem ser resolvidos em “tempo polinomial”. Isso significa que um computador (formalmente, uma máquina computacional sequencial e determinística) pode resolver o problema em um montante de tempo que tem proporção polinomial em relação ao tamanho da entrada do problema. Por exemplo, se para resolver um problema com n variáveis fornecidas (entrada), um computador gasta um tempo proporcional a n², ele é da classe P (uma proporção quadrática é um polinômio de grau 2).

Já os problemas computacionais da classe NP (tempo não-determinístico polinomial) consistem naqueles em que uma solução conhecida pode ser verificada em tempo polinomial.

Os problemas da classe P estão contidos na classe NP, ou seja, todo problema solucionável em tempo polinomial determinístico pode ter a solução verificada também em tempo polinomial. Mas existem problemas NP difíceis, para os quais ainda não se conhece uma solução polinomial, formando a classe chamada NP-completo.

A grande dúvida da computação é se P é ou não igual a NP, ou explicando em palavras mais simples, se existem problemas que não possam ser resolvidos em tempo polinomial.

Colocando a coisa em termos bem leigos, para quem “está viajando” sem entender nada até agora. Os problemas classe P são aqueles que se pode resolver em um tempo “factível” (polinomial), enquanto os NP-completo são aqueles problemas muito difíceis, que provavelmente “demorariam demais” para serem resolvidos por um computador.

A dúvida P =? NP então seria: Os problemas NP ainda não resolvidos em tempo factível (NP-completo) são porque não há realmente uma forma polinomial de serem resolvidos (P ≠ NP), ou porque essa solução apenas ainda não foi descoberta (P = NP)?

Um exemplo prático: A fatoração de um número que é produto de dos inteiros primos. Se alguém lhe disser que o número 13.717.421 pode ser escrito como o produto de dois outros inteiros, você provavelmente demorará para encontrar tais inteiros (tentando fatorar o número dado por cada número primo possível); contudo, se lhe disserem que ele é o produto de 3.607 por 3.803, você seria capaz de muito rapidamente verificar tal fato, simplesmente realizando a multiplicação.

Em busca da solução

O problema P versus NP é tão importante que foi definido como um dos Problemas do Milênio, sete dos mais difíceis enigmas da matemática, para os quais o Clay Mathematics Institute, em Cambridge, Massachusetts, EUA, instituiu no ano 2000 o prêmio de $1 milhão de dólares para a solução de cada um deles.

Em 11 de agosto de 2010, Vinay Deolalikar, dos Laboratórios de Pesquisa da HP em Palo Alto, EUA publicou um artigo alegando comprovar que P ≠ NP.

Contudo, diversos cientistas e estudiosos do assunto, como o professor Richard Lipton, do Instituto de Tecnologia da Geórgia, EUA, questionam o artigo e apontam falhas na demonstração da prova.

A comunidade científica mundial realmente suspeita que P não seja igual a NP, como buscou demonstrar Deolalikar, mas até que se comprove isso de forma inequívoca e amplamente aceita, a questão oficialmente continua em aberto.

A resposta para esse dilema não é mera questão de curiosidade científica. Muitas áreas de tecnologia envolvem problemas NP. Para citar algo crítico, modernas técnicas de criptografia digital tem sua segurança baseada na dificuldade de problemas NP-completo. Se alguém por acaso conseguir provar o contrário do que propõe Deolalikar, ou seja, que P = NP, implicaria afirmar que teoricamente existiriam meios de se desfazer a segurança da moderna criptografia em tempo polinomial.

Para saber mais:

• Solução para maior problema da computação está provavelmente errada, 2010-08-13, da NEW SCIENTIST, em Folha.com.
• Tide turns against million-dollar maths proof (em inglês), por Jacob Aron, 2010-08-13, New Scientist.
• Verbetes relacionados na Wikipédia em Português: P versus NP; NP (complexidade); NP-difícil; NP-completo.
• Verbete na Wikipedia em Inglês: P versus NP problem; P (complexity); NP (complexity); Time complexity – Polynomial time; NP-hard; NP-complete.
• Complexity Zoo (em inglês).

Reestruturei bastante a página sobre Engenharia de Software em meu site de meta-referências, hoje.

Organizei uma série de tópicos em uma seção própria: Produto de Software – Qualidade, Métricas e Teste.

Nesta seção estão os seguintes temas:

• ISO/IEC 25000 e 9126 – Qualidade do Produto de Software
• IEEE Std 1061 – Padrão IEEE para Metodologia de Métricas de Qualidade de Software
• Métricas de Software – Complexidade e Qualidade
• Medição de Software – Tamanho Funcional
• Teste e Qualidade de Software

Os outros temas gerais sobre Engenharia de Software, na mesma página (por enquanto, pois já penso em dividi-la devido ao grande tamanho e extensão), são:

• Engenharia de Software
• ISO/IEC 12207 – Processos do Ciclo de Vida de Software
• Análise e Modelagem Orientada a Objetos
• UML – Unified Modeling Language e SysML – OMG Systems Modeling Language
• Engenharia Dirigida a Modelo (MDE) e Desenho Dirigido a Domínio (DDD)
• Metodologias baseadas no Processo Unificado (UP)
• Metodologias baseadas no Desenvolvimento Ágil

É um vasto universo de temas em uma única disciplina. E nem sei se fui suficientemente abrangente.

Outra parte igualmente vasta e que vem se estendendo a passos largos em meu site é a de Arquitetura de Software, sendo que estão em páginas à parte também os temas de Integração e Arquitetura Corporativa, e de Arquitetura da Informação, Interação, Usabilidade e Acessibilidade.

Aproveitando o assunto, gostaria de recomendar os artigos Tales from the IT Crypts – O analista Frankenstein, 2010-08-12, e O Desenvolvedor “Cozinheiro Italiano”, 2010-2009-05-25, do meu amigo e grande arquiteto e engenheiro de software Marco Aurélio Mendes.

A Microsoft estendeu ao pacote de produtividade Office a política de upgrade gratuito aplicada a novas versões do sistema operacional Windows.

Quem compra qualquer edição do Microsoft Office 2007 entre abril e 30 de setembro de 2010 tem direito a atualizar o pacote gratuitamente para o Office 2010, segundo informou a Microsoft Brasil.

O programa ‘Office 2010 Technology Guarantee’ garante a atualização para o Office 2010 por meio de download, sem custo. O upgrade já está disponível, uma vez que o novo produto foi lançado no mercado.

O download é feito no endereço www.office.com/techg
Endereço alternativo: Garantia de Evolução do Microsoft Office 2010.

Podem participar do programa tanto os consumidores que adquiriram o Office 2007 separadamente no varejo (caixa) quanto quem comprou um computador novo com o pacote de programas pré-instalado. A versão de testes não é válida para atualização.

Para garantir o upgrade gratuito do Office 2010 é necessário seguir os seguintes passos:

1. Comprar e ativar o Office 2007 no período do programa;
2. Abrir uma conta do Windows Live ID;
3. Fazer o download da atualização do produto até 30 de setembro;
4. Guardar a nota fiscal de compra do Office 2007.

A versão doméstica e escolar — Microsoft Office Home and Student –, com direito a instalação/uso por três usuários, inclui o Word, Excel, PowerPoint e OneNote. Custa, na versão 2007, a partir de R$ 135,91 (na Kabum), e a partir de R$ 154 (na Balão da Informática) para a versão 2010. Ou seja, você consegue hoje o Office original a menos de 50 reais por instalação não empresarial.

Fonte: Office 2007 terá upgrade gratuito para versão 2010. Por Daniela Braun, para a PC World, 14 de abril de 2010.

Para saber mais:

• Office 2010 para usuário final é lançado oficialmente no Brasil, por Emerson Alecrim, 2010-07-28, em InfoWester Notícias.
• Devo atualizar meu computador para o Microsoft Office 2010, por Paulo, 2010-05-13, em MaxiSocial.
• Novidades Office 2010, por Equipe Compujob Web, 2010-04-07, no Blog do Computador.
• Novidades do Microsoft Office 2010, por Douglas Ciriaco, em 2009-07-13, em Baixaki.
• Maior parte das novidades do Office 2010 está em sua versão web, por Tom Spring e Edward N. Albro, da PC World/EUA, 2009-07-13.

A revista Veja desta semana tem como capa uma reportagem sobre “Falar e escrever bem” (Veja edição 2177, ano 43, nº 32, 11 de agosto de 2010, páginas 94 a 101).

Esse tema já foi capa de outras edições da revista. Pesquisando no Acervo Digital VEJA em anos recentes, encontrei por exemplo:

• “Falar e escrever certo”, edição 2025, ano 40, nº 36, 12 de setembro de 2007.
• “Falar e escrever bem” , edição 1725, ano 34, nº 44, 7 de novembro de 2001.

Como assinante de Veja há mais de 25 anos, é fácil observar os temas recorrentes em capas da revista. Quando não há furos de reportagem nem fatos emergentes ou de comoção nacional na semana — escândalos e destaques na política e na economia, o falecimento ou outro fato marcante de figuras notórias etc. –, temas coringas são sacados do cesto: Corpo e Mente, Alimentação, Avanços da Medicina, Plástica e Estética, Sexualidade, Ecologia, Casamento, Pais e Filhos. E no Natal, o tradicional tema Religião e Fé. Observo que a maioria gira em torno de saúde e comportamento.

Temas recorrentes não são necessariamente um sinal de falta de conteúdo. É saudável retomar assuntos de interesse geral de tempos em tempos, e acompanhar a sua evolução ao longo do tempo, em função das mudanças no mundo e no comportamento da sociedade, bem como nas descobertas da ciência.

Falar e escrever bem, por sinal, é um algo que me interessa muito. Tomara que continue sempre assunto recorrente nessa e em outras publicações. A atual reportagem de Veja teve como ponto de partida os tropeços de clareza e gramática dos candidatos à Presidência, no primeiro debate da Band.

Vejo com imensa tristeza como o brasileiro mediano realmente lê pouco, tem preguiça em ler e escrever, não domina o português como deveria nem na escola nem no cotidiano e, como consequência, frequentemente escreve e fala mal.

Isso sem falar na praga das mensagens curtas e instantâneas na internet e nos celulares, o que dá brecha à meninada da “nova geração conectada” para escrever errado, abreviado, truncado, sem nem pontuação.

Escrita e oratória falhas levam a comunicação e informação falhas. Quem não dá o devido valor a isso não percebe que informação e comunicação são, provavelmente, a maior riqueza e um dos principais instrumentos de poder da humanidade, ainda mais em tempos modernos.

Estatísticas coletadas dos acessos a grandes portais e backbones no mundo todo fornecem uma amostragem razoável do market share de navegadores web. Também trazem informações adicionais como o uso de plug-ins (Flash, Java, Silverlight e outros), e os sistemas operacionais e resoluções de tela utilizados nos computadores cliente.

Desde a entrada do Mozilla Firefox no mercado por volta de 2004, o Microsoft Internet Explorer saiu do quase monopólio, com perto de 95% do mercado, para atuais 60%, ao mesmo tempo que o Firefox gradativamente ocupou em torno de 20% do mercado.

A popularização do acesso internet e navegação web através de dispositivos móveis (smartphones e outros), em especial aqueles rodando os sistemas operacionais Apple iOS (do iPhone, iPod Touch e iPad), Google Android e Symbian, impulsionou outro considerável reposicionamento nesse mercado, com fatias atuais aproximadas de 7% para Google Chrome, 5% para Apple Safari e 2,5% do Opera.

Estatísticas, análises e informações detalhadas podem ser encontradas nos seguintes endereços:

• Wikipedia: Comparison of web browsers e Usage share of web browsers.
• NetApplications Net Market Share: Browser Market Share e Top Browser Share Trend, search engines, operating systems.
• Stat Owl: Web Browser Market Share, Plugins, Operating Systems, Search Engines, Web Standards.

O projeto Scientific and Technical Information Exchange (STIX) font creation lançou em 28 de maio de 2010, após mais de dez anos de desenvolvimento, as Fontes STIX 1.0.

O conjunto inicial de 23 fontes em formato OpenType está livremente disponível para baixar em STIX Fonts – www.stixfonts.org (pacote ZIP 2,6MB), além da licença de uso e documentação.

A missão do projeto de fonte STIX é elaborar um conjunto abrangente de fontes que sirvam a comunidade científica e técnica no processo que vai da criação do manuscrito à publicação final, em formatos eletrônico e impresso. Com este propósito, as fontes STIX são disponibilizadas sob licença livre de royalties para todos, inclusive editores, desenvolvedores de software, cientistas, estudantes e o público em geral.

O STIX font creation project é uma iniciativa das STI Pub companies, que inclui os Institutos Americanos de Física e de Engenharia Elétrica e Eletrônica – IEEE, as Sociedades Americanas de Química – ACS, Matemática – AMS e de Física – APS, e a Editora Elsevier.

Estas fontes matemáticas se juntam às Fontes para os amantes do TeX que já abordei no blog para suprir um conjunto profissional de fontes para quem escreve textos acadêmicos, técnicos e científicos usando um processador de textos gráfico em sistema operacional que suporte OpenType, como Windows 2000 ou superior e Linux.

O navegador Mozilla Firefox utiliza estas fontes, quando instaladas, para renderizar símbolos e expressões matemáticos na sintaxe MathML, que define mais de 2000 entidades.

STIX Fonts release 1.0 devem funcionar corretamente com Internet Explorer 8 em standards mode.

De acordo com a documentação, mais recursos OpenType serão adicionados no segundo lançamento para permitir o uso da fonte em uma aplicação como Microsoft Office Word 2010. O terceiro release acrescentará suporte a LaTeX.

Seis consultores e instrutores Java da Caelum estão escrevendo o livro Arquitetura e Design de Software: Uma visão sobre a plataforma Java, fruto de mais de dois anos de experiência ministrando o treinamento de Arquitetura e Design Java, consultorias e projetos realizados pela empresa e discussões no GUJ.com.br.

No site do livro está disponível a estrutura de conteúdo proposta, com diversos trechos rascunho para baixar em PDF.

O livro tem prefácio de Phillip Calçado. O lançamento, pela editora Campus Elsevier, foi inicialmente previsto pelos autores para novembro de 2009 e depois primeiro semestre 2010, mas pelo atraso creio que eles devem estar sofrendo na pele a Regra de Pareto: os 20% finais do livro tomando 80% do tempo… vamos aguardar.

Nas minhas primeiras impressões comparando os gerenciadores de senha (e outros dados privados) LastPass e KeePass, sai na frente o LastPass por enquanto. Veja a seguir.

Instalação e configuração inicial

LastPass

O LastPass mostra facilidades desde o download e a instalação: O link para Download já sugere a versão recomendada para a plataforma do usuário (Windows, Mac, Linux, dispositivos móveis) [+]. Tudo bem que não me ofereceu de cara a versão 64-bits otimizada para o meu Windows [-], mas o link “todos os downloads para esta plataforma” trouxe essa opção. O LastPass Universal Windows Installer 1.68.2 é em inglês [-], mas simples de instalar.

Ofereceu a opção de já instalar plug-ins de integração com os navegadores Web instalados (Internet Explorer e Firefox) e de substituir os respectivos gerenciadores de senha destes [+]. A instalação permitiu importar facilmente todas as senhas armazenadas no gerenciador do Firefox (bastou me solicitar a senha mestre deste) [+].

O programa instalado inclui interface localizada em português (e muitos outros idiomas) [+]. Nos dois navegadores Web, surgiu na barra de ferramentas o botão do LastPass, com seus menus e recursos, comportando-se de forma bem similar em ambos [+].

KeePass

Já o KeePass, em Downloads, oferece opção do KeePass 1.7 Classic Edition, e do KeyPass 2.11 Professional Edition, ambos gratuitos/livres [+] e apenas para Windows [-]. A segunda opção requer o Microsoft .NET Framework 2.0 ou superior, mas em compensação traz mais recursos, além de suportar também Linux e Mac OS X [+] se estiver instalado o Mono Framework 2.6 ou superior (projeto de software livre que implementa a especificação do .NET Framework em plataformas tipo Unix). Na dúvida sobre qual opção escolher, o link Edition Comparison Table compara as características das edições Classic e Professional lado a lado [+]. Escolhi o Professional. Existem também opções de ports contribuídos ou não oficiais para diversas plataformas móveis e o KeePassX for Linux / Mac OS X.

Oposto ao LastPass, o instalador do KeyPass 2.11 tem opção em Português do Brasil [+], mas o software instalado não traz essa opção nativamente no pacote [-], sendo necessário para isso baixar um ZIP à parte, referente à tradução de interface contribuída pela comunidade, descompactar manualmente na pasta da aplicação [-] e selecionar o novo idioma (View > Change language) no programa.

Princípios básicos

LastPass

O LastPass é voltado para o armazenamento seguro e centralizado de senhas e integração com navegadores e páginas Web. É necessário criar uma conta on-line gratuita onde as informações são armazenadas, o que possibilita sincronizar automaticamente seus dados e acessá-los de diferentes computadores e dispositivos, a qualquer momento.

Na navegação Web, o LastPass oferece para armazenar e preencher automaticamente dados de usuário e senha de acesso (autenticação) em qualquer site [+].

KeePass

O KeePass tem uma interface agradável e objetiva [+], exibindo em sua janela uma listagem em árvore das senhas (inicialmente vazia só com uma entrada exemplo, já que o programa não importa nada automaticamente).

Diferente do LastPass, não há para o KeePass uma conta on-line [-], o que contudo privilegia a privacidade máxima no armazenamento dos dados [+]. A proposta original de mobilidade entre computadores do KeePass é através do seu uso em um pendrive USB, já que sua instalação não envolve arquivos de DLL ou configurações em pastas de sistema nem entradas no registro do Windows [+]. A base de dados consiste em um único arquivo que pode ser facilmente transferido a outro computador ou dispositivo.

Quanto a autopreencher algum formulário na Web, precisou o comentário do amigo Paulinho no artigo anterior me antecipar que havia o recurso Auto-Type, e o tutorial Primeiros Passos me ensinar o atalho Ctrl+V e outros meios, mas a automação de preenchimento na Web não é tão integrada com os navegadores quanto o LastPass [-]. Não cheguei a experimentar o plug-in de terceiros KeeFox que promete integrar o KeePass ao Firefox.

O KeePass tem uma arquitetura aberta a plug-ins, com diversos disponíveis para download [+].

Conclusão do round 1

Neste primeiro round, sai na frente o LastPass por suas facilidades de instalação e de integração.

Boas práticas de segurança da informação orientam a você a utilizar senhas suficientemente grandes e complexas, combinando letras, números e símbolos. Orientam a não utilizar datas ou outras informações pessoais como base para a senha. Mais ainda, orientam a não utilizar a mesma senha em diversos locais.

Você busca seguir todas essas orientações e rapidamente se vê utilizando dezenas ou centenas de senhas diferentes e difíceis de se memorizar. Agregue isso à enorme quantidade de dados sigilosos que temos de manter, como contas bancárias, cartões de crédito, documentos etc.

E como gerenciar de forma segura esse caos, e ainda assim conseguir praticidade na hora de utilizar essas informações? Ter essa informação sempre a mão, não importa se você está usando o sistema operacional, navegando na internet, ou em trânsito tendo por perto um smartphone ou apenas um pendrive.

A solução é um programa gerenciador de senhas e dados sigilosos que seja poderoso, confiável e multiplataforma.

Os dois principais programas disponíveis são software livre (gratuitos e abertos), poderosos e estão disponíveis para diversos sistemas operacionais de computadores e smartphones:

• LastPass – oferecendo grande integração com navegadores Web e sincronização com repositório remoto centralizado para uso unificado entre diversos computadores e dispositivos, suporta Windows, Mac e Linux, Internet Explorer, Firefox, Opera e Chrome, iPhone, BlackBerry, Windows Phone, Symbian e Android.
• KeePass – prima por uma interface desktop amigável, originalmente para Windows, mas com ports para PcoketPC, Java, Linux, MacOS X, pendrives U3, iPhone, BlackBerry, Android.

Qual é o melhor? Você encontrará opiniões diversas na Internet, por exemplo:

• Password Manager Comparison – eWallet vs. KeePass vs. LastPass, 2009-06-30, em 40Tech.
• Securely manage your passwords with LastPass or KeePass, 2010-03-14, por Ed Brown, em FreakGeek.ly.
• KeePass vs Lastpass – password management, discussão nos fóruns em Productive Geek.
• KeePass Vs. LastPass, discussão em [H]ard|Forum.

Vou optar por avaliar eu mesmo os dois e ver se chego a uma conclusão. Enquanto isso, opiniões dos meus leitores são MUITO bem vindas. Qual gerenciador de senha você usa e prefere, e porque?

Existem mercados verticais específicos, que tem como base o mercado de servidores de aplicação, como o segmento de sistemas de gerenciamento de processos de negócio (BPM Suites).

Fonte: Decision Matrix: Selecting a Business Process Management Vendor, por Vuk Trifkovic, fevereiro 2010, Ovum (Datamonitor). Reproduzido por Oracle (PDF), por Metastorm (PDF, ver press release e blog), por VOSibilities (PDF).

O relatório do Gartner mostrava um cenário de mercado similar há um ano atrás.

Fonte: Magic Quadrant for Business Process Management Suites, 2009-02-18, por Janelle B. Hill, Michele Cantara, Marc Kerremans e Daryl C. Plummer, Gartner Research. Reproduzido por Software AG (PDF), por Lombardi Software (ver press release).

Ver também Gartner Publish BPMS Magic Quadrant for 2009, por Ian Louw, 2009-02-20, no blog BPM Insights; e Metastorm Positioned in Leaders Quadrant in 2009 Business Process Management Suites Magic Quadrant, press release, 2009-02-25, Metastorm.