 |  |
|
Daca cele spuse mai sus cu privire la secretul invatarii rapide a programarii, acum nu ne mai ramine decit sa incepem sa aplicam practic ideile prezentate. Pentru aceasta, avem la dispozitie urmatoarea metoda care garanteaza cu siguranta rezultate. Iat-o, pe pasi:
se citeste si se intelege cit mai bine exemplul de problema rezolvata (se poate incepe chiar cu primul exemplu de mai sus)
se acopera (se ascunde) solutia si se incearca reproducerea ei din memorie (reinventarea solutiei) pe calculator
numai in cazuri exceptionale se poate apela (se poate trage cu ochiul) la solutie
Oricare dintre noi poate recunoaste aici metoda pe care o aplica copiii din primele clase primare: metoda trasului cu ochiul la rezultatul aflat la spatele manualului sau al culegerii de probleme. Din moment ce metoda este verificata si garantata (am folosit-o si noi cindva), de ce ne-ar fi rusine s-o aplicam acum din nou ?
Iata in continuare o lista de probleme de 'antrenament' care au majoritea rezolvarea intr-unul din capitolele urmatoare. Este numai bine pentru a incepe sa aplicam metoda oferita chiar acum !
Se citesc a, b, c trei variabile reale.
Sa se afiseze maximul si minimul celor trei numere.
Sa se afiseze cele trei numere in ordine crescatoare.
Sa se determine daca cele trei numere pot reprezenta laturile unui triunghi. Daca da, sa se determine daca triunghiul respectiv este isoscel, echilateral sau oarecare.
Sa se determine daca cele trei numere pot reprezenta laturile unui triunghi. Daca da, sa se determine marimile unghiurilor sale si daca este ascutit-unghic sau obtuz-unghic.
Sa se afiseze media aritmetica, geometrica si hiperbolica a celor trei valori.
Se citeste n o valoare intreaga pozitiva.
Sa se determine daca n este divizibil cu 3 dar nu este divizibil cu 11.
Sa se determine daca n este patrat sau cub perfect.
Sa se afiseze primele n patrate perfecte.
Sa se determine numarul cuburilor perfecte mai mici decit n.
Sa se gaseasca primul numar prim mai mare decit n.
Sa se afiseze primele n numere prime: 2, 3, 5, 7, . , pn.
Sa se determine toate numerele de 4 cifre divizibile cu n.
Sa se determine suma cifrelor lui n.
Sa se afiseze rasturnatul lui n. (Ex: n=1993 => n_rasturnat =3991).
Sa se afiseze urmatorul triunghi de numere:
1 2 3 . n
Se citesc m, n doua variabile intregi pozitive.
Sa se determine toate patratele perfecte cuprinse intre m si n, inclusiv.
Sa se determine toate numerele prime cuprinse intre m si n.
Sa se determine toate numerele de 4 cifre care se divid atit cu n cit si cu m.
Sa se determine c.m.m.d.c. al celor doua numere folosind algoritmul lui Euclid.
Sa se calculeze u20 , u30 , u50 ai sirului cu formula recursiva un=1/12un-1+1/2un-2 pentru n>=2 si u0=1, u1=1/2.
Se citeste n gradul unui polinom si sirul an, an-1, . , a1, a0 coeficientilor unui polinom P.
Se citeste x, sa se determine P(x).
Se citesc x si y, sa se determine daca polinomul P schimba de semn de la x la y.
Se citeste a, sa se determine restul impartirii lui P la x-a.
Se citesc m, n gradele a doua polinoame P si Q, si coeficientii acestora. Sa se determine polinomul produs R=PxQ.
Se citeste o propozitie (sir de caractere) terminata cu punct.
Sa se determine cite vocale si cite consoane contine propozitia.
Sa se afiseze propozitia in ordine inversa si cu literele inversate (mari cu mici).
Sa se afiseze fiecare cuvint din propozitie pe cite o linie separata.
Sa se afiseze propozitia rezultata prin inserarea in spatele fiecarei vocale 'v' a sirului "pv" ("vorbirea gaineasca").
Se citeste m, n dimensiunea unei matrici A=(ai,j)mxn de valori reale.
Se citesc l, c. Sa se afiseze matricea obtinuta prin eliminarea liniei l si a coloanei c.
Se citeste n intreg pozitiv, sa se afiseze matricea obtinuta prin permutarea circulara a liniilor matricii cu n pozitii.
Sa se determine suma elementelor pe fiecare linie si coloana.
Sa se determine numarul elementelor pozitive si negative din matrice.
Sa se determine linia si coloana in care se afla valoarea maxima din matrice.
Sa se determine linia care are suma elementelor maxima.
Se citesc m, n, p si apoi se citesc doua matrici A=(ai,j)mxn si B=(bj,k)nxp.Sa se determine matricea produs C=AxB.
Se citeste un fisier ce contine mai multe linii de text.
Sa se afiseze linia care are lungime minima.
Sa se afiseze liniile care contin un anumit cuvint citit in prealabil.
Sa se creeze un fisier care are acelasi continut dar in ordine inversa.
Se citeste x o valoarea reala. Sa se determine radical(x) cu 5 zecimale exacte pe baza sirului convergent xn=1/2 (xn-1+x / xn-1) cu x0>0 arbitrar ales.
Se citeste x o valoarea reala si k un numar natural. Sa se determine radical de ordinul k din x cu 5 zecimale exacte pe baza sirului convergent xn=1/k ( (k-1) xn-1+x / xn-1k-1) cu x0>0 arbitrar ales.
Sa se determine c.m.m.m.c. a doua numere m, n citite.
Se citeste n, sa se determine toate perechile (x, y) care au cmmmc(x,y)=n.
Se citesc a, b, c intregi pozitive, sa se determine toate perechile intregi (x, y) care conduc la egalitatea c=ax+by.
Se citeste n o valoare intreaga pozitiva. Sa se determine toate descompunerile in diferenta de patrate a lui n.
Sa se determine toate tripletele (i, j, k) de numere naturale ce verifica relatia i2+j2+k2=n unde n se citeste.
Se citeste n, sa se afiseze toate numerele pitagoreice mai mici sau egale cu n.
Se citeste n, sa se determine toate numerele perfecte mai mici decit n. (Un numar este perfect daca este egal cu suma divizorilor sai, ex. 6=1+2+3.)
Se citeste n, sa se afiseze toate numerele de n cifre, formate numai cu cifrele 1 si 2 si care se divid cu 2n.
Se citeste n, sa se afiseze toate numerele de n cifre care adunate cu rasturnatul lor dau un patrat perfect.
Se citeste n intreg pozitiv, sa se afiseze n transcris in baza 2.
Se citeste n intreg pozitiv scris in baza 2, sa se afiseze n transcris in baza 10.
Se citeste n intreg pozitiv, sa se afiseze n in transcriptia romana. (Ex: 1993=MCMXCIII , unde M=1000, D=500, C=100, L=50, X=10, V=5, I=1.)
Se citeste n, sa se afiseze descompunerea acestuia in factori primi.
Se citesc m, n numaratorul si numitorul unei fractii. Sa se simplifice aceasta fractie.
Se citeste n, sa se afiseze toate posibilitatile de scriere a lui n ca suma de numere consecutive.
Se citeste n si k, sa se afiseze n ca suma de k numere distincte.
Se citeste n, sa se determine o alegere a semnelor + si - astfel incit sa avem relatia 1 (n+1) n=0, daca ea este posibila.
Se citeste n si sirul de valori reale x1, x2, . , x n-1, xn ordonat crescator. Sa se determine distanta maxima intre doua elemente consecutive din sir.
Se citeste n gradul unui polinom si sirul xn, xn-1, . , x1 solutiilor reale a unui polinom P. Sa se determine sirul an, an-1, . , a1, a0 coeficientilor polinomului P.
Se citesc doua siruri de valori reale x1, x2, . , x n-1, xn si y1, y2, . , y m-1, ym ordonate crescator. Sa se afiseze sirul z1, z2, . , z n+m-1, zn+m rezultat prin interclasarea celor doua siruri.
Un sir de fractii ireductibile din intervalul [0,1] cu numitorul mai mic sau egal cu n se numeste sir Farey de ordinul n. De exemplu, sirul Farey de ordinul 5 (ordonat crescator) este: 0/1, 1/5, ¼, 1/3, 2/5, ½, 3/5, 2/3, ¾, 4/5, 1/1. Sa se determine sirul Farey de ordinul n, cu n citit.
Se citeste n si S o permutare a multimii . Sa se determine numarul de inversiuni si signatura permutarii S.
Se citeste n si S o permutare a multimii . Sa se determine cel mai mic numar k pentru care Sk=.
Fie M= multimea numerelor obtinute pe baza regulii R1, si a regulii R2 aplicate de un numar finit de ori: R1) 1IM R2) Daca xIM atunci y=2x+1 si z=3x+1 apartin lui M. Se citeste n, sa se determine daca n apartine multimii M fara a genera toate elementele acesteia mai mici decit n.
Se citeste n, k si o matrice A=(ai,j) nxn patratica. Sa se determine Ak.
Se citeste n si o matrice A=(ai,j) nxn patratica. Sa se determine d determinantul matricii A.
Se citeste n si cele n perechi (xi, yi) de coordonate a n puncte Pi in plan. Sa se determine care dintre cele n puncte poate fi centrul unui cerc acoperitor de raza minima.
Sa se determine, cu 5 zecimale exacte, radacina ecuatiei x3+x+1=0 care exista si este unica in intervalul [-1,1].
Se citeste n si sirul de valori reale x1, x2, . , x n-1, xn. Sa se determine pozitia de inceput si lungimea celui mai mare subsir de numere pozitive.
Se citeste n, sa se afiseze binomul lui Newton: (x+y)n.
Se citeste n, sa se afiseze binomul lui Newton generalizat: (x1+x2+ . +xp)n=Sn!/(n1!n2! . np!) x1n1x2n2 . xpnp pentru n1+n2+ . +np=n si ni>0, i=1,p.
Se citeste n, sa se determine descompunerea lui n ca suma de numere Fibonacci distincte. (Fn=Fn-1+Fn-2 pentru n>1 si F1=1, F0=0).
Avem la dispozitie urmatoarele trei operatii care se pot efectua asupra unui numar n: O1) i se adauga la sfirsit cifra 4; O2) i se adauga la sfirsit cifra 0; O3) daca n este par se imparte la 2. Sa se afiseze sirul operatiilor care se aplica succesiv, pornind de la 4, pentru a obtine un n care se citeste.
Fie functia lui Ackermann definita astfel: A(i,n)=n+1 pentru i=0; A(i,n)=A(i-1,1) pentru i>0 si n=0; A(i,n)=A(i-1,A(i,n-1)) pentru i>0 si n>0. Care este cea mai mare valoare k pentru care se poate calcula A(k,k) ?
Sa se determine suma tuturor numerelor formate numai din cifre impare distincte.
Scrieti o functie recursiva pentru a determina c.m.m.d.c. a doua numere m si n.
Scrieti o functie recursiva pentru a calcula an pe baza relatiei an=(ak)2 pentru n=2k, si an=a(ak)2 pentru n=2k+1.
Scrieti o functie recursiva pentru a determina prezenta unui numar x intr-un sir de valori reale x1, x2, . , x n-1, xn ordonate crescator folosind algoritmul cautarii binare.
Scrieti o functie recursiva pentru a determina o asezare a 8 turnuri pe o tabla de sah astfel incit sa nu se atace intre ele. (Tabla de sah va fi reprezentata printr-o matrice patratica de 8x8).
Sa se determine peste citi ani data de azi va cadea in aceeasi zi a saptaminii.
Avem la dispozitie un fisier ce contine numele, prenumele si media tuturor studentilor din grupa.
Sa se afiseze studentul cu cea mai mare medie.
Sa se afiseze toti studentii bursieri.
Sa se afiseze studentul care are media cea mai apropiata de media aritmetica a mediilor pe grupa.
Sa se afiseze toti studentii din prima jumatate a alfabetului.
Sa se afiseze toti studentii in ordine inversa decit cea din fisier.
Sa se creeze un fisier catalog care sa contina aceleasi informatii in ordinea alfabetica a numelui.
Avem la dispozitie doua fisiere ce contin numele, prenumele si media tuturor studentilor din cele doua grupe ale anului in ordinea descrescatoare a mediilor.
Sa se afiseze toti studentii din ambele grupe care au media mai mare decit media anului.
Sa se creeze prin interclasare un fisier totalizator care contine toti studentii anului in ordinea descrescatoare a mediilor.
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 2n 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 2100=(210)10 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 d1, d2, . , dn o multime de n valori intregi pozitive. Se cere sa se gaseasca o partitionare a multimii d1, d2, . , dn astfel incit suma elementelor partitiei sa fie exact C.
Problema rucsacului. Avem un rucsac de capacitate intreaga pozitiva C si n obiecte cu dimensiunile d1, d2, . , dn si avind asociate profiturile p1, p2, . , pn (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 d1, d2, . , dn, cu 0<di<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 !
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 !
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 !
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 !
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 1x
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' !
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 (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 !
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 , 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 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 !
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 !
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!
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.
Am introdus acest capitol special din doua motive. Primul motiv, pentru a trezi interesul si pasiunea pentru informatica celor care pot acum sa vada cit de deosebite sint descoperirile si rezultatele din acest domeniu. Al doilea motiv, pentru ai pune in garda pe cei care, in entuziasmul lor exagerat, isi inchipuie ca pot programa calculatorul sa faca orice treaba sau sa rezolve orice problema. Asa cum am vazut si in capitolul ce trateaza despre problemele dificile ale informaticii, enunturile problemelor foarte dificile sau chiar insolvabile sint foarte simple si pot usor constitui o capcana pentru necunoscatori.
In continuare vom oferi spre edificare doar citeva exemple, urmind ca prin studiul Complexitatii algoritmilor si a dificultatii problemelor sa se aprofundeze acest domeniu fascinant dar atit de usor de confundat (poti sa dai de aceste probleme chiar si din greseala !?) si care este pacat sa fie tratat intr-un mod superficial.
Problema Stopului. Nu exista un algoritm universal valabil prin care sa se poata decide daca executia oricarui algoritm se opreste vreodata sau nu.
Comentariu: acesta este cel dintii si cel mai celebru exemplu de problema insolvabila. Demonstratia riguroasa a acestui fapt a fost data pentru prima data in 1936 de inventatorul calculatorului actual matematicianul englez Alan Mathison Turing. Odata existind aceasta demonstratie, multe din urmatoarele probleme insolvabile algoritmic s-au redus la aceasta. Implicatiile practice, teoretice si filozofice ale problemei Stopului sint foarte importante atit pentru informatica cit si pentru matematica. Astfel, doua consecinte strategice ale problemei Stopului sint: 1. nu poate exista un calculator oricit de puternic cu ajutorul caruia sa se poata decide asupra comportamentului viitor al oricarui alt calculator de pe glob; 2. nu poate sa existe in matematica o metoda generala de demonstrare inductiva-logica a propozitiilor matematice (se inchide in acest fel o mai veche cautare a matematicienilor si logicienilor cunoscuta sub numele de Entscheidungs Problem sau Problema deciziei).
Problema ecuatiilor diofantice. Nu exista o metoda generala (un algoritm) de aflare a solutiilor intregi ale unui sistem de ecuatii diofantice.
Comentariu: sistemele de ecuatii diofantice sint sistemele de ecuatii algebrice de mai multe variabile cu coeficienti intregi si carora li se cauta solutii intregi. De exemplu, a fost nevoie de ajutorul calculatorului pentru a se descoperi cea mai mica solutie a ecuatiei diofantice p4+q4+r4=s4 si care este cvadrupletul p=95600, q=217519, r=414560, s=422461 (infirmindu-se in acest fel 'conjectura' lui Leonard Euler care in 1796 a presupus ca aceasta ecuatie diofantica nu are solutii intregi). Aceasta problema ce cere o metoda generala de rezolvare a ecuatiilor diofantice este cunoscuta sub denumirea de Problema a 10-a a lui Hilbert.
Problema acoperirii planului (Problema pavajului sau Problema croirii). Fiind data o multime de forme poligonale, nu exista o metoda generala (un algoritm) care sa decida daca cu aceste forme este posibila acoperirea completa a planului (fara suprapuneri si goluri).
Comentariu: in practica este mult mai importanta problema croirii care cere sa se decupeze fara pierderi un set cit mai mare de forme date (croiuri) dintr-o bucata initiala de material oricit de mare. Este deasemenea demonstrat ca problema ramine insolvabila algoritmic chiar si atunci cind formele poligonale sint reduse la poliomine (un fel de 'mozaicuri') care se formeaza doar pe o retea rectangulara caroiata. Iata citeva exemple de multimi formate dintr-o singura poliomina si, alaturat, raspunsul la intrebarea daca cu ele se poate acoperi planul sau nu:
DA NU DA
Problema sirurilor lui Post. Se dau doua multimi egale de siruri finite de simboluri ce sint imperecheate astfel: un sir dintr-o multime cu sirul corespunzator din a doua multime. Nu exista un algoritm general prin care sa se decida daca exista o ordine de concatenare a sirurilor (simultan din cele doua multimi) astfel incit cele doua siruri lungi pereche rezultate sa fie identice.
Comentariu: de exemplu, fie A= si B= cele doua multimi de siruri de simboluri (pentru usurinta au fost alese simbolurile binare 1 si 0). Perechile corespunzatoare de siruri sint 1.(101,010), 2.(010,10) si 3.(00,001). Observam ca sirurile pereche pot avea lungimi diferite (ca in perechile 2 si 3). In continuare, pentru a vedea cum se procedeaza, cele doua siruri pereche rezultante prin concatenare le vom scrie unul deasupra celuilalt sesizind cum avanseaza procesul de egalizare a lor. Punctele sint intercalate doar pentru a evidentia perechile, ele nu contribuie la egalitate, iar comentariile ne apartin:
|
|
Concatenarea poate incepe doar cu |
|
Obligatoriu urmeaza perechea 1-a |
||
|
|
perechea a 3-a,00 de 'sus' 001 de 'jos' |
|
singura care incepe cu 1 'sus'. |
||
|
|
Daca am continua cu perechea |
|
. nu s-ar obtine rezultatul final |
||
|
|
a 3-a . |
|
oferit de perechea 2-a ! |
||
Problema cuvintelor 'egale'. Se da un anumit numar de 'egalitati' intre cuvinte. Bazindu-ne pe aceste 'egalitati' se pot obtine unele noi substituind aparitiile cuvintelor dintr-o parte a egalului cu cele din cealalta parte. Nu exista un algoritm general de a decide daca un cuvint oarecare A poate fi 'egal' cu un altul B.
Comentariu: de exemplu, fie urmatoarele cinci egalitati (cititi-le in limba engleza) EAT=AT, ATE=A, LATER=LOW, PAN=PILLOW si CARP=ME. Este CATERPILLAR egal cu MAN ? Iata sirul egalitatilor iterate care ne poate oferi raspunsul: CATERPILLAR = CARPILLAR =CARPILLATER =CARPILLOW= CARPAN= MEAN= MEATEN= MATEN= MAN.
Dar de la CARPET putem ajunge la MEAT ? Intrucit se vede ca numarul total de A-uri plus W-uri si M-uri nu se poate modifica prin nici o substitutie si intrucit CARPET are un A (adica numarul asociat este 1) iar MEAT are un A si un M (deci 2), rezulta ca aceasta egalitate nu este permisa.
Mai mult, se stie ca exista liste particulare de cuvinte pentru care nu poate exista un algoritm ce decide daca doua cuvinte sint egale sau nu. Iata o astfel de lista de sapte egalitati: AH=HA, OH=HO, AT=TA, OT=TO, TAI=IT, HOI=IH si THAT=ITHT.
Numarul problemelor cunoscute ca fiind insolvabile algoritmic este destul de mare. Cele mai multe probleme provin din matematica, subdomeniul matematicii care studiaza aceste probleme se numeste Matematica nerecursiva. De aceea ele pot fi intilnite mai ales sub numele de probleme nedecidabile sau probleme nerecursive, in enuntul lor cuvintul algoritm fiind inlocuit mai ales cu cuvintele metoda generala.
Studierea acestui domeniu a creat conditii pentru aparitia de noi directii de cercetare prin care se incearca explicarea rationamentelor matematice ba chiar se incearca descoperirea limitelor ratiunii umane in general. Unii oameni de stiinta contemporani, cum este celebrul matematician-fizician englez Roger Penrose, depun eforturi mari pentru a oferi o demonstratie matematica riguroasa pentru ipoteza ca, in cele din urma si in esenta, rationamentele umane nu sint algoritmice, nici macar cele matematice. Dupa parera lui Penrose mintea umana nu poate fi asimilata cu un calculator ci este mai mult decit atit si nu vor putea exista vreodata calculatoare sau roboti mai inteligenti decit oamenii! In ultimul capitol oferim titlurile cartilor recent aparute ce trateaza despre acest fascinant subiect .
Acest document nu se poate descarca
| E posibil sa te intereseze alte documente despre:
|
| Copyright © 2024 - Toate drepturile rezervate QReferat.com | Folositi documentele afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul document pe baza informatiilor de pe site. { Home } { Contact } { Termeni si conditii } |
Documente similare:
|
Cauta document |