Probleme dificile in C si Pascal

Dupa cum se poate banui, informatica contine si ea, la fel ca matematica, o multime de probleme foarte dificile care isi asteapta inca rezolvarea. Asemanarea cu matematica ne intereseaza mai ales in privinta unui aspect capcana asupra caruia dorim sa atragem atentia aici.

Enunturile problemelor dificile sau foarte dificile de informatica este, in 99% din cazuri, foarte simplu si poate fi citit si inteles de orice student. Acest fapt consituie o capcana sigura pentru cei ignoranti. Daca in matematica lucrurile nu stau asa, asta se datoreaza numai faptului ca studiul matematicii are vechime si problemele, impreuna cu dificultatile lor, sint ceva mai bine cunoscute. In informatica nu avem insa aceeasi situatie. Ba chiar se intimpla ca probleme foarte dificile sint amestecate in culegerile de probleme de informatica printre probleme usoare, mai ales datorita lipsei de cultura de specialitate a autorilor.

Acest capitol isi propune sa puna in garda in privinta dificultatii problemelor oferind o mica initiere in acest domeniu (mai multe se pot afla studiind Complexitatea algoritmilor si dificultatea problemelor). Deasemeni el isi propune sa umple lacuna ce mai exista inca la ora actuala in cultura de specialitate.

Dificultatea problemelor de programare a caror enunturi urmeaza este considerata maxima de teoreticienii informaticii (ele se numesc probleme NP-complete). Nu va lasati pacaliti de faptul ca le-ati intilnit in unele culegeri de programare. Ele sint depasite in dificultate doar de problemele insolvabile algoritmic ! Dar in ce consta dificultatea lor ?

