Tematică științifică · Capitolul 3
Metode de programare
- 1 Metoda greedy Descrierea metodei greedy, alegerea locală optimă, condițiile de aplicare, demonstrarea corectitudinii și aplicații clasice: problema rucsacului în varianta continuă și problema spectacolelor. ✓ GRATUIT
- 2 Metoda backtracking Metoda backtracking după planul de idei cerut la Titularizare 2019: principiul și oportunitatea utilizării, modelul general în variantă iterativă și recursivă, apoi cele trei aplicații clasice — reginele, comis-voiajorul și labirintul — fiecare cu enunț, descriere în limbaj natural, cod și o parcurgere cu valori.
- 3 Metoda divide et impera Descrierea metodei divide et impera, cele trei etape, condițiile de aplicare și oportunitatea utilizării, complexitatea și aplicațiile din programa de examen: problema turnurilor din Hanoi, sortarea prin interclasare și sortarea rapidă.
- 4 Metoda programării dinamice Descrierea metodei programării dinamice, principiul optimalității, etapele de rezolvare, oportunitatea utilizării, complexitatea și aplicațiile din programa de examen: subșirul crescător de lungime maximă, problema rucsacului în variantă discretă și subșirul comun de lungime maximă.
- 5 Generarea elementelor combinatoriale Cele șase generări cerute de programă — permutări, aranjamente, combinări, submulțimi, partițiile unui număr natural și partițiile unei mulțimi — pe același model backtracking, fiecare cu descrierea etapelor, complexitatea și o problemă rezolvată.