25-NSIJ1ME1-2

  Énoncé   Sujet

1. tache1 = Tache(1, 'Répondre aux e-mails', 45)
   tache2 = Tache(2, 'Ranger sa chambre', 60)
   

2. def avancer(self, n):
       self.duree_restante -= n
   

3. def est_terminee(self):
       return self.duree_restante <= 0
   

4. [début] (<t3>, 4) (<t7>, 4) (<t1>, 3) (<t2>, 3) (<t6>, 2) (<t4>, 1) (<t5>, 1) [fin]

5. L'instruction f.defiler()[0] renvoie <t3> et modifie ainsi la file :

   [début] (<t1>, 3) (<t2>, 3) (<t4>, 1) (<t5>, 1) [fin]

6. L'instruction f.examiner()[1] renvoie 4 sans modifier la file :

   [début] (<t3>, 4) (<t1>, 3) (<t2>, 3) (<t4>, 1) (<t5>, 1) [fin]

7. def ajouter_file_prio(f, t, p):
       f_aux = File()
       while not f.est_vide() and f.examiner()[1] >= p:
           f_aux.enfiler(f.defiler())
       f_aux.enfiler((t, p))
       while not f.est_vide():
           f_aux.enfiler(f.defiler())
       while not f_aux.est_vide():
           f.enfiler(f_aux.defiler())
   

8. Si la classe File est correctement implémentée avec des opérations defiler et enfiler en temps constant \(O(1)\), puisque chaque élément de la file f est enfilé et défilé deux fois, alors le coût d'exécution temporel de ajouter_file_prio est en \(\boxed{O(m)}\) où \(m\) est le nombre d'éléments dans f.

9. 

10. def planning(f):
        liste_taches = []
        while not f.est_vide():
            t, p = f.defiler()
            liste_taches.append(t)
            t.avancer(25)
            if not t.est_terminee():
                ajouter_file_prio(f, t, p)
        return liste_taches