Aller au contenu principal

Algorithmique

👨‍🏫 Introduction​

Objectif​

Ces travaux pratiques ont pour objectif de vous enseigner l'écriture d'algorithmes et de fonctions Python dans la finalité de résoudre des besoins concrets.

Important

Les productions réalisées dans le cadre de ce TP seront à rendre en fin de séance :

  • Envoyer obligatoirement vos fichiers sous forme d'une archive au format ZIP (et non 7zip ou 7z)
  • Effectuer le rendu uniquement depuis l'application Exercices de l'ENT, via l'exercice intitulé [6TP2] Algorithmique

Préparation​

Afin de garder organisées les productions réalisées en TP, mettre à jour l'arborescence NSI selon l'ordinateur utilisé :

💻 Ordinateur portable
  1. Lancer l'explorateur de fichiers
  2. Se rendre dans le dossier Documents
  3. Créer le dossier NSI (s'il n'existe pas déjà)
  4. Dans le dossier NSI, créer le dossier chapitre_06 (s'il n'existe pas déjà)
  5. Dans le dossier chapitre_06, créer le dossier tp2_algorithmique
🖥 Ordinateur fixe des salles informatiques
  1. Depuis le Bureau, cliquer sur l'icône intitulée Zone personnelle
  2. Créer le dossier NSI (s'il n'existe pas déjà)
  3. Dans le dossier NSI, créer le dossier chapitre_06 (s'il n'existe pas déjà)
  4. Dans le dossier chapitre_06, créer le dossier tp2_algorithmique

Téléchargement des fichiers​

Pour effectuer ce TP, il est nécessaire de télécharger certains fichiers :

  1. Télécharger le fichier ZIP contenant les fichiers du TP : 📦 télécharger
  2. Ouvrir ou décompresser le fichier ZIP
  3. Copier/coller tous les fichiers dans le dossier NSI\chapitre_06\tp2_algorithmique

🔍 Partie 1 - Recherche​

L'objectif de cette partie est la réalisation d'un programme offrant la possibilité de compter le nombre d'occurrences d'un nom d'école parmi ceux de tous les établissements scolaires de France.

Exercice 1 - Occurrences​

Nous souhaitons disposer d'une fonction permettant de compter le nombre d'occurrences d'une valeur dans un tableau, c'est-à-dire le nombre de fois où cette valeur est présente dans un tableau.

🛠 Mise en pratique​

Écrire une fonction compter qui prend en paramètres valeur, la valeur à compter, et tableau, le tableau où compter. Cette fonction renvoie le nombre d'occurrences de valeur dans tableau.

  1. Ouvrir le fichier partie1/tableau.py
  2. Implémenter la fonction compter dont la docstring et les doctests sont déjà présents.
  3. Tester sans ajouter d'appel à la fonction. Pour cela, exécuter simplement le script partie1/tableau.py, il ne doit plus y avoir d'erreurs doctests.
  4. En cas de difficultés, consulter l'algorithme sur la feuille distribuée en séance

Exercice 2 - Recherche​

Nous souhaitons disposer d'une fonction permettant chercher une valeur dans un tableau.

🛠 Mise en pratique​

Écrire une fonction rechercher qui prend en paramètres valeur, la valeur à chercher, et tableau, le tableau où effectuer la recherche. Cette fonction renvoie l'indice de la première occurrence de valeur dans tableau ou -1 si elle n'a pas été trouvée.

  1. Écrire l'algorithme de cette fonction sur la feuille distribuée en séance
  2. Ouvrir le fichier partie1/tableau.py
  3. Déclarer la fonction rechercher à la suite de la fonction compter
  4. Rédiger rédigeant la docstring et les doctests AVANT d'écrire le corps de la fonction
  5. Vérifier que les doctests soient bien tous en erreur. Il sera nécessaire d'ajouter l'instruction pass pour éviter que Python ne signale une erreur de syntaxe. Exemple :
def ma_fonction():
    """
    docsting + doctests
    """
    pass
  1. Écrire le corps de la fonction rechercher

Exercice 3 - Le programme​

Nous souhaitons disposer d'un programme permettant de compter le nombre d'établissements scolaires ayant un nom précis. Pour cela le programme :

  • Demande à l'utilisateur le nom de l'établissement à compter
  • Affiche la taille de la base de données (tableau ecoles du fichier data.py)
  • Vérifie si le nom est présent dans le tableau des noms d'établissements scolaires
  • Si le nom existe est présent, affiche le nombre d'occurrences
