Întrebări

Nivel 1

  1. Ce sunt problemele de optimizare?
  2. Ce condiție trebuie să îndeplinească soluția optimă?
  3. Ce deosebire este între optimizarea continuă și cea discretă?
  4. In ce fel de probleme se foloseste tehnica Greedy?
  5. In ce consta tehnica Greedy?
  6. Care este forma generală a algoritmului Greedy?
  7. Dece sortarea prin selecție poate fi considerată ca o aplicație a metodei Greedy?
  8. Cum se formulează varianta continuă a problemei rucsacului?
  9. Cum se rezolvă varianta continuă a problemei rucsacului?
  10. Ce este arborele de acoperire de cost minim?
  11. Care este principiul algoritmului lui Kruskal?
  12. Care este principiul algoritmului lui Prim?
  13. La ce se folosește algoritmul lui Dijkstra?
  14. Ce structuri auxiliare se folosesc în algoritmul lui Dijkstra?
  15. Care este principiul algoritmului lui Dijkstra?
  16. In ce fel de probleme se folosește tehnica programării dinamice?
  17. In ce constă principala deosebire dintre tehnica programarii dinamice si tehnica Greedy?
  18. Cum se formulează principiul optimului?
  19. Cum se formulează principiul minimului și ce legătură are cu principiul optimului?

Nivel 2

  1. Care este algoritmul folosit in tehnica Greedy (varianta continuă)?
  2. Ce fel de soluție se obține, dacă se aplică metoda Greedy în varianta discretă a problemei rucsacului?
  3. Se vor determina prin tehnica Greedy obiectele selectate dintr-o multime data, astfel incat profitul sa fie maxim.
  4. Se dă un graf. Se cere să se determine arborele de acoperire de cost minim prin algoritmul lui Kruskal.
  5. Poate fi aplicat algoritmul lui Kruskal la grafuri neconexe? Ce se obține?
  6. Formulați în pseudocod algoritmul lui Prim.
  7. Se dă un graf. se cere să se determine arborele de acoperire de cost minim prin algoritmul lui Prim.
  8. Ce se obține dacă se aplică algoritmul lui Prim la un graf neconex?
  9. Se dă un graf. Se cere să se determine prin algoritmul lui Dijkstra cea mai scurtă cale între două vârfuri date.
  10. Care sunt caracteristicile problemelor de programare dinamică?
  11. Cum se determină prin metoda programării dinamice calea cea mai scurtă între două vârfuri ale unui graf orientat?
  12. Se dă un graf orientat. Se cere să se determine prin programare dinamică cea mai scurtă cale între două vârfuri date.
  13. Cum se determină prin metoda programării dinamice ordinea optimă a calculării unui produs de matrici?
  14. Se dă un produs de matrici. Se cere să se determine ordinea optimă de efectuasre a calculelor și să se compare numărul de înmulțiri făcute în acest caz, cu cel care s-ar efectua în cazul efectuării înmulțirilor de la stânga la dreapta.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați