Algorithmique pour l'apprenti programmeur

Algorithmique pour l'apprenti programmeur

Mis à jour le jeudi 5 décembre 2013

Vous venez d'apprendre les bases d'un langage de programmation ? Vous vous êtes peut-être rendu compte que parfois, en modifiant un peu votre programme, vous pouvez obtenir le même résultat mais 2, 10 ou 1000 fois plus vite ?

De telles améliorations ne sont pas le fruit du hasard, ni même dues à une augmentation de la mémoire vive ou à un changement de processeur : il y a plusieurs manières de programmer quelque chose et certaines sont incroyablement meilleures que d'autres.

Avec un peu de réflexion, et des outils théoriques de base, vous serez vous aussi en mesure de faire de bons choix pour vos programmes. À la fin de ce tutoriel, vous serez de meilleurs développeurs, en mesure de comprendre, corriger et concevoir des programmes plus efficaces.

But du tutoriel

Les deux notions clés de ce tutoriel sont les suivantes : la complexité, et les structures de données. La complexité est une manière d'estimer les performances d'un algorithme. Les structures de données sont la manière dont vous organisez les informations dans votre programme. En choisissant une structure de données adaptée, vous serez capables de coder des opérations très performantes (de faible complexité).

Chaque algorithme résout un problème donné. Pour chaque problème, il existe un ou plusieurs algorithmes intéressants (mais on en découvre de nouveaux tous les ans !). Nous vous présenterons, dans ce tutoriel, un petit panorama de problèmes "courants", dans le but de vous familiariser avec la complexité et les structures de données. Vous apprendrez par exemple à chercher un élément qui vous intéresse à l'intérieur d'un ensemble d'éléments, à trier un ensemble, ou même à trouver le plus court chemin d'un "endroit" à un autre.

Prérequis

Le but de ce tutoriel n'est pas de vous apprendre à programmer. Pour le lire, vous devez déjà savoir programmer. L'apprentissage de l'algorithmique n'utilise pas de concepts bas niveau (assembleur, etc.) ou de bibliothèques logicielles spécialisées (SDL, Qt...), mais vous devez être à l'aise avec les variables, conditions, boucles et fonctions. La connaissance du concept de 'récursivité' (si vous vous sentez en manque, il y a déjà un tuto à ce sujet sur le SDZ) est aussi un avantage.

Le langage que vous utilisez n'est pas très important, car on tentera de formuler les algorithmes d'une manière qui en est indépendante. Nous donnerons aussi, pour les curieux, des exemples dans quelques langages de programmation. Si vous n'y voyez pas le vôtre, trouvez-en un suffisamment proche, et faites un petit effort. :)

La complexité algorithmique est une mesure formelle de la complexité d'un algorithme. Elle s'exprime donc en langage mathématique. Le calcul de certains algorithmes avancés est très compliqué et demande des connaissances mathématiques poussées. Cependant, notre tutoriel se concentre sur des choses simples, et devrait être largement accessible : une connaissance des puissances et des racines (carrées) devrait suffire à être à l'aise. Un objet plus avancé, la fonction logarithme, sera présenté et expliqué avant son utilisation.

Historique

Ce tutoriel est en cours d'écriture. Vous l'avez déjà lu, et vous voulez savoir si quelque chose a été rajouté ?
Voici un historique des modifications, les plus récentes en premier :

  • 08 août 2011 : correction d'une bévue repérée par Arnolddu51, et clarification par Cygal de la recherche de racine par dichotomie, suite à une question de bouboudu21

  • 15 juin 2010 : révision de l'implémentation C du tri par fusion sur les listes

  • 13 juin 2010 : diverses reformulations suite aux commentaires des lecteurs (candide, Equinoxe, programLyrique)

  • 12 juin 2010 : implémentation en C du tri par sélection sur les tableaux

  • juillet 2009 : correction de quelques typos, clarification de certains passages

  • 26 avril 2009 : ajout d'exemples de code pour le chapitre sur les arbres

  • 25 avril 2009 : ajout d'icônes pour les chapitres existants

  • 22 avril 2009 (partie 3) ajout du deuxième chapitre : arbres; les exemples de code sont à venir

  • 20 avril 2009 (partie 3) ajout d'un premier chapitre, assez simple, sur les piles et les files

  • 27 février 2009 (partie 1) reformulation et clarification de certains paragraphes

  • 22 février 2009 : ajout de l'historique, présentation d'un site d'exercices en fin de deuxième partie

  • 18 février 2009 (partie 2) ajout d'exemples de code C pour les listes chaînées

  • 11 février 2009 (partie 2) chapitre "Introduction au problème du tri"

  • janvier 2009 : zcorrection par ptipilou (rédaction arrêtée à cause d'un bug du SdZ)

  • mi octobre 2008 (partie 2) chapitre "Notions de structures de données : tableaux et listes chaînées"

  • début septembre 2008 (partie 2) chapitre "Une classe d'algorithme non naïfs : diviser pour régner", par lasts et Cygal

  • mi août 2008 (partie 1) publication de la première partie

déroulement d'un cours

  • 1

    Dès aujourd'hui, vous avez accès au contenu pédagogique et aux exercices du cours.

  • 2

    Vous progressez dans le cours semaine par semaine. Une partie du cours correspond à une semaine de travail de votre part.

  • !

    Les exercices doivent être réalisés en une semaine. La date limite vous sera annoncée au démarrage de chaque nouvelle partie. Les exercices sont indispensables pour obtenir votre certification.

  • 3

    À l'issue du cours, vous recevrez vos résultats par e-mail. Votre certificat de réussite vous sera également transmis si vous êtes membre Premium et que vous avez au moins 70% de bonnes réponses.

Découvrez aussi ce cours en...

Exemple de certificat de réussite
Exemple de certificat de réussite