Nom de votre établissement scolaire : GASTON BACHELARD
La base de données comporte 9999 entrées.
Le nom "GASTON BACHELARD" est bien présent dans la base de données.
7 établissements scolaires portent ce nom.

🛠 Mise en pratique​

  1. Créer un nouveau fichier Python
  2. L'enregistrer sous le nom main.py dans le dossier partie1
  3. Importer le module data (instruction import)
  4. Importer le module tableau
  5. Écrire le code permettant d'obtenir le nom de l'établissement à rechercher auprès de l'utilisateur
  6. Afficher la taille de la base de données conformément à l'exemple
  7. Utiliser la fonction rechercher du module tableau sur le tableau ecole afin de vérifier la présence du nom dans le tableau ecoles
  8. Selon la valeur de renvoyée par l'appel de fonction rechercher :
    • Si le nom a été trouvé, afficher :
      Le nom "{nom_recherché}" est bien présent dans la base de données.
      {n} établissements scolaires portent ce nom.
    • Si le nom n'a pas été trouvé, afficher :
      Le nom "{nom_recherché}" n'a pas été trouvé dans la base de données.
Pour les plus rapides

Une fois votre programme terminé, essayez de le rendre plus tolérant face à la saisie de l'utilisateur. L'idée serait d'obtenir des résultats même si l'utilisateur saisit simplement "gaston" comme nom d'établissement scolaire. Voici un ensemble d'instructions et d'expressions exécutées dans la console Python qui devraient vous inspirer :

>>> saisie = "gaston"
>>> saisie in "GASTON BACHELARD"
False
>>> saisie.upper()
'GASTON'
>>> saisie.upper() in "GASTON BACHELARD"
True

👊 Partie 2 - Force brute​

Cadenas à trois chiffres

Vous êtes face à un cadenas à trois chiffres dont vous avez oublié le code. Cette deuxième partie des travaux pratiques consiste en la réalisation d'un programme capable de découvrir les valeurs du tableau secret contenant 3 entiers compris en 0 et 9 :

secret = [int(v) for v in base64.b64decode("NSwyLDE=").decode("utf8").split(",")]
Remarque

Bien entendu, il vous est possible de découvrir le code par un simple print(secret) mais ce n'est pas l'objectif.

Force brute

La force brute (brute force attack) est une attaque informatique consistant à tester, l’une après l’autre, chaque combinaison possible d'un mot de passe ou d'une clé. (source : CNIL)

Exercice 4 - Identique​

Nous souhaitons disposer d'une fonction permettant de vérifier si deux tableaux sont identiques.

🛠 Mise en pratique​

Écrire une fonction comparer qui prend en paramètres tableau1 et tableau2, les deux tableaux à comparer. Cette fonction renvoie True si les tableaux sont identiques, False sinon.

  1. Écrire l'algorithme de cette fonction sur la feuille distribuée en séance
  2. Ouvrir le fichier partie2/tableau.py
  3. Implémenter la fonction comparer, la docstring et les doctests sont déjà présents.
  4. Tester la fonction en exécutant simplement le script partie2/tableau.py. Il ne doit plus y avoir d'erreurs doctests.

Exercice 5 - Génération​

Pour cet exercice, vous avez la possibilité de réaliser la fonction demandée de trois façons différences. La difficulté étant croissante, choisissez l'option qui vous convient le mieux. Attention, pour celles et ceux qui la connaissent, l'utilisation de la méthode append() n'est pas autorisée.

  1. Nous souhaitons disposer d'une fonction permettant de générer un tableau de 3 entiers aléatoires compris entre 0 et 9
  2. Nous souhaitons disposer d'une fonction permettant de générer un tableau de n entiers aléatoires compris entre 0 et 9
  3. Nous souhaitons disposer d'une fonction permettant de générer un tableau de n entiers aléatoires compris entre 0 et 9 en utilisant un tableau en compréhension

🛠 Mise en pratique​

