Metoda Greedy

5 Óntrebri | Total Attempts: 155

SettingsSettingsSettings
Metoda Greedy

Testul se adreseaza elevilor de clasa a XI, profil matematica-informatica, intensiv informatica sau pentru pregatirea examenului de bacalaureat, disciplina informatica


Questions and Answers
  • 1. 
    O singura statie de servire (procesor, pompa de benzina etc) trebuie sa satisfaca cererile a n clienti. Timpul de servire necesar fiecarui client este cunoscut in prealabil: pentru clientul i este necesar un timp ti, 1 ‚ȧ i ‚ȧ n. Daca dorim sa minimizam timpul total de asteptare atunci 
    • A. 

      Selectam intotdeauna clientul cu timpul maxim de servire din multimea de clienti ramasa

    • B. 

      Selectam intotdeauna clientul cu timpul minimde servire din multimea de clienti ramasa

  • 2. 
    Se considera graful ponderat din imaginea alaturata: Ordinea de selectare a muchiilor in vederea obtinerii unui arbore partial de cost minim, prin utilizarea strategiei Greedy , este:
    • A. 

      (1, 2), (2, 3), (1, 4), (4, 5), (4, 7), (6, 7)

    • B. 

      (1, 2), (2, 3), (6, 7), (4, 5), (2, 5), (1, 4)

    • C. 

      (5, 6), (5, 7), (3, 6), (2, 4), (3, 5), (1, 4)

  • 3. 
    Managerul artistic al unui festival trebuie sa selecteze o multime cat mai ampla de spectacole care pot fi jucate in singura sala pe care o are la dispozitie. Stiind ca i s-au propus 8 spectacole si pentru fiecare spectacol i-a fost anuntat intervalul in care se va desfasura: 1: [10, 15) 2: [2, 4) 3: [7, 9) 4: [21, 25) 5: [10, 12) 6: [12, 15) 7: [7, 8) 8: [20, 27) Care spectacole trebuie selectate pentru a permite spectatorilor sa vizioneze un numar cat mai mare de spectacole?
    • A. 

      1, 8

    • B. 

      2, 4, 5, 6, 7

    • C. 

      2, 3, 1, 8

    • D. 

      2, 3, 5, 6, 8

  • 4. 
    Se considera ca trebuie transportate cu ajutorul unui rucsac de capacitate 10kg, obiecte cu greutatile 8kg, 6kg si 4kg. Pentru fiecare kg transportat castigul obtinut este 1 LEU. Stiind ca obiectele se incarca integral in sac si ca se poate alege cel mult un obiect din fiecare tip, atunci solutia optima este (se noteaza prin 1 - selectarea obiectului, iar prin 0 - neselectarea acestuia):
    • A. 

      (1, 0, 0)

    • B. 

      (0, 1, 1)

    • C. 

      (1, 1, 1)

    • D. 

      (1, 1, 0)

  • 5. 
    Se doreste planificarea optimala (penalizarea totala sa fie minima) a 7 lucrari, fiecare lucrare i fiind data prin termenul de predare t[i] si penalizarea p[i] care se plateste in cazul in care lucrarea nu este finalizata la timp. Se presupune ca pentru executarea unei lucrari este necesara o unitate de timp si ca nu se pot executa doua lucrari in acelasi timp. Se considera datele de intrare: i t[i] p[i] 1 4 50 2 3 40 3 2 60 4 3 20 5 4 70 6 2 10 7 1 130 Care este penalizarea totala minima ce se poate obtine?