Introduction

Quoi ?

Pour résoudre un problème, il faut commencer par le décomposer en sous‑problèmes. Pour chaque sous‑problème à résoudre, on décrit les opérations à réaliser sous la forme d’un algorithme. Il existe une multitude d’algorithmes pour résoudre un problème, mais ils ne se valent pas tous.

L’algorithmique étudie les propriétés de ces algorithmes. Cette analyse est nécessaire pour nous aider à décider quel algorithme utiliser. On se propose à présent de passer en revue quelques propriétés importantes des algorithmes.

Pourquoi ?

Si tous les chemins mènent à Rome, on ne peut en emprunter qu’un. Lorsqu’on est face à plusieurs chemins pour arriver au même résultat, il est important de choisir le chemin le plus optimal.

Vous avez déjà rencontré plusieurs algorithmes pour arriver jusqu’ici. Encore plus fort, vous avez rencontré plusieurs algorithmes pour résoudre un même problème, ce qui nous met face à un dilemme : quelle algorithme choisir ? Et y a‑t‑il une solution à tout problème ?

Comment ?

Dans un premier temps nous allons nous intéresser à la notion de complexité : comment déterminer la vitesse d’un algorithme ? Si plusieurs bonnes solutions existent, alors il faut choisir la plus rapide. Mais sera‑t‑elle toujours la solution la plus rapide ?

Dans un deuxième temps, si vous le souhaitez, vous pouvez ouvrir la porte merveilleuse de la récursivité, à la manière des Infinity Mirror Room de Yayoi Kusama.

Objectifs

A la fin de ce chapitre, vous saurez ce qui fait qu’un algorithme est un bon algorithme et quels critères prendre en considération pour choisir le meilleur algorithme. Vous verrez également qu’il existe des problèmes relativement simples que l’on n’arrive toujours pas à résoudre.

• Pouvoir déterminer quelle est la meilleure solution pour un problème donné, en fonction de critères objectifs.

• Comprendre pourquoi certains problème simples n’ont pas de solution exacte.

• [Optionnel] Créer des fonctions récursives, qui s’appellent elles‑mêmes.