06/05/2008

Algoritmos de Verificação

Uma curiosidade que podem experimentar.
É sobre números de telemóvel, pensem no vosso número de telemóvel sem o indicativo.

1- Digite os 3 primeiros algarismos de seu telemóvel (não vale o indicativo 91, 93 ou 96...);
2- Multiplique por 80.
3- Some 1.
4- Multiplique por 250.
5- Some com os 4 últimos algarismos do mesmo telemóvel.
6- Some com os 4 últimos algarismos do mesmo telemóvel de novo.
7- Subtraía 250.
8- Divida por 2.

Então o resultado coincide ou não!
Este processo é o que se chama de um algoritmo de verificação (ou de confirmação).
Um algoritmo é uma maneira que adoptamos para resolver um problema, por exemplo para resolver uma equação de 2º grau usamos a formula resolvente para equações de 2º grau, então podemos dizer que a formula resolvente (para equações de 2º grau) é o algoritmo que usamos para resolver equações de 2º grau.
Os algoritmos de confirmação são usados para confirmar se um dado número pertencente a algo é verdadeiro, ok vou tentar clarificar... =P
Por exemplo nos supermercados para os artigos serem identificados, estes possuem um código de barras, os livros possuem o ISBN, um código que os identifica o livro, as notas de euro possuem o numero de série, os bilhetes de avião também possuem um numero para identificar a viagem. Como podem ver estes códigos são de grande importância, imaginem uma transferência de dinheiro entre bancos, o numero de série das notas tem que ser enviado para que quem receba o dinheiro possa confirmar que não falta nenhuma ou que nenhuma é falsa, no caso das notas de euro há mais características que permitem saber se uma nota é falsa ou não, para além do numero de série.
Ou imaginem num supermercado quando a senhora da caixa passa uma garrafa de água e o preço registado é cinco euros, sem dúvida que há algum problema com o código de barras.
Estes algoritmos de confirmação permitem-nos saber se há algum problema com o código do objecto que estão a representar, digamos assim.
O conjunto de passos apresentados no inicio deste post são isso, um algoritmo de verificação dos números de telemóvel. Penso que o número indicador não é considerado porque muda consoante a rede.
Por curiosidade e já que estamos a falar de algoritmos de confirmação eu vou deixar aqui o algoritmo de confirmação das notas de euro. Este algoritmo serve para todas as notas.
As notas euro são compostas por uma série de números e por uma letra. As letras indicam o país a que a nota pertence e cada letra tem um valor correspondente



Alguns dos países que aí estão não possuem euros mas foi-lhes atribuída uma letra e um número caso decidissem adoptar a moeda.
Então o algoritmo consiste em somar todos os números da série, depois soma-se o resultado ao número a que a letra corresponde. Agora o resultado desta soma tem que ser múltiplo de 9, isto é, se dividirmos o resultado por 9 a divisão tem que dar resto de zero, se não der significa que a nota é falsa!
Este tipo de algoritmo também é usado nos bilhetes de identidade, apesar de, em alguns BIs não ser possível verificar devido a um "pequeno" problema, mas vou deixar esse assunto para outro post.

23 comentários:

Paulo Ferro disse...

Um exemplo de algoritmo de verificação que me vem logo à cabeça, e que é muito simples, é no caso da divisão. Um aluno do 1º ciclo para saber se fez correctamente uma divisão, pode realizar a multiplicação (operação inversa) para confirmar o resultado obtido.

Metódica disse...

Olá Paulo, seja bem vindo,
Essa é a chamada prova real, se não me engano :)

proffil disse...

Metódica, eu sei que não domino a coisa... mas... não deu o que era suposto dar!... deu **00*0*, em vez de **0*0*... :(
E juro que usei a calculadora...

proffil disse...

OK: já descobri o meu erro!...ehheeh
Considerei mal quais eram os três primeiros dígitos... como se o indicativo tivesse três algarismos em vez de DOIS...
É sempre a mesma coisa!... demasiado distraída para a matemática!... :P
Agora já deu lindamente certo!

Metódica disse...

Proffil
Eheh, essas coisas acontecem, comigo pelo menos acontecem com alguma frequencia =P
O importante é que pode confirmar =D

alf disse...

belo post sim senhor. E não sabia isso das notas.

Estes algoritmos e códigos de controle de erro são fundamentais em todos os sistemas digitais, em que toda a informação é reduzida a números, no caso em código binário. Todos os processos de transmissão desta informação está sujeita a "ruidos" que podem transformar "0" em "1" e vice-versa, pelo que o uso de informação adicional destinada a detectar e recuperar informação danificada é essencial, ocupando mesmo uma parte muito significativa do total de dados transmitidos. Sem isto não podia haver televisão digital nem internet nem nada que meta transmissão de dados.

Não é isto, pois, uma mera curiosidade, mas algo de grande importancia.

Já agora, a prova dos nove também é um algoritmo de verificação elementar, usado no liceu.

Metódica disse...

É verdade Alf!
Estes algoritomos são de extrema importância na sociedade.

antonio disse...

Todos nós temos um algoritmo de verificação, a que muitos chamam de estado de alerta... nele se jogam afectos, confianças, empatias, nele nascem todos os ódios de estimação e se cimentam inimizades fiéis e persistentes. Nele nascem e morrem estados de alma.

Metódica disse...

Meu caro António, anda muito poético =D

alf disse...

em relação ao comentário do António, está muito bem observado! Mas um reparo: em vez de neles cimentar ódios de estimação, porque não cimentar amizades de estimação?

Metódica disse...

Acho que se cimenta tudo o que formos construindo com os outros e em nós próprios =)

