P2_12.2_Gabarito

Prévia do material em texto

UFSC - CTC - INE5403 - Fundamentos de Matema´tica Discreta para a Computac¸a˜o
Semestre 12.2 - Data: 12/nov/2012 - Prof. Daniel S. Freitas - Turma A - Segunda Prova
1. (2,0 pontos) Seja o conjunto A = {1, 2, 3} e considere as relac¸o˜es R e S sobre A apresentadas abaixo na sua forma matricial:
MR =
 1 1 00 1 0
1 0 1
 MS =
 1 1 10 1 1
0 0 0

(a) Obtenha as matrizes das seguintes relac¸o˜es: R ∩ S e R ◦ S.
MR∩S =
 1 1 00 1 0
0 0 0
 MR◦S = MS �MR =
 1 1 11 1 1
0 0 0

(b) E´ poss´ıvel obter o conjunto A/R de todas as classes de equivaleˆncia de R ◦ S? Se a sua resposta for positiva, obtenha A/R; se for
negativa, justifique-a.
Resposta: Na˜o e´ poss´ıvel, pois R ◦ S na˜o e´ de equivaleˆncia, ja´ que na˜o e´ reflexiva.
2. (1,0 ponto) Sejam R e S relac¸o˜es sobre um conjunto A, o qual conte´m, pelo menos, treˆs elementos. Analise as seguintes afirmativas:
I. Se R e S sa˜o sime´tricas, enta˜o R ∩ S e´ sime´trica.
II. Se R e S sa˜o sime´tricas, enta˜o R ∪ S e´ necessariamente sime´trica.
III. Se R e S sa˜o reflexivas, enta˜o R ∩ S e´ reflexiva.
IV. Se R e S sa˜o reflexivas, enta˜o R ∪ S e´ necessariamente reflexiva.
A ana´lise permite concluir que esta´(esta˜o) CORRETA(AS):
Resposta: todas as afirmativas
3. (1,0 ponto) Quantos inteiros positivos de treˆs algarismos, todos diferentes de zero, teˆm pelo menos dois algarismos iguais?
Resposta: Ha´ 9× 9× 9 = 729 nu´meros de treˆs algarismos na˜o nulos. Destes, 9× 8× 7 = 504 teˆm os treˆs algarismos distintos. Portanto, ha´
729− 504 = 225 nu´meros com pelo menos dois algarismos iguais.
4. (1,0 ponto) O nu´mero de strings de bits de comprimento 10 que conteˆm no ma´ximo treˆs 1’s e´ dado por:
Resposta: C(10, 3) + C(10, 2) + C(10, 1) + C(10, 0) = 120 + 45 + 10 + 1 = 176
5. (1,0 ponto) Quantas strings com 3 d´ıgitos decimais possuem exatamente 2 d´ıgitos que sa˜o 4?
Resposta: C(3, 1)× 9 = 27
6. (1,0 ponto) De quantos modos e´ poss´ıvel comprar 4 picole´s em uma loja que os oferece em 7 sabores distintos?
Resposta: C(7 + 4− 1, 4) = 210
7. (1,0 ponto) Seja o conjunto A = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), 4, 3), (4, 4)} e seja R a
relac¸a˜o bina´ria sobre A definida por (a, b)R(c, d) se e somente se a× b = c× d. Sabendo que R e´ uma relac¸a˜o de equivaleˆncia, obtenha A/R,
ou seja, compute as classes de equivaleˆncia geradas pela relac¸a˜o em A.
Resposta:
• os pares (x, y) equivalentes a (a, b) sa˜o aqueles cujo produto “x.y” e´ igual a “a.b”
• os produtos diferentes sa˜o: 1× 1, 1× 2, 1× 3, 1× 4, 2× 3, 2× 4, 3× 3, 3× 4 e 4× 4
• enta˜o as (9) classes de equivaleˆncia sa˜o:
R((1, 1)) = {(1, 1)}
R((1, 2)) = {(1, 2), (2, 1)}
R((1, 3)) = {(1, 3), (3, 1)}
R((1, 4)) = {(1, 4), (2, 2), (4, 1)}
R((2, 3)) = {(2, 3), (3, 2)}
R((2, 4)) = {(2, 4), (4, 2)}
R((3, 3)) = {(3, 3)}
R((3, 4)) = {(3, 4), (4, 3)}
R((4, 4)) = {(4, 4)}
8. (2,0 pontos) Marque V ou F:
(V) Sejam f(n) e g(n) func¸o˜es cujos domı´nios sa˜o subconjuntos de Z+ e assuma que f(n) = 65536×n5 e g(n) = 128×n5. Enta˜o e´ correto
dizer que f e´ O(g).
Justificativa: ∀n ≥ 1, temos que f(n) = (65536/128)× g(n) = 512× g(n)
(F) O nu´mero de strings de 10 bits que comec¸am e terminam com um 1 e´ 210 − 4.
Justificativa: na verdade, este nu´mero vale 28
(F) E´ preciso selecionar no mı´nimo 7 nu´meros diferentes do conjunto {1, 3, 5, 7, 9, 11, 13, 15} para garantir que pelo menos um par destes
nu´meros selecionados fornec¸a uma soma igual a 16.
Justificativa: o Princ´ıpio do Pombal mostra que basta selecionar 5 nu´meros diferentes deste conjunto para ter esta garantia
(V) Se R e´ uma relac¸a˜o de equivaleˆncia, enta˜o R−1 e´ uma relac¸a˜o reflexiva e sime´trica.
Justificativa: R−1 consiste nos mesmos pares (a, b) presentes em R, mas com as posic¸o˜es trocadas, ou seja, se (a, b) ∈ R, enta˜o
(b, a) ∈ R−1. Por outro lado, se R e´ de equivaleˆncia, enta˜o R e´ reflexiva e sime´trica. Se R e´ reflexiva, enta˜o ∀a ∈ A, temos que
(a, a) ∈ R. Trocar as posic¸o˜es, neste caso, na˜o altera o par, de modo que (a, a) ∈ R−1 e R−1 tambe´m e´ reflexiva. Ale´m disto,
se R e´ sime´trica, e´ porque para todo par (a, b), temos que (b, a) ∈ R. Ora, esta mesma condic¸a˜o vale no sentido inverso, ou seja,
(b, a) ∈ R⇒ (a, b) ∈ R, pois ela tem que valer ∀(a, b), o que mostra que a inversa tambe´m e´ sime´trica.
(V) Para computar o fecho transitivo de uma relac¸a˜o R na˜o transitiva, nunca e´ necessa´rio considerar poteˆncias de R maiores do que n.
Justificativa: conforme lema provado em aula, caminhos de tamanhos maiores do que a quantidade total (n) de elementos do conjunto
sobre o qual a relac¸a˜o R foi definida envolvem repetic¸a˜o de no´s e, portanto, aparecem tambe´m em alguma poteˆncia de R menor ou
igual a n.
(V) Se uma relac¸a˜o R sobre um conjunto A e´ transitiva, enta˜o sempre devera´ ocorrer R3 ⊆ R
Justificativa: ver teorema provado em aula (nos slides)
(F) Dada uma relac¸a˜o R sobre um conjunto A, temos que R∞ e´ transitiva se, e somente se, R e´ transitiva.
Justificativa: independente de R, temos que R∞ sempre e´ transitiva
(F) Na˜o e´ correto afirmar que n5 e´ de ordem mais baixa do que n6.
Justificativa: n5 e´ O(n6), pois n5 ≤ n6, ∀n ≥ 1
Por outro lado: afirmar que ∃c, k tais que n6 ≤ c.n5, ∀n ≥ k permite concluir que n ≤ c, o que e´ uma contradic¸a˜o, pois n tem que
poder assumir qualquer valor.
Conclusa˜o: n5 e´ O(n6, mas n6 na˜o e´ O(n5), de modo que n5 e´, de fato, de ordem mais baixa do que n6.
1
Formula´rio (definic¸o˜es e fo´rmulas possivelmente u´teis):
• Uma relac¸a˜o bina´ria de um conjunto na˜o vazio A em um B e´ um subconjunto de A×B
• 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´ sime´trica sse: ∀a, b ∈ A, (a, b) ∈ R→ (b, a) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ assime´trica sse: ∀a, b ∈ A, (a, b) ∈ R→ (b, 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 equivaleˆncia sse R e´ reflexiva, sime´trica e transitiva
• Multiplicac¸a˜o de matrizes booleanas (operac¸a˜o ”�”): multiplicac¸a˜o matricial tradicional, mas com a operac¸a˜o ”×”substitu´ıda por ”∧” e a
operac¸a˜o ”+”substitu´ıda por ”∨”
• Caminhos: para uma relac¸a˜o R sobre A, temos: MRn = MR �MR � . . .�MR (n fatores)
• Composic¸a˜o de relac¸o˜es: MS◦R = MR �MS
• Algoritmo WARSHALL:
FECHO = MR
for k = 1 to n
for i = 1 to n
for j = 1 to n
FECHO[i,j ] = FECHO[i,j ] ∨ (FECHO[i,k ] ∧ FECHO[k,j ])
• Uma func¸a˜o f : A→ B e´ injetora sse ∀a, b ∈ A, a 6= b→ f(a) 6= f(b)
• Uma func¸a˜o f : A→ B e´ sobrejetora sse ∀b ∈ B, ∃a ∈ A tal que f(a) = b
• Uma func¸a˜o f : A→ B e´ bijetora sse for injetora e sobrejetora
• f e´ O(g) se existem constantes c e k tais que: |f(n)| ≤ c · |g(n)|, ∀n ≥ k
• f e´ de ordem mais baixa do que g se f e´ O(g) mas g na˜o e´ O(f)
• Princ´ıpio da Multiplicac¸a˜o: Suponha que duas tarefas devem ser executadas em sequeˆncia. Se ha´ n1 modos de executar a tarefa T1 e se, para
um destes modos, T2 pode ser realizada de n2 maneiras, enta˜o a sequeˆncia T1T2 pode ser realizada de n1 × n2 formas diferentes.
• Se 1 ≤ r ≤ n, enta˜o o nu´mero de arranjos de n objetos tomados r a r e´: P (n, r) = n!
(n−r)!
• Seja A um conjunto com |A| = n e seja 1 ≤ r ≤ n. O nu´mero de sequeˆncias de comprimento r que podem ser formadas com elementos de A,
permitindo repetic¸o˜es, e´ nr
• Seja A um conjunto com |A| = n e 0 ≤ r ≤ n. O nu´mero de combinac¸o˜es dos elementos de A tomados r a r e´ dado por: C(n, r) = n!
r!(n−r)!
• Existem C(n+ r − 1, r) = C(n+ r − 1, n− 1) combinac¸o˜es r a r de um conjunto com n elementos quando a repetic¸a˜o e´ permitida.
• O nro de permutac¸o˜es distintas que podem ser formadas com uma colec¸a˜o de n objetos, aonde o 1o objeto aparece k1 vezes, o 2o objeto
aparece k2 vezes, etc..., e´ dado por:
n!
k1!k2!···kt! , aonde k1 + k2 + · ··+ kt = n
• Princ´ıpio do pombal: Se n pombos sa˜o acomodados em m cub´ıculos de um pombal, enta˜o um dos cub´ıculos deve conter pelo menos
b(n− 1)/mc+ 1 pombos.
• Teorema Binomial: Sejam x e y varia´veis e n um inteiro na˜o-negativo. Enta˜o: (x+ y)n = ∑nj=0 (nj)xn−jyj
• Identidade de Pascal: (n+1
k
)
=
( n
k−1
)
+
(n
k
)
• Sequeˆncia dos Nu´meros de Catala˜o: C0 = 1, C1 = 1, Cn =
∑n−1
k=0 CkCn−k−1 (para n ≥ 2)
• 1 + a+ a2 + a3 + · · ·+ an−1 = an−1
a−1 1 + 2 + 3 + · · ·+ n =
n(n+1)
2
• Suponha que a equac¸a˜o caracter´ıstica rk − c1.rk−1 − · · · − ck = 0 tem k ra´ızes distintas r1, r2, . . . , rk. Enta˜o uma sequeˆncia {an} e´ uma
soluc¸a˜o da relac¸a˜o de recorreˆncia: an = c1.an−1 + c2.an−2 + · · · + ck.an−k sse an = α1.r1n + α2.r2n + · · · + αk.rkn, aonde α1, α2, . . . , αk
sa˜o constantes.
• Recorreˆncias Dividir-e-Conquistar: f(n) = a.f(n/b) + c e´ O(log n), se a = 1 e O(nlogba), se a > 1 (f crescente e n divis´ıvel por b).
• an pode ser expresso como polinoˆmio sse houver um natural k tal que ∀n ≥ 0, ∆k+1an = 0
Neste caso: an = a0
(n
0
)
+ (∆a0)
(n
1
)
+ (∆2a0)
(n
2
)
+ · · ·+ (∆ka0)
(n
k
)
onde: ∆a e´ a sequeˆncia cujo n-e´simo termo e´: ∆an = an+1 − an
• Princ´ıpio da Inclusa˜o-Exclusa˜o: Sejam A1, A2, . . . , An conjuntos finitos. Enta˜o:
|A1 ∪A2 ∪ · · · ∪An| =
∑
1≤i≤n |Ai| −
∑
1≤i<j≤n |Ai ∩Aj |+
∑
1≤i<j<k≤n |Ai ∩Aj ∩Ak| − · · · + (−1)n+1|A1 ∩A2 ∩ · · · ∩An|
2