Les Listes

a) [1, 2, 3, [4, 5]]     append ajoute UN element (ici une liste)
b) [1, 2, 3, 4, 5]       extend ajoute chaque element
c) [1, 9, 2, 3]
d) [1, 2, 3, 4]          += equivaut a extend sur une liste
e) None                  reverse renvoie None
f) [1, 2, 3]             u et t designent le MEME objet
g) [1, 7, 8, 3]          une tranche peut etre remplacee par un nombre different d'elements
h) [2]                   on supprime les indices 0 et 2

def miroir(t):
    """Nouvelle liste contenant les elements de t en ordre inverse. Theta(n)."""
    res = []
    for i in range(len(t) - 1, -1, -1):
        res.append(t[i])
    return res

def renverse_en_place(t):
    """Renverse t en place. Theta(n) temps, Theta(1) espace."""
    g, d = 0, len(t) - 1
    while g < d:
        t[g], t[d] = t[d], t[g]
        g += 1
        d -= 1

def est_palindrome(t):
    """t se lit-elle de la meme facon dans les deux sens ?"""
    g, d = 0, len(t) - 1
    while g < d:
        if t[g] != t[d]:
            return False
        g += 1
        d -= 1
    return True

def rotation(t, k):
    """Nouvelle liste decalee de k crans vers la gauche (k quelconque dans Z)."""
    n = len(t)
    if n == 0:
        return []
    k %= n                       # gere k negatif ou k > n
    return [t[(i + k) % n] for i in range(n)]

assert miroir([1, 2, 3]) == [3, 2, 1]
t = [1, 2, 3]; renverse_en_place(t); assert t == [3, 2, 1]
assert est_palindrome([1, 2, 1]) and not est_palindrome([1, 2])
assert rotation([1, 2, 3, 4], 1) == [2, 3, 4, 1]
assert rotation([1, 2, 3, 4], -1) == [4, 1, 2, 3]
assert rotation([1, 2, 3, 4], 6) == [3, 4, 1, 2]

Le k %= n est essentiel : il ramene tout decalage a un decalage equivalent dans \(\{0,\dots,n-1\}\), y compris pour \(k\) negatif grace a la convention de signe du modulo Python.

def fusion(t, u):
    """Fusionne deux listes triees. Theta(n + m)."""
    res = []
    i = j = 0
    while i < len(t) and j < len(u):
        if t[i] <= u[j]:
            res.append(t[i]); i += 1
        else:
            res.append(u[j]); j += 1
    res.extend(t[i:])            # au plus une des deux est non vide
    res.extend(u[j:])
    return res

def intersection_triee(t, u):
    """Elements communs a deux listes triees, sans repetition. Theta(n + m)."""
    res = []
    i = j = 0
    while i < len(t) and j < len(u):
        if t[i] < u[j]:
            i += 1
        elif t[i] > u[j]:
            j += 1
        else:
            if not res or res[-1] != t[i]:    # eviter les doublons
                res.append(t[i])
            i += 1; j += 1
    return res

assert fusion([1, 3, 5], [2, 3, 8]) == [1, 2, 3, 3, 5, 8]
assert intersection_triee([1, 2, 2, 5], [2, 3, 5, 5]) == [2, 5]

1. Chaque tour de boucle consomme exactement un element de \(t\) ou de \(u\) : il y a donc au plus \(n+m\) tours, soit \(\Theta(n+m)\). C'est optimal (il faut lire toutes les donnees). Cette fonction est le coeur du tri fusion (chapitre 12).

3. L'approche par ensembles coute \(\Theta(n+m)\) en moyenne mais ne suppose pas les listes triees, ce qui est plus general. En revanche elle exige des elements hachables, consomme \(\Theta(n+m)\) memoire supplementaire, et son cout est \(\Theta(nm)\) dans le pire cas theorique (collisions). La fusion, elle, est deterministe, n'exige qu'une relation d'ordre, et se generalise a des donnees trop volumineuses pour tenir en memoire (tri externe).

def deuxieme_max(t):
    """Deuxieme plus grande valeur distincte de t, ou None. Un seul parcours."""
    m1 = m2 = None
    for x in t:
        if m1 is None or x > m1:
            m1, m2 = x, m1
        elif x != m1 and (m2 is None or x > m2):
            m2 = x
    return m2

def k_plus_grands(t, k):
    """Les k plus grandes valeurs de t, en ordre decroissant."""
    return sorted(t, reverse=True)[:k]

assert deuxieme_max([3, 7, 7, 1]) == 3
assert deuxieme_max([5, 5, 5]) is None
assert deuxieme_max([]) is None
assert k_plus_grands([3, 1, 4, 1, 5], 2) == [5, 4]

3. Trois strategies :

Le seuil entre les deux premieres est \(k \approx \log_2 n\) : pour \(n = 10^6\), \(\log_2 n \approx 20\). Au-dela d'une vingtaine de valeurs cherchees, mieux vaut trier.

