Algorithmique et programmation (Python)

On considère la suite définie par u₀ = 10 et, pour tout n, uₙ₊₁ = 0,5 uₙ + 4.
a) Écris une fonction terme(n) qui renvoie uₙ.
b) Calcule u₁, u₂ et u₃ à la main.
c) Écris une fonction seuil() (avec une boucle while) renvoyant le plus petit entier n tel que uₙ < 8,05.
d) Détermine cette valeur et interprète le comportement de la suite.

On veut approcher une solution de l'équation x³ + x − 5 = 0 dans l'intervalle [1 ; 2] par dichotomie. On pose :
def f(x):
return x**3 + x - 5
a) Vérifie que f(1) et f(2) sont de signes contraires. Que peut-on en déduire ?
b) Effectue deux étapes de dichotomie à la main (donne les milieux et les nouveaux intervalles).
c) Écris une fonction dicho(n) qui renvoie le milieu de l'intervalle obtenu après n étapes.

On approche l'aire sous la courbe de f(x) = x² entre 0 et 1 par la méthode des rectangles (points à gauche), avec n rectangles :
def f(x):
return x**2
def rectangles(n):
s = 0
p = 1 / n
for k in range(n):
s = s + f(k * p) * p
return s
a) Que vaut p, et que représente-t-il ?
b) Calcule rectangles(4) à la main.
c) Vers quelle valeur exacte cette somme tend-elle quand n devient grand ?

Un QCM comporte 10 questions ; à chacune on répond au hasard parmi 4 propositions, donc juste avec probabilité p = 0,25. On note X le nombre de bonnes réponses.
a) Quelle loi suit X ? Donne son espérance et son écart type.
b) Écris une fonction simul() qui simule une valeur de X.
c) Écris un programme qui, à partir de 10000 appels à simul(), estime la probabilité P(X ≥ 5).

a) Écris une fonction est_premier(n) qui renvoie True si l'entier n (avec n ≥ 2) est premier, False sinon.
b) Déroule est_premier(21) et est_premier(23) en expliquant.
c) À l'aide de est_premier, écris une instruction construisant la liste des nombres premiers inférieurs à 30.

On additionne les inverses des carrés : S(n) = 1 + $\frac{1}{4}$ + $\frac{1}{9}$ + … + $\frac{1}{n^{2}}$.
def S(n):
s = 0
for k in range(1, n+1):
s = s + 1 / (k*k)
return s
a) Calcule S(3) sous forme de fraction, puis en décimal (arrondi au millième).
b) Écris une fonction seuil() renvoyant le plus petit n tel que S(n) > 1,5.
c) Sachant que S(n) se rapproche de $\frac{\pi ^{2}}{6}$ quand n grandit, cette somme peut-elle un jour dépasser 2 ?

Une liste L est triée dans l'ordre croissant. On y cherche une valeur v par dichotomie :
def recherche(L, v):
a = 0
b = len(L) - 1
while a <= b:
m = (a + b) // 2
if L[m] == v:
return True
elif L[m] < v:
a = m + 1
else:
b = m - 1
return False
On prend L = [2, 5, 8, 11, 14, 17, 20].
a) Déroule recherche(L, 14) en indiquant a, b et m à chaque étape.
b) Déroule recherche(L, 9).
c) Combien d'étapes au maximum faut-il pour une liste de 7 éléments ? Et pour 1000 éléments ?

On lance une pièce truquée qui tombe sur Pile avec probabilité p = 0,6, n fois, et on note la fréquence de Pile :
import random
def frequence(n):
s = 0
for i in range(n):
if random.random() < 0.6:
s = s + 1
return s / n
a) Pour n = 50, quelle est l'espérance de S = nombre de Piles ?
b) Vers quelle valeur la fréquence s/n tend-elle quand n devient très grand ? Quel résultat le justifie ?
c) Écris un code qui appelle frequence(50) mille fois et calcule la moyenne des fréquences obtenues. Autour de quelle valeur devrait-elle se situer ?

a) Écris une fonction pgcd(a, b) qui calcule le plus grand commun diviseur de deux entiers positifs par l'algorithme d'Euclide (restes successifs).
b) Déroule pgcd(48, 36) en détaillant les étapes.
c) Utilise ce résultat pour rendre la fraction $\frac{36}{48}$ irréductible.

La suite de Syracuse part d'un entier N : tant qu'on n'a pas atteint 1, si le terme est pair on le divise par 2, sinon on le remplace par 3 fois lui-même plus 1. On compte le nombre d'étapes (le « temps de vol ») :
def vol(N):
n = N
c = 0
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
c = c + 1
return c
a) Déroule la suite pour N = 6 et donne la valeur renvoyée.
b) Fais de même pour N = 3.
c) Que renvoie vol(1) ? Explique.