Capitole speciale de informatica

Curs 1

10 octombrie 2011

1 Despre acest curs

Prezentare: Mircea Marinemail: mmarin@info.uvt.ro

• Cursul va prezenta capitole speciale din calculul simbolic. Veti ınvatadespre algoritmi simbolici care sunt utili ın informatica si stiintele exacte,precum: algoritmi de aritmetica multi-precizie, calcule cu polinoame mul-tivariate (factorizare, rezolvarea sistemelor de ecuatii polinomiale, etc.),integrare simbolica, si ınsumari simbolice.

• Se vor efectua experimente cu implementari concrete ale algoritmilor pre-zentati ın acest curs, folosind sistemul de calcul simbolic Mathematica.

• Evaluare:

– probleme si exercitii indicate la sfarsitul fiecarui curs (50%). Re-zolvarea exercitiilor presupune utilizarea sistemului Mathematica.

– proiecte individuale (50%)

• Pagina web a cursului este

web.info.uvt.ro/~mmarin/lectures/CSI

• cu link-uri la materialele de curs etc.

• Literatura recomandata:

– F. Winkler. Polynomial Algorithms in Computer Algebra. Springer-Verlag 1996.

– J. von zur Gaten and J. Gerhard. Modern Computer Algebra. Cam-bridge University Press 2003.

– J. Grabmeier, E. Kaltofen, V. Weispfenning. Computer Algebra Hand-book. Springer-Verlag 2003.

Pentru mai multe informatii, consultati periodic pagina web a acestui curs

web.info.uvt.ro/~mmarin/lectures/CSI

1

2 Ce este calculul simbolic?

Calculul simbolic (sau calculul algebric) este o metoda de efectuat calcule cuexpresii matematice (de exemplu, formule, ecuatii, polinoame, etc.) cu ajutorulun aparat (de obicei un calculator). Acest mod de calcul este ın contrast cucalculul numeric ın care se opereaza cu aproximari ale cantitatilor numericeluate ın considerare.

Exista o varietate larga de algoritmi utili care provin din calculul simbolicsi sunt folositi ın calcule stiintifice si ingineresti avansate. Exemple tipice sunt:

