O problema da mochila

Ferramentas em Excel-Vba

  1. (Fácil)

Digamos que eu vá fazer uma viagem para a Europa. Tenho 6 itens, cada um com um peso e um valor.

Consigo carregar no máximo 60 kg na minha mochila. Quais os itens a levar, de forma a maximizar o valor na mochila, dentro da restrição?

  1. (Difícil) Agora, tenho mais de 30 itens, e consigo carregar 800 Kg. Desenvolver um algoritmo para resolver o problema (o solver do Excel é suficiente).

Solução

Este problema pode ser resolvido utilizando o solver.

Imagine uma variável de decisão binária (0 = não levo o item, 1 = levo o item).

ProblemaMochila_Solucao.xlsx

Queremos maximizar o valor a ser carregado.

A função objetivo será o somarproduto entre a variável binária e o valor de cada item.

A restrição será o somarproduto entre a variável binária e o peso de cada item, que deve ser menor ou igual ao peso máximo.

No solver, definir a…

Ver o post original 194 mais palavras

Proof of work na vida real

O protocolo “proof of work” é utilizado atualmente em criptomoedas, e foi originalmente concebido para evitar spams. Mas o interessante é que, antes mesmo de existir o conceito computacional, a lógica já era aplicada faz muito tempo na sociedade e na natureza: diplomas, certificados, e até a plumagem do pavão. Vejamos como.


O proof of work consiste na entidade “A” mostrar, sinalizar, provar a uma entidade “B” que um trabalho foi feito (daí o nome, prova de trabalho).

Uma utilidade: evitar spams. Hoje em dia, é muito barato computacionalmente mandar um milhão de e-mails de uma só vez. Se, a cada e-mail enviado fosse necessária uma prova de trabalho (digamos, resolver um problema matemático difícil), haveria um limite natural: a capacidade de processamento do computador.

Para funcionar, o proof of work deve ser assimétrico: um problema difícil de resolver, porém, fácil de conferir o resultado.

Interessante notar também que a…

Ver o post original 559 mais palavras

Review – Alura

Fiz um trial da plataforma de ensino Alura, e explorei os cursos com intensidade, nos últimos dias.

Algumas impressões gerais:
– Tem uma quantidade enorme de tópicos relativos à TI: Programação, Dev Ops, Mobile.
– Para o meu foco de interesse, tinha uma trilha em Data Science, com cursos diversos: Excel, VBA, Power BI, Estatística, Python, Modelagem de dados. Machine learning, SQL server. Dentro de cada curso desses, uma programação de aulas a ser seguida.

As aulas consistem em vídeos didáticos, e exercícios no final – alguns de múltipla escolha, outras para colocar código. Há também um fórum de discussão (também joguei uma pergunta para ver se alguém respondia, e um outro aluno respondeu logo a seguir).

A licença não é por curso, mas por mensalidade. A pessoa pode explorar quantos cursos quiser, neste período.

Fiz um curso do início ao fim, para ver a questão do certificado. Mesmo sendo…

Ver o post original 56 mais palavras

Metaheurística com 2 variáveis

Ferramentas em Excel-Vba

