Éléments de Programmation en Python (UL1IN011 / LU1IN001)

Fiches de vocabulaire exhaustives couvrant les concepts fondamentaux de programmation en Python : types, expressions, instructions, boucles, preuves de correction et terminaison, complexité, structures de données, séquences, n-uplets, compréhensions, ensembles, dictionnaires, procédures de tableaux et orientation objet.

MrPython

Environnement de développement graphique et pédagogique dédié à l'apprentissage de Python en mode étudiant, structuré en quatre zones : la zone de commandes, la zone d'édition, la zone d'affichage et la zone d'évaluation d'expressions.

Expression atomique

Entité textuelle syntaxique élémentaire qui s'évalue directement en elle-même sans calcul ni décomposition, telle qu'un entier ($\text{int}$), un flottant ($\text{float}$), un booléen ($\text{bool}$) ou une chaîne littérale ($\text{str}$).

Expression composée

Combinaison arborescente de sous-expressions (atomiques ou composées) agencées à l'aide d'opérateurs arithmétiques, de comparateurs ou d'appels de fonctions.

Évaluation

Processus mécanique et déterministe réalisé par la machine consistant à calculer la valeur finale représentée par une expression bien formée.

Instruction

Ordre opérationnel donné à la machine pour exécuter une action ou modifier un état en mémoire, qui s'interprète séquentiellement et ne produit aucune valeur propre.

