O algoritmo de Damm

25-10-2015 19:22

 

    Vivemos rodeados de números. Quer em casa como no trabalho, sentimos necessidade de contar, calcular, comparar, medir e localizar. E o que seria do mundo se não tivéssemos números? Sem os números não saberíamos as horas ou a data. Não seríamos capazes de contar quantas coisas temos, ou quantas coisas gostaríamos de ter. E o que fazer quanto ao número da nossa porta ou aos contactos telefónicos que todos os dias utilizamos? Um exercício interessante consiste em tentar reescrever algumas notícias desta edição do Tribuna das Ilhas sem qualquer referência a números. Esta tarefa é mais complicada do que à primeira vista possa parecer. Por exemplo, para noticiar o resultado de uma partida de futebol, teríamos obrigatoriamente que substituir o resultado numérico por expressões como "sem golos"; "poucos golos"; "muitos golos"; "ainda mais golos"; ...

 

    Uma simples carteira pode servir de mote para uma longa conversa sobre exemplos de aplicação da Matemática no quotidiano. E aqui não pretendemos aludir às contas (difíceis) que é necessário fazer em tempo de crise. A verdade é que o número de série das notas de euro, bem como os números de identificação do cartão de cidadão (antigo número do BI ou Número de Identificação Civil, Número de Documento, Número de Identificação Fiscal, Número de Identificação da Segurança Social e Número de Utente de Saúde) são exemplos de números de identificação com algarismo de controlo (check digit). Os códigos de barras, os números dos cartões VISA e o Número de Identificação Bancária são outros exemplos. 

 

    Explorámos alguns destes números de identificação em vários artigos publicados no Tribuna das Ilhas ao longo dos últimos anos. A eficácia na deteção de erros que possam surgir na escrita, transmissão ou leitura de uma sequência de algarismos varia consideravelmente de algoritmo para algoritmo. Todos estes algoritmos detetam erros singulares (quando escrevemos o algarismo "a" em vez do algarismo "b"), que são os erros mais comuns (79,1%). Já as transposições de algarismos adjacentes (quando escrevemos "ab" em vez de "ba", por exemplo, ao premir as teclas do computador pela ordem errada) têm uma ocorrência de cerca de 10,2%. Os algoritmos utilizados nos códigos de barras e nos cartões VISA nem sempre detetam este tipo de erro. Nos códigos de barras não são detetadas as trocas entre o 6 e o 1, entre o 7 e o 2, entre o 8 e o 3 e entre o 9 e o 4. Já nos cartões VISA não são detetadas as trocas entre o 0 e o 9. 

 

 

    Há algoritmos mais eficazes, nomeadamente aqueles que detetam 100% dos erros singulares e 100% das transposições de algarismos adjacentes (que são os erros mais comuns, pois ocorrem cerca de 90% das vezes em que é cometido um erro). Mas a eficácia tem um custo: se permanecermos no âmbito da aritmética modular, é necessário recorrer a mais de um algarismo de controlo ou à utilização de mais símbolos para além dos algarismos habituais (do 0 ao 9); se abrirmos mão da aritmética modular, podemos recorrer a outras estruturas que requerem conceitos de Matemática mais sofisticados. 

 

    Em 1969, Verhoeff propôs um sistema eficaz que se baseia no grupo diedral D5 das simetrias de um pentágono regular. Recentemente, em 2004, H. Michael Damm provou na sua tese de doutoramento a existência de quase-grupos totalmente anti-simétricos para ordens diferentes de 2 e 6. A tabela da imagem define um quase-grupo totalmente anti-simétrico de ordem 10, adaptado de um exemplo apresentado por Damm na sua tese. Esta tabela é o que se designa por quadrado latino: em cada linha e em cada coluna, cada um dos símbolos utilizados deve figurar uma e uma só vez. Os quadrados latinos
surgiram pelas mãos de um grande matemático, talvez o maior matemático de todos os tempos: Leonhard Euler (1707-1783).

 

    Este tipo de tabelas não é totalmente estranho ao leitor. Se olhar com atenção, encontrará apenas duas diferenças em relação aos tradicionais desafios de Sudoku: não existem as chamadas "regiões" e utiliza-se o 0, para além dos algarismos 1-9. 

 

    A descoberta de Damm impulsionou o desenvolvimento de um novo algoritmo com o seu nome, que tem a vantagem de apenas utilizar os algarismos tradicionais, do 0 ao 9, e de detetar 100% dos erros singulares e 100% das transposições de algarismos adjacentes. Em relação ao algoritmo de Verhoeff, tem uma implementação mais simples e deteta 100% dos erros fonéticos (por exemplo, quando se escreve 15 em vez de 50, devido à pronúncia semelhante destes números em inglês: "fifteen" e "fifty"). 

 

    Na imagem, ilustra-se um exemplo de aplicação deste algoritmo para determinar o algarismo de controlo do número 201436571? (o ponto de interrogação representa o algarismo de controlo, por enquanto, desconhecido). Devemos considerar a igualdade 0*2*0*1*4*3*6*5*7 *1*?=0. A expressão do primeiro membro é formada pelo 0 seguido dos algarismos do número 201436571? separados pelo símbolo *, que representa a operação binária definida pela tabela da imagem. A tabela deve ser lida como se de um jogo da batalha naval se tratasse (cada algarismo da tabela é determinado pela linha e pela coluna a que pertence). Os cálculos devem ser feitos da esquerda para a direita, seguindo o sentido normal de leitura. Tem-se 0*2=1 (a linha do 0 e a coluna do 2 intersectam-se no 1). Da mesma forma, 1*0=7 (a linha do 1 e a coluna do 0 intersectam-se no 7). Segue-se 7*1=9, 9*4=4, 4*3=3, 3*6=3, 3*5=8, 8*7=2 e 2*1=2. Ficamos com 2*?=0. Ao observar com atenção a linha do 2, apercebemo-nos que o 0 pertence à coluna do 2, pelo que terá que ser 2*2=0. Sendo assim, 2 é o algarismo de controlo que pretendíamos determinar (como a diagonal principal da tabela é composta por zeros, o algarismo de controlo coincide sempre com o último algarismo calculado).

 

    De facto, os quadrados latinos  têm aplicações muito interessantes e úteis, para além de simples desafios de Sudoku. 

 

 

Ricardo Cunha Teixeira (Docente/investigador no Departamento de Matemática da U. dos Açores e colaborador no CcT)

 

Página pessoal do autor: www.rteixeira.uac.pt

 

Ver artigo original em: http://www.tribunadasilhas.pt/index.php/opiniao/item/9968-o-algoritmo-de-damm

 

Comentários

Não foram encontrados comentários.

Novo comentário