import heapq
assert heapq.nlargest(2, [3, 1, 4, 1, 5]) == [5, 4]

def pascal(n):
    """n+1 premieres lignes du triangle de Pascal."""
    tri = [[1]]
    for i in range(1, n + 1):
        prec = tri[-1]
        tri.append([1] + [prec[k-1] + prec[k] for k in range(1, i)] + [1])
    return tri

T = pascal(20)
for n, ligne in enumerate(T):
    assert sum(ligne) == 2**n

2. Demonstration. Par la formule du binome de Newton avec \(a = b = 1\) : \[ 2^n = (1+1)^n = \sum_{k=0}^{n}\binom{n}{k}1^k1^{n-k} = \sum_{k=0}^{n}\binom{n}{k}. \] Interpretation combinatoire : le nombre de parties d'un ensemble a \(n\) elements vaut \(2^n\), et l'on peut les compter en classant selon leur cardinal \(k\).

# 3. crosse de hockey
from math import comb
for k in range(6):
    for n in range(k, 15):
        assert sum(comb(i, k) for i in range(k, n+1)) == comb(n+1, k+1)
print("crosse de hockey verifiee")

Preuve : par recurrence sur \(n\), en utilisant la relation de Pascal \(\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}\).

def binomial(n, k):
    """C(n,k) en Theta(min(k, n-k)) multiplications, en arithmetique exacte."""
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)                 # symetrie : C(n,k) = C(n,n-k)
    res = 1
    for i in range(k):
        res = res * (n - i) // (i + 1)     # la division tombe TOUJOURS juste
    return res

for n in range(30):
    for k in range(n + 1):
        assert binomial(n, k) == comb(n, k)

La division entiere est exacte a chaque etape car apres \(i+1\) tours, res vaut \(\binom{n}{i+1}\), qui est entier. Calculer fact(n)//(fact(k)*fact(n-k)) donnerait le meme resultat mais manipulerait des entiers enormes : pour \(n = 1000\), \(n!\) a plus de 2500 chiffres.

def affiche(h):
    """Dessine l'histogramme, la plus haute barre en haut."""
    for niveau in range(max(h), 0, -1):
        print("".join("#" if x >= niveau else " " for x in h))

def plus_grand_rectangle_n2(h):
    """Aire maximale d'un rectangle inscrit. Theta(n^2)."""
    n, meilleur = len(h), 0
    for i in range(n):
        hauteur = h[i]
        for j in range(i, n):
            hauteur = min(hauteur, h[j])       # hauteur du rectangle sur [i, j]
            meilleur = max(meilleur, hauteur * (j - i + 1))
    return meilleur

assert plus_grand_rectangle_n2([2, 1, 5, 6, 2, 3]) == 10
affiche([2, 1, 5, 6, 2, 3])

   #
  ##
  ##
  ##
# ## #
######

4. Version lineaire. Pour chaque barre \(i\), le plus grand rectangle dont \(i\) est la barre la plus basse s'etend jusqu'a la premiere barre strictement plus basse a gauche et a droite. On determine ces deux frontieres en un seul parcours a l'aide d'une pile d'indices a hauteurs croissantes : quand une barre plus basse arrive, on depile toutes les barres plus hautes, et pour chacune la frontiere droite est l'indice courant.

def plus_grand_rectangle(h):
    """Aire maximale d'un rectangle inscrit. Theta(n) grace a une pile."""
    pile, meilleur = [], 0
    for i, x in enumerate(h + [0]):        # sentinelle 0 pour vider la pile
        while pile and h[pile[-1]] >= x:
            hauteur = h[pile.pop()]
            gauche = pile[-1] + 1 if pile else 0
            meilleur = max(meilleur, hauteur * (i - gauche))
        pile.append(i)
    return meilleur

import random
for _ in range(500):
    t = [random.randint(0, 9) for _ in range(random.randint(1, 10))]
    assert plus_grand_rectangle(t) == plus_grand_rectangle_n2(t)
print("version lineaire validee")

Chaque indice est empile et depile au plus une fois : le cout total est \(\Theta(n)\), bien que la boucle interne puisse etre longue a un tour donne. C'est un raisonnement d'analyse amortie.

def tri_par_denombrement(t, k=None):
    """Trie une liste d'entiers de {0,...,k}. Theta(n + k)."""
    if not t:
        return []
    if k is None:
        k = max(t)
    compte = [0] * (k + 1)
    for x in t:                       # Theta(n)
        compte[x] += 1
    res = []
    for v in range(k + 1):            # Theta(k)
        res.extend([v] * compte[v])   # Theta(n) au total
    return res

import random
for _ in range(300):
    t = [random.randint(0, 20) for _ in range(random.randint(0, 30))]
    assert tri_par_denombrement(t) == sorted(t)

2. Temps \(\Theta(n+k)\), memoire \(\Theta(k)\). C'est lineaire quand \(k = O(n)\), donc strictement meilleur que \(\Theta(n\log n)\).

