Articole

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

Introducere Î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. Leonard Euler a demonstrat că nu este posibil ca o persoană să traverseze fiecare pod o si ... (mai mult)

Problema comis voiajorului este o problemă celebră de informatică: Un comis-voiajor (agent comercial) trebuie să 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. Dacă asociem problemei un graf neorientat, constatăm că t ... (mai mult)

Considerăm următoarea problemă: Se dau două șiruri de cifre zecimale. Să se determine cifrele comune, în ordine crescătoare. În funcție de numărul de cifre din cele două șiruri, putem realiza diverse soluții: căutăm fiecare termen din primul șir în al doilea șir. Șirul cu valorile comune va trebui sortat. dacă șirurile sunt sortate (sau le sortăm) procedăm ca mai sus, dar căutăm bin ... (mai mult)

Considerăm un tablou 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ă. În asemenea situații put ... (mai mult)

Introducere Căutarea unei valori într-un vector se poate face în două moduri: secvențial – presupune analizarea fiecărui element al vectorului într-o anumită ordine (de obicei de la stânga la dreapta). Când se găsește valoarea căutată parcurgerea vectorului se poate opri. În cel mai rău caz, pentru un vector cu n elemente parcurgerea face n pași, complexitatea timp a căutării secvenți ... (mai mult)

Șmenul lui Mars în vector Să presupunem că avem un vector A[] cu n elemente, indexate de la 1 la n, inițial nule, în care se fac mai multe operații Adună(s,d,X) prin care toate elementele din secvența delimitată de indicii s d cresc cu valoarea X. Se cere afișarea elementelor din A după efectuarea acestor operații. Metoda descrisă în continuare este cunoscută în lumea olimpicilor la inf ... (mai mult)

Introducere Ciurul lui Eratostene reprezintă o metodă de determinare a tuturor numerelor prime mai mici sau egale cu o valoare dată, n. În practică, valoarea lui n trebuie să fie una rezonabilă, ea depinzând de restricțiile de timp și memorie aplicate problemei. Ciurului Eratostene se aplică în felul următor – în continuare lucrăm cu n=30: se scriu toate numerele naturale de la 1 la ... (mai mult)

Problema: Se dă un număr natural n. Să se genereze toate submulțimile mulțimii {1,2,3,...,n}. Soluție: Pentru rezolvare folosim metoda backtracking. Acest articol prezintă două metode de rezolvare. Metoda 1 În vectorul soluție x[] vom memora pe rând câte o submulțime. Deoarece submulțimile au număr variabil de elemente, și vectorul soluție va avea un număr variabil de elemente. ... (mai mult)