-
8/6/2019 [InfoIasi][FII][FAI] Model examen final + solutii (iunie 2011 - A)
1/7
1. Utilizand Teorema Chineza a Resturilor, sa se rezolve sistemul de ecuatii:x 2 mod 3x 3 mod 4x 4 mod 7
(25p)
Solutie:
Numerele 3, 4, 7 sunt coprime doua cate doua, deci se poate aplicaTeorema Chineza a Resturilor.
(I) Se calculeaza m = 3 4 7 = 84, c1 =m3 = 28, c2 =
m4 = 21,
c3
= m7
= 12;
(II) Se rezolva ecuatiile
28x 2 mod 3 x 2 mod 3 x1 = 2;
21x 3 mod 4 x 3 mod 4 x2 = 3;
12x 4 mod 7 5x 4 mod 7 x3 = 5;
(III) Solutia sistemului se obtine astfel:x0 = (c1x1 + c2x2 + c3x3) mod m
= (28 2 + 21 3 + 12 5) mod 84= 179 mod 84= 11
1
-
8/6/2019 [InfoIasi][FII][FAI] Model examen final + solutii (iunie 2011 - A)
2/7
2. Codificati sirul aababcabcdabcde folosind varianta clasica a algoritmului
Huffman. (25p)Solutie:
Sursa de informatii atasata sirului este:
A a b c d e 5 4 3 2 1
Aplicand algoritmul Huffman obtinem:
Astfel, codificarea finala va fi:
111110111001111001001111001001000
2
-
8/6/2019 [InfoIasi][FII][FAI] Model examen final + solutii (iunie 2011 - A)
3/7
3. Definiti ordinul unui element ntr-un grup finit si demonstrati urmatoarele
proprietati ale acestuia:Fie G un grup finit si a G.
(a) Daca ak = e atunci ordG(a) | k, pentru orice numar ntreg k.Justificati faptul ca ordG(a) | |G|;
(b) Pentru orice numar ntreg k, are loc proprietatea
ordG(ak) =
ordG(a)
(ordG(a), k).
(25p)
Solutie:
ordG(a) = | < a >G | = min({n N|an = e})
(a) Conform Teoremei Impartirii cu Rest, avem k = q ordG(a) + r,unde 0 r < ordG(a). Vom obtine
e = aqordG(a)+r
= (aordG(a))q
ar
= ar
Rezulta ca r = 0 (altfel, s-ar contrazice minimalitatea lui ordG(a)) si,
n final, ca ordG
(a) | k.Relatia ordG(a) | |G| rezulta din Teorema lui Lagrange (ordinul sub-grupului indus de a divide ordinul grupului).
(b) Notam m = ordG(a)(ordG(a),k) . Trebuie sa demonstram ca m este cel mai
mic numar natural nenul cu proprietatea (ak)m
= e.
- (ak)m
= (ak)ordG(a)
(ordG(a),k) = (aordG(a))k
(ordG(a),k) = e (am folosit faptulca aordG(a) = e);
- Presupunem, prin reducere la absurd, ca exista 0 < n < m astfelncat (ak)n = e. Obtinem akn = e, ceea ce implica, conform
punctului (a), ca ordG(a) | kn, sau, echivalent, m | k(ordG(a),k)n (ammpartit cu (ordG(a), k)). Deoarece m si
k(ordG(a),k)
sunt coprime,
rezulta ca m | n, ceea ce constituie o contradict ie (deoarece amconsiderat 0 < n < m). Astfel rezulta si minimalitatea lui m.
3
-
8/6/2019 [InfoIasi][FII][FAI] Model examen final + solutii (iunie 2011 - A)
4/7
4. Determinati semantica programului S, sub interpretarea uzuala pe N:
(S) z := 0; while (x = 0) do (z := z + y; x := x 1)
(25p)
Solutie:
Vom nota
S1 = z := 0S2 = while (x = 0) do S3S3 = z := z + y; x := x 1
Fie o asignare (stare) arbitrara. Daca = atunci I(S)() = .Altfel
I(S)() = I(S1; S2)()= I(S2)(I(S1)())= I(S2)(I(z := 0)())= I(S2)([z/I0(0)])= I(S2)([z/0])
Vom evalua mai departe I(S2)(), pentru o asignare (stare) arbitrara :
I(S2)() = I(while (x = 0) do S3)(
)
=
, daca I((x = 0))() = 0I(while (x = 0) do S3)(I(S3)(
)), daca I((x = 0))() = 1
= (F)(), unde
F(f)() =
, daca (x) = 0,f(I(z := z + y; x := x 1)(
)), daca (x) = 0
Cel mai mic punct fix al functiei F va fi determinat folosind constructiadin Teorema de Punct Fix:
(F) = sup({Fi() fi
|i N}).
Mai exact, vom avea f0() = si fi+1() = F(fi)(
), pentru oriceasignare (stare) .
4
-
8/6/2019 [InfoIasi][FII][FAI] Model examen final + solutii (iunie 2011 - A)
5/7
Vom determina mai ntai cateva elemente ale acestui lant. Pentru a
usura notatia, vom introduce un sir de asignari definit recursiv dupacum urmeaza:
modif(0) = ,
modif(i+1) =
modif(i)[z/(
modif(i)(z) +
modif(i)(y))][x/(
modif(i)(x) 1)], i 0.
Vom nota modif(1) si prin
modif.
Se poate demonstra usor prin inductie ca au loc relatiile:
modif(i)(x) = (x) i,
modif(i)(y) = (y),
modif(i)(z) =
(z) + i
(y),
pentru 1 i (x).
Vom obtinef1() = F(f0)()
=
, daca (x) = 0,, daca (x) = 0,
f2() = F(f1)()
= , daca (x) = 0,
f1(
modif), daca
(x) = 0,
=
, daca (x) = 0,modif, daca
modif(x) = 0,, altfel
=
modif(0), daca (x) = 0,
modif(1), daca (x) = 1,
, altfel
5
-
8/6/2019 [InfoIasi][FII][FAI] Model examen final + solutii (iunie 2011 - A)
6/7
f3() = F(f2)(
)
= , daca (x) = 0,
f2(modif), daca (x) = 0,
=
, daca (x) = 0,modif, daca
modif(x) = 0,(modif)modif, daca
modif(x) = 1,, altfel
=
modif(0), daca (x) = 0,
modif(1), daca (x) = 1,
modif(2), daca (x) = 2,
, altfel
Vom demonstra prin inductie ca, oricare ar fi i 0, are loc relatia
fi() =
modif(j), daca
(x) = j, 0 j i 1,, altfel
- pasul de baza - simpla verificare;
- pasul inductiv - fie i 0 arbitrar - presupunem ca fi are formapropusa. Pentru a demonstra ca si fi+1 are forma corespunzatoarevom folosi relatia de recurenta:
fi+1() = F(fi)()
=
, daca (x) = 0,fi(
modif), daca (x) = 0,
=
, daca (x) = 0,(modif)modif(j), daca
modif(x) = j, 0 j i 1,, altfel
=
, daca (x) = 0,modif(j+1), daca
(x) = j + 1, 0 j i 1,, altfel
=
modif(j), daca
(x) = j, 0 j (i + 1) 1,, altfel
q.e.d.
6
-
8/6/2019 [InfoIasi][FII][FAI] Model examen final + solutii (iunie 2011 - A)
7/7
Fie (x) = n. Vom obtine:
I(S)() = I(S2)(), unde = [z/0]
= (F)()= (sup({fi|i N}))(
)= sup({fi(
)|i N})= modif(n),
ceea ce va conduce n final la I(S)() = [x/0][z/(x) (y)], pentruorice asignare (stare) .
7