Códigos, genética e puzzles

Algumas recomendações de livros, para quem gosta da parte de exatas.

  1. O livro dos códigos, Simon Singh.

Conta a história da criptografia, desde os primórdios até os dias de hoje.

Especialmente interessante é uma descrição detalhada de como o Enigma funcionava. O Enigma era o dispositivo de criptografia dos alemães, na Segunda Grande Guerra, e era considerado indecifrável.

Um grupo de cientistas ingleses, incluindo Alan Turing, conseguiu decifrar o Enigma, dando aos aliados uma vantagem estratégica enorme (eles conseguiram ter a confiança de que o Dia D ocorreria sem grandes problemas, por exemplo)

Link da Amazon: https://amzn.to/3kPY3DG

  1. Genética e DNA em Quadrinhos, Mark Schultz.

Eu gosto bastante do poder de simplificação e visualização de temas complexos em quadrinhos.

O livro é uma introdução divertida à genética, incluindo Gregor Mendel, Charles Darwin e a famosa dupla hélice do DNA, descoberta pela dupla Watson e Crick.

Link da Amazon: https://amzn.to/3lMhAWZ

Aproveitando, na mesma linha, Química em Quadrinhos, de Larry Gonick:
Link da Amazon: https://amzn.to/3fkbjiH

  1. Mania de Matemática, Ian Stewart.

O matemático Ian Stewart é autor de vários livros populares sobre matemática.


Neste livro, ele descreve com bastante detalhe alguns puzzles. O nível é bem alto, são puzzles difíceis.

Link da Amazon: https://amzn.to/35QmoFp

Um exemplo é a “Quadratura do Quadrado”: como cobrir um quadrado com quadrados menores, de tamanhos diferentes?

Como a “quadratura do quadrado” é um problema difícil demais, ataquei a “quadratura do retângulo” no link a seguir.

https://ideiasesquecidas.com/2019/11/15/quadraturas-do-retangulo/

Na mesma linha, tem o Mania de Matemática II:

Link da Amazon: https://amzn.to/2KnT8gF

Boa diversão!

Veja também:

https://ideiasesquecidas.com/2016/06/19/calculo-em-quadrinhos-bioquimica-em-quadrinhos/

https://ideiasesquecidas.com/2020/09/18/nietzsche-em-quadrinhos/

Para que servem os autovetores?

Para te deixar multi-milionário? É verdade, pelo menos para os criadores do Google. O algoritmo PageRank basicamente encontra autovalores e autovetores.

No curso de Álgebra Linear, os professores ensinam autovetores conforme a equação da figura.

A grande interpretação da equação é que são a solução de problemas que referenciam a si mesmos.

A ideia básica do Google é simples. Ao invés de rankear os inúmeros sites da internet manualmente (como eram outros engines da época), ela recorre ao número de citações.

Se tiver muitos sites importantes com link para o meu site, o meu site também se torna importante.

Então é só contar os links, correto?

Não. Porque um site porcaria pode estar gerando um monte de links para enganar o sistema.

Como eu sei que o site é importante, sendo que ele é importante porque outros sites dizem que ele é importante?

Quem avalia os avaliadores?

É um problema autorrefenciável… exatamente o problema dos autovalores e autovetores.

O PageRank mostrou-se inúmeras vezes superior aos demais buscadores da época, e foi o primeiro passo para a empresa de Sergei Brin e Larry Page (o Page do PageRank, além de significar página) se tornar o que é hoje.

E eu, demorei 20 anos para entender a importância dos autovetores… tarde demais para criar um Google.

Veja também:

https://ideiasesquecidas.com/2015/08/15/logaritmos-neperianos/

https://ideiasesquecidas.com/2016/05/15/negativo-x-negativo-positivo-por-que/

P, NP, PSPACE e BQP

Um breve resumo dessa sopa de letrinhas da complexidade computacional.

P –  Problemas que podem ser RESOLVIDOS em tempo polinomial.

NP – Problemas que podem ser VERIFICADOS em tempo polinomial.

NP complete – Os problemas mais difíceis da classe NP.

PSPACE – Problemas que necessitam de uma quantidade polinomial de memória.

BQP – Problemas de podem ser resolvidos eficientemente num computador quântico.

Uma explicação mais elaborada.

