Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

7 - Calcul Formel > Cours LB partie 2 > Flashcards

Cours LB partie 2 Flashcards

1
Q

Définition fonctionnelle des codes de Reede-Solomon

A

F ∈ {F}q[X]<k→ (F(α1), …, F(αn)) avec αi != αj, n ≥ k et αi ∈ {F}q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Complexité de l’encodage sans erreur naïf

A

O(k) opérations arithmétiques car n évaluations :
- 2k multiplications et k additions avec l’algorithme naïf
- k multiplications et k additions avec l’algorithmes de Horner

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Calcul de F(α) utilisé dans l’algorithme dichotomique

A

F(α) = F mod (X - α)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Algorithme d’évaluation multipoints rapide (entrée, sortie, algorithme)

A
  • Entrée : P ∈ {K}[X]<k, (α1, …, αn) ∈ {K} avec n ≥ k)
  • Sortie : (P(αi))i = 1..n
  • Algorithme EMR :
    • Si deg(P) = 0 :
      • Renvoyer(p1, …, pn)
    • P0 ← P mod Πi = 1 → n//2 (X - αi)
    • P1 ← P mod Πi = n//2+1 → n (X - αi)
    • Renvoyer CONCAT(EMR(P0, (αi)i = 1..n//2), EMR(P1, (αi)i = n//2..n))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Complexité du produit polynomial naïf

A

O(n2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Complexité du produit polynomial par Karatsuba

A

O(nlog23)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Complexité du produit polynomial par FFT

A

S’il y a une racine de l’unité dans le corps, O(nlogn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Complexité du produit polynomial retenu pour tous les corps (sans condition)

A

O(nlog2n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Définition de la super-linéarité

A

Pour M : M(n) ≥ k × M(n/k)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Complexité de la division polynomiale naÏve

A

Pour A = B×Q + R, O(deg(B) × deg(Q))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Complexité de la division polynomiale par dichotomie

A

Pour A = B×Q + R et n = deg(B), O(M(n)logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Complexité de la division polynomiale par itération de Newton

A

Pour A = B×Q + R et n = deg(B), O(M(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Cas dans lequel la division polynomiale naïve est plus efficace que la division par itération de Newton

A

Pour A = B×Q + R, si deg(A) = deg(B) + 1, alors deg(Q) = 1 :
- O(n) avec l’algorithme naïf
- O(M(n)) avec l’itération de Newton

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Complexité du calcul naïf de Πi = 1→n (X - αi)

A

Avec une simple boucle sur n, O(nM(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Complexité du calcul non-naïf de Πi = 1 → n (X - αi)

A

Avec la dichotomie Πi = 1 → n (X - αi) = Πi = 1 → n//2 (X - αi)Πi = n//2+1 → n (X - αi), O(M(n)logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Complexité de l’algorithme EMR (Évaluation Multipoints Rapide) sans pré-caclul

A

O(M(n)log2n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Complexité de l’algorithme EMR (Évaluation Multipoints Rapide) avec pré-caclul

A

O(M(n)logn) + O(M(n)logn)
(pré-calcul des Π + algorithme même)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Formule de complexité de l’algorithme EMR avant calcul

A

C(n) = 2M(n/2)log(n/2) + 2M(n/2) + 2C(n/2)
(pré-calcul + divisions pour le modulo + récursion)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Algorithme de calcul de l’arbre des sous-produits (entrée, sortie, algorithme)

A
  • Entrée : α1, …, αn
  • Sortie : arborescence des sous-produits
  • Algorithme :
    • Utiliser l’algorithme dichotomique pour calculer Πi=1→k (X - αi) et sauvegarder chaque sous-produit au fur et à mesure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Complexité du calcul de l’arbre des sous-produits

A

O(M(n)logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Quand est-ce qu’il est possible d’effectuer un décodage sans erreur ?

A

Lorsqu’il y a au moins k évaluations sans erreur, où deg(P) < k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Distance de code en fonction du degré et du nombre d’évaluations

A

Pour deg(P) < k et n évaluations, on sait qu’il faut au plus n - k effacements, donc d - 1 = n - k ⇔ d = n - k + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Définition fonctionnelle de l’interpolation de Lagrange

A

(αi, yi)i=1..k → P ∈ {P}q[X]<k tel que P(αi) = yi pour i=1..k avec deg(P) < k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Formule de Lagrange

A

P(X) = Σi=1..k yiLi(X) avec Li(X) un polynôme de Lagrange

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Formule des polynômes de Lagrange

A

Li = Ai(X)/Ai(αi) avec Ai(X) = Πi!=j (X - αj) = A(x)/(X - αi)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Forme des différents vecteurs utilisés dans le calcul de l’interpolation de Lagrange, pour X = (αi)i=1..k

A
  • Ai(X) → (0, 0, …, !=0, …, 0, 0)
  • Li(X) → (0, 0, …, 1, …, 0, 0)
  • yiLi(X) → (0, 0, …, yi, …, 0, 0)
  • P(X) = (y1, y2, …, yi, …, yn-1, yn)
27
Q

Étapes de calcul de l’interpolation de Lagrange (version naïve)

A
  • Calculer Ai(X) = Πi!=j (X - αj) = A(X)/(X - αi)
  • Calculer Ai(αi)
  • Calculer Li = Ai(X)/Ai(αi)
  • Calculer yiLi
  • Faire la somme des résultats obtenus
28
Q

Complexité du calcul des polynômes de Lagrange (version naïve)

A
  • O(k) pour Ai(X) car division avec deg(B) = 1 et deg(Q) = k
  • O(k) pour Ai(αi)
  • Total : O(k2)
29
Q

Complexité du calcul naïf de l’interpolation de Lagrange

A
  • Calcul de chaque Li(X) en O(M(k)logk) donc en tout O(kM(k)logk)
  • Calcul de chaque yiLi(X) en O(k) donc O(k2) en tout
  • Calcul de la somme finale de P en O(k2)
  • Total : O(kM(k)logk)
30
Q

Astuce utilisée pour être moins naïf dans le calcul des polynômes de Lagrange

A
  • (uv)’ = u’v + uv’
  • (uvw)’ = (uv)’w + (uv)w’ = u’vw + uv’w + uvw’
  • (Πi=1→k fi)’ = Σi=1→k (Πj!=i fj)×fi’
31
Q

Étapes de calcul des polynômes de Lagrange (version non-naïve)

A
  • Calculer A(X) = Πi=1→k (X - αi)
  • Dériver A(X) : A’(X) = Σi=1→k Πj!=i (X - αj) = Σi=1→k Ai(X)
  • Calculer A’(αl) = Σi=1→k Πj!=i (αl - αj) et comme tous les produits s’annulent sauf 1, A’(αl) = Πj!=l (αl - αj) et on a la constante qui est en diviseur du polynôme de Lagrange Lk(X)
32
Q

Reformulation de la somme finale de l’interpolation de Lagrange

A

P(x)
= Σi=1..k yiLi(X)
= Σi=1..k yi(Ai(X) / Ai(αi))
= Σi=1..k yi((A(X)/(X - αi)) / Ai(αi))
= Σi=1..k yi(A(X) / (Ai(αi) × (X - αi)))
= Σi=1..k (yi / Ai(αi)) × (A(X) /(X - αi))
= Σi=1..k bi × (A(X) / (X - αi)) avec bi = yi/ Ai(αi)

33
Q

Complexité détaillée de la somme naïve finale de l’interpolation de Lagrange

A
  • Divisions naïves (car deg(Q) = 1) en O(n)
  • Multiplications par bi en O(n)
  • Sommes en O(n)
  • Total O(n2) car n fois les opérations précédentes
34
Q

Idée sur laquelle est basée l’algorithme dichotomique pour la somme finale de l’interpolation de Lagrange

A

Soient
- A0 Πj=1..n//2 (X - αj)
- A1 Πj=n//2+1..n (X - αj)
alors
Σi=1..n bi × (A(x) / (X - αi))
= (Σi=1..n//2 bi × (A0(x) / (X - αi))) × A1(x)
+
(Σi=n//2+1..n bi × (A1(x) / (X - αi))) × A0(x)

35
Q

Algorithme de calcul de la somme finale de l’interpolation de Lagrange (entrée, sortie, algorithme)

A
  • Entrée : n, (αi)i=1..n, (bi)i=1..n
  • Sortie : Σi=1..k bi × (A(X) / (X - αi))
  • Algorithme :
    • Si n = 1, renvoyer b1
    • S0 = Algorithme(n//2, (αi)i=1..n//2, (bi)i=1..n//2)
    • S1 = Algorithme(n-n//2, (αi)i=n//2+1..n, (bi)i=n//2+1..n)
    • S = S0A1 + S1A0
    • Renvoyer S
36
Q

Formule de complexité de l’algorithme de calcul de la somme finale de l’interpolation de Lagrange

A

M(n)logn + S(n) ≤ M(n)logn + 2S(n/2) + 2M(n/2)
(ASP + 2 appels récursifs + 2 produits)

37
Q

Complexité de l’algorithme de calcul de la somme finale de l’interpolation de Lagrange

A

O(M(n)logn)

38
Q

Définition du problème de décodage unique des codes de Reede-Solomon

A

Instance : Message (αi, yi)i=1..n reçu avec au plus e erreur où e = (n - k)//2 = (d - 1)//2 avec d la distance de code
Problème : Retrouver F ∈ {F}q[X]<k satisfaisant F(αi) = yi sauf en eu plus e indices

39
Q

Idée derrière le polynôme locateur d’erreur

A

On sait que dans le décodage unique des code de Reede-Solomon, on a presque toujours (F(αi) = yi) ⇔ (F(αi) -yi = 0), donc si on trouve un polynôme Λ qui est nul en les erreurs, Λ(X) × (F(X) - yi) est toujours nul en X = αi

40
Q

Polynôme locateur d’erreur

A

Λ(x) = Πi tel que F(αi) != yi (X - αi)

41
Q

Équation clé (première écriture)

A

Λ(αi)yi = (ΛF)(αi)

42
Q

Équation clé (première reformulation)

A
  • Inconnues : φ, ψ ∈ {F}q[X] avec deg(φ) ≤ e et deg(ψ) < k + e
  • Équations : φ(αi)yi = ψ(αi) pour i = 1..n
43
Q

Solution évidente non-nulle de l’équation clé

A

(Λ, ΛF)

44
Q

Lemme d’“unicité” des solutions de l’équation-clé (énoncé)

A

Soient (φ1, ψ1) et (φ2, ψ2) des solutions non-nulles, alors (ψ1 / φ1) = (ψ2 / φ2)

45
Q

Lemme d’“unicité” des solutions de l’équation-clé (schéma de preuve)

A
  • Montrer que ψ1φ2 et ψ2φ1 sont égaux
  • Montrer que φ1 et φ2 sont non-nuls sinon les deux solutions sont nulles
  • Montrer qu’on a alors ψ1φ2 = ψ2φ1 ⇔ (ψ1 / φ1) = (ψ2 / φ2)
46
Q

Algorithme de décodage de Reese-Solomon (entrée, sortie, algorithme)

A
  • Entrée : (yi)i=1..n, k, n, e, (αi)i=1..n, {F}q
  • Sortie : F ∈ {F}q[X]<k telle que F(αi) = yi en ≥ n - e points, ou “NON”
  • Algorithme :
    • Si l’espace de l’équation-clé est {(0, 0)}, renvoyer NON
    • Si φ divise ψ et deg(ψ / φ) < k, renvoyer (ψ / φ)
    • Renvoyer NON
47
Q

Propriété de correction de l’algorithme de décodage de Reese-Solomon (énoncé)

A

L’algorithme réussit si et seulement le mot reçu était proche d’un mot de code

48
Q

Propriété de correction de l’algorithme de décodage de Reese-Solomon (schéma de preuve)

A

⇐ :
- Montrer que si le mot reçu était proche d’un mot de code, alors il existe une solution (φ, ψ) telle que φ divise ψ et deg(ψ / φ) < k en utilisant le lemme d’unicité avec (Λ, F) et (φ, ψ)

⇒ :
- Définir g tel que φ(αi)yi = ψ(αi) = g(αi)φ(αi)
- Montrer que g(αi) = yi là où φ(αi) est non-nul
- Montrer que φ(αi) est nul sur au plus e points par définition de l’équation-clé

49
Q

Équation clé (reformulation avec Lagrange)

A

φ(αi)yi = ψ(αi)
⇔ φ(αi)L(αi) = ψ(αi)
⇔ (φL - ψ)(αi) = 0
avec L l’interpolant de Lagrange des yi en αi

50
Q

Degré du polynôme (φL - ψ)

A
  • deg(φ) ≤ e
  • deg(L) = n - 1
  • deg(ψ) ≤ k + e - 1
  • deg(φL - ψ) > n
51
Q

Comment peut-on montrer que (φL - ψ) est nul ?

A
  • On ne peut pas utiliser la technique dans laquelle un polynôme de degré n s’annule en n-1 points, parce qu’on sait que deg(φL - ψ) > n
  • Soit G = Πi=1..n (X - αi), alors (φL - ψ)(αi) est nul si et seulement si G divise (φL - ψ)(αi), c’est-à-dire que φL - ψ vaut 0 modulo G
52
Q

Équation clé (dernière reformulation avec G = Πi=1..n (X - αi))

A
  • Inconnues : φ, ψ ∈ {F}q[X] avec deg(φ) ≤ e et deg(ψ) < k + e
  • Équations : φL = ψ mod G
53
Q

Forme des solutions de l’équation clé (denière reformulation)

A

Soient u et v des coefficients de Bezout, c’est-à-dire des coefficients tels que uG + vL = R avec R multiple du PGCD de G et L, alors (V, R) est solution de l’équation-clé (si on fait attention aux degrés)

54
Q

Algorithme d’Euclide pour le PGCD

A

PGCD(A, B) :
- Q1, R2 = DivEucl(R0 = A, R1 = B)
- Q2, R3 = DivEucl(R1 = B, R2)
- Q3, R4 = DivEucl(R2, R3)
- …
- Ql-1, Rl = DivEucl(Rl-2, Rl-1) avec Rl = 0
- Renvoyer Rl-1

55
Q

Correction de l’algorithme d’Euclide (schéma de preuve)

A
  • Preuve de la récurrence :
    • Montrer que PGCD(A, B) = PGCD(B, R) en montrant que A = BQ + R, c’est à dire que (D divise A et D divise B) ⇔ (D divise B et D divise R) ou encore que si les diviseurs communs sont les mêmes, les plus grands d’entre eux sont égaux
    • Pour cela, faire les deux sens de ⇔
  • Preuve de la terminaison :
    • Montrer qu’on finit bien par avoir Rl = 0
    • Pour cela, poser l = deg(A), alors deg(Rl) ≤ deg(Rl-1) - 1 ≤ … ≤ deg(R0) - l, donc l’algorithme se termine en l + 1 = deg(A) + 1 étapes au plus
56
Q

Complexité de l’algorithme d’Euclide

A

Avec la division naïve, chaque divisions coûte O(deg(Ri)deg(Qi)) = O(deg(Ri)(deg(Ri-1) - deg(Ri))), donc en tout Σi=1..l-1 deg(Ri)(deg(Ri-1) - deg(Ri)) ≤ deg(A)deg(B)

57
Q

Cas de base de l’algorithme d’Euclide étendu

A

uiA + viB = Ri :
- Pour i = 0, A = R0 = 1A + 0B → u0 = 1, v0 = 0
- Pour i = 1, B = R1 = 0A + 1B → u1 = 0, v1 = 1

58
Q

Principe de l’agorithme d’Euclide étendu

A

On travaille avec des couples, c’est à dire qu’on exprime (Ri, Ri+1) en fonction de (Ri-1, Ri) :
(Ri….) = (0 1…)(Ri-1)
(Ri+1) = (1 -Qi)(Ri )
= Ti×Ti-1×…×T1(R0, R1)

Donc
(Ri….) = (ui… vi…)(R0)
(Ri+1) = (ui+1 vi+1)(R1)

59
Q

Algorithme d’Euclide étendu

A
  • AEE(A, B) avec deg(A) > deg(B) :
    • i = 1
    • (R0, R1) ← (A, B)
    • (u0 v0) ← (1 0)
      ..(u1 v1) ……(0 1)
    • Tant que Ri != 0 :
      • (Qi, Ri+1) ← DivEucl(Ri-1, Ri)
      • (ui+1, vi+1) ← (1 - Qi)(ui-1 vi-1)
        ………………………………(ui… vi…)
      • i = i + 1
    • Renvoyer Ri-1, ui-1, vi-1
60
Q

Correction de l’algorithme d’Euclide étendu (schéma de preuve)

A
  • Même terminaison que le PGCD
  • Correction :
    • On a déjà montré que Ri-1 = PGCD(A, B)
    • On doit montrer que ui-1A + vi-1B = Rui-1 par récurrence
      • Cas de base pour i = 0 et i = 1
      • Hérédité avec des manipulations de matrices
61
Q

Complexité de l’algorithme d’Euclide étendu (détails de calcul)

A
  • Montrer que ∀ i≥1, deg(vi) = Σj=1..i-1 deg(Qi) = r0 - ri-1 par récurrence
  • Montrer que ∀ i≥2, deg(ui) = Σj=1..i-1 deg(Qi) = r1 - ri-1 par récurrence
  • Additionner le coût des divisions euclidiennes (deg(A)deg(B)) au coût de calcul de ui+1 (deg(A)deg(B))
62
Q

Complexité de l’algorithme optimal d’Euclide étendu (qui n’est pas celui que l’on a vu en cours)

A

O(M(n)logn)

63
Q

Défaut de l’algorithme optimal d’Euclide étendu (qui n’est pas celui que l’on a vu en cours)

A

On ne peut pas sortir toutes les informations car cela dépasserait la complexité, donc on ne peut récupérer que les Qi

7 - Calcul Formel (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions