%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]] %% nav-fin %% # Atelier 2 - Professeur populaire Cet atelier résout un problème de choix par force brute : on énumère toutes les combinaisons et on garde la meilleure. Il s'appuie sur la section force brute du chapitre [[Code et Développement/Programmation/Optimisation de problème/01_Complexité algorithmique|Complexité algorithmique]]. Énoncé repris de la Battle Dev Hello Works de novembre 2018 (isograd.com). Niveau : ★★☆. ## Énoncé Un professeur donne des cours particuliers de 60 minutes. Chaque élève propose deux créneaux. Le professeur donne cours à un élève sur un seul de ses deux créneaux, ou ne le prend pas. Le professeur ne donne cours qu'à un élève à la fois. Il ne peut pas terminer un cours et en commencer un autre à la même minute : un cours qui finit à la minute 180 interdit un cours qui commence à la minute 180. Il faut calculer le nombre maximal d'élèves différents que le professeur peut prendre. ### Format des données - Ligne 1 : un entier N, de 3 à 8, le nombre d'élèves. - Lignes 2 à N + 1 : deux entiers de 0 à 1000, les débuts en minutes des deux créneaux de l'élève. Chaque créneau dure 60 minutes. La sortie est le nombre maximal d'élèves. ### Exemple ``` 5 205 300 210 370 290 380 120 305 390 110 ``` La réponse est 4. Une solution prend l'élève 1 de 205 à 265, l'élève 2 de 370 à 430, l'élève 3 de 290 à 350 et l'élève 4 de 120 à 180. Aucune combinaison ne permet de prendre les 5 élèves. ## Données Les cinq jeux de test sont chargés dans le dossier de Python de cette page. Le fichier `outputN.txt` contient la réponse attendue pour `inputN.txt`. ```sq-fichier nom: input1.txt --- 3 60 400 120 340 120 400 ``` ```sq-fichier nom: output1.txt --- 2 ``` ```sq-fichier nom: input2.txt --- 5 205 300 210 370 290 380 120 305 390 110 ``` ```sq-fichier nom: output2.txt --- 4 ``` ```sq-fichier nom: input3.txt --- 6 69 150 65 166 67 13 199 116 33 8 27 82 ``` ```sq-fichier nom: output3.txt --- 3 ``` ```sq-fichier nom: input4.txt --- 6 347 94 256 500 335 480 479 57 135 300 247 388 ``` ```sq-fichier nom: output4.txt --- 5 ``` ```sq-fichier nom: input5.txt --- 8 799 978 180 600 907 852 967 576 697 37 682 391 364 214 220 833 ``` ```sq-fichier nom: output5.txt --- 8 ``` ## Lire un fichier La fonction `lire_creneaux` renvoie la liste des créneaux d'un fichier, un tuple `(debut1, debut2)` par élève. Exécutez cette cellule avant les suivantes. ```sq-python def lire_creneaux(nom): with open(nom) as f: lignes = [ligne.strip() for ligne in f if ligne.strip()] N = int(lignes[0]) return [tuple(int(x) for x in l.split()) for l in lignes[1:N + 1]] def lire_sortie(nom): with open(nom) as f: return int(f.read().strip()) T = lire_creneaux("input1.txt") print(T) #--- sortie [(60, 400), (120, 340), (120, 400)] ``` ## Question 1 : énumérer les combinaisons Chaque élève a deux créneaux. Avec N élèves, il y a donc 2^N façons de choisir un créneau par élève. On obtient toutes ces façons en comptant en base 2 de 0 à 2^N − 1. Avec N = 3, les nombres 000, 001, 010, …, 111 donnent les huit choix. Le chiffre de rang j indique le créneau retenu pour l'élève j : 0 pour le premier, 1 pour le second. L'instruction `format(i, '03b')` écrit `i` en binaire sur 3 chiffres : `format(5, '03b')` vaut `'101'`. Écrivez `combinaisons(T)`, qui renvoie la liste des 2^N listes de débuts de créneaux. ```sq-python def combinaisons(T): N = len(T) resultat = [] # à compléter return resultat for c in combinaisons(T): print(c) #--- correction def combinaisons(T): N = len(T) resultat = [] for i in range(2 ** N): b = format(i, '0' + str(N) + 'b') resultat.append([T[j][int(b[j])] for j in range(N)]) return resultat for c in combinaisons(T): print(c) #--- tests assert len(combinaisons(T)) == 8, "3 élèves donnent 2^3 = 8 combinaisons" assert combinaisons(T)[0] == [60, 120, 120], "la première combinaison prend le premier créneau de chaque élève" assert combinaisons(T)[5] == [400, 120, 400], "5 s'écrit 101 : second, premier, second créneau" assert len(combinaisons(lire_creneaux("input5.txt"))) == 256, "8 élèves donnent 256 combinaisons" #--- sortie [60, 120, 120] [60, 120, 400] [60, 340, 120] [60, 340, 400] [400, 120, 120] [400, 120, 400] [400, 340, 120] [400, 340, 400] ``` Le module `itertools` produit les mêmes combinaisons : `itertools.product(*T)` renvoie un tuple de débuts pour chaque choix. ## Question 2 : compter les cours d'une combinaison Une combinaison fixe un début par élève. Certains créneaux se chevauchent. Il faut garder le plus grand nombre de créneaux sans chevauchement. Tous les créneaux durent 60 minutes. On trie les débuts dans l'ordre croissant. On prend le premier créneau, puis chaque créneau qui commence strictement après la fin du dernier créneau pris. Ce choix glouton est optimal, car le créneau qui commence le plus tôt est aussi celui qui finit le plus tôt. Écrivez `nb_cours(debuts)`. ```sq-python def nb_cours(debuts): nombre = 0 # à compléter return nombre print(nb_cours([60, 120, 120])) print(nb_cours([205, 370, 290, 120, 110])) #--- correction def nb_cours(debuts): nombre = 0 fin = None for d in sorted(debuts): if fin is None or d > fin: nombre += 1 fin = d + 60 return nombre print(nb_cours([60, 120, 120])) print(nb_cours([205, 370, 290, 120, 110])) #--- tests assert nb_cours([60, 120, 120]) == 1, "le cours de 60 finit à 120 : aucun cours ne peut commencer à 120" assert nb_cours([205, 370, 290, 120, 110]) == 4, "110 et 120 se chevauchent, les quatre autres débuts sont compatibles" assert nb_cours([120, 181]) == 2, "un cours qui commence à 181 suit un cours fini à 180" #--- sortie 1 4 ``` ## Question 3 : garder la meilleure combinaison Écrivez `resoudre(nom)`, qui renvoie le plus grand nombre de cours sur toutes les combinaisons. Vérifiez les cinq jeux de test. ```sq-python def resoudre(nom): T = lire_creneaux(nom) # à compléter return 0 for k in range(1, 6): print(k, resoudre("input" + str(k) + ".txt"), lire_sortie("output" + str(k) + ".txt")) #--- correction def resoudre(nom): T = lire_creneaux(nom) return max(nb_cours(c) for c in combinaisons(T)) for k in range(1, 6): print(k, resoudre("input" + str(k) + ".txt"), lire_sortie("output" + str(k) + ".txt")) #--- tests assert resoudre("input1.txt") == 2, "input1.txt donne 2" assert resoudre("input2.txt") == 4, "input2.txt donne 4" assert resoudre("input3.txt") == 3, "input3.txt donne 3" assert resoudre("input4.txt") == 5, "input4.txt donne 5" assert resoudre("input5.txt") == 8, "input5.txt donne 8" #--- sortie 1 2 2 2 4 4 3 3 3 4 5 5 5 8 8 ``` ## À retenir - La force brute examine les 2^N choix de créneaux. Avec N ≤ 8, cela fait au plus 256 combinaisons. - Chaque combinaison est traitée par un tri et un parcours, en O(N log N). Le calcul total est en O(2^N × N log N). - Ce temps double à chaque élève ajouté. Avec 1000 élèves, la force brute n'est plus possible : c'est l'objet de l'[[Code et Développement/Programmation/Optimisation de problème/Atelier 3 - Professeur débordé|atelier 3]]. %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]] %% nav-fin %%