Fise Informatica Clasa a XI-a
Liceu > informatica xi
Metoda Greedy în Programare 1
1. Obiectivele lecției: 2. Ce este metoda Greedy? 3. Etapele metodei Greedy 4. Avantaje și dezavantaje Avantaje Dezavantaje Simplu de înțeles și implementat. Nu garantează soluția optimă pentru toate problemele. Eficient din punct de vedere...
Liceu > informatica xi
Metoda Backtracking în Programare 2
1. Obiectivele lecției: 2. Ce este metoda Backtracking? 3. Probleme rezolvate prin backtracking 4. Avantaje și dezavantaje Avantaje Dezavantaje Garantează găsirea soluției, dacă există. Ineficient pentru probleme de dimensiuni mari. Explorează toate posibilitățile. Timp de...
Liceu > informatica xi
Metoda Divide et Impera în Programare 3
1. Obiectivele lecției: 2. Ce este metoda Divide et Impera? 3. Caracteristici și aplicabilitate 4. Avantaje și dezavantaje Avantaje Dezavantaje Reduce complexitatea problemelor mari. Poate consuma mai multă memorie (recursivitate). Ușor de paralelizat. Necesită o...
Liceu > informatica xi
Metoda Programării Dinamice în Programare 4
1. Obiectivele lecției: 2. Ce este Programarea Dinamică? 3. Avantaje și dezavantaje Avantaje Dezavantaje Reduce recalculările prin memorarea soluțiilor. Necesită mai multă memorie pentru stocarea intermediară. Garantează o soluție optimă, dacă există. Poate fi dificil...
Liceu > informatica xi
Alocarea Dinamică a Memoriei – Concepte de Bază 5
1. Obiectivele lecției: 2. Ce este alocarea dinamică a memoriei? 3. Cum funcționează alocarea dinamică în C++? int* p = new int; // Alocă memorie pentru un int *p = 42; // Stochează valoarea 42...
Liceu > informatica xi
Structuri de Date Liniare Implementate Dinamic – Liste Liniare Simplu Înlanțuite 6
1. Obiectivele lecției: 2. Ce este o listă liniară simplu înlănțuită? 3. Avantaje și dezavantaje Avantaje Dezavantaje Dimensiunea listei este dinamică. Accesul la un element necesită parcurgere secvențială. Inserarea și ștergerea elementelor sunt eficiente. Consumul...
Liceu > informatica xi
Structuri de Date Liniare Implementate Dinamic – Liste Liniare Dublu Înlanțuite 7
1. Obiectivele lecției: 2. Ce este o listă liniară dublu înlănțuită? struct Nod { int valoare; Nod* urmator; Nod* anterior; }; 3. Avantaje și dezavantaje Avantaje Dezavantaje Permite parcurgerea bidirecțională. Necesită mai...
Liceu > informatica xi
Structuri de Date Liniare Implementate Dinamic – Liste Circulare Simplu Înlanțuite 8
1. Obiectivele lecției: 2. Ce este o listă circulară simplu înlănțuită? 3. Avantaje și dezavantaje Avantaje Dezavantaje Permite parcurgerea continuă a listei. Mai dificil de implementat decât listele simple. Eficientă pentru aplicații circulare (ex.: bucle)....
Liceu > informatica xi
Structuri de Date Liniare Implementate Dinamic – Liste Circulare Dublu Înlanțuite 9
1. Obiectivele lecției: 2. Ce este o listă circulară dublu înlănțuită? struct Nod { int valoare; Nod* urmator; // Pointer către următorul nod Nod* anterior; // Pointer către nodul anterior }; 3....
Liceu > informatica xi
Structuri de Date Liniare Implementate Dinamic – Stiva 10
1. Obiectivele lecției: 2. Ce este o stivă? 3. Avantaje și dezavantaje Avantaje Dezavantaje Structură simplă și ușor de implementat. Accesibilitate limitată (doar vârful stivei). Eficientă pentru gestionarea problemelor LIFO. Necesită mai multe operații pentru...
Liceu > informatica xi
Structuri de Date Liniare Implementate Dinamic – Coada 11
1. Obiectivele lecției: 2. Ce este o coadă? 3. Avantaje și dezavantaje Avantaje Dezavantaje Structură simplă și ușor de implementat. Inserarea și ștergerea sunt limitate la capete. Eficientă pentru gestionarea operațiilor FIFO. Acces aleator nu...
Liceu > informatica xi
Structuri de Date Arborescente Implementate Dinamic – Arbori 12
1. Obiectivele lecției: 2. Ce este un arbore? 3. Avantaje și dezavantaje Avantaje Dezavantaje Eficient pentru căutări rapide în structuri mari (BST). Implementarea și gestionarea sunt mai complexe. Structură flexibilă pentru date ierarhice. Consumul de...
Liceu > informatica xi
Structuri de Date Arborescente Implementate Dinamic – Arbore Parțial de Cost Minim 13
1. Obiectivele lecției: 2. Ce este un arbore parțial de cost minim? 3. Aplicații practice ale MST 4. Algoritmi clasici pentru MST 5. Implementarea algoritmului lui Kruskal Structura pentru reprezentarea grafului #include <iostream> #include <vector>...
Liceu > informatica xi
Structuri de Date Arborescente Implementate Dinamic – Arbori Binari 14
1. Obiectivele lecției: 2. Ce este un arbore binar? 3. Avantaje și dezavantaje Avantaje Dezavantaje Structură flexibilă pentru gestionarea datelor ierarhice. Gestionarea dinamică necesită atenție pentru integritate. Traversare eficientă pentru căutare, inserare și ștergere. Performanța...
Liceu > informatica xi
Structuri de Date Arborescente Implementate Dinamic – Arbore Binar Heap 15
1. Obiectivele lecției: 2. Ce este un heap binar? 3. Avantaje și dezavantaje Avantaje Dezavantaje Eficient pentru accesarea elementelor de maxim/minim. Inserarea și eliminarea implică reorganizarea arborelui. Structura este compactă datorită proprietății de arbore complet....
Liceu > informatica xi
Ștergerea nodului rădăcină în Min-Heap/Max-Heap 16
1. Concept general: Ștergerea nodului rădăcină dintr-un heap presupune eliminarea elementului care respectă proprietățile heap-ului: Pașii generali pentru ștergerea rădăcinii: 2. Implementarea pentru Max-Heap Heapify-Down în Max-Heap Această funcție rearanjează elementele astfel încât proprietatea Max-Heap...
Liceu > informatica xi
Teoria Grafurilor: Grafuri Neorientate – Noțiuni Introdutive 17
1. Obiectivele lecției: 2. Ce este un graf? 3. Elemente fundamentale ale unui graf neorientat 4. Exemple simple de grafuri neorientate 5. Reprezentarea grafurilor neorientate Exemplu pentru un graf cu 4 noduri: 1–2 | |...
Liceu > informatica xi
Teoria Grafurilor: Grafuri Neorientate – Tipuri de Grafuri 18
1. Obiectivele lecției: 2. Ce este un graf neorientat? Un graf neorientat este format din: 3. Tipuri de grafuri neorientate 1. Graf complet 1–2 |\ /| | X | |/ \| 3–4 2. Graf vid...
Liceu > informatica xi
Teoria Grafurilor: Grafuri Neorientate – Metode de Reprezentare 19
1. Obiectivele lecției: 2. Ce este un graf neorientat? Un graf neorientat este definit prin: 3. Metode de reprezentare a grafurilor 1. Matricea de adiacență 1–2 | | 3–4 Matricea de adiacență: 0 1 1...
Liceu > informatica xi
Teoria Grafurilor: Grafuri Neorientate – Parcurgerea Grafurilor 20
1. Obiectivele lecției: 2. Ce este parcurgerea unui graf? Parcurgerea unui graf reprezintă vizitarea tuturor nodurilor, urmând un anumit algoritm.Aceasta poate fi utilizată pentru: 3. Metode principale de parcurgere 1. Parcurgerea în adâncime (DFS) Exemplu:...
Liceu > informatica xi
Teoria Grafurilor: Grafuri Neorientate – Noțiuni Introdutive și Parcurgerea în Adâncime (DFS) 21
1. Noțiuni introductive Ce este un graf? Un graf este o structură matematică care constă din: Grafuri neorientate Un graf neorientat este un graf în care muchiile nu au direcție, adică {u,v}={v,u}\{u, v\} = \{v,...
Liceu > informatica xi
Teoria Grafurilor: Grafuri Orientate – Noțiuni Introdutive 22
1. Obiectivele lecției: 2. Ce este un graf orientat? Un graf orientat (sau digraf) este o structură matematică formată din: Proprietăți: 3. Exemple de grafuri orientate (1) → (2) ↑ ↓ (4) ← (3) 4....
Liceu > informatica xi
Teoria Grafurilor: Adiacență, Incidență, Grad, Drum și Circuit 23
1. Adiacență 1–2 | | 4–3 2. Incidență 1–2 | | 4–3 3. Grad 1–2 | | 4–3 4. Drum 1–2 | | 4–3 5. Circuit 1–2 | | 4–3 6. Implementări în C++ 1....
Liceu > informatica xi
Teoria Grafurilor: Tipuri de Grafuri 24
1. Graf Parțial 1–2–3 | | 4–5 1–2 3 | 4 2. Subgraf 1–2–3 | | 4–5 1–2 | 5 3. Graf Plin (Graf Dens) 4. Graf Complet 1–2 |\ /| | X...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Matricea de Adiacență 25
1. Ce este Matricea de Adiacență? Matricea de adiacență este o metodă de reprezentare a unui graf (neorientat sau orientat) folosind o matrice binară AAA de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde ∣V∣|V|∣V∣ este numărul de...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Matricea de Incidență 26
1. Ce este Matricea de Incidență? Matricea de incidență este o metodă de reprezentare a unui graf (neorientat sau orientat) utilizând o matrice III de dimensiune ∣V∣×∣E∣|V| \times |E|∣V∣×∣E∣, unde: 2. Definiție Pentru un graf...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Lista Nodurilor 27
1. Ce este Lista Nodurilor? Lista nodurilor este o metodă de reprezentare a grafurilor în care se specifică explicit nodurile grafului, iar conexiunile dintre noduri (muchiile sau arcele) sunt tratate separat. Aceasta este o metodă...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Lista Arcelor 28
1. Ce este Lista Arcelor? Lista arcelor este o metodă de reprezentare a unui graf (neorientat sau orientat) printr-o listă de perechi care descriu conexiunile dintre noduri. Această metodă este utilă pentru a stoca și...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Matricea Costurilor 29
1. Ce este Matricea Costurilor? Matricea costurilor este o metodă de reprezentare a unui graf ponderat (orientat sau neorientat) în care fiecare element din matrice reprezintă costul asociat unei muchii sau unui arc dintre două...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Matricea Drumurilor 30
1. Ce este Matricea Drumurilor? Matricea drumurilor este o metodă de reprezentare a unui graf care indică existenta unui drum între două noduri. Aceasta este o matrice binară PPP de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde:...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Algoritmul Roy-Warshall 31
1. Ce este Algoritmul Roy-Warshall? Algoritmul Roy-Warshall este un algoritm utilizat pentru a determina matricea drumurilor într-un graf. Mai exact, acest algoritm determină dacă există un drum între două noduri iii și jjj într-un graf...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Algoritmul Roy-Floyd 32
1. Ce este Algoritmul Roy-Floyd? Algoritmul Roy-Floyd (cunoscut și ca Floyd-Warshall) este un algoritm utilizat pentru a determina drumurile minime între toate perechile de noduri dintr-un graf ponderat. Acesta este aplicabil atât pentru grafuri orientate,...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Algoritmul lui Dijkstra 33
1. Ce este Algoritmul lui Dijkstra? Algoritmul Dijkstra este un algoritm de găsire a drumului minim între un nod sursă și toate celelalte noduri dintr-un graf ponderat, orientat sau neorientat. Este eficient pentru grafuri fără...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Algoritmul lui Prim 34
1. Ce este Algoritmul lui Prim? Algoritmul Prim este un algoritm utilizat pentru a găsi arborele de acoperire minim (MST – Minimum Spanning Tree) într-un graf ponderat neorientat conectat. Un arbore de acoperire minim este...
Liceu > informatica xi
Metode de Reprezentare a Grafurilor: Algoritmul lui Kruskal 35
1. Ce este Algoritmul lui Kruskal? Algoritmul Kruskal este o metodă pentru a găsi arborele de acoperire minim (MST – Minimum Spanning Tree) într-un graf ponderat, neorientat. Se bazează pe alegerea iterativă a muchiilor cu...