#Algorithmique 1Copier le lien

Prérequis: bases de programmation (boucles, récursivité, fonctions), premières notions de complexité en O.

Objectifs du module:

• Analyser le temps et l'espace d'un algorithme, distinguer meilleur cas, cas moyen et pire cas.
• Connaître les algorithmes et structures fondamentaux (tris, arbres, tas, tables de hachage) avec leurs coûts exacts.
• Choisisir et appliquer les grandes stratégies: diviser pour régner, glouton, programmation dynamique, parcours de graphes.
• Reconnaître un problème NP-complet et réagir correctement (réductions, heuristiques, approximations).
• Démontrer la correction d'un algorithme (invariant, récurrence, preuve par induction).

#Progression du coursCopier le lien

#Les quatre questions du moduleCopier le lien

#Comment mesurer un algorithme?Copier le lien

Indépendamment de la machine et du langage: par le taux de croissance du temps d'exécution en fonction de la taille de l'entrée. La notation O donne une borne supérieure asymptotique, Ω une borne inférieure, Θ l'encadrement exact. On précise toujours pour quel cas (meilleur, moyen, pire) l'analyse est faite: trier un tableau déjà trié, presque trié ou inversé ne coûte pas la même chose au tri par insertion.

#Quels outils fondamentaux?Copier le lien

Les tris d'abord: le tri par insertion pour les petites entrées ou presque triées, le tri fusion et le tri rapide pour le travail sérieux, le tri par tas pour la garantie en place, les tris par comptage et par base quand les clés s'y prêtent. Les structures ensuite: arbres de recherche et tas pour les ensembles ordonnés et files de priorité, tables de hachage pour le dictionnaire pur. Chaque coût découle d'un invariant de structure.

#Quelles stratégies de conception?Copier le lien

• Diviser pour régner: couper en sous-problèmes indépendants, résoudre, combiner; analyse par récurrence et théorème maître.
• Glouton: un choix local irréversible à chaque étape; correct seulement si ce choix local apparaît dans une solution optimale (à prouver, pas à espérer).
• Programmation dynamique: des sous-problèmes chevauchants qu'on résout une fois, dans un tableau ou par mémoïsation.

#Quelles limites?Copier le lien

Certains problèmes résistent: aucun algorithme polynomial connu, et pour les NP-complets on sait que si un seul cède, tous cèdent (réductions polynomiales). La réaction professionnelle n'est pas de chercher quand même un algorithme exact rapide, mais de changer d'objectif: instances petites, heuristiques, algorithmes d'approximation garantis.

#Algorithme, instance, correctionCopier le lien

Un algorithme est une procédure de calcul bien définie: elle prend une valeur, ou un ensemble de valeurs, en entrée, et produit une valeur, ou un ensemble de valeurs, en sortie, en un temps fini. On peut aussi le voir comme un outil de résolution d'un problème bien spécifié — l'énoncé du problème décrit la relation entrée/sortie attendue pour des instances de taille arbitraire, et l'algorithme décrit la procédure concrète qui réalise cette relation.

Une instance est une entrée particulière du problème. Pour le problème du tri:

• Entrée: une suite de n nombres A = ⟨a₁, a₂, …, a_n⟩.
• Sortie: une permutation A′ = ⟨a′₁, a′₂, …, a′_n⟩ de A telle que a′₁ ≤ a′₂ ≤ … ≤ a′_n.

Un algorithme est correct si, pour toute instance fournie en entrée, il s'arrête — il termine son calcul en un temps fini — et produit la solution correcte de cette instance. Un algorithme incorrect peut échouer de deux façons distinctes: ne pas s'arrêter du tout sur certaines entrées, ou s'arrêter avec une réponse fausse.

Cette définition sépare deux obligations qu'il faut démontrer séparément:

1. La terminaison. Aucune boucle infinie, aucune récursion dont l'argument ne décroît pas. C'est la partie qu'on oublie, et c'est celle qui produit les programmes qui « marchent » sur les exemples et se bloquent en production.
2. La correction partielle. Si l'algorithme s'arrête, sa réponse est la bonne. C'est ce que démontre l'invariant de boucle ou l'induction structurelle.

La méthode d'analyse asymptotique et la preuve de correction sont deux activités indépendantes: un algorithme rapide mais faux ne vaut rien, et un algorithme correct mais exponentiel ne passe pas à l'échelle. Le module demande les deux.

#MéthodologieCopier le lien

1. Spécifier précisément l'entrée, la sortie et les préconditions.
2. Proposer un algorithme naïf correct, même lent: référence pour tester les versions rapides.
3. Améliorer avec une structure ou une stratégie identifiée, et mesurer le gain.
4. Prouver la correction par invariant ou induction.
5. Analyser le coût en temps et en espace, pire cas et cas moyen.
6. Tester sur les cas limites (entrée vide, entrée triée, doublons, entrée inverse de l'intuition).

L'expression pédagogique de ce module alterne preuves sur papier, implémentations chronométrées et exercices chronométrés de type examen.

#Exercice de diagnosticCopier le lien

Avant d'entrer dans le module, sachons reconnaître les classes de coût sur du code simple:

1# A2total = 03for x in t:4    total += x5 6# B7paires = []8for x in t:9    for y in t:10        paires.append((x, y))11 12# C13while n > 1:14    n = n // 2

Correction: A traverse le tableau une fois, O(n). B est doublement imbriqué sur le même tableau, n² paires, O(n²). C divise n par 2 à chaque tour, ⌊log₂ n⌋ tours, O(log n). Reconnaître ces trois squelettes (balayage, double boucle, division par deux) couvre la majorité des analyses du module.

#QuizCopier le lien