Spécification (d'une fonction)

Partie contractuelle du code décrivant le problème résolu et son mode d'utilisation externe sans exposer son algorithme interne ; elle regroupe l'en-tête typé (signature), les éventuelles préconditions et la description documentaire (docstring).

Précondition

Contrainte logique exprimée sous forme d'expression booléenne que les arguments d'entrée doivent impérativement satisfaire pour que le bon fonctionnement et la correction de la fonction soient garantis.

Instruction return

Instruction de contrôle interrompant immédiatement l'exécution du corps d'une fonction pour transmettre la valeur de retour calculée à l'expression appelante.

Variable locale

Emplacement mémoire alloué sur la pile, identifié par un nom choisi par le programmeur, typé et initialisé pour stocker temporairement une valeur utile aux calculs internes d'une fonction.

Alternative simple (if ... else)

Structure conditionnelle permettant d'effectuer un embranchement exclusif entre deux blocs d'instructions (conséquent ou alternant) selon la valeur de vérité d'une condition booléenne.

Évaluation paresseuse (court-circuit)

Mode d'évaluation des opérateurs logiques and et or dans lequel le second opérande n'est pas évalué dès lors que le premier opérande suffit à déterminer le résultat final de l'expression.

Prédicat

Fonction qui calcule une propriété logique et dont le résultat est exclusivement une valeur booléenne de type $\text{bool}$ (True ou False).

Boucle while

Instruction de répétition itérant l'exécution d'un bloc d'instructions (le corps de la boucle) tant que sa condition logique d'arrêt s'évalue à True.

Simulation de boucle

Tableau de suivi d'exécution décrivant chronologiquement, tour par tour, les états successifs pris par l'ensemble des variables modifiées dans le corps d'une boucle depuis l'entrée jusqu'à la sortie.

Invariant de boucle

Propriété logique reliant les variables du programme, vraie avant l'entrée dans la boucle et conservée après chaque tour de boucle, permettant d'établir formellement la correction du résultat à la sortie.

Variant de boucle

Grandeur entière positive à l'entrée de la boucle qui décroît strictement à chaque tour d'itération et s'annule lorsque la condition devient fausse, apportant la preuve que la boucle termine.

Problème de l'arrêt

Problème fondamental d'indécidabilité prouvé par Alan Turing démontrant l'inexistence d'un algorithme universel capable de déterminer à coup sûr si un programme arbitraire s'arrêtera ou bouclera indéfiniment.

Thèse de Church-Turing

Thèse affirmant l'équivalence d'expressivité entre les machines de Turing, le $\lambda$-calcul de Church et les fonctions récursives de Kleene, formalisant la notion universelle de calculabilité (Turing-complétude).

Séquence

Structure de données ordonnée linéairement regroupant une collection finie d'éléments accessibles séquentiellement ou par leur position indicée.

Type range

Séquence immuable représentant un intervalle fini d'entiers consécutifs délimité par une borne inférieure incluse $m$ et une borne supérieure exclue $n$, noté range(m, n).

Chaîne de caractères (str)

Séquence immuable de caractères textuels ordonnés et indexés selon la norme Unicode, délimitée par des apostrophes ou des guillemets.

Tranchage (slicing)

Opération d'extraction construisant une nouvelle sous-séquence à partir d'indices délimités selon la syntaxe s[i:j:k] (indice de début inclus $i$, indice de fin exclu $j$ et pas de saut $k$).

Schéma de réduction

Modèle algorithmique de parcours d'une séquence agrégeant ses éléments pas à pas afin de produire une information synthétique plus simple (telle qu'une somme, un comptage ou un booléen d'existence).

Schéma de transformation (map)

Modèle algorithmique consistant à appliquer une même fonction à chaque élément d'une séquence pour construire une nouvelle séquence transformée de même longueur.

Schéma de filtrage (filter)

Modèle algorithmique évaluant un prédicat sur chaque élément d'une séquence pour construire une sous-séquence formée uniquement des éléments validant cette condition.

Fonction partielle

Fonction mathématique ou informatique qui n'est pas définie pour toutes les valeurs possibles de son type d'entrée, signalant l'absence de résultat par la valeur None (type Optional[T]).

Variable de type (TypeVar)

Paramètre formel de type (couramment noté $T$) permettant de définir des fonctions polymorphes et génériques applicables à des structures de données quel que soit le type de leurs éléments.

Liste (List[T])

Structure de données séquentielle, homogène et mutable capable d'accueillir un nombre arbitraire d'éléments de même type ordonnés par indices.

Mutabilité

Caractéristique d'un objet informatique dont l'état interne peut être modifié en place directement en mémoire (sans réallocation ni reconstruction complète de la structure).

Méthode .append()

Opération primitive en place ajoutant un nouvel élément à la fin d'une liste existante par effet de bord sans reconstruire l'ensemble de la liste en mémoire.

Complexité asymptotique ($\Theta$)

Mesure mathématique de l'ordre de grandeur du temps de calcul ou de l'espace mémoire requis par un algorithme exprimée en fonction de la taille $n$ de ses entrées à des facteurs constants près.

Classes $P$ et $NP$

Classification de complexité séparant les problèmes décisionnels solubles en temps polynomial ($P$) de ceux dont une solution candidate peut être vérifiée en temps polynomial ($NP$).

$n$-uplet (Tuple)

Structure de données immuable et ordonnée composée d'un nombre fixe $n$ d'éléments ($n \ge 2$) pouvant chacun appartenir à des types hétérogènes distincts.

Déconstruction de $n$-uplet

Instruction extrayant simultanément les composantes d'un tuple dans des variables dédiées par déballage syntaxique de la forme v1, v2, ..., vn = u.

Alias de type

Identifiant synthétique attribué à une expression de typage complexe afin d'en faciliter la lecture et l'usage dans les signatures de fonctions.

Compréhension de liste

Syntaxe déclarative concise permettant de construire une liste par application combinée d'un parcours d'itérable, d'une transformation et d'un filtre sous la forme [elem for var in seq if cond].

Ensemble (Set[T])

Collection non ordonnée d'éléments uniques, distincts et immuables (hachables), éliminant d'emblée toute duplication et offrant des opérations d'appartenance à coût unitaire.

Dictionnaire (Dict[K, V])

Structure de données associative organisée sous forme de paires clé-valeur dans laquelle chaque clé unique et immuable de type $K$ permet un accès direct et rapide à sa valeur associée de type $V$.

Itérable

Structure de données abstraite (liste, ensemble, chaîne, intervalle, dictionnaire) capable de fournir successivement ses éléments au protocole de boucle for ou aux compréhensions.

Procédure

Fonction programmée principalement pour produire un effet de bord en mémoire sur des structures mutables ou vers des canaux de sortie, renvoyant la valeur conventionnelle None.

Remplacement en place (l[i] = e)

Instruction modifiant directement la case mémoire associée à l'indice $i$ d'un tableau ou d'une liste sans réallocation ni copie des autres éléments.

Tri par sélection

Algorithme de tri quadratique ($\Theta(n^2)$) procédant de gauche à droite en recherchant à chaque étape le plus petit élément restant pour l'échanger en place avec l'élément d'indice courant.

Tri-fusion (Merge Sort)

Algorithme de tri efficace selon le principe diviser pour régner scindant la liste en sous-listes unitaires avant de les réassembler deux à deux par interclassement ordonné en complexité $\Theta(n \log_2(n))$.

Carré magique

Matrice carrée de dimension $n \times n$ constituée de tous les entiers distincts de $1$ à $n^2$ telle que les sommes de chaque ligne, de chaque colonne et des deux diagonales principales sont toutes rigoureusement égales.

Classe (Programmation Orientée Objet)

Description structurelle définissant un nouveau type abstrait d'objet en encapsulant ses variables d'état (attributs) et les opérations autorisées pour les manipuler (méthodes).