Fiche de révision - Algorithmique¶

1. Parcours séquentiel¶

Examine les éléments un par un, du premier au dernier
Fonctionne sur tout tableau (trié ou non)
Complexité : O(n)

Permet de : chercher un élément, trouver le max/min, compter, calculer une moyenne.

def recherche(tab, val):
    for i in range(len(tab)):
        if tab[i] == val:
            return i
    return -1

2. Recherche dichotomique¶

Divise l'intervalle de recherche en deux à chaque étape
Nécessite un tableau trié
Complexité : O(log₂ n)

n	Étapes max (dichotomie)	Étapes max (séquentiel)
1 000	10	1 000
1 000 000	20	1 000 000

def recherche_dicho(tab, val):
    g, d = 0, len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == val: return m
        elif tab[m] < val: g = m + 1
        else: d = m - 1
    return -1

Terminaison : variant d - g décroît strictement. Correction : invariant « si val est dans tab, elle est entre g et d ».

3. Tri par sélection¶

Cherche le minimum dans la partie non triée et le place à sa position
Complexité : O(n²) dans tous les cas
Tri non stable

def tri_selection(tab):
    for i in range(len(tab) - 1):
        i_min = i
        for j in range(i + 1, len(tab)):
            if tab[j] < tab[i_min]:
                i_min = j
        tab[i], tab[i_min] = tab[i_min], tab[i]

4. Tri par insertion¶

Insère chaque élément à sa place dans la partie déjà triée (comme un jeu de cartes)
Complexité : O(n²) pire cas, O(n) meilleur cas (tableau trié)
Tri stable et adaptatif

def tri_insertion(tab):
    for i in range(1, len(tab)):
        cle = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j -= 1
        tab[j + 1] = cle

5. Comparaison sélection / insertion¶

	Sélection	Insertion
Pire cas	O(n²)	O(n²)
Meilleur cas	O(n²)	O(n)
Stable	Non	Oui
Adaptatif	Non	Oui

6. Algorithmes gloutons¶

Fait le meilleur choix local à chaque étape, sans revenir en arrière
Simple et rapide, mais pas toujours optimal
Rendu de monnaie (système euro) : glouton optimal
Sac à dos : glouton peut échouer

7. K plus proches voisins (KNN)¶

Classification : prédit la classe d'un élément selon ses k voisins les plus proches
Distance euclidienne : \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)
Classe prédite = classe majoritaire parmi les k voisins

Algorithme :

Calculer la distance à tous les points connus
Trier par distance croissante
Prendre les k plus proches
Voter : la classe la plus fréquente gagne
Choisir k impair (éviter les ex æquo)
Normaliser les données si les échelles diffèrent

8. Preuves d'algorithmes¶

Outil	Usage
Variant de boucle	Prouve la terminaison (quantité entière ≥ 0, strictement décroissante)
Invariant de boucle	Prouve la correction (propriété vraie à chaque itération)

Pour un invariant, montrer : initialisation (vrai au départ), conservation (reste vrai à chaque tour), terminaison (implique le résultat voulu).