Aller au contenu

Algorithmique

Dans cette partie, on va souvent manipuler des cartes à jouer.

On supposera les cartes posées sur la table, côte à cote sur une ligne, face cachée.

Pour décrire la valeur d'une carte, on utilise une paire YZ:

  • Y est la valeur de la carte : 2-10 pour les chiffres, J pour le valet (Jack), Q pour la reine (Queen), K pour le roi (King), et A pour l'as (Ace).
  • Z est sa couleur : T pour le trèfle (Trefle), H pour le coeur (Heart), D pour le carreau (Diamond), S pour le pique (Spade).
  • XX représente une carte face cachée.

Ainsi, 2H est le 2 de coeur, QT la dame de trèfle, et JD le valet de carreau.

On s'autorisera, au maximum, à avoir deux cartes face visible à la fois, et à ne déplacer que des cartes visibles.

Activité : présence d'une carte

Vous avez 10 cartes devant vous : 2 - 10 et l'As d'une couleur. Proposez une méthode, en respectant les contraintes ci-dessus, pour vérifier si le 7 de votre couleur (ou une autre carte) est présent.

Essayez dans un premier temps avec les cartes face visible, ça vous donnera peut-être des idées.

On retourne les cartes l'une après l'autre. Si on trouve le 7, alors il est présent et on s'arrête. Sinon, il n'est pas présent.

Activité : camarade malicieux

Faites executer votre méthode par quelqu'un d'autre. Cette personne devra être la plus malicieuse possible, c'est à dire tout faire pour rendre le mauvais résultat ou ne jamais s'arrêter, tout en respectant la méthode comme vous l'avez décrite. Essayez par la suite d'améliorer votre description pour éviter ce genre de soucis.

Soyez vraiment malicieux, essayez de trouver des failles dans la méthode ! Choisissez des cartes initiales qui vous avantage.

Malice :

Dans la solution proposée plus tôt, rien ne précise qu'on doit s'arrêter de retourner les cartes si on ne trouve pas le 7. On peut donc toujours continuer de retourner des cartes et ne jamais s'arrêter.

La méthode ne précise pas non plus que les cartes doivent être toutes retournées. On peut donc retourner deux cartes l'une après l'autre en boucle pour "éviter" le 7 si il est présent.

Amélioration :

Il nous faut blinder notre méthode, en précisant bien chaque étape.

On retourne chaque carte, l'une après l'autre, en commençant par la gauche. Si une des cartes est le 7 de coeur, on s'arrête, et le 7 de coeur est présent. Quand on retourne la carte la plus à droite, si elle n'est pas le 7 de coeur, on s'arrête, et le 7 de coeur n'est pas présent.

Nous venons d'écrire un algorithme.

Algorithme

Algorithme

Un algorithme est une méthode de résolution de problème exprimée sous forme d'une séquence non ambigüe d'instructions et d'opérations.

  • problème : à prendre au sens large : calcul, communication entre des machine, préparation d'un plat, ...
  • séquence : indique la possibilité d'exprimer une temporalité, les instructions sont exécutées les unes après les autres.
  • non ambigüe : l'algorithme décrit la méthode sans laisser de place à l'imagination ou à une interprétation différente de celle prévue.
Remarque (avancée)

Selon la thèse de Church-Turing, tout problème qui admet une méthode de résolution qui peut être exprimée sous forme d'un algorithme admet aussi une méthode de résolution qui peut être exprimée sous une forme ne comportant aucune temporalité, à l'aide de fonctions récursives, une notion vue en terminale.

Les langages de programmation impératifs, comme Python, permettent d'exprimer des algorithmes sous une forme compréhensible par un logiciel ou un ordinateur.

On préférera parfois utiliser une langue naturelle, comme le français, ou un mélange entre un langage de programmation et une langue naturelle, le pseudocode.

On présente souvent un algorithme comme une fonction, avec des données attendues en entrée, ou précondition et une sortie, ou postcondition, le résultat produit.

Dans les dépliants ci-dessous se trouve un exemple d'algorithme exprimé dans divers langages.

Pseudocode 
entrée : une liste l de n entiers. v un entier.
sortie : V si v est dans l, F sinon.

pour chaque élément e de l:
    si e vaut v : 
        on retourne V
on retourne F
Python 
def est_present(l, v):
    """l une liste d'entiers 
    v un entier
    retourne True si v est dans l, False sinon
    """

    for e in l:
        if e == v:
            return True
    return False
Javascript 
/**
 * l une liste d'entiers 
 * v un entier
 * retourne true si v est dans l, false sinon
*/
function est_present(l, v){
    for (e of l){
        if (v === e){
            return true;
        }
    }
    return false;
}
C++

note : vector est un des équivalent en C++ du type list en Python

/** retourne true si v est dans l, false sinon */
bool est_present(vector<int> l, int v){
    for (int e : l){
        if (l == v){
            return true;
        }
    }
    return false;
}
C

note : Un des équivalent du type list en Python en C, appelé tableau, est l'adresse (appelée "pointeur") d'un bloc de mémoire vive, associé à la taille du bloc, de type size_t.

/** l un pointeur vers un tableau d'entiers
t le nombre d'éléments du tableau

retourne true si v est dans l, false sinon.
*/    
bool est_present(int* l, size_t t, int v){
    for (size_t i = 0; i < t; t++){
        if(l[i] == v){
            return true;
        }
    }
    return false;
}

Comme vous pouvez le voir, chaque morceau de code est différent, mais l'idée générale de manipulation des données reste la même : on cherche à savoir si une valeur est présente dans une liste (ou tableau).

L'algorithmique est la discipline qui étudie les algorithmes et qui en prouve des propriétés, indépendamment du langage choisi. Par exemple, on peut prouver qu'un algorithme produit une sortie valide pour toute entrée valide, ou encore étudier la performance des algorithmes.