Arquivo de etiquetas: algoritmos

Algoritmo de Verhoeff

Na edição 16 da Revista PROGRAMAR em Outubro de 2008 foi publicado o artigo Algoritmos para o Cálculo de Dígito Verificador que descreveu o cálculo de dígito verificador para códigos de identificação a partir dos métodos de módulo 10 e 11. Além dos algoritmos já apresentados existem outros mecanismos para cálculo e obtenção de dígitos verificadores, podendo-se destacar o algoritmo de Verhoeff, tema deste artigo.

O algoritmo ora apresentado foi desenvolvido por Jacobus (Koos) Verhoeff, matemático holandês para sua tese de doutorado em 1969 (GARCIA, et. al., 2007, p. 47). Verhoeff escreveu um algoritmo capaz de operacionalizar sequências de dígitos decimais de qualquer tamanho, evitando desta forma a ocorrência de erros de dados (HAMMING, 1986, p.27) e de transposição de dígitos adjacentes quando efectuados por utilizadores humanos (WAGNER & PUTTER,1989), tais como:

  • Substituir um dígito por um outro dígito. Por exemplo, invés de informar os dígitos 5678 acaba-se por informar 4678, onde o dígito que deveria ser 5 foi substituído pelo dígito 4. Este tipo de erro ocorre quando se acciona no teclado uma tecla adjacente à tecla que deveria ter sido realmente accionada. Ocorre em cerca de 60% a 90% dos casos.
  • Omissões ou adições de dígitos. Este tipo de erro ocorre normalmente por falta de atenção do utilizador. Ocorre em cerca de 10% a 20% dos casos.
  • Trocar da ordem entre dois dígitos. Por exemplo, invés de informar os dígitos 5678 acaba-se por informar 6578, onde os dígitos 56 foram trocados pelos dígitos 65. Este tipo de erro ocorre quando se escreve muito rápido em um teclado. Ocorre em cerca de 10% a 20% dos casos.

Continuar a ler

Manipulação de Datas

Introdução

No mundo da programação, é comum necessitarmos de algum utilitário que efectue cálculos com datas do calendário gregoriano. Os ambientes de programação integrados normalmente possuem tais funções já definidas internamente, bastando ao programador apenas fazer uso das mesmas. A principal questão deste artigo é responder à questão: como podem esses cálculos ser processados? Para solucionar este tipo de problemas, é conveniente conhecer e utilizar algoritmos específicos. Existem várias formas e soluções, no entanto é aconselhável utilizar aquelas que já tenham sido testados como, por exemplo, algoritmos utilizados na área da Observação Astronómica, que possibilitam calcular qualquer data a partir do ano 4712 a.C. Para entender melhor o processo do cálculo de datas, torna-se necessário entender os conceitos de: Dia Juliano, Calendário Juliano, Calendário Gregoriano e Ano Bissexto.

Continuar a ler

Algoritmia Clássica em C++

Breve Introdução Histórica

A linguagem C++ foi desenvolvida durante os anos 80 na Bell Labs, pelo cientista de computação dinamarquês Bjarne Stroustrup. Esta linguagem é muitas vezes retratada como uma evolução da linguagem C. De facto, esta linguagem foi a principal base de desenvolvimento de C++, tanto mais que a primeira versão da nova linguagem tinha o nome de C With Classes, evoluindo mais tarde para C++. Em português deve-se pronunciar “cê mais mais” sendo que em inglês esta linguagem é pronunciada como “cee plus plus”.

Continuar a ler

Grafos – 2ª Parte

Depois de na primeira parte (ver Edição 10) termos feito uma introdução ao mundo dos grafos e de termos lançado as primeiras bases para uma melhor compreensão destas estruturas, chegou a altura de perceber, realmente, que problemas podem ser resolvidos.

Pode ficar já claro que o número de algoritmos que resolvem problemas baseados em grafos é enorme, demasiado extenso para ficar completo um artigo, portanto nada melhor do que começar pelos mais simples (e importantes). Preferi manter o nome dos algoritmos e dos problemas em inglês para ser mais fácil encontrá-los numa pesquisa.

Continuar a ler

Grafos – 1ª Parte

Introdução: O que é um grafo

O leitor certamente que já ouviu falar em grafos. São amplamente usados em matemática, mas sobretudo em programação.

Formalmente, um grafo é uma colecção de vértices (V) e uma colecção de arcos (E) constituídos por pares de vértices. É uma estrutura usada para representar um modelo em que existem relações entre os objectos de uma certa colecção.

Pense nos vértices como “locais“. O conjunto dos vértices é o conjunto de todos os locais possíveis. Nesta analogia, os arcos (ou arestas) representam caminhos entre estes locais. O conjunto E (vou usar o termo mais comum – “E” do inglês “edges“) contém todas as ligações entre os locais.

Utilizar grafos é de grande utilidade na representação de problemas da vida real.

Continuar a ler