Fise Informatica Clasa a XI-a

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 al timpului. Necesită o analiză atentă pentru a verifica aplicabilitatea. Util în probleme cu substructuri optime. Greșeli în alegerea regulii...

Citește Mai Mult

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 execuție poate fi foarte mare (explozie combinatorică). Permite revenirea și testarea altor soluții. Poate necesita optimizări pentru a fi practică....

Citește Mai Mult

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 analiză atentă pentru combinare. Aplicabilitate largă. Nu toate problemele pot fi împărțite logic. 5. Exemple practice Exemplu 1: Binary Search...

Citește Mai Mult

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 de implementat pentru probleme complexe. Eficient pentru probleme care au subprobleme repetate. Necesită identificarea clară a subproblemelor. 4. Probleme rezolvate...

Citește Mai Mult

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 delete p;         // Eliberează memoria 4. Avantaje și dezavantaje Avantaje Dezavantaje Flexibilitate în gestionarea memoriei. Necesită gestionare manuală (risc de...

Citește Mai Mult

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 de memorie suplimentară pentru pointere. Nu este necesară alocarea unui bloc mare de memorie. Mai dificil de implementat comparativ cu...

Citește Mai Mult

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 multă memorie pentru pointere suplimentare. Operații de inserare și ștergere eficiente. Mai complicat de implementat decât listele simplu înlănțuite. Utilă...

Citește Mai Mult

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). Gestionarea pointerilor poate fi complicată. Inserarea și ștergerea nodurilor sunt rapide. Este necesară atenție pentru a menține lista circulară. 4....

Citește Mai Mult

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. Avantaje și dezavantaje Avantaje Dezavantaje Parcurgere bidirecțională continuă. Gestionarea pointerilor este mai complexă. Eficientă pentru aplicații circulare (ex.: cozi). Necesită...

Citește Mai Mult

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 acces aleator. Utilă în aplicații precum recursivitatea sau backtracking. 4. Implementarea unei stive folosind liste simplu înlănțuite Structura unui nod...

Citește Mai Mult

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 este posibil. Poate fi implementată dinamic. Necesită gestionarea pointerilor pentru dinamism. 4. Implementarea unei cozi folosind liste simplu înlănțuite Structura...

Citește Mai Mult

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 memorie crește cu dimensiunea arborelui. 4. Structura unui nod struct Nod {     int valoare;       // Informația stocată     Nod*...

Citește Mai Mult

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> #include <algorithm> using namespace std; struct Muchie {     int sursa, destinatie, cost; }; // Comparator pentru sortarea muchiilor după...

Citește Mai Mult

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 poate scădea în cazuri de arbori dezechilibrați. Este baza pentru alte structuri complexe, cum ar fi heap-uri. 4. Structura unui...

Citește Mai Mult

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. Performanța scade dacă arborele devine dezechilibrat. Util pentru aplicații precum algoritmii de sortare și cozi de priorități. 4. Reprezentarea unui...

Citește Mai Mult

Ș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 să fie restabilită după ștergerea rădăcinii. void heapifyDown(vector<int>& heap, int index) {     int stanga = 2 * index +...

Citește Mai Mult

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 |   | 4–3 Matricea de adiacență: 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0...

Citește Mai Mult

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 1    2    3 3. Graf regulat 1–2 |   | 4–3 4. Graf bipartit 1–3 | \ | 2   4–5 5....

Citește Mai Mult

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 1 1 0 0 1 1 0 0 1 1 1 1 0 #include <iostream> using namespace std; void afisareMatrice(int...

Citește Mai Mult

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:     1–2     |   |     4–3 DFS(1): 1 → 2 → 3 → 4 #include <iostream> #include <vector> using...

Citește Mai Mult

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, u\}{u,v}={v,u}. Elemente fundamentale: Reprezentarea grafurilor 2. Parcurgerea în adâncime (DFS) Definiție: DFS (Depth-First Search) explorează un graf mergând cât mai...

Citește Mai Mult

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. Reprezentări ale grafurilor orientate 1. Matricea de adiacență (1) → (2)  ↑     ↓ (4) ← (3) Matricea de adiacență: 0...

Citește Mai Mult

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. Matricea de adiacență și gradul fiecărui nod #include <iostream> using namespace std; void afisareMatrice(int n, int matrice[100][100]) {     for...

Citește Mai Mult

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 | |/ \| 3–4 5. Graf Turneu (1) → (2)  ↑  ↘   ↓ (3) ← (4) 6. Graf Bipartit 1–3...

Citește Mai Mult

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 noduri din graf. 2. Definiție Pentru un graf G=(V,E)G = (V, E)G=(V,E): 3. Caracteristici 4. Avantaje și Dezavantaje Avantaje Dezavantaje...

Citește Mai Mult

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 G=(V,E)G = (V, E)G=(V,E): 3. Caracteristici 4. Exemplu pentru Grafuri Neorientate Graf: 1–2 |   | 4–3 Reprezentare: Matricea de incidență:...

Citește Mai Mult

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ă simplă și fundamentală, utilizată adesea ca bază pentru alte tipuri de reprezentări, cum ar fi lista de adiacență sau lista...

Citește Mai Mult

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 prelucra graful într-un mod eficient, mai ales atunci când graful este sparse (cu puține conexiuni comparativ cu numărul de noduri)....

Citește Mai Mult

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ă noduri. Dacă nu există o muchie/arc între două noduri, se utilizează o valoare convențională (de obicei infinit ∞\infty∞). 2. Structura...

Citește Mai Mult

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: 2. Caracteristici 3. Exemple de Grafuri și Matricea Drumurilor Graf Neorientat Graful: 1–2 |   | 4–3 Lista muchiilor: E =...

Citește Mai Mult

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 (orientat sau neorientat). 2. Obiectiv 3. Ideea Algoritmului Algoritmul Roy-Warshall se bazează pe conceptul de nod intermediar: 4. Pas cu...

Citește Mai Mult

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, cât și pentru grafuri neorientate. 2. Obiectiv 3. Ideea Algoritmului Algoritmul Roy-Floyd se bazează pe conceptul de nod intermediar: 4....

Citește Mai Mult

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ă greutăți negative. 2. Obiectiv 3. Ideea Algoritmului Algoritmul funcționează pe baza unui proces iterativ: 4. Complexitate 5. Exemplu Graf Ponderat...

Citește Mai Mult

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 un subgraf care conectează toate nodurile cu costul total minim al muchiilor. 2. Obiectiv 3. Ideea Algoritmului Algoritmul funcționează pe...

Citește Mai Mult

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 cea mai mică greutate, asigurându-se că nu se formează cicluri. 2. Obiectiv 3. Ideea Algoritmului Pentru a detecta ciclurile eficient,...

Citește Mai Mult