Ir ao conteúdo principal

Exercícios 3.5 Exercícios Adicionais: Detectando Error

1. Códigos UPC.

O Código Universal de Produtos (UPC com sua sigla em inglês) se encontra na maioria dos produtos de supermercados e lojas de varejo. O UPC é um código de 12 dígitos que identifica o fabricante de um produto e o produto mesmo (Figura 3.5.1). Os primeiros 11 dígitos contém informação sobre o produto; o último dígito se usa para a detecção de error. Se \(d_1 d_2 \cdots d_{12}\) é um número UPC válido, então

\begin{equation*} 3 \cdot d_1 + 1 \cdot d_2 + 3 \cdot d_3 + \cdots + 3 \cdot d_{11} + 1 \cdot d_{12} \equiv 0 \pmod{10}. \end{equation*}

  1. Mostre que o número UPC 0-50000-30042-6, que aparece na Figura 3.5.1, é um número UPC válido.

  2. Mostre que o número 0-50000-30043-6 não é um número UPC válido.

  3. Escreva uma fórmula para calcular o dígito verificador, \(d_{12}\text{,}\) de um número UPC.

  4. O método de detecção de erros do UPC pode detectar la maior parte dos erros de transposição; isto é, pode determinar se dois dígitos foram trocados. Mostre que o erro de transposição 0-05000-30042-6 não é detectado. Encontre um erro de transposição que sim seja detectado. Pode encontrar uma regra general sobre quais são os erros de transposição que são detectados?

  5. Escreva um programa que determina se um número UPC é válido.

Figura 3.5.1. Un código UPC

2.

É frequentemente útil utilizar a notação de produto interno para este método de detecção de erros; por isso, utilizaremos a notação

\begin{equation*} (d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n } \end{equation*}

para dizer que

\begin{equation*} d_1 w_1 + d_2 w_2 + \cdots + d_k w_k \equiv 0 \pmod{ n}. \end{equation*}

Suponhamos que \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) é um método de detecção de erros para o número de identificação de \(k\) dígitos \(d_1 d_2 \cdots d_k\text{,}\) onde \(0 \leq d_i \lt n\text{.}\) Demonstre que todos os erros em um só dígito são detectados se e somente se \(\gcd( w_i, n ) = 1\) para \(1 \leq i \leq k\text{.}\)

3.

Seja \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) um método de detecção de erros para o número de identificação de \(k\) dígitos \(d_1 d_2 \cdots d_k\text{,}\) onde \(0 \leq d_i \lt n\text{.}\) Demonstre que todas as transposições de dois dígitos \(d_i\) e \(d_j\) são detectadas se e somente se \(\gcd( w_i - w_j, n ) = 1\) para \(i\) e \(j\) entre 1 e \(k\text{.}\)

4. Códigos ISBN.

Cada livro tem um International Standard Book Number (ISBN). Este é um código de 10 dígitos que indica a editora e o título do livro. O décimo dígito é um dígito verificador que satisfaz

\begin{equation*} (d_1, d_2, \ldots, d_{10} ) \cdot (10, 9, \ldots, 1 ) \equiv 0 \pmod{11}. \end{equation*}

Um problema é que \(d_{10}\) pode ter de ser 10 para que o produto interior seja zero; nesse caso, são necessários 11 dígitos para que o método funcione. Assim, um X é utilizado como décimo primeiro dígito para representar o 10. Assim o ISBN 3-540-96035-X é um código ISBN válido.

  1. É ISBN 0-534-91500-0 um código ISBN válido? E é ISBN 0-534-91700-0 ou o ISBN 0-534-19500-0?

  2. Este método serve para detectar todos os erros em um só dígito? E todos os erros de transposição?

  3. Quantos códigos ISBN diferentes existem?

  4. Escreva um programa que permita calcular o dígito verificador para os primeiros nove dígitos de um código ISBN.

  5. Uma editora tem escritórios na Alemanha e nos Estados Unidos. O seu prefixo alemão é 3-540. Se o seu prefixo americano for 0-abc, encontre abc tal que o resto do código ISBN seja o mesmo para um livro impresso na Alemanha e nos Estados Unidos da América. Sob o método de codificação ISBN, o primeiro dígito identifica a língua; o alemão é 3 e o inglês é 0. O próximo conjunto de números identifica a editora, e o último conjunto identifica o livro específico.