Écrire une fonction generer_tableau qui ne prend pas de paramètre (méthode 1), ou prend le paramètre n correspondant à la taille du tableau à générer (méthodes 2 et 3). Cette fonction renvoie un tableau contenant 3 entiers aléatoires compris entre 0 et 9 (méthode 1), ou n entiers aléatoires compris entre 0 et 9 (méthodes 2 et 3).

  1. Ouvrir le fichier partie2/tableau.py
  2. Implémenter la fonction generer_tableau sans oublier la docstring (il n'y a pas de doctests à écrire pour cette fonction).

Exercice 6 - Le programme​

Nous souhaitons découvrir un code secret à 3 chiffres par une attaque force brute. Ces trois chiffres sont stockés dans le tableau secret, un tableau de trois entiers compris entre 0 et 9.

Méthode naïve​

Une première technique consiste à générer des tableaux de 3 nombres entiers aléatoires compris entre 0 et 9 et de les comparer avec secret. Celui-ci simule une personne qui testerait des combinaisons au hasard en espérant découvrir par chance la bonne. L'algorithme serait le suivant :

Entrée : un tableau "secret" de 3 entiers compris entre 0 et 9 inconnus
Sortie : Affichage de valeurs de 3 entiers

trouvé <- Faux

Tant que trouvé est Faux:
 |  Solution = generer tableau aléatoire de 3 entiers compris entre 0 et 9
 |  Si solution est identique à secret alors
 |   |  trouvé <- Vrai
 |  Fin si
Fin tant que

Afficher solution
  1. Ouvrir le fichier partie2\main.py.
  2. Ce fichier contient le tableau secret. Ne gâchez pas l'expérience de la découverte de la valeur en utilisant la fonction print directement sur secret.
  3. Implémenter l'algorithme naïf
  4. Ajouter un compteur afin de compter le nombre de tentatives qui auront été nécessaires pour découvrir la valeur

Vous devez obtenir un affichage similaire à celui-ci :

Solution   : [1, 2, 3]
Tentatives : 999

Méthode améliorée​

Si vous deviez chercher le code d'un cadenas, testeriez-vous vraiment des codes au hasard ? Trouvez une méthode plus fiable afin de découvrir le code.

  1. Écrire l'algorithme de votre méthode sur la feuille distribuée en séance
  2. Implémenter votre algorithme directement à la suite de la méthode naïve
Vous avez terminé ?

En informatique les mots de passe sont généralement hachés grâce à un algorithme de hachage. Celui renvoie en sortie une chaine de taille fixe spécifique à la chaîne de caractères transmise en entrée. Il en existe plusieurs versions telles que MD5 ou SHA1. MD5, est parfois utilisé pour hacher les mots de passe avant de les stocker.

>>> import hashlib
>>> hashlib.md5("MotDePasseSecret".encode()).hexdigest()
'db5721e2872cc413f210c1cce6cbd8da'

Il n'existe aucun moyen rapide permettant de récupérer l'information d'origine à partir de sa version hachée. L'usage d'un algorithme force brute est la seule solution possible. La méthode consiste à hacher toutes les combinaisons de chaînes de caractères possibles et de comparer leur hachage avec celui que l'on souhaite casser.

Essayer de retrouver le mot de passe caché derrière le hachage f2f8ad94aba8986f69bb005dfd216fce, sachant que :

  • le mot de passe fait 3 caractères
  • les caractères utilisés appartiennent aux ensembles [0-9] ou [a-z]

Questions

  • Donner une formule permettant de connaître le nombre de combinaisons à tester dans le pire des cas pour un mot de passe de taille n
  • Comment renforcer encore la force du mot de passe ?

📦 Envoi du travail​

Création du fichier ZIP​

Pour faciliter le partage de plusieurs fichiers et dossiers, il est plus pratique de les regrouper dans un unique fichier au format ZIP. Lire les instructions selon l'ordinateur utilisé :

💻 Ordinateur portable (Windows 11)
  1. Lancer l'explorateur de fichiers
  2. Se rendre dans le dossier NSI\chapitre_06\
  3. Sélectionner le dossier tp2_algorithmique en cliquant une seule fois dessus avec le bouton gauche
  4. Cliquer avec le bouton droit sur le dossier tp2_algorithmique
  5. Choisir l'option Compresser dans le fichier ZIP
  6. Nommer le fichier nom_prenom_tableaux.zip
🖥 Ordinateur fixe des salles informatiques (Windows 10)
  1. Lancer l'explorateur de fichiers
  2. Se rendre dans le dossier NSI\chapitre_06\
  3. Sélectionner le dossier tp2_algorithmique en cliquant une seule fois dessus avec le bouton gauche
  4. Cliquer avec le bouton droit sur le dossier tp2_algorithmique
  5. Choisir l'option Envoyer vers ▸ Dossier compressé
  6. Nommer le fichier nom_prenom_tableaux.zip

Transmission du fichier ZIP​

  1. Se connecter à l'ENT
  2. Accéder à l'application Exercices
  3. Cliquer sur l'exercice [6TP2] Algorithmique
  4. Cliquer sur Parcourir et choisir le fichier ZIP créé précédemment
  5. Valider l'envoi du devoir en cliquant sur Rendre le devoir