Informatică clasa a XI-a: algoritmi și grafuri

La nivelul clasei a XI-a, accentul util se mută de la scrierea instrucțiunilor la alegerea și justificarea algoritmului. Acest ghid organizează tehnicile, grafurile și arborii din Algo25. Eticheta clasei este un reper de învățare; verifică separat ce cere programa aplicabilă și profesorul tău.

Înainte de algoritmi avansați, asigură-te că stăpânești vectorii, funcțiile și recursivitatea din parcursul anterior. O implementare sofisticată nu compensează o stare definită neclar sau o limită de indice greșită.

Începe cu analiza timpului și memoriei

Citește complexitatea algoritmilor și compară O(n), O(n log n) și O(n²) pe limite concrete. Nu transforma aceste clase în promisiuni universale de secunde: limbajul, operațiile și mediul influențează timpul real.

Pentru fiecare problemă, notează n maxim și dimensiunea valorilor. Aceasta te ajută să alegi atât algoritmul, cât și tipurile numerice. O soluție liniară poate fi greșită prin overflow, iar una corectă pe hârtie poate depăși memoria dacă păstrează o matrice prea mare.

Backtracking, greedy sau programare dinamică?

Backtracking explorează alegeri și respinge ramurile invalide. Este potrivit pentru generări și spații de căutare suficient de mici. Scrie ce înseamnă o soluție parțială și ce condiție poate fi verificată înainte de completare.

Greedy fixează alegeri locale și are nevoie de o justificare că acestea păstrează o soluție optimă. Testele sunt utile pentru a găsi contraexemple, dar nu înlocuiesc demonstrația. În programare dinamică, definește starea, tranzițiile, bazele și ordinea de calcul înainte de cod.

Compară secvența de sumă maximă cu subșirul crescător de lungime maximă. În prima problemă pozițiile sunt consecutive, în a doua pot fi sărite. O diferență mică în enunț schimbă starea și algoritmul, deci nu alege tehnica doar după un cuvânt familiar.

Grafuri: modelul înaintea parcurgerii

În capitolul de grafuri, identifică mai întâi vârfurile, muchiile și sensurile. Verifică dacă există costuri, muchii multiple sau vârfuri izolate. Matricea și listele de adiacență au costuri diferite, iar reprezentarea trebuie aleasă în raport cu dimensiunile.

Învață BFS și DFS, apoi conexitatea și arborii. Pentru distanțe în număr de muchii folosești BFS; pentru costuri nenegative poți studia Dijkstra; pentru costuri negative ai nevoie de condițiile Bellman–Ford. Sortarea topologică se aplică grafurilor orientate aciclice. Aceste condiții trebuie să apară în explicația soluției, nu numai în comentariile codului.

Arbori și structuri auxiliare

Continuă cu vectorul de tați, adâncimile și subarborii, apoi cu arbori binari și BST. Separă forma arborelui de proprietatea valorilor. Un heap, un arbore de căutare și un arbore parțial minim rezolvă probleme diferite, deși toate folosesc cuvântul arbore.

La Prim și Kruskal urmărește de ce alegerea unei muchii nu strică optimalitatea. La DSU urmărește componentele, fără să confunzi părinții administrativi cu muchiile arborelui rezultat. Fă un exemplu manual înainte de a combina mai multe structuri într-o singură soluție.

Exersează

Ai un graf neorientat în care fiecare muchie costă unu. Ce metodă simplă calculează distanțele de la o sursă? Răspuns: BFS, deoarece ordinea pe niveluri coincide cu numărul muchiilor. Dacă apar costuri diferite, această justificare nu mai este suficientă.

Încheie fiecare temă cu o problemă din catalog și cu o comparație între două abordări. Pentru pregătirea examenului, folosește separat ghidul BAC, unde alegerea documentelor oficiale și a profilului contează la fel de mult ca ordinea lecțiilor.

Întrebări frecvente

Trebuie să memorez toți algoritmii de grafuri?

Învață întâi ce problemă rezolvă și în ce condiții. Implementarea devine mai ușor de reconstituit când înțelegi invariantul.

Cum aleg între greedy și programare dinamică?

Verifică dacă alegerea locală poate fi justificată. Dacă deciziile depind de rezultate ale subproblemelor, definește o stare și analizează tranzițiile.

BFS calculează orice drum minim?

Nu. El minimizează numărul muchiilor sau costul când toate muchiile au aceeași pondere pozitivă. Costurile arbitrare cer alte metode.

Este suficient să am un algoritm rapid?

Nu. El trebuie să fie corect, să respecte memoria și să folosească tipuri numerice suficiente. Eficiența este una dintre condiții.

Toate aceste teme intră automat la BAC?

Nu deduce programa din catalogul bibliotecii. Verifică documentele oficiale pentru profilul și anul examenului, apoi selectează lecțiile relevante.