Durée conseillée : 90 minutes. Réussite à 60 %. Les ressources du cours sont autorisées ; l'IA peut aider à comprendre, mais tu dois savoir expliquer chaque réponse.
Partie 1 — Questions (40 points)
1. On compte les opérations plutôt que les secondes parce que :
- A. les secondes dépendent de la machine
- B. les opérations sont plus rapides
- C. c'est une règle de Python
2. 5n² + 30n + 100 s'écrit en Big O :
- A. O(n)
- B. O(100)
- C. O(n²)
3. Deux boucles imbriquées de n tours donnent :
- A. O(n)
- B. O(n²)
- C. O(2n)
4. Pourquoi fib(n) récursif naïf est-il lent ?
- A. il recalcule les mêmes sous-problèmes
- B. il utilise des listes
- C. il est écrit en Python
5. liste.pop(0) coûte :
- A. O(1)
- B. O(log n)
- C. O(n)
6. Aucun tri par comparaisons ne fait mieux en général que :
- A. O(n)
- B. O(n log n)
- C. O(log n)
7. Si T(2n)/T(n) ≈ 4, la croissance est :
- A. quadratique
- B. linéaire
- C. constante
8. Avant d'optimiser, il faut :
- A. réécrire en C
- B. ajouter un cache
- C. profiler pour trouver le goulot
✅ Réponses de la partie 1
- A
- C
- B
- A
- C
- B
- A
- C
Partie 2 — Problème pratique (40 points)
On te donne cette fonction qui doit renvoyer les k mots les plus fréquents d'un texte :
def top_mots(texte, k):
mots = texte.split()
uniques = []
for m in mots:
if m not in uniques:
uniques.append(m)
comptes = [(m, mots.count(m)) for m in uniques]
comptes.sort(key=lambda c: (-c[1], c[0]))
return comptes[:k]
- Donne son Big O et identifie les coûts cachés.
- Écris une version plus rapide qui renvoie le même résultat.
- Vérifie l'équivalence sur 300 textes aléatoires.
- Mesure les deux pour 4 tailles et estime l'exposant de chacune.
Partie 3 — Justification (20 points)
Rédige un mini-rapport de 10 lignes : cause de la lenteur, correction, preuves (équivalence et mesures), limites de ta conclusion.
Barème
| Partie | Points |
|---|---|
| 1 — Questions | 40 |
| 2 — Problème pratique | 40 |
| 3 — Justification | 20 |
HEF-030 — Complexité

