Licence CC BY-SA

Premiers exemples de structures de données et d'algorithmes courants

  1. Notions de structures de données : tableaux et listes chaînées

    1. Définition

    2. Ajout / retrait, taille, accès à un élément

    3. Concaténation, filtrage

    4. Synthèse

  2. Une classe d'algorithme non naïfs : diviser pour régner

    1. Gagner au jeu du 'Plus ou Moins'

    2. Dichotomie : Recherche dans un dictionnaire

    3. Calcul de la complexité

    4. Trouver un zéro d'une fonction

    5. Diviser pour régner : exponentiation rapide

  3. Introduction au problème du tri

    1. Formuler le problème du tri

    2. Tri par sélection

    3. Implémentation du tri par sélection

    4. Le retour du "diviser pour régner" : Tri fusion

Je pense que vous avez maintenant acquis les bases de l'algorithmique. Si vous avez bien compris tout ce qui a été dit jusque là, vous devriez être capable de vous faire vous-même une idée sur la complexité des algorithmes simples, et d'intégrer cette réflexion dans votre manière de programmer.

Ne vous attendez pas cependant à faire des merveilles dès maintenant. Le "sens de la complexité" (la capacité à évaluer la complexité de son travail, sans forcément rentrer dans des précisions formelles pointues) demande de la pratique, il faut que cela devienne une habitude. Dans la prochaine partie, nous vous présenterons d'autres algorithmes courants, que vous rencontrerez sans doute dans de nombreuses situations, et qui agrandiront donc à la fois votre trousse à outils algorithmique, et votre capacité à estimer les complexités.

Le choix du cours est donc le suivant : restez sur votre chaise, lisez (… quand ils seront disponibles !) les prochains chapitres, faites les exercices proposés (et d'autres en plus si vous voulez), et vous apprendrez beaucoup de chose. Il y a d'autres sources d'informations disponibles (… et oui, tout ne se résume pas au Site du Zéro !), et je voudrais en mentionner une en particulier : France-IOI. C'est une association qui prépare, à travers une série d'exercices d'algorithmiques, à des compétitions d'informatique. Ce ne sont pas les compétitions qui m'intéressent ici, mais leurs exercices : ils sont variés, formateurs, et corrigés avec soin. Leur idée est de former les visiteurs à l'algorithmique à travers une série d'exercice progressifs à chercher.

Si vous avez envie d'un peu de pratique, n'hésitez pas à y jeter un coup d'oeil. Bien sûr, le concept n'est pas unique et il existe d'autres sites d'exercices (comme Project Euler, qui est malheureusement plus orienté mathématiques) et de descriptions d'algorithmes (par exemple la wikipédia). N'hésitez pas à vous renseigner et travailler par vous-même.