Algorithmique pour l'apprenti programmeur
Last updated on Thursday, December 5, 2013
  • Facile

Free online content available in this course.

Got it!

Introduction du cours

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

How courses work

  • 1

    You have now access to the course contents and exercises.

  • 2

    You will advance in the course week by week. Each week, you will work on one part of the course.

  • !

    Exercises must be completed within one week. The completion deadline will be announced at the start of each new part in the course. You must complete the exercises to get your certificate of achievement.

  • 3

    At the end of the course, you will get an email with your results. You will also get a certificate of achievement if you are a <a href="/premium>Premium</a> Member and if you got at least 70% of your answers right.

Example of certificate of achievement
Example of certificate of achievement