3. Non. La borne \(\Omega(n\log n)\) ne vaut que pour les algorithmes dont la seule operation autorisee sur les donnees est la comparaison de deux elements. Ici on utilise les valeurs comme des indices : c'est une information supplementaire sur la nature des donnees, qui echappe au modele. Le cout est de supposer les cles entieres et bornees, et de payer \(\Theta(k)\) memoire — pour \(k = 10^{12}\) la methode est inutilisable.

def tri_denombrement_stable(paires, k):
    """Trie une liste de (cle, valeur) sur la cle, de facon STABLE. Theta(n + k)."""
    compte = [0] * (k + 1)
    for cle, _ in paires:
        compte[cle] += 1
    # positions de depart de chaque cle (sommes prefixes)
    debut, s = [0] * (k + 1), 0
    for v in range(k + 1):
        debut[v] = s
        s += compte[v]
    res = [None] * len(paires)
    for p in paires:                  # parcours dans l'ordre : stabilite garantie
        res[debut[p[0]]] = p
        debut[p[0]] += 1
    return res

p = [(2, "a"), (1, "b"), (2, "c"), (0, "d"), (1, "e")]
assert tri_denombrement_stable(p, 2) == [(0,"d"), (1,"b"), (1,"e"), (2,"a"), (2,"c")]

La stabilite vient du parcours final dans l'ordre initial, chaque element etant place a la premiere position encore libre de sa cle. C'est cette stabilite qui permet de chainer plusieurs tris par denombrement pour obtenir le tri par base (radix sort), en \(\Theta(d(n+b))\) pour des cles a \(d\) chiffres en base \(b\).

1. Deux boucles imbriquees : \(\Theta(n^2)\) comparaisons.

def deux_termes_hachage(t, c):
    """Existe-t-il i != j avec t[i] + t[j] = c ? Theta(n) en moyenne."""
    vus = set()
    for x in t:
        if c - x in vus:          # le complement a deja ete rencontre
            return True
        vus.add(x)
    return False

def deux_termes_pointeurs(t, c):
    """Meme probleme, sur une COPIE triee. Theta(n log n) temps, Theta(1) espace en plus du tri."""
    u = sorted(t)
    g, d = 0, len(u) - 1
    while g < d:
        s = u[g] + u[d]
        if s == c:
            return True
        if s < c:
            g += 1                # la somme doit augmenter
        else:
            d -= 1                # la somme doit diminuer
    return False

assert deux_termes_hachage([2, 7, 11, 15], 9)
assert deux_termes_pointeurs([2, 7, 11, 15], 9)
assert not deux_termes_pointeurs([1, 2, 3], 100)
import random
for _ in range(500):
    t = [random.randint(-20, 20) for _ in range(random.randint(0, 12))]
    c = random.randint(-20, 20)
    naif = any(t[i] + t[j] == c for i in range(len(t)) for j in range(i+1, len(t)))
    assert deux_termes_hachage(t, c) == naif == deux_termes_pointeurs(t, c)

3. Correction des deux pointeurs. Invariant : « si une solution existe dans \(u\), alors il en existe une avec les deux indices dans \([g, d]\) ».

• Initialisation : \([g,d] = [0, n-1]\) contient tous les indices. Vrai.
• Conservation : supposons \(u_g + u_d < c\). Pour tout \(j \le d\), on a \(u_g + u_j \le u_g + u_d < c\) : aucune paire contenant l'indice \(g\) ne peut convenir. On peut donc eliminer \(g\) sans perdre de solution, ce que fait g += 1. Le cas \(u_g + u_d > c\) est symetrique (aucune paire contenant \(d\) ne convient).
• Terminaison : \(d - g\) est un entier naturel strictement decroissant : la boucle s'arrete. A la sortie, \(g \ge d\) : l'intervalle est vide, donc par l'invariant il n'existe aucune solution, et l'on renvoie bien False.

Le cout est \(\Theta(n)\) apres le tri, donc \(\Theta(n\log n)\) au total.

def trois_termes(t, c):
    """Existe-t-il trois indices distincts de somme c ? Theta(n^2)."""
    u = sorted(t)
    n = len(u)
    for i in range(n - 2):
        g, d = i + 1, n - 1
        while g < d:
            s = u[i] + u[g] + u[d]
            if s == c:
                return True
            if s < c:
                g += 1
            else:
                d -= 1
    return False

assert trois_termes([-1, 0, 1, 2, -1, -4], 0)

4. On fixe le premier terme (\(n\) choix) et l'on applique les deux pointeurs sur le reste : \(\Theta(n^2)\). Plus generalement, le probleme a \(k\) termes se resout en \(\Theta(n^{k-1})\) par cette recurrence. On conjecture qu'on ne peut pas faire mieux que \(\Theta(n^{\lceil k/2\rceil})\) ; pour \(k = 3\) la conjecture 3SUM affirme qu'aucun algorithme sub-quadratique n'existe, et elle sert de base a de nombreuses reductions en geometrie algorithmique.