TP Python – Rapports de coût et durées

BTS SIO SISR 2e année – Pour aller plus loin – S13

Note

Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.

Exercice A – Ratio de doublement

Écris ratio_doublement(f, n) qui renvoie f(2 * n) / f(n).

J'anticipe. Que vaut ce ratio pour f(n) = n ? Pour f(n) = n² ?

###

Lancer assert ratiopy-unddoublement(lambda n: n, 10) == 2.0bksl-nlassert ratiopy-unddoublement(lambda n: n py-str n, 10) == 4.0bksl-nlassert ratiopy-unddoublement(lambda n: 1, 50) == 1.0bksl-nlassert abs(ratiopy-unddoublement(lambda n: n py-strpy-str 3, 7) - 8) < 1e-9bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def ratiopy-unddoublement(f, n):bksl-nl """Renvoie f(2n) / f(n)."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice B – Estimer la classe

Écris estime_ordre(f) qui calcule le ratio de doublement en n = 64 et renvoie une chaîne : "O(1)" si ratio < 1,05 ; "O(log n)" si < 1,5 ; "O(n)" si < 2,1 ; "O(n log n)" si < 3 ; "O(n^2)" si < 5 ; "O(n^3)" si < 9 ; sinon "O(2^n)". C'est une heuristique : elle ne prouve rien.

J'anticipe. Calcule à la main les ratios en 64 pour n, n log2 n, log2 n.

###

Lancer assert estimepy-undordre(lambda n: 7) == "O(1)"bksl-nlassert estimepy-undordre(lambda n: py-undpy-undimportpy-undpy-und('math').log2(n)) == "O(log n)"bksl-nlassert estimepy-undordre(lambda n: 3 py-str n + 5) == "O(n)"bksl-nlassert estimepy-undordre(lambda n: n py-str py-undpy-undimportpy-undpy-und('math').log2(n)) == "O(n log n)"bksl-nlassert estimepy-undordre(lambda n: n py-str n / 10) == "O(n^2)"bksl-nlassert estimepy-undordre(lambda n: n py-strpy-str 3) == "O(n^3)"bksl-nlassert estimepy-undordre(lambda n: 2 py-strpy-str n) == "O(2^n)"bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def estimepy-undordre(f):bksl-nl """Classe estimee d'apres le ratio f(128)/f(64)."""bksl-nl ...bksl-nlbksl-nl

---

---

Je comprends. Trouve une fonction que cette heuristique classe mal (indice : une constante grande devant un petit terme).

Exercice C – Opérations en jours

Écris duree_jours(ops, par_seconde) qui renvoie la durée en jours (1 jour = 86 400 s) de ops opérations à par_seconde opérations par seconde.

J'anticipe. Reprends l'exercice 6 : à quoi sert l'hypothèse de vitesse ?

###

Lancer assert abs(dureepy-undjours(86400, 1) - 1) < 1e-9bksl-nlassert abs(dureepy-undjours(499999500000, 1e6) - 5.78703) < 1e-4bksl-nlassert abs(dureepy-undjours(2 py-strpy-str 60, 1e9) - 13343.9) < 0.1bksl-nlassert dureepy-undjours(0, 1e9) == 0bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def dureepy-undjours(ops, parpy-undseconde):bksl-nl """Duree en jours."""bksl-nl ...bksl-nlbksl-nl

---

---

Exercice D – Facteur de croissance

Écris facteur_croissance(f, a, b) qui renvoie f(b) / f(a). Utilise-la pour retrouver le rapport 13,33 de l'exercice 5 avec f(n) = n * log2(n).

###

Lancer assert facteurpy-undcroissance(lambda n: n, 10, 100) == 10.0bksl-nlassert facteurpy-undcroissance(lambda n: n py-str n, 10, 100) == 100.0bksl-nlassert abs(facteurpy-undcroissance(lambda n: n py-str py-undpy-undimportpy-undpy-und('math').log2(n), 1000, 10000) - 13.33) < 0.01bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

def facteurpy-undcroissance(f, a, b):bksl-nl """Renvoie f(b) / f(a)."""bksl-nl ...bksl-nlbksl-nl

---

---