Algorithmique basique en Python

Fiches de vocabulaire et notions fondamentales du cours d'algorithmique et programmation en Python.

Lexique (mots-clés)

Ensemble de mots réservés au sein d'un langage de programmation servant à éviter toute ambiguïté syntaxique ou sémantique.

Syntaxe

Règles formelles définissant la structure et la validité des instructions écrites dans un langage de programmation, décrites au moyen d'une grammaire formelle.

Symbole terminal (BNF étendue)

Mot ou signe figé directement issu du lexique du langage (par exemple : $si$, $alors$, $+$), ne pouvant plus être décliné.

Symbole non-terminal (BNF étendue)

Structure syntaxique notée entre chevrons ($\langle \dots \rangle$) représentant une règle grammaticale devant être remplacée par une déclinaison valide (ex. : $\langle entier \rangle$, $\langle condition \rangle$).

Méta-symboles BNF

Symboles servant à spécifier la grammaire elle-même : $::=$ (défini par), $|$ (alternative), $+$ (une fois ou plus), $*$ (zéro fois ou plus), $[\ ]$ (optionnel / au plus une fois), et $(\ )$ (groupement).

Typage dynamique (Python)

Propriété selon laquelle les variables ne possèdent pas de type fixe prédéclaré et peuvent référencer des données de natures distinctes au fil de l'exécution, bien que les valeurs en mémoire soient elles-mêmes strictement typées.

Fonction type()

Fonction prédéfinie retournant la classe ou le type effectif d'un objet ou d'une valeur passée en argument (ex. : $<class\ 'int'>$, $<class\ 'float'>$).

Type int

Type de données modélisant les entiers relatifs ($\mathbb{Z}$), dont la capacité de stockage en mémoire n'a pas de limite fixe en Python 3.