Anónimo disse...

Olá..
Desculpem mas tenho uma coisa a dizer..
Deixando a importância dos algorítmos e falando apenas no esquema de verificação dos números de telemóveis.
Não sei como funciona a atribuição dos números dos telemóveis mas o algorítmo descrito é válido para todos os numeros até sete algarismos e facilmente arranjo um para todos os números até nove alagarismos (numeros de telemóveis com os indicativos).
O que concluo é que não pode ser um esquema para verificar os números dos telemóveis pois é válido para todos os números até 7 algarismos. Para funcionar para o número total do telemóvel (incluindo indicativo) poderia ser algo assim:

1- Digite os 3 primeiros algarismos de seu telemóvel;
2- Multiplique por 800;
3- Some 1.
4- Multiplique por 2500;
5- Some com os 6 últimos algarismos do mesmo telemóvel.
6- Some com os 6 últimos algarismos do mesmo telemóvel de novo.
7- Subtraia 2500.
8- Divida por 2.

Verifiquem e vejam que dá... pois dá para todos os números até 9 algarismos...

Curioso

Dulcineia disse...

Quando é que vais postar sobre uma coisa normal????? Só para ter uma ideia...

antonio disse...

Hum! Muito profundo Metódica... cuidado com os algoritmos!

Metódica disse...

Olá Anónimo, esteja à vontade.
Realmente é interessante, comigo funcionou.
Acho que acabou de descobir o algoritmo de verificação dos números de telemovel com o indicativo =)

Metódica disse...

Dulcineia
O post anterior é sobre uma coisa normal ;)

Anónimo disse...

Olá mais uma vez...

O que eu quiz dizer no meu comentário anterior é que todos os números (incluindo os que não são de telemóvel) podem ser descritos pelo algorítmo que apresentou. Qualquer número com 7 algarismos...
Eu apenas generalizei para nove...

A conclusão (se aquilo for um algorítmo para números de telemóveis) é que tudos os números são possíveis (para telemóveis).

Curioso

Metódica disse...

Curioso
Acho que já percebi o que quer dizer...
Um algoritmo de verificação serve para confirmar se um dado número está correcto ou não como disse no texto. Mas se por exemplo no algoritmo de verificação que voce deixou, eu usar nos primeiros tres números números que não sejam de telemovel e em vez disso escolhér tres números ao acaso vou obter um resultado, mas esse resultado não me vai dizer nada, porque não estou a querer confirmar um número de telemovel.
Uma analogia talvez ajude...
Por exemplo voce tem uma receita para um bolo de laranja, mas imagine que não tem laranjas e resolve usar cenouras, vai ter um bolo na mesma, mas não vai ser o de laranja.
É mais ou menos isso que acontece no caso do algoritmo, por exemplo no caso do seu algoritmo se voce não quiser intruduzir os primeiros 3 números de um telemovel pode introduzir uns tres números ao acaso irá ter um resultado assim como acabou por ter um bolo mas não será um número de telemovel assim como não foi um bolo de laranja.
(Era isto que estava preguntar?)

proffil disse...

Pois fiz como curioso disse... e deu certo! :)
Esse curioso deve ser curiosamente sabido nestas coisas!... eheheh

proffil disse...

Claro que não percebi patavina da lógica subjacente!... :(
Mas isso é outra coisa! :P

Metódica disse...

Proffil estamos sempre a aprender =D

A lógica subjacente é a minha explicaçao?

anonimodenome disse...

eu enviei dois comentários que não vejo por aqui.
afirmei que este não é um algoritmo de verificação.
equivale a dizer que 1=1 e mostrei o porquê.
como é verificado para qualquer nº não verifica/testa nada.
também o algoritmo usado nas notas foi muito mal escolhido pelos responsáveis da segurança monetária.
o porquê demora a explicar.
na net procure 'check digit algoritm' para ficar mais dentro do problema.
no entanto dou-lhe os parabéns pelo seu blog. com os erros aprende-se.
continue a estudar.
mas ficarei desiludido se exercer censura nos meus comentários.

Metódica disse...

Anónimodenome bem vindo =)
Obrigada!

Eu não recebi os seus comentários anteriores, não sei o que se passou...
Eu publico os comentários que me deixam não os censuro. É estranho, estive a confirmar e não tenho nada na caixa de correio...
Mas sinta-se à vontade para comentar! =)

Eu sei que o algoritmo foi muito mal escolhido.
Estou a ler um livro de Buescu e foi de um capitulo onde o autor falava do algoritmo de verificação das notas de euro que me lembrei de fazer este post.

Com os erros é que se aprende: concordo plenamente :)