P – São os problemas “fáceis” de serem resolvidos.

NP – São os problemas “fáceis” de serem verificados. Ou seja, dada uma resposta, é fácil verificar se ela atende ou não o problema. Porém, não é necessariamente fácil chegar à solução.

Portanto, podem existir problemas que são fáceis de verificar, porém difíceis de resolver.

Exemplo simples. Rearrumar a palavra a seguir:

lrsdhreeaaamb

É bem mais difícil encontrar a solução do que verificar que “desembaralhar” é a resposta.

Os problemas mais difíceis de todos os NP são chamados NP-Completos. Diversos problemas da vida real, como o da Satisfiabilidade, são NP-Completos.

Existe também o NP-Hard, que são problemas pelo menos tão difíceis quanto os NP-completo. Problemas de otimização são assim. NP-Completo é achar uma solução, o NP-Hard, achar a melhor solução. O famoso problema do Caixeiro-Viajante é um exemplo de problema de otimização.

Um grande problema não resolvido do mundo é se P = NP. Até hoje, não foi possível provar que são iguais ou não diferentes. É, inclusive, um dos desafios do milênio do Instituto Clay, valendo 1 milhão de dólares!

O BQP são problemas resolvíveis por um computador quântico. Suspeita-se que seja possível resolver problemas mais difíceis que a classe P, porém sem resolver o NP-completo.

Portanto, a figura que representa os graus de complexidade é apenas uma ideia. Se P for igual a NP, nem precisaríamos de computador quântico! Bastaria usar esse algoritmo, que resolve problemas difíceis de forma fácil.

O problema P vs NP é complicado de provar, não à toa, até hoje não foi resolvido.

Porém, até hoje os problemas difíceis continuam difíceis, o que é um forte indício de que P é diferente de NP, e que problemas difíceis continuarão difíceis – e que computadores quânticos serão muito úteis.

https://pt.wikipedia.org/wiki/BQP

https://en.wikipedia.org/wiki/P_versus_NP_problem

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Entre no grupo de estudos de Computação Quântica:

https://www.facebook.com/groups/1013309389112487

Prova visual da sequência 1/2 + 1/4 + 1/8 + … = 1

A sequência 1/2 + 1/4 + 1/8 + … = 1 é conhecida faz tempo, e há uma prova visual bastante bonita.

Imagine que vamos somando retângulos, onde a área corresponde ao valor da sequência.

O primeiro tem área 1/2 (lados 1 x 1/2):

O segundo com área 1/4 (lados 1/2 e 1/2):

O terceiro com área 1/8 (lados 1/4 e 1/2):

(As cores mudam, porque o código que escrevi joga cores aleatórias)

E assim sucessivamente. Após 8 iterações:

Note um padrão: sempre sobra um retângulo, e esse retângulo sempre é preenchido com metade da área na iteração seguinte.

Após 20 iterações:

A soma da área vai tendendo a se aproximar de 1, sem nunca chegar.

Um exercício é fazer numa calculadora ou no Excel a soma 1/2 + 1/4 + 1/8 +1/16 + … até cansar, e verificar o resultado!

Para brincar iterativamente, neste link:

https://asgunzi.github.io/Soma-Serie-Meio/

Source code no Github:

https://github.com/asgunzi/Soma-Serie-Meio

Veja também:

https://ideiasesquecidas.com/laboratorio-de-matematica/

https://ferramentasexcelvba.wordpress.com/2018/09/02/mil-cardioides-no-excel/

Parabéns, Excel!

O MS Excel completou 35 anos no dia 30/09.

É o software de produtividade onipresente do mundo. Desde o estagiário no primeiro dia, até os diretores, todos usam o Excel de alguma forma.

Nas imagens: o Excel 1.5, o Visicalc (a primeira planilha eletrônica do mundo) e o titã Atlas segurando o mundo nas costas.

Semanalmente, eu posto dicas, problemas e alguns desafios relativos a Excel e VBA, no site a seguir.

https://ferramentasexcelvba.wordpress.com/

Fica a dica!

O Iceberg de Analytics

Reflexão. Uns 90% de qualquer (bom) trabalho em Analytics não tem relação com o modelo superlegal cheio de matemática, mas com todo o trabalho consultivo envolvido.

