Articolele lui Candale Silviu (silviu)

Păduri de mulțimi disjuncte

Î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: …

Citește articolul

Biconexitate

Fie G=(V,E) un graf neorientat conex: …

Citește articolul


Algoritmul Roy-Warshall-Floyd

Î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. …

Citește articolul


Principiul lui Dirichlet

Principiul lui Dirichlet sau Principiul cutiei, sau Principiul porumbeilor este o generalizare a următoarei afirmații: Dacă avem trei pantofi, atunci avem sigur cel puțin doi pantofi drepți sau cel puțin doi pantofi stângi.

Citește articolul

Graf eulerian

În 1736, matematicianul elvețian Leonard Euler a rezolvat o problemă cunoscută astăzi ca “Problema celor șapte poduri din Königsberg”. Prin orașul Königsberg, azi Kaliningrad trece un râu pe care sunt două insule, acestea și malurile fiind unite prin poduri ca în imaginea de mai jos. …

Citește articolul


Graf hamiltonian

Problema comis voiajorului este o problemă celebră de informatică: Un comis-voiajor (agent comercial) trebuie viziteze n orașe. Cunoscându-se șoselele existente între orașe, să se determine o modalitate (toate modalitățile) prin care comis-voiajorul poate parcurge fiecare oraș o singură dată și se întoarce în orașul de plecare. …

Citește articolul

Tablouri bidimensionale

Tablourile unidimensionale C/C++ au elemente de același tip. Astfel, tipul elementelor poate fi chiar tablou (unidimensional); elementele tabloului sunt la rândul lor tablouri unidimensionale, care au elemente de un anumit tip. Aceste tablouri se numesc bidimensionale sau matrice. …

Citește articolul


Vectori caracteristici și de frecvență

Considerăm următoarea problemă: Se dau două șiruri de cifre zecimale. Să se determine cifrele comune, în ordine crescătoare.

Citește articolul

Sume parțiale în tablouri

Considerăm un tabloul cu elemente numerice. În unele probleme se cere să determinăm rapid suma elementelor din anumite secvențe date. Desigur, o soluție este parcurgerea tuturor elementelor din secvență și determinarea sumei, dar această operație are complexitatea \( O(n) \), iar dacă numărul de sume care trebuie calculate este mare soluția poate fi inacceptabilă. …

Citește articolul