Division entière (//)

Opérateur arithmétique calculant le quotient euclidien entier issu de la division de deux nombres.

Modulo (%)

Opérateur arithmétique renvoyant le reste entier de la division euclidienne de deux opérandes.

Opérateur puissance (**)

Opérateur binaire calculant l'élévation à la puissance ($a^b$), remarquable pour son associativité à droite.

Type float

Type représentant les nombres en virgule flottante ($\approx \mathbb{R}$), conforme à la norme IEEE 754 en double précision, assurant environ 15 chiffres significatifs et un exposant d'ordre $10^{\pm 300}$.

Mantisse

Partie significative d'un nombre en virgule flottante qui détermine la précision et l'erreur relative lors de sa représentation machine.

Non-associativité des flottants

Phénomène numérique dans lequel l'égalité $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ n'est pas garantie sur les nombres flottants en raison des erreurs d'arrondi ou de troncature.

Divergence du calcul flottant

Instabilité numérique survenant lors d'opérations itératives (comme $A_{n+1} = 11 \times A_n - 1$ avec $A_1 = 0.1$) parce que la valeur décimale $0.1$ possède un développement binaire périodique infini non exact en machine.

Type bool

Type logique ne pouvant prendre que deux valeurs possibles : True ou False.

Opérateur d'égalité (==)

Prédicat comparant la valeur logique de deux expressions et retournant un booléen (True ou False), distinct de l'affectation ou d'une équation à résoudre.

Opérateur d'identité (is)

Opérateur vérifiant si deux variables font référence au même objet physique en mémoire, à ne pas confondre avec l'égalité de valeur $==$.

Valeurs considérées comme False (Falsy)

Éléments automatiquement évalués à faux dans un test booléen : None, le zéro numérique ($0$, $0.0$), et les collections ou séquences vides ($""$, $()$, $[]$, ${}$, $set()$, $range(0)$).

Type str

Type immuable modélisant une chaîne de caractères textuelle, encadrée par des guillemets simples ($'$), doubles ($"$), ou triples ($"""$ ou $'''$) pour les textes multi-lignes.

f-string (chaîne formatée)

Chaîne de caractères précédée du préfixe f ou F permettant d'incorporer directement des expressions Python entre accolades ${}$ afin qu'elles soient évaluées à la volée.

raw-string (préfixe r)

Chaîne de caractères précédée de la lettre r ou R empêchant l'interprétation des séquences d'échappement introduites par l'antislash (\).

Fonction repr()

Fonction fournissant une représentation textuelle non ambiguë d'un objet, généralement exploitable par l'interpréteur Python pour recréer fidèlement ledit objet.

Fonction eval()

Fonction invoquant de manière dynamique l'interpréteur Python pour analyser et exécuter le code contenu sous forme de chaîne de caractères.

Fonction print()

Fonction d'entrée/sortie standard assurant l'affichage console de ses arguments, paramétrable via les options sep (séparateur) et end (caractère final).

Fonction input()

Fonction d'entrée bloquante capturant une saisie utilisateur au clavier et la renvoyant sous forme de chaîne de caractères (str).

Affectation (=)

Opération consistant à lier un nom de variable à une valeur ou à une référence en mémoire, matérialisée par le signe =.

Affectation parallèle (simultanée)

Mécanisme associant simultanément un ensemble d'expressions à un ensemble de variables (par exemple : $x, y = y, x$) en utilisant en réalité des tuples.

Opérateurs combinés d'affectation

Opérateurs tels que +=, -=, *=, /= ou //= combinant une opération mathématique et la réaffectation du résultat sur la même variable.

Boucle while

Structure itérative fondamentale répétant un bloc d'instructions indenté tant que la condition logique associée reste évaluée à True.

Fonction range()

Générateur séquentiel d'entiers parcourant les valeurs depuis une borne minimale incluse jusqu'à une borne maximale exclue.

Algorithme d'Euclide (PGCD)

Méthode arithmétique efficace calculant le plus grand commun diviseur de deux entiers selon la relation $\text{pgcd}(u, v) = \text{pgcd}(v, u \pmod v)$ et $\text{pgcd}(u, 0) = |u|$.

Associativité à gauche

Règle syntaxique évaluant successivement les opérateurs de même niveau de priorité de la gauche vers la droite (comportement standard pour la majorité des opérateurs Python).

Associativité à droite

Règle syntaxique évaluant les opérateurs de même priorité de la droite vers la gauche, applicable notamment à l'opérateur puissance ($**$) et à l'affectation ($=$).

Type list

Structure de données dynamique, modifiable (mutable) et ordonnée, pouvant contenir des éléments de types variés indicés de $0$ à $n-1$.

Découpage de liste (slicing)

Syntaxe $a[i:j]$ extrayant une sous-séquence comprenant les éléments de l'indice $i$ inclus jusqu'à l'indice $j$ exclu.

Méthode append()

Méthode propre aux listes permettant d'ajouter un nouvel élément directement à la fin de la collection existante.

Méthode insert()

Méthode de liste insérant un nouvel élément à une position indicée précise en décalant les éléments suivants.

Liste en compréhension

Syntaxe concise créant une nouvelle liste par transformation et filtrage explicite d'un itérable selon la forme $[\text{f}(x)\ \text{for}\ x\ \text{in}\ \text{iterable}\ \text{if}\ \text{condition}]$.

Type tuple

Séquence ordonnée d'éléments non modifiable (immuable), couramment délimitée par des parenthèses.

Type dict

Structure de données associative organisée sous forme de paires clé: valeur ($dico[cle]$), où chaque clé doit être unique et immuable.

Pile (Stack)

Zone mémoire d'exécution réservée au stockage des variables locales et des pointeurs de référence.

Tas (Heap)

Zone de mémoire dynamique allouée pour héberger les objets créés (listes, dictionnaires, instances), distincte des identificateurs qui les référencent.

Partage de référence (Pile et Tas)

Situation survenant lors d'une affectation telle que $t2 = t1$, où deux variables situées dans la pile partagent et désignent le même objet physique en mémoire au sein du tas.