Clasele 9-10 lecția 24 - 25 mar 2015

Algoritmul lui Euclid extins

Întrucât nu-mi place să-mi las bâlbele necorectate, :-) iată o explicație mai clară pentru Algoritmul lui Euclid extins.

Știm să calculăm cel mai mare divizor comun cu algoritmul lui Euclid (simplu). Fie

$d=\gcd(a,b)$

Numărul d mai are o proprietate interesantă: el este cel mai mic întreg pozitiv care poate fi scris ca

$d=ax+by$, unde x și y sunt numere întregi.

Această formulă se numește identitatea lui Bézout. Puteți găsi o demonstrație aici.

Algoritmul lui Euclid extins calculează nu doar d, ci și x și y. Fie a = 378, b = 60 și să considerăm calculele făcute de algoritmul lui Euclid simplu. El înlocuiește, repetitiv, perechea $(a,b)$ cu perechea $(b,a\,{\bmod {\,}}b)$:

a	b	d
378	60
60	18
18	6
6	0	6

De aici, valoarea lui d se propagă pur și simplu în sus, datorită egalității $\gcd(a,b)=\gcd(b,a\,{\bmod {\,}}b)$:

a	b	d
378	60	6
60	18	6
18	6	6
6	0	6

Acum vrem să calculăm, pe parcurs, și valorile x și y. Pe ultima linie ele sunt banal de calculat, căci b este 0.

a	b	d	x	y
378	60
60	18
18	6
6	0	6	1	0

Cum propagăm aceste valori în sus? Mai exact, dacă am descoperit că

$bx_{0}+(a\,{\bmod {\,}}b)y_{0}=d$

cum aflăm x și y astfel încât

$ax+by=d$?

Fie $a=qb+r$. Atunci avem sistemul de ecuații în x și y:

${\begin{cases}(qb+r)x+by&=d\\bx_{0}+ry_{0}&=d\end{cases}}$

Le reformulăm în funcție de b și r:

${\begin{cases}(qx+y)b+xr&=d\\x_{0}b+y_{0}r&=d\end{cases}}$

și obținem

${\begin{cases}x&=y_{0}\\y&=x_{0}-qy_{0}\end{cases}}$

Cu această formulă putem completa tabelul:

a	b	d	x	y
378	60	6	-3	19
60	18	6	1	-3
18	6	6	0	1
6	0	6	1	0

Anexez media:extendedEuclid.cpp pentru o implementare recursivă și una iterativă.

Aplicație

Algoritmul lui Euclid extins poate fi folosit pentru a afla inversele elementelor în $\mathbf {Z} _{n}^{*}$. Pentru a calcula inversul lui a, aplicăm algoritmul lui Euclid extins pentru a și n. Prin definiție $\gcd(a,n)=1$, căci altfel inversul lui a nu este definit. Calculăm x și y cu algoritmul lui Euclid extins a. î. $ax+ny=1$. Rezultă în mod trivial că $ax\equiv 1{\pmod {n}}$, deci x este inversul lui a.

Skip lists

Skip lists sunt o structură utilă la modul general. Ea ne oferă complexitate $O(\log n)$ sau mai bun pentru majoritatea operațiilor:

• inserare
• ștergere
• căutare
• aflarea elementului anterior / următor
• aflarea elementului minim / maxim
• numărarea elementelor mai mici / mai mari decât un element
• aflarea celui de-al k-lea element ca valoare

Ca și arborii echilibrați, skip lists sunt un fel de „briceag elvețian” al structurilor de date. Ele se codează mai ușor și folosesc mai puțină memorie decât arborii echilibrați. Sigur, nu trebuie să le folosiți fără măsură, ignorând soluții mai deștepte.

Vom urma notele de la clasele 11-12.

Temă

• Tema 20 juniori