Essa versão é um pouquinho mais elaborada que a versão com uma variável (https://ferramentasexcelvba.wordpress.com/2021/03/27/exemplo-de-metaheuristica-uma-variavel/)

Serve para resolver o problema linear:

Max 10*x +5*y

Sujeito a:

2*x+4*y <= 50

1*x -6*y <= 15

É semelhante ao anterior, mas agora as variáveis são matrizes.

‘Inicializando coeficientes FO

coefFO(1) = 10

coefFO(2) = 5

‘Inicializando coeficientes Matriz

coefMatriz(1, 1) = 2

coefMatriz(1, 2) = 4

coefMatriz(2, 1) = 1

coefMatriz(2, 2) = -6

‘Inicializando rhs

RHS(1) = 50

RHS(2) = 15

Um parâmetro adicional, restringindo as variáveis a assumir valor máximo 50 e mínimo 0.

For i = 1 To nvar

varmin(i) = 0 ‘Range Mínimo

varmax(i) = 50 ‘Range Máximo

Next i

Em linhas gerais:

– Escolhe valores aleatórios no range das variáveis

– Pondera o valor aleatório com a melhor solução até agora

– Lambda controla o mix valor aleatório x melhor solução até agora. No início lambda é…

Ver o post original 184 mais palavras

Exemplo de metaheurística – uma variável

Ferramentas em Excel-Vba

A ideia aqui é escrever uma série de metaheurísticas de dificuldade crescente.

Começando do caso mais simples possível. Variável unidimensional “x”.

Defino um range de valores, no caso, x entre 0 e 100.

varmin = 0 ‘Range Mínimo

varmax = 100 ‘Range Máximo

Seja a função objetivo –x^3 + 20*x^2 + 100, mostrado no gráfico abaixo.

Private Function FO(ByVal var) As Double

‘Implementa a função objetivo

FO = -var ^ 3 + 20 * var ^ 2 + 100

End Function

Este algoritmo vai:

- escolher um valor aleatório entre 0 e 100

– ponderar o valor aleatório com a melhor solução até agora

– lambda controla o mix valor aleatório x melhor solução até agora. No início lambda é pequeno, depois vai aumentando

– função objetivo que avalia a solução

– salva o histórico

Trecho do código:

For iter = 1 To Niteracoes ‘Numero de iteracoes

lambda = iter…

Ver o post original 75 mais palavras

Exemplo de aplicação do método RSA

Computação e Informação Quântica

Muito se fala do método RSA para criptografia, que utiliza chaves assimétricas.

Eu queria mostrar um exemplo numérico prático, simples, para entendimento do conceito.

Suponha que Alice queira mandar uma mensagem para Bob, utilizando o protocolo RSA.

A regra. Para encriptar uma mensagem “m” (que Alice tem), é necessária uma chave de encriptação “e”, e um grande número “N” (fornecidos por Bob).

O mensagem criptografada “c” é dada por

Por exemplo, com as chaves N = 143, e = 7, Alice quer encriptar a mensagem 14.

c = 14 ^7 mod 143 = 53.

A mensagem encriptada 53 é enviada a Bob.

Para números pequenos, é possível fazer essas contas no Excel. Para números grandes, não é possível, porque esbarra no limite de representação de números inteiros do Excel.

É mais jogo usar o Wolfram Alpha (https://www.wolframalpha.com/)

Basta digitar 14^7 mod 143 e teclar Enter.

Para decriptar a…

Ver o post original 330 mais palavras

Representação visual do MDC

Qual o máximo divisor comum entre 9 e 21?

O MDC é um dos principais conceitos de Teoria dos Números, e o algoritmo de Euclides continua sendo extremamente eficiente até hoje.

Vi uma versão visual deste, e gostaria de compartilhar.

Qual o máximo divisor comum entre 9 e 21?

21 / 9 = 2 (representado pelos dois quadrados de tamanho 9) e sobra 3

9 / 3 = 3 (vide os três quadrados de tamanho 3) e sobra…

Portanto, o MDC é 3.

A planilha em anexo plota essa visualização de MDC para dois valores quaisquer de a e b.

Exemplo. MDC(10, 2 ) = 2, o último quadrado de tamanho 2.

Outro exemplo, entre 6 e 9 (mdc = 3, o último quadrado 3×3).

Planilha para download em https://github.com/asgunzi/MDC-visual. É necessário ativar macros.

Veja também:

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

Ver o post original 1 mais palavra

Metaheurística para o Caixeiro-Viajante

Ferramentas em Excel-Vba

Implementação em VBA de metaheurística para resolução do problema do caixeiro-viajante.

A metaheurística não vai dar o valor ótimo, porém na prática, pode entregar um valor bom o suficiente.

Algumas vantagens: é mais flexível em termos de modelar restrições, é grátis (um solver tem licença que pode custar algumas dezenas de milhares de dólares, no mínimo).

Algumas desvantagens: ter alguém que manje muito de otimização combinatória para adaptar o código corretamente, não garantir a solução ótima.

De qualquer forma, é uma alternativa viável, competitiva e possível de ser utilizada, para problemas de otimização combinatória.

Segue para download no Github.

https://github.com/asgunzi/travelingSalesmanVBA

Ideias técnicas com uma pitada de filosofia
https://ideiasesquecidas.com/

Ver o post original

O código da transposição

Ferramentas em Excel-Vba

Dentre os métodos existentes em criptografia, há alguns bens simples (e fáceis de quebrar).

O código da transposição funciona assim.

Imagine uma mensagem a ser enviada: “Conta a lenda que dormia”.

Temos que ter um tamanho para quebrar a mensagem em pedaços menores.

Digamos que o tamanho seja 5.

Escrevemos a mensagem numa tabela, quebrando pelo tamanho dado.

Para codificar a mensagem, começamos a ler pelas colunas

A primeira coluna é codificada como “C nur”. A segunda é “oadem”.

A mensagem completa vira:

“C nuroademn a itl daaeqo”

Exercício: o que está escrito a seguir, sabendo que foi utilizado o código da transposição (com outro tamanho)?

“Tapem uule aéedena no a npa a aãev sloq”

Exercício extra. Criar uma função que codifique e decodifique o código, com uma string e um tamanho de entrada.


Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Veja também:

Ver o post original

Método babilônico para raiz quadrada

Ferramentas em Excel-Vba

Uma forma de encontrar a raiz quadrada de um número é com um método conhecido desde os babilônios.

Digamos que eu queira encontrar a raiz de N = 81.

Escolho um número qualquer, digamos a = 5.

Fazemos a conta (a + N/a)/2

Dá (5 + 81/5) / 2 = 10,6

E continuamos a fazer esse mesma conta:

(10,6 + 81/10,6) /2 = 9,12

Os próximos números já dá 9, raiz de 81.

Outro exemplo, quero a raiz de N = 121 e começo com a = 80:

80,00
40,76
21,86
13,70
11,27
11,00
11,00
11,00
11,00

Em poucos passos, converge para 11, raiz de 121.

É um exercício simples. Segue planilha para download.

Raiz.xlsx

Vide também: Método Babilônico para Aproximação de Raiz Quadrada de um Número n | O Baricentro da Mente

Ver o post original