Clasa a X-a | C++
Divide et impera și metoda Greedy
Învață să descompui o problemă în subprobleme mai mici cu metoda Divide et impera (maxim și minim, sortarea prin interclasare, căutarea binară) și să alegi optimul local pas cu pas cu metoda Greedy (monede, spectacole, rucsacul fracționar), în limbajul C++, stil Bacalaureat.
Metoda Divide et impera - caracteristici
Principiul descompunerii, rezolvării și combinării subproblemelor
Ce vei învăța:
- Cele trei etape: descompunere, rezolvare, combinare
- Condițiile în care se aplică metoda
- Cazul de bază al recursivității
- Suma unui interval cu Divide et impera
Maximul și minimul prin Divide et impera
Funcția recursivă maxim(st, dr) și varianta pentru minim
Ce vei învăța:
- Determinarea maximului pe un interval
- Compararea rezultatelor celor două jumătăți
- Adaptarea algoritmului pentru minim
- Analiza pas cu pas pe un exemplu concret
Sortarea prin interclasare (merge sort)
Divizare în jumătăți, sortare recursivă și interclasare
Ce vei învăța:
- Ideea sortării prin interclasare
- Interclasarea a două secvențe sortate
- Implementarea completă în C++
- Complexitatea algoritmului
Aplicații Divide et impera
Suma elementelor, numărarea parelor, căutarea binară
Ce vei învăța:
- Suma elementelor unui tablou prin D&I
- Numărarea elementelor pare pe interval
- Căutarea binară ca aplicație a metodei
- Rezolvarea a două probleme PbInfo
Metoda Greedy - caracteristici
Alegerea optimă locală, fără reconsiderarea deciziilor
Ce vei învăța:
- Principiul alegerii optime locale
- De ce nu se reconsideră deciziile
- Condițiile de aplicare a metodei
- Primul program Greedy în C++
Problema monedelor (restul minim)
Plata unui rest cu număr minim de monede
Ce vei învăța:
- Strategia greedy a monedei celei mai mari
- Urmărirea algoritmului pas cu pas
- Implementarea completă în C++
- Când greedy dă soluția optimă
Planificarea activităților (spectacolele)
Numărul maxim de activități compatibile, sortare după sfârșit
Ce vei învăța:
- Sortarea spectacolelor după ora de sfârșit
- Condiția de compatibilitate a două spectacole
- Implementarea completă în C++
- Rezolvarea problemei Spectacole
Probleme Greedy aplicative
Rucsacul fracționar și problema platoului
Ce vei învăța:
- Rucsacul fracționar: eficiența valoare/greutate
- Luarea de fracțiuni din obiecte
- Problema platoului: tăierea în bucăți
- Implementări complete în C++
Recapitulare și test
Tabel rezumativ D&I vs Greedy și probleme de recapitulare
Ce vei învăța:
- Compararea metodelor D&I și Greedy
- Recunoașterea tipului fiecărei probleme
- Recapitularea algoritmilor parcurși
- Test final de verificare a cunoștințelor
Probleme avansate Divide et impera
Numărarea inversiunilor și căutarea în tablou sortat și rotit
Ce vei învăța:
- Numărarea inversiunilor prin interclasare
- Căutarea într-un tablou sortat și rotit
- Complexitățile O(n log n) și O(log n)
- Programe C++ complete, stil BAC
Probleme avansate Greedy
Rucsacul fracționar cu sortare și problema platoului extins
Ce vei învăța:
- Rucsacul fracționar cu sortare prin interclasare
- Problema platoului extins
- Înmulțirile încrucișate pentru eficiență
- Programe C++ complete, stil BAC
Probleme combinate D&I și Greedy
Probleme care folosesc ambele metode într-un singur program
Ce vei învăța:
- Rolul fiecărei metode într-o problemă combinată
- Interclasare + umplere greedy
- Selecție greedy + verificare D&I
- Programe C++ complete, stil BAC
Recapitulare generală
Recapitularea modulului și tabel rezumativ D&I vs Greedy
Ce vei învăța:
- Recapitularea tuturor algoritmilor modulului
- Tabel rezumativ D&I vs Greedy
- Tabelul complexităților
- Reguli de aur și greșeli frecvente
Evaluare finală a modulului
Structura evaluării și probleme model rezolvate
Ce vei învăța:
- Structura evaluării: Subiectul I și Subiectul II
- Probleme model de teorie, 30 de puncte
- Problemă model D&I, 35 de puncte
- Problemă model Greedy, 35 de puncte
Resursele modulului
Competențe dobândite
Competența 1.3
Identificarea caracteristicilor strategiilor de rezolvare prin Divide et impera și Greedy
- Identificarea etapelor metodei Divide et impera
- Identificarea alegerii optime locale în metoda Greedy
- Asocierea algoritmilor studiați cu cele două metode
- Recunoașterea datelor de intrare, ieșire și manevră
Competența 2.3
Explicarea modului de lucru al metodelor Divide et impera și Greedy
- Explicarea descompunerii, rezolvării și combinării
- Explicarea de ce Greedy nu reconsideră deciziile
- Justificarea criteriului de alegere pentru fiecare problemă
- Compararea soluțiilor obținute cu cele clasice
Competența 3.3
Aplicarea metodelor Divide et impera și Greedy în rezolvarea de probleme
- Scrierea funcțiilor recursive specifice D&I
- Implementarea sortării prin interclasare și a căutării binare
- Implementarea algoritmilor greedy: monede, spectacole, rucsac
- Rezolvarea de probleme PbInfo în C++
Competența 4.3
Analiza avantajelor și limitărilor metodelor Divide et impera și Greedy
- Analiza complexității algoritmilor D&I
- Identificarea cazurilor în care Greedy nu dă soluția optimă
- Compararea eficienței a două variante de rezolvare
- Evaluarea corectitudinii soluțiilor obținute
Competența 5.3
Utilizarea instrumentelor de verificare și testare a algoritmilor
- Urmărirea pas cu pas a algoritmilor recursivi
- Testarea soluțiilor pe exemple date
- Verificarea cazurilor limită ale programelor
- Corectarea erorilor de logică în implementări