Terminales Spé NSI

Ce chapitre se concentre sur les modules de Python et sur les modalités d’importation des données des modules dans l’environnement de travail.

Qu’est-ce qu’un module ?

• Quand la taille du code augmente, il peut être pratique de le diviser en entités organisées qui peuvent continuer à interagir.
• Un module permet aussi de se créer une «  boite à outils » contenant des fonctions appelées depuis plusieurs programmes.
• Finalement, un module permet de bénéficier du travail déjà effectué, maximisant ainsi la réutilisabilité du code.

Modules et fichiers

À cette fin, chaque fichier est considéré comme un module individuel, et réciproquement. Le nom de fichier d’un module est le nom du module auquel on ajoute l’extension .py.

Cette séance a pour objectif de vous familiariser avec la création et la manipulation de modules.

Algorithmique

En informatique, pour qu’un algorithme puisse être implémenté, il est nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou d’instructions à réaliser » s’effectue en une durée finie .

Recherche d’un élément dans un tableau

La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :

• La recherche linéaire itérative ;
• La recherche linéaire récursive ;
• La recherche dichotomique itérative ;
• La recherche dichotomique récursive.

Travail à faire

• Implémenter en Python les cinq algorithmes suivants et répondre aux questions.

Recherche séquentielle (ou linéaire)

Recherche séquentielle itérative

Introduction

Une chaîne de caractère est une structure de données qui permet de rassembler en un unique objet une succession ordonnée de caractères. Ainsi, une définition récursive d’une chaîne de caractères pourrait être :

Une liste est une structure de données qui permet de rassembler en un unique objet une succession ordonnée d’objets (ou de valeurs). Ainsi, une définition récursive d’une liste pourrait être :

La récurrence est un raisonnement mathématique courant et parmi les plus puissants pour démontrer des théorèmes ou construire des objets. Par exemple, on l’utilise dans un cours de mathématique de lycée pour montrer que :

• Pour tout entier $n \geqslant 0$, on a : $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$ ;
• Un entier naturel n’est autre que 0 ou le successeur d’un entier naturel (0 est 0, 1 est le successeur de 0, 2 est le successeur de 1, …).

En programmation, on peut raisonner de façon identique, nous allons construire des fonctions et des structures de données (listes chaînées, arbres, etc.) à l’aide d’une hypothèse de récurrence et d’un point de départ. Le déroulement de la récurrence sera quant à lui pris en charge par la machine.