Spre deosebire de matematica, dificultatea problemelor de informatica nu este data de faptul ca nu se cunoaste un algoritm de rezolvare a lor, ci datorita faptului ca nu se cunoaste un algoritm eficient (!) de rezolvare a lor. Existenta unei metode de proiectare a algoritmilor atit de general valabila, cum este metoda back-tracking, face ca prea putine probleme cu care ne putem intilni sa nu aiba o solutie. Dar, intrucit in cazul metodei back-tracking, cautarea solutiei se face intr-un mod exhaustiv (se cauta peste tot', pentru ca sa fim siguri ca nu lasam nici o posibilitate neexplorata), durata cautarii are o crestere exponential-proportionala cu dimesiunea datelor de intrare. De exemplu, timpul de cautare care depinde de valoarea de intrare n poate avea o expresie de forma T(n)=c 2ⁿ secunde, unde c este un factor de proportionalitate ce poate varia, sa zicem, de la c=12.5  cind algoritmul este executat pe un calculator sau c=62.8 cind el este rulat pe un calculator de cinci ori mai performant. Dar, indiferent de calculator, pentru n=100 avem 2¹⁰⁰=(2¹⁰)¹⁰ deci timpul masurat in secunde are ordinul de marime mai mare de 30. Cea mai larga estimare pentru virsta Universului nostru nu depaseste 20 mild. ani ceea ce transformat in secunde conduce la un ordin de marime mai mic de 20. Deci, chiar si pentru valori mici ale lui n (de ordinul sutelor) am avea de asteptat pentru gasirea solutiei de 10 miliarde de ori mai mult decit a trecut de la Big Bang incoace ! Pot fi in aceasta situatie considerate astfel de programe ca rezolvari rezonabile, doar pentru ca ele gasesc solutia in cazurile in care n=2, 3, 4, . , 10

Exemplele urmatoare sint doar citeva, usor de intilnit 'din greseala', dintr-o lista cunoscuta ce contine la ora actuala peste sase sute de astfel de probleme. Pentru fiecare din aceste probleme nu li se cunosc alte solutii decit inutilii algoritmi de gen back-tracking. In lista apare des notiunea de graf, asa ca o vom introduce in continuare cit mai simplu cu putinta: printr-un graf se intelege o multime de virfuri si o multime de  muchii care unesc unele virfuri intre ele. Orice harta (schematizata) rutiera, feroviara sau de trafic aerian reprezinta desenul unui graf.

Problema partitionarii sumei. Fie C un intreg pozitiv si d₁, d₂, . , d_n o multime de n valori intregi pozitive. Se cere sa se gaseasca o partitionare a multimii d₁, d₂, . , d_n astfel incit suma elementelor partitiei sa fie exact C.

Problema rucsacului. Avem un rucsac de capacitate intreaga pozitiva C si n obiecte cu dimensiunile d₁, d₂, . , d_n si avind asociate profiturile p₁, p₂, . , p_n (in caz ca ajung in rucsac). Se cere sa se determine profitul maxim ce se poate obtine prin incarcarea rucsacului (fara ai depasi capacitatea).

Problema colorarii grafului. Sa se determine numarul minim de culori (numarul cromatic) necesar pentru colorarea unui graf astfel incit oricare doua virfuri unite printr-o muchie (adiacente) sa aiba culori diferite.

Problema impachetarii. Presupunind ca dispunem de un numar suficient de mare de cutii fiecare avind capacitatea 1 si n obiecte cu dimensiunile d₁, d₂, . , d_n, cu 0<d_i<1, se cere sa se determine numarul optim (cel mai mic) de cutii necesar pentru impachetarea tutror celor n obiecte.

Problema comisului voiajor. (varianta simplificata) Dindu-se un graf (o harta), se cere sa se gaseasca un circuit (un sir de muchii inlantuite) care trece prin fiecare virf o singura data.

Majoritatea acestor probleme apar ca probleme centrale la care se reduc in ultima instanta problemele concrete ale unor domenii capitale ale economiei si industriei, cum sint de exemplu planificarea investitiile, planificarea imprumuturilor si esalonarea platii dobinzilor, alocarea si distribuirea resurselor primare (mai ales financiare), etc. Pentru nici una din aceste probleme strategice nu se cunoaste un algoritm optim de rezolvare, ci doar solutii aproximative. Daca s-ar cunoaste algoritmii de solutionare optima atunci majoritatea sectoarelor si proceselor macro- si micro-economice ar putea fi conduse in timp real si optim (!!) cu calculatorul, fara a mai fi necesara prezenta umana.

Un exemplu cert de domeniu care s-a dezvoltat extraordinar si in care rolul soft-ului a fost esential este chiar domeniul constructiei de calculatoare, mai ales domeniul proiectarii si asamblarii de micro-procesoare. Daca ati vazut ca schema electronica interna de functionare a unui microprocesor din familia Pentium, daca ar fi desenata clasic, ar ocupa o plansa de dimensiuni 5x5 metri (!), nu mai aveti cum sa va indoiti de faptul ca numai un soft de proiectare si cablare performant mai poate controla si stapini super-complexitatea rezultata. Putina lume stie insa ca astfel de programe de proiectare performante au putut sa apara numai datorita faptului ca problema ce sta in spatele functionarii lor, problema desenarii grafurilor planare, nu se afla pe lista de mai sus a problemelor foarte dificile ale informaticii !

Probleme nesolutionate inca

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 !

Proiect: Fisa de lucru - operatii cu numere intregi Referat: Jocuri didactice matematica - lantul buclucas

Rezolvind numai una dintre ele veti fi recompensati pe masura: riscati sa deveniti celebri!

Conjectura lui Catalan. Singurele puteri naturale succesive sint 8 si

Observatie: intr-o exprimare matematica riguroasa, singura solutie in numere naturale m, n, p, q a ecuatiei n^m+1=p^q este n=2, m=3, p=3 si q

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 !

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 a²+b², b²+c² , c²+a² si a²+b²+c² 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 !

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 S_k>0 /(k(k+1))=S_k>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' !

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 !

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 atunci se cere gasirea unui punct (x,y) astfel incit x²+y², (x-1)²+y², x²+(y-1)² si (x-1)²+(y-1)² 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 !

Problema sumei de puteri. Care este suma seriei de inverse de puteri 1/1+1/2³+1/3³+1/4³+1/5³+ . ?

Observatie: se cere sa se spuna catre ce valoare converge seria S_k>0 /k³ sau S_k>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 , in cazul in care in locul puterii a 3-ia punem puterea a 4-a seria converge la p

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.

Problema ecuatiei diofantice de gradul 5. Exista a, b, c, and d intregi pozitivi astfel incit a⁵+b⁵=c⁵+d⁵ ?

Observatie: Se cunoaste ca in cazul in care puterea este 3 avem solutia: 1³+12³=9³+10³ iar in cazul in care puterea este 4 avem solutia: 133⁴+134⁴=59⁴+158⁴ .

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 xⁿ+yⁿ=zⁿ nu admite solutie pentru n>2. Dar tot in aceeasi perioada a descoperit si faptul ca cea mai mica solutie a ecuatiei diofantice x² - 109*y² = 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 !

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=C² 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 !

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 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

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- 10³⁰ atunci orizontul ei de valabilitate este 10³⁰. 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.