Asa cum s-a putut constata in capitolul anterior, exista multe probleme in informatica pentru care inca nu se cunosc solutii eficiente. In continuare vom oferi o lista de probleme nesolutionate inca. De fapt, ele apar mai ales in matematica, fiind cunoscute sub numele de conjecturi, si au toate ca specific un fapt care este de mare interes pentru programatori. Incertitudinea asupra lor ar putea fi definitiv inlaturata nu numai prin demonstratie matematica ci si cu ajutorul formidabilei puteri de calcul a computerelor. Astfel, fiecare din aceste conjecturi numerice ar putea fi infirmata (concluzia ar fi atunci ca conjectura este falsa) daca i s-ar gasi un contraexemplu. Este necesar doar sa se gaseasca un set de numere pentru care propozitia respectiva sa fie falsa. Ori, acest efort nu este la indemina niciunui matematician dar este posibil pentru un programator inzestrat si pasionat. El nu are decit sa scrie un program eficient si sa puna calculatorul sa caute un contra-exemplu.
Atragem atentia asupra unui aspect important. Fiecare problema contine aceeasi capcana ca si in problemele capitolului anterior: algoritmii de cautare a contra-exemplelor pot fi conceputi rapid, relativ simpli si cu efort de programare redus (de exemplu, prin trei-patru cicluri for imbricate sau printr-o solutie gen back-tracking) dar ei vor deveni in scurt timp total ineficienti si vor conduce la programe mari consumatoare de timp. De aceea, va sugeram sa tratati cu multa atentie problemele din acest capitol. Dupa parerea noastra, abordarea acestui tip de probleme cere din partea programatorului un anumit grad de maiestrie !
Rezolvind numai una dintre ele veti fi recompensati pe masura: riscati sa deveniti celebri !
1. Conjectura lui Catalan. Singurele puteri naturale succesive sint 8=23 si 9=32.
Observatie: intr-o exprimare matematica riguroasa, singura solutie in numere naturale m, n, p, q a ecuatiei nm+1=pq este n=2, m=3, p=3 si q=2.
Comentariu: avem sirul numerelor naturale 1, 2, 3, 4, 5,…; incercuind toate puterile de gradul 2: 1, 4, 9, 16, 25,… apoi toate cele de gradul 3: 1, 8, 27, 64, 125, … apoi cele de grad 4, 5, … vom constata ca singurele doua numere incercuite alaturate sint 8 si 9 ! Adica puterile obtinute, cu cit sint mai mari, cu atit au tendinta sa se 'imprastie' si sa se 'distanteze' unele de altele tot mai tare. In mod misterios, ele nu-si suporta vecinatatea unele cu altele !
2. Conjectura cutiei rationale. Nu se cunoaste existenta unei cutii paralelipipedice avind lungimile celor trei laturi, ale celor trei diagonale ale fetelor si a diagonalei principale intregi.
Observatie: intr-o exprimare matematic riguroasa, nu se cunoaste sa existe trei intregi a, b, c astfel incit a2+b2, b2+c2 , c2+a2 si a2+b2+c2 sa fie toate patru patrate perfecte.
Comentariu: in multe subdomenii ale constructiilor ,de exemplu sa ne gindim la stilpii de inalta tensiune ridicati pe virfuri inalte de munte si asamblati in intregime 'la fata locului' numai din bare imbinate cu suruburi (fara sudura), este de mare interes ca dintr-un numar cit mai mic de subansamble simple (un fel de 'caramizi') sa se asambleze obiecte mari cu cit mai multe configuratii. Evident, dimensiunile obiectelor rezultate vor avea marimea ca o combinatie intreaga ale dimensiunilor subansamblelor initiale. Dupa cum rezulta insa din conjectura, se pare ca este imposibil sa se construiasca scheletul intarit (pe diagonale) al unei cutii paralelipipedice din bare de lungimi tipizate. Cel putin una din diagonale necesita ajustarea lungimii unei bare !
3. Problema umplerii patratului unitate. Intrebare: este posibil ca multimea dreptunghiurilor de forma 1/k x 1/(k+1), pentru fiecare k intreg pozitiv, sa umple in intregime si fara suprapuneri patratul unitate, de latura 1x1
Observatie: este evident ca suma infinita a ariilor dreptunghiurilor este egala cu aria patratului unitate. Avem Sk>01/(k(k+1))=Sk>0(1/k-1/(k+1))=1.
Comentariu: aparent, descoperirea dezvoltarilor in serie pare sa fi plecat de la unele evidente propietati geometrice, usor de sesizat chiar din desene simple in care valorilor numerice li se asociaza segmente de lungimi corespunzatoare. Iata insa o surpriza in aceasta situatie: suma seriei numerice este evidenta analitic insa reprezentarea geometrica a 'fenomenului' este 'imposibila' !
4. Conjectura fractiilor egiptene (atribuita lui Erdös si Graham). Orice fractie de forma 4/n se descompune ca suma de trei fractii egiptene (de forma 1/x).
Observatie: intr-o exprimare matematic riguroasa, pentru orice n natural exista trei valori naturale, nu neaparat distincte, x, y, si z astfel incit 4/n=1/x+1/y+1/z.
Comentariu: este inca un mister motivul pentru care egiptenii preferau descompunerea factiilor numai ca suma de fractii egiptene. Descoperisera ei aceasta descompunere minimala a fractiilor de forma 4/n ? Dar mai ales, ce procese fizice reale erau astfel mai bine modelate ? Inclinam sa credem ca exista o legatura intre fenomenele fizice ondulatorii, transformata Fourier si fractiile egiptene !
5. Problema punctului rational. Exista un punct in plan care sa se afle la o distanta rationala de fiecare din cele patru virfuri ale patratului unitate ?
Observatie: daca consideram un patrat unitate avind virfurile de coordonate (0,0), (1,0), (0,1) si (1,1) atunci se cere gasirea unui punct (x,y) astfel incit x2+y2, (x-1)2+y2, x2+(y-1)2 si (x-1)2+(y-1)2 sa fie toate patru patrate perfecte. Atentie, x si y nu este obligatoriu sa fie intregi ! Acest fapt ridica foarte serioase probleme la proiectarea unui algoritm de cautare a unui astfel de punct (x,y).
Comentariu: la fel ca si in cazul cutiei rationale, se pare ca exista limitari serioase si neasteptate in incercarea de optimizare a numarului de subansamble necesare pentru construierea scheletelor sau cadrelor de sustinere. Se pare ca cele doua dimensiuni pe care geometria plana se bazeaza conduce la o complexitate inerenta neasteptat de mare !
6. Problema sumei de puteri. Care este suma seriei de inverse de puteri 1/1+1/23+1/33+1/43+1/53+… ?
Observatie: se cere sa se spuna catre ce valoare converge seria Sk>01/k3 sau Sk>0k-3. Se stie ca in cazul in care in locul puterii a 3-ia (cu minus) punem puterea a 2-a (cu minus) seria converge la p 2/6, in cazul in care in locul puterii a 3-ia punem puterea a 4-a seria converge la p 4/90.
Comentariu: desi pare a fi o problema de analiza matematica pura deoarece ni se cere sa gasim expresia sintetica si nu cea numerica aproximativa a sumei seriei, exista insa uluitoare descoperiri asemanatoare ale unor formule de analiza numerica sau chiar dezvoltari in serie (cea mai celebra fiind cea a lui cifrelor hexazecimale ale lui p) facute cu ajutorul calculatorului prin calcul simbolic ! Mai multe amanunte gasiti la adresa corespunzatoare de Internet pe care am trecut-o in ultimul capitol.
7. Problema ecuatiei diofantice de gradul 5. Exista a, b, c, and d intregi pozitivi astfel incit a5+b5=c5+d5 ?
Observatie: Se cunoaste ca in cazul in care puterea este 3 avem solutia: 13+123=93+103 iar in cazul in care puterea este 4 avem solutia: 1334+1344=594+1584 .
Comentariu: cautarea unor algoritmi generali de rezolvare a ecuatiilor diofantice a condus la importante descoperiri in matematica dar si in informatica. De exemplu, celebrul matematician Pierre Fermat, “stirnit” fiind de problemele continute in lucrarea Arithmetika a matematicianului antic Diofant din Alexandria (de unde si numele ecuatiilor diofantice), a descoperit in 1637 faimoasa sa teorema: Ecuatia diofantica xn+yn=zn nu admite solutie pentru n>2. Dar tot in aceeasi perioada a descoperit si faptul ca cea mai mica solutie a ecuatiei diofantice x2 - 109*y2 = 1 este perechea x=158 070 671 986 249 si y= 15 140 424 455 100. Dumneavoastra incercati doar sa verificati aceasta solutie fara ajutorul calculatorului si va veti putea da seama de performantele pe care le-a realizat Fermat ! In informatica este acum cunoscut si demonstrat ca este imposibil sa se construiasca un algoritm general pentru rezolvarea ecuatiilor diofantice !
8. Problema celor 13 orase. Puteti localiza 13 orase pe o planeta sferica astfel incit distanta minima dintre oricare doua dintre ele sa fie cit mai mare cu putinta ?
Observatie:
de fapt nu se cunoaste cit de mult
poate fi marita distanta minimala ce se obtine
dintre cele 78 de distante (date de cele 78=C213 de imperecheri posibile de orase).
Comentariu: daca s-ar cere localizarea a doar 12 puncte pe sfera, nu este greu de aratat ca asezarea care indeplineste conditia ceruta este in virfurile unui icosaedru (vezi figura alaturata). In acest caz, distanta minima maximizata este egala cu latura icosaedrului. Este greu de crezut ca in cazul descoperirii asezarii a 13 puncte pe sfera se poate porni tocmai de la icosaedru ! Evident ca in rezolvarea aplicativ-practica a acestui tip de probleme nesolutionate geometric pina in prezent rolul programatorului poate fi capital. La ora actuala pentru astfel de situatii se ofera solutii aproximative. Acestea constau din algoritmi care incearca sa aproximeze cit mai exact solutia optima intr-un timp rezonabil de scurt. Evident ca in aceste conditii algoritmii de cautare exhaustiva (gen back-tracking) sint cu totul exclusi !
9. Conjectura lui Collatz. Se pleaca de la un n intreg pozitiv. Daca n este par se imparte la doi; daca n este impar se inmulteste cu trei si i se aduna unu. Repetind in mod corespunzator doar acesti doi pasi se va ajunge intotdeauna la 1 indiferent de la ce valoare n se porneste ?
Observatie: de exemplu, pornind de la n=6 obtinem in 8 pasi sirul valorilor: 6, 3, 10, 5, 16, 8, 4, 2, 1.
Comentariu: valoarea finala 1 este ca o 'gaura neagra' care absoarbe in final sirul obtinut. 'Raza' de-a lungul careia are loc 'caderea' in gaura neagra 1 este data mereu de sirul puterilor lui 2: 2, 4, 8, 16, 32, 64, … cu ultima valoare de forma 3k+1, adica 4, 16, 64, 256, …. Se pare ca valorile obtinute prin cele doua operatii nu pot 'sa nu dea' nicicum peste acest sir care le va face apoi sa 'cada in gaura neagra' 1!
10. Problema inscrierii patratului. Dindu-se o curba simpla inchisa in plan, vom putea intotdeauna gasi patru puncte pe curba care pot sa constituie virfurile unui patrat ?
Observatie: in cazul curbelor inchise regulate (ce au axe de simetrie: cerc, elipsa, ovoid) nu este greu de aratat prin construire efectiva ca exista un patrat ce se 'sprijina' pe curba. Pare insa de nedovedit acelasi fapt in cazul unor curbe inchise foarte neregulate ! Gasirea celor patru puncte, intr-o astfel de situatie, este de neimaginat fara ajutorul calculatorului !
Comentariu: o consecinta surprinzatoare a acestei conjecturi este faptul ca pe orice curba de nivel (curba din teren care uneste punctele aflate toate la aceasi altitudine) am putea gasi patru puncte de sprijin pentru o platforma patrata (un fel de masa) perfect orizontala, de marime corespunzatoare. Acest fapt ar putea sa explice ampla raspindire a meselor cu patru picioare (!?) in detrimentul celor cu trei: daca ii cauti pozitia, cu siguranta o vei gasi si o vei putea aseza pe toate cele patru picioare, astfel masa cu patru picioare va oferi o perfecta stabilitate si va sta perfect orizontala, pe cind cea cu trei picioare desi sta acolo unde o pui din prima (chiar si inclinata) nu ofera aceeasi stabilitate.
In speranta ca am reusit sa va stirnim interesul pentru astfel de probleme nesolutionate inca si care sint grupate pe Internet in liste cuprinzind zeci de astfel de exemple (vezi adresa oferita in ultimul capitol), incheiem acest capitol cu urmatoarea constatare: descoperirile deosebite din matematica actuala au efecte rapide si importante nu numai in matematica ci si in informatica. Sa oferim doar un singur exemplu de mare interes actual: algoritmii de incriptare/decriptare cu cheie publica, atit de folositi in comunicatia pe Internet, se bazeaza in intregime pe proprietatile matematice ale divizibilitatii numerelor prime.
Ceea ce este interesant si chiar senzational este faptul ca in informatica nevoia de programe performante a condus la implementarea unor algoritmi care se bazeaza pe cele mai noi descoperiri din matematica, chiar daca acestea sint inca in stadiul de conjecturi! De exemplu, pentru acelasi domeniu al criptarii cu cheie publica exista deja algoritmi de primalitate senzational de performanti care se bazeaza pe Ipoteza (conjectura) lui Riemman. (Mai multe amanunte puteti gasi la adresele de Internet pe care le oferim in ultimul capitol.)
Este acest fapt legitim ? Ce incredere putem avea in astfel de programe ? Dupa parerea noastra putem acorda o totala incredere acestor algoritmi dar numai in limitele 'orizontului' atins de programele de verificare a conjecturii folosite. Daca programul de verificare a verificat conjectura numerica pe intervalul 1- 1030 atunci orizontul ei de valabilitate este 1030. Domeniile numerice pe care le pot acoperi calculatoarele actuale sint oricum foarte mari si implicit ofera o precizie suficienta pentru cele mai multe calcule cu valori extrase din realitatea fizica.
|
