Algorithmique II

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 même problème, mais tous ces algorithmes ne se valent pas.

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

Objectifs de la thématique

A la fin de ce chapitre, vous saurez ce qui fait d’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 exactement.

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

Appliquer la stratégie algorithmique « diviser pour régner ».

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

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