Les algorithmes
Qu'est-ce qu'un problème ?
Il s'agit d'une question à résoudre par des méthodes rationnelles ou scientifiques.
Exemple #1
Le problème du fermier sur la berge
Enoncé
Un fermier possède :
Le fermier doit traverser une rivière avec un petit bateau disponible sur la berge.
Les contraintes sont les suivantes :
- Le bateau permet d'emmener un seul passager ou objet à la fois
- Le canard ne doit pas être laissé seul avec le maïs
- Le renard ne doit pas être laissé seul avec le canard
Ce problème montre l’importance des contraintes
Si on les supprime le problème n’en est plus un.
Il nous montre aussi l’importance de connaître toutes les actions possibles pour résoudre un problème.
Solution : Reformuler le problème et le regarder sous tous les angles avant de chercher une solution
Exemple #2
Le jeu du taquin
Enoncé
| 4 | 7 | 2 |
| 8 | 6 | 1 |
| 3 | 5 |
Configuration initiale du jeu
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 |
Ce que l'on doit obtenir à la fin
Comment faire pour solutionner le problème sans faire “à l’aveugle” ?
La solution : diviser pour mieux régner. On peut remarquer que si on découpe le problème en petit morceau, on peut développer un pattern de "petit train".
Les clés pour solutionner un problème
- Toujours avoir un plan
- Reformuler le problème
- Diviser le problème
- Commencer par ce que l'on sait faire
- Simplifier le problème
- Chercher des analogies
- Expérimenter
- Garder la motivation
Pour plus de détails
Think Like A Programmer An Introduction To Creative Problem Solving (V. Anton Spraul)Qu’est ce qu’un algorithme ?
Il s’agit d’une suite (finie) d’opérations élémentaires qui permettent de résoudre un problème.
C’est une procédure de calcul qui prend en entrée un ensemble V de valeurs et qui retourne en sortie en ensemble V’ de valeurs.
Un algorithme doit toujours se terminer et fournir un résultat.
Un algorithme est dit correct si pour chaque ensemble de valeurs V en entrée il fournit le même ensemble de résultat V' en sortie.
On utilise parfois certains algorithmes non corrects si l'on sait gérer le taux d'erreur de l'algorithme.
Certains problèmes ne sont pas calculables, il n'existe pas d'algorithme qui permette leur résolution.
Connaissez vous des exemples d'algorithme ?
Oui, vous en utilisez tous les jours !
La recette de cuisine
début
remplir_casserole(eau)
tant_que (eau_non_bouillante)
chauffer_casserole(feu_max)
fin_tant_que
remplir_casserole(pâtes)
tant_que (pâtes_non_cuites)
chauffer_casserole(feu_fort)
fin_tant_que
égouter_pâtes
servir_pâtes
fin
Exemple d'Algo pour calculer le PGCD
(Plus Grand Commun Diviseur)
début
nb_1, nb_2
max = max(nb_1, nb_2)
min = min(nb_1, nb_2)
reste = max modulo min
tant_que (reste différent de zéro)
max = min
min = reste
reste = max modulo min
fin_tant_que
pgcd = min
fin
Petit rappel sur le PGCD
Les structures algorithmiques
- Les structures de contrôle
- Les structures de données
Pour plus de détails
La complexité
Il s'agit en fait de l'efficacité de l'algorithme que l'on va développer.
- En temps
- En mémoire