1. Metodele de rezolvare a sistemelor algebrice, ca de exemplu{4x2 + 16 y4 − 4 y2 − 3 = 0x2 + y2 = 1

solve−−−→

{{x→ ±

√3

2, y → ±

1

2

},

{x→ ±

√3

2, y → ±

1

2

}}.

Observatie: Solutiile calculate sunt exacte si contin radicali. Comparatiacest rezultat cu cel al unei metode de rezolvare numerica:{

4x2 + 16 y4 − 4 y2 − 3 = 0x2 + y2 = 1

numeric solve−−−−−−−−→ {{x→ ±0.866025, y → ±0.5}, {x→ ±0.866025, y → ±0.5}} .

Solutia numerica este o aproximare a solutiei exacte.

2. Integrarea simbolica a expresiilor algebrice:∫x

x2 − adx

compute−−−−−→1

2log(x2 − a)

∫ √5

√3

1

x2 + x− 1dx

compute−−−−−→2(

arctanh(

2 + 1√5

)+ arctanh

(2√

35 + 1√

5

))√

5

3. Rezolvarea sistemelor de ecuatii diferentiale (sau cu derivate partiale)−6

∂q

∂x(x) +

∂2p

∂x2(x)− 6 sin(x) = 0

6∂2q

∂x2(x) + a2

∂p

∂x(x)− 6 cos(x) = 0

p(0) = 0, q(0) = 1, p′(0) = 0, q′(0) = 1

(1)

solve−−−→{{

p(x)→ −12 sin(ax)

a(a2 − 1)− 6 cos(ax)

a2+

12 sin(x)

a2 − 1+

6

a2,

q(x)→ sin(ax)

a− 2 cos(ax)

a2 − 1+

(a2 + 1) cos(x)

a2 − 1

}}for a 6∈ {−1, 0, 1}.

2

4. Reprezentari grafice ale varietatilor algebrice (adica, suprafete si curbedefinite de sisteme de ecuatii polinomiale). Varietatile algebrice pot fispecificate ın 2 feluri:

Implicit: In acest caz, punctele curbei sau suprafetei sunt solutiile unuisistem de ecuatii polinomiale. De exemplu:

(a) f(x, y) = 2x4 − 3x2y+ y4 − 2y3 + y2. Pentru a reprezenta graficaceasta curba, trebuie sa fixam o regiune ın care se efectueazareprezentarea, de exemplu pentru (x, y) ∈ [−2, 2]× [0, 2.5]

Plot−−−→ o curba ’tacnode’ -2 -1 0 1 20.0

0.5

1.0

1.5

2.0

2.5

(b) f(x, y, z) = x2 + y2 + z2 − 4. Pentru a reprezenta grafic aceastasuprafata, trebuie sa specificam o regiune din spatiul ın caredorim sa vizualizam reprezentarea, de exemplu pentru (x, y, z) ∈[−2, 2]× [−2, 2]× [−2, 2]

Plot3D−−−−→ o suprafata sferica

-2

-1

0

1

2

-2

-1

0

1

2

-2

-1

0

1

2

Parametric: In acest caz, coordinatele punctelor depind de valoarea u-nuia sau mai multor parametri. Reprezentarile grafice se produc cal-culand coordonatele punctelor de pe suprafata pentru valori diferite

3

ale parametrilor. De exemplu:x(t) =

t3 − 6t2 + 9t− 2

2t4 − 16t3 + 40t2 − 32t+ 9

y(t) =t2 − 4t+ 4

2t4 − 16t3 + 40t2 − 32t+ 9

Pentru t ∈ [−7, 7]ParametricPlot−−−−−−−−−→ reprezinta aproape toata curba ’tac-

node’ pe care am descris-o implicit.

5. Calculul cu matrici, simplificarea expresiilor algebrice (de ex.,√

5 + 2√

6+√5− 2

√6

Simplify−−−−−→ 2√

3), etc.

Numerosi algoritmi de acest fel sunt implementati ın sisteme software care potasista matematicienii, fizicienii, astronomii, inginerii, etc, sa efectueze calculelecostisitoare de rutina si sa le acorde timp sa se concentreze pe aspectele creativeale rezolvarii problemelor.

Calculul simbolic poate fi ımpartit, ın linii mari, ın 2 categorii:

1. logica computationala, care are ca teme mari de studiu demonstrarea au-tomata a teoremelor si programarea logica.

2. algebra computationala.

In acest curs vom discuta doar subiecte legate de algebra computationala.

3 Ce este Algebra Computationala?

In linii mari, algebra computationala este studiul algoritmilor care difera decalculul numeric prin punerea accentului pe calculul cu simboluri care reprezintaconcepte matematice. In vreme ce calculul numeric opereaza cu numere, al-goritmii din algebra computationala opereaza cu polinoame, functii rationale,functii trigonometric, numere algebrice, etc. Acest lucru nu ınseramna ca nu maiavem nevoie defel de algoritmii numerici. Ambele forme de calcul — numericsi simbolic — au meritele si lipsurile lor, si din acest motiv este important saavem la ındemana sisteme de calcul care faciliteaza ambele moduri de calcul.

Caracteristicile principale ale algebrei computationale sunt:

1. Algebra computationala opereaza cu structuri algebrice. Astfel de struc-turi pot fi domenii de numere algebrice, inele de polinoame, campuri defunctii, campuri de ecuatii diferentiale, s.a.m.d. De multe ori, este beneficsa se simplifice o expresie algebrica ınainte de a o evalua numeric. In felulacesta, expresia devine mai simpla, mai usor de evaluat pentru valori nu-merice ale variabilelor, iar calculele de evaluare numerica produc erori deaproximare mai mici.

4

2. Rezultatele algoritmilor de algebra computationala sunt exacti si nu suntefectati de erori de aproximare. De exemplu, solutiile algebrice ale sis-temului de ecuatii {

x2 + y2 − 1 = 0x− y = 0

sunt (1/√

2, 1/√

2) si (−1/√

2,−1/√

2), ın vreme ce solutiile numerice suntapproximative: (0.7071, 0.7071) si (−0.7071,−0.7071).

3. In general, valorile de intrare ale algoritmilor simbolici sunt expresii sauformule, si se doreste ca rezultatul calculelor sa fie deasemenea o expresiesau formula. Algoritmii de algebra computationala pot da rezultate ınforma algebrica ın loc sa calculeze valori numerice pentru puncte specificede evaluare. Astfel de expresii algebrice pot fi extrem de utile, deoareceele pot descrie felul ın care modificari ale parametrilor afecteaza rezultatulcalculelor.

Un exemplu tipic este∫x

x2 − adx =

x2 − a2

ın loc de

∫ 12

0

x

x2 − 1dx = 0.143841.

In consecinta, se pot construi algoritmi de decizie ın algebra computatio-nala, ca de exemplu pentru descompunerea polinoamelor ın factori, echiva-lenta expresiilor algebrice (de exemplu, sunt echivalente expresiile

√2 + 1

si 1/(√

2 − 1)?), integrarea simbolica a unor clase specifice de expresii,rezolvarea unor sisteme tipice de ecuatii diferentiale, validarea ipotezelorgeometrice, parametrizarea curbelor algebrice, etc.

3.1 Cateva Aplicatii ale Algebrei Computationale

1. “Problema mutarii pianului”. Problema este “sa se gaseasca o cale care vapermite mutarea unui corp B de la o pozitie initiala a o pozitie destinatiedorita, ın asa fel ıncat sa nu se loveasca nici un obstacol.”

A metoda posibila este descrisa ın

J.T. Schwartz, M. Sharir. On the “Piano Movers” Problem. II. Gen-eral Techniques for computing topological properties of real algebraicmanifolds. Adv. Appl. Math. 4:298-351. 1983.

5

Ideea este de a reprezenta pozitiile lui B ca pe o multime semi-algebricaL ın R, adica, ca pe o reuniune, intersectie, sau diferenta de multimi

{(x1, . . . , xm) | p(x1, . . . , xm) ∼ 0},

unde p este un polinom cu coefficienti rationali, iar ∼∈ {=, <,>}. Inacest fel, problema este redusa la ıntrebarea: “E posibil sa conectam douapuncte P1, P2 ale unei semi-varietati algebrice L cu o cale, adica, fac eleparte din aceeasi componenta conexa a lui L?” Algoritmul CAD al luiCollins de eliminare a cuantificatorilor ın campuri reale ınchise poate fifolosit pentru a afla raspunsul la aceasta ıntrebare.

2. Demonstrarea teoremelor geometrice. Exista numeroase metode ın algebracomputationala pentru demonstrarea teoremelor din geometria euclideanacare pot fi descrise cu sisteme de ecuatii polinomiale. De exemplu, se poatedemonstra ca “Piciorul perpendicularei pe ipotenuza unui triunghi drep-tunghic si mijloacele laturilor triunghiului sunt puncte conciclice” (Fig.1). Ipotezele acestei afirmatii geometrice pot fi descrise cu ecuatii polino-miale care caracterizeaza relatiile dintre coordonatele punctelor din figura.Deasemenea, concluzia acestei afirmatii poate fi descrisa cu o ecuatie poli-nomiala.

Figure 1: Demonstrarea teoremelor geometrice

Ipoteze:h1 ≡ 2 y3 − y1 = 0 (E este mijlocul lui AC).h2 ≡ (y7− y3)2 + y28 − (y7− y4)2− (y8− y5)2 = 0 (EM si FM suntla fel de lungi).

...hm ≡ . . .

Concluzie: c ≡ (y7 − y3)2 + y28 − (y7 − y9)2 − (y8 − y10)2 = 0 (EM siHM sunt la fel de lungi).

In acest fel, problema geometrica se reduce la demonstrarea faptului ca

h1 = 0 ∧ . . . ∧ hm = 0⇒ c = 0.

6

Acest tip de problema poate fi rezolvat cu algoritmul bazelor Grobner.Acest algoritm este implementat ın majoritatea sistemelor de calcul sim-bolic, inclusiv ın Mathematica.

De obicei, demonstrarea automata a teoremelor geometrice se bazeaza pefaptul ca atat atat ipotezele cat si concluzia unei constructii geometrice(2D sau 3D) pot fi descrise simbolic, ca sisteme de relatii (ecuatii sauinecuatii) polinomiale. Aceste relatii se obtin prin fixarea unui sistem decoordonate (2D sau 3D) si prin traducerea proprietatilor geometrice ınrelatii polinomiale. In final, se aplica o metoda de calcul simbolic pentrua demonstra relatii ıntre formule polinomiale. Exemple tipice de astfel demotode de calcul simbolic sunt:

• Algoritmul bazelor Grobner (ilustrat mai devreme)

• Algoritmul de descompunere algebrica cilindrica (CAD) al lui Collins,care are aplicatii si pentru rezlvarea problemei“mutarii pianului.”

3. Analiza varietatilor algebrice. O varietate algebrica este colectia de punctedeterminata de un sistem de ecuatii polinomiale. De exemplu, curba ’tac-node’ pe care am reprezentat-o grafic mai devreme:

f(x, y) = 2x4 − 3x2y + y4 − 2y3 + y2 = 0 (2)

este o varietate algebrica. Un punct singular al unei curbe este un punctın care ’ramurile’ curbei se intersecteaza. Adesea se doreste calculul coor-donatelor punctelor singulare. Cum putem gasi punctele singulare?

Ne putem folosi de faptul ca punctele singulare au coordonate ale carorvalori sunt solutii ale sistemului de ecuatii algebrice

f(x, y) = 0,∂f

∂x(x, y) = 0,

∂f

∂y(x, y) = 0.

Pentru curba ’tacnode’, acest sistem este 2x4 − 3x2y + y4 − 2y3 + y2 = 08x3 − 6x y = 0

−3x2 + 2y − 6y2 + 4y3 = 0(3)

Sistemul poate fi rezolvat algebric daca ıl aducem mai ıntai la o formamai simpla. Putem efectua calculul unei baze Grobner pentru sistemul depolinoame care constituie sistemul de ecuatii, si sa obtinem ın acest felsistemul simplificat:

(3)GrobnerBasis−−−−−−−−→

3x2 + 2y2 − 2y = 0x y = 0x3 = 0

Solve−−−→{{x→ 0, y → 0} , {x→ 0, y → 1}}

In acest fel am gasit punctele singulare (0, 1) si (0, 1).

4. Modelare stiintifica si tehnologica. Adesea, probleme din aceste domeniipot fi prezentate ce probleme de integrare sau de rezolvare a sistemelor deecuatii diferentiale. Un exemplu sugestiv este sistemul (1) de la pagina 2.

7

3.2 Limitari ale Algebrei Computationale

O ıntrebare simpla este: Daca algebra computationala poate efectua toate ecestecalcule complexe, de ce nu a ınlocuit cu totul calculul numeric? Motivul este lafel de simplu: algebra computationala are propriile ei limitari. Uneori,calculul unei solutii exacte este exrem de costisitor. Deasemenea, exista clase deprobleme pentru care nu se cunosc ınca metode de rezolvare simbolica.Si deasemenea, exista probleme despre care stim ca nu pot fi rezolvatesimbolic.

4 Sisteme de algebra calculatorie

Primele sisteme de programre pentru algebra computationala au aparut ın anii’50. De atunci pana acum au aparut numeroase sisteme extrem de performantede calcul simbolic. Majoritatea sunt concepute pentru domenii restranse deaplicatie, ca de exemplu fizica energiilor ınalte, mecanica celesta, teoria rela-tivitatii, si geometria algebrica.

Mentionam aici cateva sisteme de algebra computationala ın care sunt im-plementati numerosi algoritmi importanti de interes general.

Maple, Mathematica, Axiom, Macsyma, Reduce, Magma, Alder

In acest curs se va urmari familiarizarea cu sistemul de calcul simbolic Mathe-matica. Mathematica este un sistem foarte performant de calcul simbolic pentruaplicatii tehnice. Este un produs al Wolfram Research, iar ultima versiune esteMathematica 8. Exista o colectie impresionanta de surse de documentare:

• Documentation Center – un centru de documentare integrat care descrielimbajul de baza al sistemului Mathematica, contine tutoriale de calculsimbolic (functii matematice, formule, matrici, algebra liniara si polino-miala, sisteme de ecuatii diferentiale si cu derivate partiale,etc.), manipu-larea datelor, vizualizare si grafica, etc.

• Resurse free:

– Wolfram Mathworld (mathworld.wolfram.com): probabil cea maibogata resursa web de cunostinte mathematice.

– Wolfram Demonstrations Project (demonstrations.wolfram.com):o resursa gratuita de vizualizari interactive, cu suport pornind de laresurse de educatie elementara pana la subiecte de cercetare avansata.

5 Mathematica: Curs introductiv

Acest curs introductiv va ilustra principiile de baza ale utilizarii sistemuluiMathematica si va indica modul ın care se efectueaza calcule numerice, sim-bolice si grafice pe durata unei sesiuni Mathematica.

8

5.1 Sesiune Mathematica

Pentru a porni Mathematica, efectuati double-click pe icoana Mathematica.Aplicatia va porni o sesiune odata cu deschiderea catorva ferestre. Figura 2ilustreaza ferestrele care sunt deschise cand se porneste Mathematica versiunea7 pe un calculator Macintosh. Se disting 2 ferestre:

Figure 2: Mathematica 7 pe un calculator Mac (Mac OS X Leopard)

• O fereastra Welcome cu hiperlink-uri la tutoriale si resurse de documentare.Linkul Getting Started ofera o introducere concisa sistemului Math-ematica. Fereastra Welcome urmeaza sa fie ınchisa la sfarsitul fazei deautodocumentare, dupa care se poate trece la faza de programare.

• Un notebook cu titlul Untitled 1.

Un notebook este o fereastra specifica sistemului Mathematica care joacasi rolul de editor. Expresiile editate vor fi introduse in celule de intrare (engl.input cells). Apasand Shift+Enter se declanseaza evaluarea expresiei introduseın o celula de intrare. Daca evaluarea produce un rezultat, atunci Mathematicaıl va afisa ın o celula de iesire (engl. output cell) imediat dupa celula de intrare.

Celulele de intrare se editeaza una sub alta. Selectarea celulei care urmeazasa fie evaluata (cu Shift+Enter) sau a pozitiei de editare din notebook se poateface cu mouse click.

Mathematica poate produce 3 tipuri de rezultate: numerice, simbolice sigrafice. Figura 5.1 ilustrateaza efectele unei sesiuni Mathematica. De regula,celulele sunt delimitate de paranteze dreptunghiulare ın oar tea dreapta. Celulelede intrare ıncep cu ‘In[n]:=’ unde n este un numar unic generate de sistem pen-tru fiecare celula evaluata. Celulele de iesire ıncep cu ‘Out[n]:=’ unde n estenumarul celulei de intrare a carei evaluare a generat celula de iesire.

Pentru a ıncheia o sesiune, selectati optiunea din meniul Mathematica→Quit

Mathematica. Notebook-urile pot fi salvate, reıncarcate sau reevaluate.

9

In � Outnumbers

Cell delimitingbrackets

Cell withgraphic output

Cell withnumeric output

Cell withsymbolic output

Figure 3: Snapshot al unei sesiuni Mathematica

Observatii importante despre sintaxa sistemului Mathematica

1. Celulele de intrre pot contine comentarii ıntre (* si *).

2. Comenzile predefinite din Mathematica au nume care ıncep cu litere mari.

3. Apelurile de functii au argumentele scrise ıntre paranteze drepte. De ex-emplu, trebuie sa scriem Sin[π/2 + x + y] ın loc de sin(π/2 + x + y);Log[x2 + 2] ın loc de loge(x

2 + 2), etc.

4. Unele simboluri au interpretari predefinite. De exemplu: True si False(pentru valori de adevar), Pi, I, E, etc. Detalii despre interpretarea unuisimbol definit Sbl se pot obtine evaluand expresia ?Sbl. De exemplu:

afiseaza interpretarea predefinita a simbolului Pi.

10

5. Operatorii urmatori sunt folositi frecvent ın Mathematica:

• a b pentru ab (exponentiere); / pentru ımpartire; Sqrt[x] pentru√x;

• ∗ sau spatiu pentru ınmultire (‘a ∗ b’ say ‘a b’ reprezinta produsul luia cu b)

• {. . .} este constructor de liste. De exemplu, {a, b, c} este lista deelemente a, b, c.

6. Maniul Palette faciliteaza utilizarea unei palete pentru a edita expresiicare arata similar cu notatia matematica. De exemplu, paleta Basic-

MathAssistant contine sabloane pentru numeroase formule matematiceuzuale.

Teme de laborator (pentru saptamana viitoare)

Rezolvati exercitiile urmatoare ıntr-un notebook Mathematica (de ex., Answers.nb),iar apoi tipariti raspunsurile si prezentati-le la ınceputul seminarului urmator.

1. Cititi explicatile si exemplele illustrative din notebook-ul CrashCourse1.nbce poate fi descarcat de pe pagina web a acestui curs. Rezolvati exercitiile1.1-1.6.

2. Folositi Mathematica pentru a calcula matricile inverse si determinantiimatricilor urmatoare:

(a) A =

1 a a2

1 b b2

1 c c2

(b) B =

x− y y yy x− y yy y x− y

Observatii importante.

• O matrice

a11 · · · a1n...

. . ....

an1 · · · ann

este reprezentata ın Mathematica ca

o lista {{a11, . . . , a1n}, . . . {an1, . . . , an,n}}. Aceasta forma este greude analizat vizual. Pentru a afisa matricea A ın formatul matematicuzual, se poate folosi apelul MatrixForm[A]. De exemplu:

MatrixForm[{a, b}, {c, d}] ıntoarce

(a bc d

).

• Se poate folosi sablonul

(� �� �

)al paletei BasicMathAssistant

pentru editarea matricilor.

11

• Sa se foloseasca metodele Inverse si Det din Mathematica pentrua efectua aceste calcule, si MatrixForm pentru a afisa rezultatele ınformat matematic. Sa se utilizeze metoda Simplify pentru a sim-plifica determinantii si inversele matricilor calculate de Mathematica.De exemplu:

MatrixForm

Simplify

Inverse

1 1 1a b ca2 b2 c2

calculeaza inversa matricii

1 1 1a b ca2 b2 c2

, o simplifica si ıntoarce

rezultatul ın forma matriceala.

3. Pentru rezolvarea simbolica a unui sistem de ecuatii polinomiale, se ape-leaza

Solve[{l1==r1, . . . , lm==rm}, {x1, . . . , xn}]

unde l1, r1, . . . , ln, rn sunt expresii polinomiale ın variabilele x1, . . . , xn.Sa se foloseasca metoda Solve pentru a rezolva sistemul de ecuatii 2x4 − 3x2y + y4 − 2y3 + y2 = 0

8x3 − 6x y = 0,4y3 − 3x2 − 6y2 + 2y = 0.

Cate solutii diferite obtineti?

4. N[expr] calculeaza o aproximare numerica a expr, iar FullSimplify[expr]simplifica expresia simbolica expr. Fie

expr :=

√4 + 2

√3 +

√4− 2

√3− 2

√3.

Sa se calculeze N[expr] si FullSimplify[expr]. Care rezultat este mai precis?

12