P3_121_Gabarito

Prévia do material em texto

UFSC - CTC - INE5403 - Fundams. de Mat. Discreta para a Computac¸a˜o - Sem. 12.1 - 25/jun/2012 - T. 01208A
Nome:
Terceira prova
Atenc¸a˜o: nas questo˜es objetivas a seguir, apenas uma alternativa deve ser claramente marcada. Questo˜es com mais de uma marcac¸a˜o sera˜o
consideradas erradas.
1. (1,0 ponto) Com relac¸a˜o ao poset ({{1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}},⊆),
analise as seguintes afirmativas:
I. Ele possui exatamente 2 elementos maximais.
II. Ele possui exatamente 3 elementos minimais.
III. O seu maior elemento e´ {2, 3, 4}
IV. O seu menor elemento e´ {1}
V. O supremo de {{2}, {4}} e´ {{2, 4}}
VI. Todas as cotas superiores de {{2}, {4}} sa˜o {{4}, {2, 4}, {2, 3, 4}}
VII. Todas as cotas inferiores de {{1, 3, 4}, {2, 3, 4}} sa˜o {{4}, {2, 4}, {3, 4}}
VIII. O ı´nfimo de {{1, 3, 4}, {2, 3, 4}} e´ {3, 4}
IX. Ele possui exatamente dois subconjuntos de 4 elementos totalmente ordenados.
A ana´lise permite concluir que:
Resposta: somente II, V e VIII sa˜o verdadeiras.
Justificativa: (Extremos de Posets - ver definic¸o˜es no formula´rio))
• para comec¸ar, e´ u´til montar o diagrama de Hasse deste reticulado:
• por este diagrama, nota-se que:
– este reticulado possui exatamente 3 elementos maximais: {1, 2}, {1, 3, 4} e {2, 3, 4} (II e´ V)
– as cotas superiores de {{2}, {4}} sa˜o apenas {2, 4} e {2, 3, 4}, de modo que o seu supremo e´ {2, 4} (V e´ V)
– as cotas inferiores de {{1, 3, 4}, {2, 3, 4}} sa˜o apenas {3, 4} e {4}, de modo que o seu ı´nfimo e´ {3, 4} (VIII e´ V)
2. (1,0 ponto) Seja A = {2, 3, 4, . . . , 100}, com a ordem parcial de divisibilidade. Enta˜o o nu´mero de elementos maximais que (A,≤) possui e´:
Resposta: 50.
Justificativa:
• todos os elementos de A que va˜o de 2 ate´ 50 dividem algum outro elemento do conjunto (no mı´nimo, os seus dobros esta˜o, certamente,
em A);
• mas na˜o ha´, em A, nenhum elemento que seja divis´ıvel pelos 50 elementos que va˜o de 51 ate´ 100 �
3. (1,0 ponto) A quantidade de reticulados diferentes que existem sobre A = {a, b, c, d} e´ dada por: (dica: um reticulado e´ definido pela disposic¸a˜o
dos elementos sobre um diagrama de Hasse)
Resposta: 4! +A(4, 2)
Justificativa: (Reticulados e Diagrams de Hasse)
• todo reticulado pode ser associado com o seu diagrama de Hasse;
• existem apenas duas possibilidades de estrutura para o diagrama de Hasse de um reticulado com 4 elementos:
o o
| / \
o o o
| \ /
o o
|
o
• cada reticulado diferente corresponde a uma maneira de acomodar os 4 elementos em uma destas duas estruturas;
• no primeiro caso, qualquer permutac¸a˜o dos 4 elementos gera um diagrama diferente;
• no 2o caso, o reticulado e´ determinado pelo maior elemento e pelo menor elemento: uma vez definidos estes dois, a posic¸a˜o dos outros
dois e´ irrelevante;
• portanto, existem 4! +A(4, 2) = 36 reticulados diferentes diferentes sobre um conjunto com 4 elementos �
4. (1,0 ponto) Prove que, em um reticulado (L,≤), e´ va´lido afirmar que: ∀a, b ∈ L, a ∨ (a ∧ b) = a
Resposta: (Propriedades elementares de Reticulados)
• pela definic¸a˜o de supremo, sabemos (ver formula´rio) que para todo reticulado vale a ≤ (a ∨ b), de modo que obtemos imediatamente
que a ≤ a ∨ (a ∧ b)
• por outro lado:
– sabemos que a ≤ a, pois todo reticulado e´ uma relac¸a˜o reflexiva
– ale´m disto, pela definic¸a˜o de ı´nfimo, sabemos que (ver formula´rio) (a ∧ b) ≤ a
– isto significa que a e´ uma cota superior de a e de a ∧ b, de modo que deve valer: a ∨ (a ∧ b) ≤ a
• enta˜o, uma vez que a ≤ a ∨ (a ∧ b) e a ∨ (a ∧ b) ≤ a, chegamos a a ∨ (a ∧ b) = a
– pois todo reticulado e´ uma relac¸a˜o antissime´trica �
1
5. (1,0 ponto) Prove que, em uma A´lgebra Booleana qualquer Bn, e´ va´lido afirmar que: ∀a, b, c ∈ Bn, se a ≤ b, enta˜o: a ∨ c ≤ b ∨ c.
Resposta: (Propriedades elementares de A´lgebras Booleanas)
• pela definic¸a˜o de supremo, sabemos (ver formula´rio) que para todo reticulado (e, portanto, para toda A´lgebra Booleana) vale: b ≤ (b∨c)
e c ≤ (b ∨ c)
• enta˜o, uma vez que a ≤ (b ∨ c) e c ≤ (b ∨ c), conclu´ımos que (b ∨ c) e´ uma cota superior de a e de c
– de modo que, pela definic¸a˜o de supremo, obtemos que: (a ∨ c) ≤ (b ∨ c) �
6. (1,0 ponto) Lu´ıs Ina´cio escreveu todos os nu´meros de 1 a 2009 numa folha de papel. Com os amigos, combinou o seguinte: cada um deles
poderia apagar quantos nu´meros quisesse e escrever, no fim da lista, o algarismo das unidades da soma dos nu´meros apagados. Por exemplo,
se algue´m apagasse os nu´meros 28, 3, 6, deveria escrever no fim da lista o nu´mero 7, pois 28 + 3 + 6 = 37. Apo´s algum tempo, sobraram
somente dois nu´meros. Se um deles era 2000, qual dos nu´meros a seguir poderia ser o outro?
Resposta: 5.
Justificativa: (Aritme´tica mo´dulo 10)
• para comec¸ar, note que obter o algarismo das unidades da soma de todos os nu´meros de 1 a 2009 e´ o mesmo que obter o resultado
desta soma mo´dulo 10, de modo que ele na˜o muda pelo fato das somas intermedia´rias terem sido efetuadas
• no in´ıcio, temos que (∑i=2009i=1 i)mod 10 = 5, pois ∑i=10i=1 i = (1 + 10).10/2 = 55
– de modo que cada bloco de 10 nu´meros consecutivos na soma tera´ d´ıgito das unidades igual a 5
– logo, o d´ıgito das unidades da soma de 1 a 2000 deve ser o mesmo de 200× 5, ou seja, 0
• enta˜o, se, dos dois nu´meros que sobraram, um era 2000, o outro deve ser 5 (pois a soma de 1 a 9 e´ 45) �
7. (1,0 ponto) Vamos chamar de selo de um nu´mero inteiro positivo o par (x; y) no qual x e´ o nu´mero de divisores positivos desse nu´mero menores
do que ele e y e´ a soma desses divisores. Por exemplo, o selo do nu´mero 10 e´ (3;8) pois o nu´mero 10 tem como divisores menores do que ele os
nu´meros 1, 2 e 5, cuja soma e´ 8. Ja´ o selo do nu´mero primo 13 e´ (1;1) . Ha´ nu´meros cujo selo e´ (6;m). Qual e´ o menor valor poss´ıvel para m?
Resposta: 63
Justificativa: (Quantidade de divisores)
• seja n um nu´mero com selo (6;m)
• se n possui 6 divisores menores do que ele, enta˜o, no total, ele possui 7 divisores (contando com ele pro´prio).
• ora, para que um nu´mero tenha uma quantidade de divisores que e´ um nu´mero primo, a u´nica possibilidade (ver formula´rio) e´ que a
fatorac¸a˜o dele inclua apenas um primo e que o expoente deste primo, neste caso, seja 6
• ou seja, n deve ser igual a p6, para algum primo p
• de modo que a soma dos divisores de n deve ser igual a: m = 1 + p+ p2 + p3 + p4 + p5
• da´ı, para que m seja mı´nimo, p tera´ que ser o mı´nimo poss´ıvel
• logo: p = 2 e m = 1 + 2 + 22 + 23 + 24 + 25 = 63 �
8. (1,0 ponto) Um valor de x que resolve a congrueˆncia linear 7x− 11 ≡ 13 (mod 19) e´ dado por:
Resposta: 74
Justificativa: (Resoluc¸a˜o de congrueˆncias lineares)
• primeiro, note que:
7x− 11 ≡ 13 (mod 19) ⇔ 7x ≡ 24 (mod 19) ⇔ 7x ≡ 5 (mod 19)
• para resolver esta congrueˆncia, precisamos da inversa de 7 em Z19, a qual pode ser obtida por uma aplicac¸a˜o simples do algoritmo de
Euclides Estendido (que e´ dado no formula´rio):
a b ba/bc d x y
19 7 2 1 3 −8
7 5 1 1 −2 3
5 2 2 1 1 −2
2 1 2 1 0 1
1 0 - 1 1 0
• de modo que: 7−1 ≡ −8 ≡ 11 (mod 19)
• enta˜o, multiplicando ambos os lados de 7x ≡ 5 (mod 19) por 11, obtemos:
11.7.x ≡ 11.5 (mod 19) ou seja: x ≡ 55 ≡ 74 (mod 19) �
9. (1,0 ponto) Seja a operac¸a˜o y = x7 mod n, aonde n = p.q e´ dado pelo produto de 2 nu´meros primos.
(a) Com base no que foi visto em aula sobre o RSA, descreva uma forma eficiente (melhor do que testar todas as possibilidades) de se
obter x a partir de um valor dado y (ou seja, explique como obter de maneira eficiente a “raiz se´tima modular” de um valor y dado).
Resposta: esta operac¸a˜o e´ equivalente a uma cifragem do RSA, com expoente pu´blico e = 7. Enta˜o, para obter x novamente
a partir do y dado, basta fazer yd mod n, aonde d = 7−1 mod φ(n), para φ(n) = (p − 1).(q − 1). Isto vai funcionar porque
7.d ≡ 1 (mod φ(n)) ⇒ 7.d = k.φ(n) + 1, de modo que, pelo Teorema de Euler, teremos yd ≡ x7.d ≡ (xφ(n))k.x1 ≡ x (mod n) (com o
aux´ılio do Teorema Chineˆs do Resto, pode-se mostrar que isto funciona mesmo quando mdc(x, n) 6= 1).
(b) Utilizeo procedimento descrito no item anterior para obter o valor de x que satisfaz: x7 ≡ 4 (mod 33)
Resposta:
• φ(33) = φ(3× 11) = (3− 1)× (11− 1) = 20
• 7× d ≡ 1 (mod 20) ⇒ d = 3 (por simples inspec¸a˜o)
• desta forma, temos que: x = 43 mod 33 = 64 mod 33 = 31 �
2
10. (1,0 ponto) Mostre que se a e b sa˜o congruentes mo´dulo 7, enta˜o (10a+ 13) e (−4b+ 20) tambe´m sa˜o congruentes mo´dulo 7.
Resposta: (Conceito de Congrueˆncia)
• primeiro, note que:
(10a+ 13)− (−4b+ 20) = 10a+ 4b+ 13− 20 = 10a+ 4b− 7
• enta˜o, uma vez que a ≡ b (mod 7), temos que: a = b+ k.7
• substituindo isto na equac¸a˜o anterior, obtemos:
(10a+ 13)− (−4b+ 20) = 10(b+ k7) + 4b− 7 = 14b+ 70k − 7 = 7(2b+ 10k − 1)
• isto nos permite dizer que existe l tal que (10a+ 13) = (−4b+ 20) + 7l
• o que equivale a dizer que (10a+ 13) ≡ (−4b+ 20) (mod 7) �
Formula´rio (definic¸o˜es e fo´rmulas possivelmente u´teis):
• Relac¸a˜o R sobre um conjunto A e´ reflexiva sse: ∀a ∈ A, (a, a) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ antissime´trica sse: sea 6= b, ∀a, b ∈ A, (a, b) ∈ R→ (b, a) /∈ R
• Relac¸a˜o R sobre um conjunto A e´ transitiva sse: ∀a, b, c ∈ A, (a, b) ∈ R ∧ (b, c) ∈ R→ (a, c) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ uma relac¸a˜o de ordenamento sse R e´ reflexiva, antissime´trica e transitiva
• Dado um poset (A,≤), um elemento a ∈ A e´ chamado de um menor elemento de A se a ≤ x, ∀x ∈ A.
• Dado um poset (A,≤), um elemento b ∈ A e´ um elemento minimal de A se ¬∃x ∈ A tal que x < b
• Dado um poset (A,≤) e um subconjunto B ⊆ A, um elemento x ∈ A e´ uma cota superior (“upper bound”) de B, se ∀b ∈ B, b ≤ x e um
elemento y ∈ A e´ uma cota inferior (“lower bound”) de B, se ∀b ∈ B, y ≤ b
• Dado um poset (A,≤) e dois elementos x, y ∈ A, o supremo de {x, y}, denotado por x ∨ y = sup(x, y), se houver, e´ o menor elemento das
cotas superiores e o ı´nfimo de {x, y}, denotado por x ∧ y = inf(x, y), se houver, e´ o maior elemento das cotas inferiores
• Dado um reticulado (L,≤), vale: “a ≤ a ∨ b e b ≤ a ∨ b” e tambe´m: “se a ≤ c e b ≤ c, enta˜o a ∨ b ≤ c”
• Seja (L,≤) um reticulado limitado com maior elemento I e menor elemento O, e seja a ∈ L. Um elemento a′ ∈ L e´ chamado de complemento
de a se a ∨ a′ = I e a ∧ a′ = O.
• Sejam 2 elementos de uma A´lgebra Booleana Bn: x = a1a2 . . . an e y = b1b2 . . . bn. Enta˜o:
x ≤ y ⇔ ak ≤ bk para k = 1, 2, . . . , n
x ∧ y = c1c2 . . . cn , onde ck = min{ak, bk} x ∨ y = d1d2 . . . dn , onde dk = max{ak, bk}
x′ = z1z2 . . . zn , onde: zk = 1 se xk = 0 e zk = 0 se xk = 1
• Algumas propriedades ba´sicas de uma A´lgebra Booleana (L,≤) (x, y e z sa˜o elementos arbitra´rios de L):
x ∨ (x ∧ y) = x e x ∧ (x ∨ y) = x x ∨ y = y ∨ x e x ∧ y = y ∧ x
x ∨ (y ∨ z) = (x ∨ y) ∨ z x ∧ (y ∧ z) = (x ∧ y) ∧ z
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
x ∨ x′ = I e x ∧ x′ = O I’ = O e O’ = I
(x ∧ y)′ = (x′ ∨ y′) (x ∨ y)′ = (x′ ∧ y′)
• Notac¸a˜o: G1 ' G2 significa que “G1 e´ isomo´rfico a G2”
• Teoria de Nu´meros: (a, b ∈ Z), (n ∈ Z, n > 1)
a|b⇔ b = a.k para k ∈ Z e a ≡ b (mod n)⇔ n|(a− b)
Teor. Fund. da Aritm.: Todo inteiro composto n pode ser escrito de exatamente uma maneira como um produto da forma n = pe11 p
e2
2 · · · perr
Dado um nro em sua fatorac¸a˜o em primos n = pe11 p
e2
2 . . . p
er
r , o nro de divisores positivos de n e´ dado por: (1 + e1)× (1 + e2)× . . .× (1 + er)
a = ba/nc × n+ (a mod n) [(a mod n)× (b mod n)] modn = (a× b) mod n
Teorema de Euler: se mdc(a, n) = 1, enta˜o: aφ(n) ≡ 1(mod n)
Func¸a˜o Totient de Euler: φ(n) = n.
∏
p|n
(
1− 1
p
)
em particular: φ(p.q) = (p− 1).(q − 1)
Se d = mdc(a, b), enta˜o: ∃ inteiros x e y tais que: d = ax+ by
Euclides-estendido(a, b):
1. if b == 0 then return(a, 1, 0)
2. (d′, x′, y′) = Euclides-estendido(b , amod b)
3. (d, x, y) = (d′, y′, x′ − ba/bc.y′)
4. return (d, x, y)
RSA: cifragem: y = xemodn, decifragem: x = ydmodn onde: n = p.q, p e q sa˜o primos, e = d−1modφ(n)
3