Introduction

L'algorithmique est l'étude des méthodes de résolution de problèmes. Sa mise en pratique conduit à des programmes qui résolvent des instances de ces problèmes : remplir au mieux un sac, planifier un projet, réduire une image sans en déformer le contenu, retrouver une sous-séquence commune à deux brins d'ADN, organiser un dictionnaire pour que les recherches y soient rapides… Ce cours s'adresse à toute personne qui sait déjà programmer en Java et qui veut apprendre à concevoir des algorithmes, à les justifier et à en mesurer l'efficacité.

Le but

À la fin du parcours, vous saurez :

• résoudre un problème d'optimisation par la programmation dynamique, et reconnaître quand la résolution gloutonne échoue ; la méthode est appliquée à une dizaine de problèmes concrets ;
• donner un sens précis aux instructions d'un programme (logique de Hoare), écrire un programme à partir d'une propriété invariante, et analyser sa complexité dans le pire cas ;
• employer les méthodes de résolution séquentielle, dichotomique et diviser pour régner, et les grands algorithmes de tri.

Les structures de données sont introduites au fil des problèmes : tableaux à une, deux et trois dimensions, listes et tableaux de listes, graphes représentés par des tableaux de listes d'arcs, arbres binaires de recherche, tas représentés dans des tableaux.

Ce qu'il faut savoir avant de commencer

• En Java : les variables, les boucles, les méthodes et les tableaux. Le cours Programmation Java du même site les enseigne à partir de zéro, et l'annexe A en fait un aide-mémoire.
• En mathématiques : le calcul algébrique, les sommes, les puissances et le logarithme, et le raisonnement par récurrence. C'est le niveau de la fin du lycée en filière scientifique, complété au fil des chapitres.

Le parcours

Le cours compte deux parties.