O algoritmo de Damm

(...) 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 devem 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). (...)

A multiplicação de dois números segundo o algoritmo de Karatsuba

Em tempos que já lá vão, aprendemos um algoritmo para multiplicar números. Talvez o nosso professor não o designasse “algoritmo” para não nos assustar, mas, independentemente da formalidade do nome, aprendemos um conjunto bem definido de regras para executar a operação da multiplicação. Este artigo descreve este algoritmo e o algoritmo inventado pelo matemático russo Anatoly Alexeevitch Karatsuba (1937–2008).

Matrizes e Quadrados Mágicos

Na sociedade atual, completamente dominada pela constante procura de informação, faz todo o sentido recorrer a formas organizadas de apresentar os dados recolhidos que permitam uma leitura rápida e acessível. As matrizes, pela sua estrutura, possibilitam este tipo de abordagem com vista ao tratamento de uma grande quantidade de informação. (...) Poucas áreas da Matemática sofreram nos últimos 30 anos uma evolução tão significativa como a Teoria de Matrizes. Isto deve-se ao desenvolvimento de computadores cada vez mais potentes do ponto de vista da capacidade computacional, bem como à introdução de métodos matriciais em diferentes áreas de aplicação. Atualmente, a Teoria de Matrizes é utilizada com frequência para modelar muitos fenómenos do mundo real. Mas quando é que surgiu este ramo da Matemática? (...) Embora este ramo da Matemática tenha sido desenvolvido a partir de meados do século XIX, conceitos elementares de matrizes remontam ao período anterior ao nascimento de Cristo, uma vez que os chineses aplicavam métodos matriciais para resolver certos sistemas de equações. Os quadrados mágicos constituem outro exemplo de aplicação rudimentar do conceito de matriz. As lendas sugerem que os quadrados mágicos são originários da China, tendo sido referidos pela primeira vez num manuscrito do tempo do imperador Yu, cerca de 2200 a. C. (...) Em 1514, Albrecht Dürer, conhecido artista da Renascença, pintou um quadro intitulado "Melancolia", onde figura um quadrado mágico, precisamente de ordem 4 (figura 2). De notar que os dois números centrais da última linha do quadrado permitem ler "1514", o ano em que o quadro foi pintado. O leitor pode comprovar que a soma dos números de cada linha, de cada coluna e de cada uma das duas diagonais desse quadrado é sempre igual a 34, a constante mágica. Além disso, 34 é a soma dos números dos cantos (16+13+4+1=34) e do quadrado central 2x2 (10+11+6+7=34). (...)

Matemática no quotidiano : do cartão VISA ao Número de Identificação Bancária

(...) Existem diferentes tipos de sistemas de identificação com check digit. A escolha do algoritmo a implementar deve satisfazer dois princípios: por um lado, é importante escolher um sistema eficaz que detete o maior número possível de erros; por outro lado, a sua utilização no terreno deve ser de alguma forma acessível, particularmente para quem tem de lidar diariamente com os números produzidos por esse algoritmo. Hoje em dia a utilização de meios eletrónicos revela-se muito eficaz, quer para gerar o algarismo de controlo de novos números, como para validar números que já se encontrem em circulação. Mesmo assim, há uma série de requisitos importantes a ter em conta quando se pretende implementar um novo sistema de identificação. Desde logo, a escolha do alfabeto, ou seja, dos símbolos a utilizar. Normalmente, opta-se por recorrer apenas aos dez algarismos vulgarmente utilizados, do 0 ao 9. É o caso do exemplo que se segue. O método desenvolvido pela IBM, também conhecido por algoritmo de Luhn, aplica-se à generalidade dos cartões de crédito: VISA e VISA Electron (em que o primeiro algarismo da esquerda é um 4), MarterCard (5), American Express (3) e Discover (6), entre outros. Considere-se o número de um cartão VISA: 4188 3600 4538 6426. Como é habitual, o algarismo de controlo é o primeiro algarismo da direita, ou seja, o algarismo das unidades (6). Para verificar se este número é válido, procede-se da seguinte forma (...). Há um algoritmo mais eficaz, desenvolvido por Verhoeff em 1969, que utiliza os mesmos símbolos (os algarismos do 0 a 9). Este sistema deteta 100% dos erros singulares, 100% das transposições de algarismos adjacentes e algumas das transposições intercaladas. Paradoxalmente, é um método pouco utilizado, talvez por necessitar de uma maior bagagem matemática.(...) Na imagem, ilustra-se um exemplo de aplicação deste algoritmo para determinar o algarismo de controlo do número 201034571? (o ponto de interrogação representa o algarismo de controlo, por enquanto, desconhecido). (...) Se nos predispusermos a alargar o alfabeto de símbolos ou a considerar mais de um algarismo de controlo, podemos obter algoritmos ainda mais eficazes na deteção de erros. É o caso dos algoritmos estabelecidos pela norma ISO/IEC 7064. Por exemplo, o algoritmo MOD 11-2 é utilizado para identificar as receitas médicas em Portugal e utiliza um símbolo adicional (o X, que representa o número 10). Já o algoritmo MOD 97-10 requer a utilização de dois algarismos de controlo e é empregue na emissão do Número de Identificação Bancária (NIB). (...)