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 :

1. Calculer la distance à tous les points connus
2. Trier par distance croissante
3. Prendre les k plus proches
4. 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).