A grande complexidade dos problemas do mundo real não está em resolver com perfeição um problema difícil. Está em formular um problema resolvível, com os recursos existentes, a um custo (de licenças e de tempo) acessíveis.

E é por isso que projetos falham….


Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Grupo – Quantum Computing

Estou criando um grupo de estudos sobre “computação quântica”, no link a seguir. O objetivo é trocar ideias, notícias sobre eventos e cursos.   https://www.facebook.com/groups/1013309389112487

Pelas reações e comentários, há bastante interesse sobre o assunto.

Favor divulgar apenas para quem pode contribuir com o tema.

Qiskit Summer School 2020

Postagem sobre o summer school do Qiskit.

https://www.linkedin.com/posts/arnaldogunzi_ibm-qiskit-quantumcomputing-activity-6706320160816435201-EOMD

Quantum computing is a emerging field of knowledge. What was only theory years ago now is becoming reality.

I’m very proud and honoured to have attended the Qiskit Summer School 2020.

This course covered hot topics as quantum algorithms, error correction, superconducting devices and quantum chemistry, as well as labs to test our knowledge.

Thanks to Abraham Asfaw, James Wooton, Elisa Bäumer, Zlatko Minev and all the other members of #IBM.

Super Square One

O cubo Super Square One é o da foto:

