Articole recomandate

QuickSort sau Sortarea rapidă este o metodă eficientă de sortare a unui tablou, descoperită în 1960 de programatorul britanic C.A.R. Hoare. Pentru un set de n valori oarecare algoritmul efectuează $O(n\log n)$ comparații, dar în cazul cel mai nefavorabil se efectuează $O(n^2)$ comparații. Algoritmul este de tip divide et impera; el sortează o secvență a tabloului (inițial întreg ... (mai mult)

Așa cum știm deja, fiecărui program C++ care rulează pe calculator i se alocă trei zone distincte în memoria RAM, în care se află datele pe care le prelucrează acel program: zona de date – aici se alocă memorie pentru variabilele globale; acestea sunt inițializate cu 0 și sunt vizibile pe tot parcursul programului, în toate funcțiile definite după declararea acestora zona de stivă – a ... (mai mult)

De multe ori datele folosite într-un program caracterizează obiecte/fenomene din realizate, iar acestea au mai multe caracteristici decât un simplu număr sau un șir de caractere. De exemplu, o persoană poate fi caracterizată prin câteva informații: nume – șir de caractere prenume – șir de caractere sex – (M/F) probabil caracter vârsta – număr natural salariu – număr real etc. Pe ... (mai mult)

Divide et Impera este o metodă de programare bazată pe un principiu simplu: problema dată se descompune în două (sau mai multe) subprobleme (de același tip ca problema inițială, dar de dimensiuni mai mici); se rezolvă independent fiecare subproblemă; se combină rezultatele obținute pentru subprobleme, obținând rezultatul problemei inițiale. Subproblemele trebuie să fie de același t ... (mai mult)

Algoritmul lui Dijkstra determină pentru un nod dat într-un graf orientat cu costuri costurile minime ale drumurilor care au acel nod ca extremitate inițială. Mai precis, pentru un nod s – sursă, algoritmul determină pentru orice nod x costul minim al unui drum de la s la x. Strategia algoritmului lui Dijkstra este una de tip Greedy: se menține un tablou d[], în care d[x] reprezintă ... (mai mult)

Un graf orientat G=(V,E) este tare conex dacă pentru orice pereche de noduri distincte (x,y) există cel puțin un drum de la x la y și există cel puțin un drum de la y la x. Pentru un graf orientat, se numește componentă tare conexă un subgraf tare conex maximal – prin adăugarea a încă unui nod, subgraful obținut nu mai este tare conex. Exemplu Graful de mai sus nu este tare conex. El ... (mai mult)

În unele situații se cere gruparea elementelor unei mulțimi date într-o colecție de submulțimi disjuncte. Pentru o astfel de colecție sunt importante următoarele operații: stabilirea submulțimii din care face parte un anumit element pentru două elemente date, reuniunea submulțimilor din care fac parte aceste elemente Pentru fiecare submulțime se stabilește un reprezentant – unul din ... (mai mult)

Fie G=(V,E) un graf neorientat conex: un nod al grafului se numește punct de articulație sau nod critic dacă subgraful obținut prin eliminarea lui nu este conex; o muchie se numește punte sau muchie critică dacă graful parțial obținut prin eliminarea ei nu este conex; un graf neorientat se numește biconex dacă nu conține puncte de articulație; se numește componentă biconexă un subgr ... (mai mult)

Arbore liber Un arbore este un graf conex și aciclic. Se mai numește și arbore liber. Următoarele propoziții sunt adevărate: Un arbore cu n vârfuri are n-1 muchii. Un arbore este un graf conex și minimal cu această proprietate; dacă s-ar mai elimina o muchie, graful nu ar mai fi conex. Un arbore este un graf aciclic și maximal cu această proprietate; dacă s-ar mai adăuga o muchie, ... (mai mult)

În jurul anului 1960 a fost descoperit un algoritm pentru drumuri în grafuri orientate. Descoperirea a fost făcută independent de către trei oameni de stiință în domeniul algoritmilor: Robert Floyd, Bernard Roy și Stephen Warshall. Algoritmul se regăsește sub diferite denumiri care conțin numele descoperitorilor, este bazat pe programarea dinamică și poate fi utilizat în următoarele d ... (mai mult)