Dans ce module, vous apprendrez que les programmes basés sur des algorithmes efficaces peuvent résoudre le même problème des milliards de fois plus rapidement que les programmes basés sur des algorithmes naïfs. Vous apprendrez à estimer le temps d'exécution et la mémoire d'un algorithme sans même l'implémenter. Armé de ces connaissances, vous serez en mesure de comparer différents algorithmes, de sélectionner les plus efficaces et enfin de les mettre en œuvre dans le cadre de nos défis de programmation !

Dans ce module, vous découvrirez une classe d'algorithmes apparemment naïfs mais puissants, les algorithmes gourmands. Après avoir appris l'idée clé qui sous-tend les algorithmes gourmands, vous aurez peut-être l'impression qu'ils représentent le couteau suisse algorithmique qui peut être appliqué pour résoudre presque tous les défis de programmation de ce cours. Mais attention : à quelques exceptions près, cette idée intuitive fonctionne rarement dans la pratique ! Pour cette raison, il est important de prouver qu'un algorithme gourmand produit toujours une solution optimale avant d'utiliser cet algorithme. À la fin de ce module, nous testerons votre intuition et votre goût pour les algorithmes gourmands en vous proposant plusieurs défis de programmation.

Dans ce module, vous découvrirez une technique algorithmique puissante appelée "diviser pour régner". Grâce à cette technique, vous verrez comment effectuer des recherches dans d'énormes bases de données des millions de fois plus rapidement qu'en utilisant la recherche linéaire naïve. Vous apprendrez même que la méthode standard de multiplication des nombres (que vous avez apprise à l'école primaire) est loin d'être la plus rapide ! Nous appliquerons ensuite la technique "diviser pour régner" pour concevoir deux algorithmes efficaces (merge sort et quick sort) pour trier d'énormes listes, un problème qui trouve de nombreuses applications dans la pratique. Enfin, nous montrerons que ces deux algorithmes sont optimaux, c'est-à-dire qu'aucun algorithme ne peut trier plus rapidement !

Dans ce dernier module du cours, vous découvrirez une technique algorithmique puissante permettant de résoudre de nombreux problèmes d'optimisation, la programmation dynamique. Il s'est avéré que la programmation dynamique peut résoudre de nombreux problèmes qui échappent à toutes les tentatives de résolution à l'aide de la stratégie de l'avidité ou de la division et de la conquête. Il existe d'innombrables applications pratiques de la programmation dynamique : de la maximisation des recettes publicitaires d'une chaîne de télévision à la recherche de pages Internet similaires, en passant par la recherche de gènes (le problème où les biologistes doivent trouver le nombre minimum de mutations pour transformer un gène en un autre). Vous apprendrez comment la même idée permet d'effectuer automatiquement des corrections orthographiques et de montrer les différences entre deux versions d'un même texte.

Dans ce module, nous continuons à nous entraîner à la mise en œuvre de solutions de programmation dynamique.