É primo do Square One, já mostrado anteriormente aqui (https://ideiasesquecidas.com/2020/08/06/como-resolver-o-square-one-parte-1/)

O método de resolução é bastante similar ao Square One.

Se eu pegar a camada de cima e a de baixo, vou ter o Square One. Se considerar apenas as camadas do meio, também. Doravante, vou chamar de camadas de fora e camadas do meio.

Exemplo: este é o “movimento translado” nas camadas de fora.

E este é o “movimento translado” nas camadas do meio:

Movimento base, em todas as camadas:

A única dificuldade que encontrei foi a de reconhecer as peças das camadas do meio. Isso porque elas não têm a marcação de cor superior e inferior.

É mais ou menos simples resolver esse problema. Basta arrumar primeiro as camadas de fora, e depois, comparar a peça com a posição que ela deveria estar, na camada de fora. Assim, dá para reconhecer se ela deveria estar na camada 2 ou na camada 3.

Este cubo também pode mudar a forma, assim como o Square One.

Aqui, encontrei uma limitação. Consigo chegar na posição “chave”, mas não consigo avançar. Chega uma hora que este cubo não gira mais, talvez algum defeito de projeto. Não quis forçar, porque se ele desmontar, nunca mais consigo remontar.

Em resumo. O Super Square One é fácil de resolver, sabendo mexer no Square One. A única dificuldade é reconhecer as peças do meio, que é facilmente resolvido comparando com a camada de fora arrumada.

Veja outros cubos mágicos aqui:

https://ideiasesquecidas.com/cubos-magicos/

https://ideiasesquecidas.com/2016/01/20/dissecando-o-x-cube/

Como resolver o Square One – Parte 3

Dando continuidade a post anterior, https://ideiasesquecidas.com/2020/08/06/como-resolver-o-square-one-parte-1/, e https://ideiasesquecidas.com/2020/08/08/como-resolver-o-square-one-parte-2/ segue uma lista de algoritmos.

Um truque simples, para aquecer. É um movimento para trocar meio layer.

Agora com algoritmos que mexem na forma do cubo.
Note que há várias formas que o SquareOne pode assumir. O objetivo dos movimentos abaixo é fazer ele ficar no formato de cubo.

A forma mais simples, e chave para as demais, é o que chamei de Posição Chave.


Outra comum é a “forma de pata”, do vídeo abaixo.

O inverso da forma de pata:

Esta forma é mais complexa.
Chave e Quadrado:

Desfaz chave e quadrado:

Deve-se decorar as formas mais comuns mostradas acima.

A lógica é a seguinte: mexer o cubo até chegar em alguma forma reconhecível acima. Sabendo resolver as posições mostradas, facilita demais a vida.

Algoritmo de paridade

Este é para os casos em que ocorre uma “paridade impossível”, do tipo mostrado na figura.

É um movimento bem complexo, talvez até demais – não consegui achar um mais simples.
A instrução é fazer o movimento, chegar até a posição chave, e resolver o cubo.

Colocando tudo junto, os passos para resolver o Square One são:

  • Via algoritmos de forma, faça este ficar com a forma de cubo.
  • Resolver os cantos, utilizando o algoritmo troca cantos como auxílio, quando rotações simples não são possíveis.
  • Resolver as laterais, com movimentos como o básico I e II, troca 2 laterais, etc
  • Se a paridade não der certo, utilizar o movimento para acertar a paridade

Os movimentos mostrados são suficientes para resolver o SquareOne, com folga.
Também é necessário muita prática, para aprender a reconhecer os padrões e conseguir utilizar plenamente as dicas colocadas.

Vale também mexer no simulador do site Ruwix (https://ruwix.com/online-puzzle-simulators/square-1-simulator.php).

Boa diversão.

Como resolver o Square One – Parte 2

Dando continuidade a post anterior, segue uma lista de algoritmos para ajudar a resolver o SquareOne.

A ideia é criar movimentos que mexam com o menor número possível de peças, a fim de conseguir criar um padrão compreensível. É a mesma lógica de “movimento invariante” de outros cubos: mexo, volto e vou anotando os efeitos.

Os movimentos básicos, no começo, serão compostos de forma a chegar a movimentos mais complexos no final desta seção.

Até agora, vamos mostrar apenas movimentos que não variem a forma do cubo. No próximo post, vamos mexer na forma.

Mov Base I

Vídeo no Youtube:

Mov Base II

Mov Troca Layers

Mov Translado

Esse movimento fica mais claro se isolar somente as peças que se movem:


Mov Translado -1

É a mesma coisa, mas ao contrário – aliás, todos os movimentos descritos aqui têm a versão inversa, e dominá-las pode ser muito útil.


Mov Troca 2 simples

Mov Troca 2 lateral

Mov Troca 4 laterais

Mov Troca 4 cantos

Este movimento é importante para arrumar as peças dos cantos.

Mov Troca 3 laterais

Posição triangular

Quando as peças laterais estiverem numa situação como a da figura, basta um movimento UR para transformar essa posição em outra que dê para aplicar o movimento Troca 3 laterais ou algum dos truques acima.

Há um número infindável de combinações possíveis, então cada caso vai ser diferente. Porém, essa é a ideia: dominar os movimentos básicos acima, e transformar este caso em alguma posição resolvível acima.

No próximo post, algoritmos de forma, e a seguir, como juntar todos os elementos.

Parte 3:

https://ideiasesquecidas.com/2020/08/09/como-resolver-o-square-one-parte-3/

Vide também:

https://ideiasesquecidas.com/2020/08/06/como-resolver-o-square-one-parte-1/

https://ideiasesquecidas.com/cubos-magicos/

https://ideiasesquecidas.com/2015/10/18/como-resolver-o-dodecaedro-magico-introducao/

Como resolver o Square One – Parte 1

O cubo Square One (ou Square -1) é o da foto. Ele tem movimentos bem diferentes do Rubik tradicional – ou seja, deu para aproveitar pouco dos movimentos daquele.

Foto deste bagunçado.

Este tutorial tem várias partes: notação, algoritmos básicos, algoritmos de forma, e colocar tudo junto.

Atenção: eu inventei as soluções da minha cabeça, então não há equivalente entre o tutorial postado aqui e outros que podem existir na internet.

A primeira parte é a da notação básica. Ela usa a notação do Rubik: Upper, Down, Right, Left, Front, Back (esse últimos dois não são usados aqui).

Partiremos da base do Square One,

Movimento U (note que é sempre horário).

Movimento U2 (ou seja, o U aplicado duas vezes).

Movimento U’ (rotação anti-horária)

Movimento U2′

Agora, na camada de baixo.

Movimento D:

Movimento D2.

Movimento D’:

Movimento D2′:

Movimento U’R

Uma foto deste último movimento:

Continua abaixo:

https://ideiasesquecidas.com/2020/08/08/como-resolver-o-square-one-parte-2/

https://ideiasesquecidas.com/2020/08/09/como-resolver-o-square-one-parte-3/

Veja também:

Simulador no site Ruwix: https://ruwix.com/online-puzzle-simulators/square-1-simulator.php

https://ideiasesquecidas.com/cubos-magicos/

https://ideiasesquecidas.com/2015/05/31/poliedros-magicos/