Geometria analitica e algebra linear

UNIVERSIDADE FEDERAL DE OURO PRETO - UFOP

ICEA

LISTA 2: ARITMÉTICA MODULAR E CÓDIGOS DE BARRAS

MATHEUS MOREIRA DA SILVA 12.2.8427

FELIPE DE ARAGAO GONCALVES 12.2.8293

LUDMILA KELLEN REIS PEREIRA 13.2.8622

MATEUS LOPES BICALHO 13.2.8472

GABRIEL FELIPE DE OLIVEIRA MACEDO 12.2.8097

JOÃO MONLEVADE

JUNHO - 2014

---

MATHEUS MOREIRA DA SILVA 12.2.8427

FELIPE DE ARAGAO GONCALVES 12.2.8293

LUDMILA KELLEN REIS PEREIRA 13.2.8622

MATEUS LOPES BICALHO 13.2.8472

GABRIEL FELIPE DE OLIVEIRA MACEDO 12.2.8097

LISTA 2: ARITMÉTICA MODULAR E CÓDIGOS DE BARRAS

                Trabalho apresentado ao Professor. Éden Amorim da disciplina Geometria Analítica e Álgebra Linear da turma T41 EP.

     

Universidade Federal De Ouro Preto

João Monlevade

1. ARITMÉTICA MODULAR

Até então trabalhamos com vetores com coordenadas e escalares reais, ou seja, com elementos de R. Nesse primeiro item vamos estabelecer um novo conjunto e suas operações: o conjunto dos inteiros módulo1 m, Zm = f0; 1; 2; _ _ _ ;m-1g. Primeiramente, vamos recordar a divisão de inteiros.

Definição 1 (Divisão inteira). Dados números inteiros n e m, a divisão de n por m produz inteiros q e r tais que n = q m + r; onde q é chamado quociente e r o resto. Esses números são únicos, desde que 0 _ r < m.

Exemplo: na divisão de 10 por 3 temos 10 = 3 _ 3 + 1, ou seja, o quociente é 3 e o resto é 1. Já na divisão de -10 por 3 temos -10 = -4 _ 3 + 2, ou seja, quociente -4 e resto 2.

Definição 2 (Congruência módulo m). 2 Dizemos que dois números inteiros a e b são congruentes módulo m se têm o mesmo resto na divisão m. Nesse caso escrevemos a = b mod. m ou simplesmente a = b, quando estiver claro no contexto e valor de m.

Exemplo: 10 = 7 mod. 3, pois na divisão por 3 temos ambos com resto 1.

Dizemos que o número a foi reduzido módulo m quando expressamos sua congruência pelo

o resto de sua divisão por m. No exemplo acima, 10 e 7 quando reduzidos módulo 3 são congruentes a 1.

1. Dado o conjunto f-41;-23;-10;-2; 4; 7; 11; 15; 17; 21g, separe-o em 3 subconjuntos disjuntos: o subconjuntos dos números congruentes a 0 módulo 3, congruentes a 1 e congruentes a 2.

2. Mostre que, se a e b são congruentes módulo m, então a - b = km para algum k 2 Z (ou seja, a - b é múltiplo de m).

Definimos o conjunto Zm como sendo o conjunto das classes de congruência módulo m, ou seja, o conjunto finito f0; 1; 2; _ _ _ ;m-1g dos restos na divisão por m. Nesse conjunto, tratamos os números inteiros reduzindo-os módulo m. No exemplo anterior, em Z3 podemos escrever 10 = 7 = 1.

Nesse conjunto podemos definir duas operações, baseada nas seguintes propriedades:

Proposição 1 (Linearidade). Se a e b têm resto r1 e r2, respectivamente, na divisão por m, então:

• a + b tem resto r1 + r2 e

• ab tem resto r1r2.

Isso permite definir somas e produtos em Zm: basta reduzir os números módulos m e somá-os ou multiplicá-los, na ordem que considerar mais adequada; o resultado será o mesmo.

Exemplo: em Z3, vamos somar 10 e 8. Se primeiro reduzirmos e em seguida somarmos

10 + 8 = 1 + 2 = 3 = 0 mod 3:

Ou, somando primeiro e reduzindo depois, obtemos 10 + 8 = 18 = 0 mod 3: Para o produto, igualmente: 10 _ 8 = 1 _ 2 = 2 mod 3 ou 10 _ 8 = 80 = 2 mod 3.

Em particular, fica evidenciada uma estrutura cíclica no conjunto Zm.

3. Reduza as expressões em Z5:

(a) 10 + 12(7 + 3)

(b) (2 _ 3 + 17)(1 + 15 _ 3)

4. Demonstre a proposição 1.

2 CÓDIGOS E VERIFICAÇÃO

Podemos definir um vetor m-ário (binário, trinário, etc.) de n coordenadas como sendo um elemento de Znm, da forma ~b = (b1; b2; _ _ _ ; bn); onde bi 2 Zm; 1 _ i _ n:

Esse também é um conjunto finito. As operações de soma e multiplicação por escalar, assim como o produto escalar de vetores em Znm é análoga à definição usal para vetores em Rn, onde escalares agora também são elementos em Zm.

1. Elementos de Z32 são vetores binários de 3 coordenadas. Liste todos seus elementos.

2. Calcule em Z32

: (1; 0; 1) + (1; 1; 0).

3. Quantos elementos há em Znm?

Um sistema comum de identificação usa vetores em algum Znm conveniente para representar objetos, produtos, usuários, entre outros conjuntos finitos. Por exemplo, os códigos de barra do padrão UPC, como mostrado na figura (2), usam uma sequência de barras de espessuras diversas para identificar um produto. Cada barra é representada por um número entre 0 e 9 associado a sua espessura. Em um código de barra desse tipo, os 11 primeiros dígitos identificam o produto e o último é chamado dígito verificador. Assim, podemos representá-los por um vetor de código da forma ~c = (u1; u2; _ _ _ ; u11; d) 2 Z11+110 ; onde destacamos o último dígito d apenas para evidenciar o dígito verificador. No exemplo da figura, temos o vetor (0; 7; 4; 9; 2; 7; 0; 2; 0; 9; 4; 6).