GÉNÉRALITÉS SUR LES ALGORITHMES

1 - Terminaison


?

def ?
?

def ?
?


2 - Invariants de boucles, correction


?

def ?
?

def ?
?


3 - Complexité temporelle


?

def MeilleurNumérateur(x, q) :
    p = int(q * x)
    if abs(x - (p + 1)/q) < abs(x - p/q) :
        return p + 1
    else :
        return p
def PlusProcheFraction(x, q_max) :
    meilleur_q = 1 ; meilleur_p = MeilleurNumérateur(x, 1)
    err = abs(x - meilleur_p / meilleur_q)
    for q in range(2, q_max) :
        p = MeilleurNumérateur(x, q) ; e = abs(x - p/q)
        if e < err :
            meilleur_p = p ; meilleur_q = q ; err = e
    return (meilleur_p, meilleur_q)

?

def IndiceMinimumPartiel(L, a, b) :
def TriParSélections(L) :

?

def Dichotomie(f, a, b, ε) :
    c = (a + b) / 2
    if b - a < 2 * ε :
        return c
    else :
        if f(a) * f(c) <= 0 :
            return Dichotomie(f, a, c, ε)
        else :
            return Dichotomie(f, c, b, ε)

?

def ?
?

def ?
?


4 - Complexité spatiale


?

def ?
?

def ?
?