Scheda di revisione: Introduction à la programmation et récursivité

📋 Plan du Cours

1. Histoire de la programmation
2. Types de langages de programmation
3. Variables, types et opérations
4. Mise au point d’un programme
5. Bibliothèques et modularité
6. Récursivité et appels récursifs
7. Terminaison et correction partielle
8. Preuves des fonctions récursives

📖 2. Types de langages de programmation

🔑 Notions clés & Définitions

• Langages compilés : Ce sont des langages dont le code source est traduit par un compilateur en code binaire exécutable par la machine.
• Langages interprétés : Ce sont des langages dont le code source est exécuté par un interpréteur, ligne par ligne, sans produire directement de binaire exécutable.
• Langages semi-interprétés : Ce sont des langages où un compilateur produit d’abord un langage intermédiaire, puis l’interpréteur exécute ce bytecode.

📝 Points essentiels

• Un langage compilé produit un exécutable, tandis qu’un langage interprété exécute directement le code source via un interpréteur.
• Un langage semi-interprété traduit d’abord le code source en bytecode, puis l’interpréteur utilise ce fichier intermédiaire pour exécuter.
• Le cours cite comme exemples de langages compilés Fortran, Cobol, Pascal, Ada, C et C++.
• Le cours cite comme exemples de langages interprétés Prolog, HTML, JavaScript, Python et XML.
• Le cours cite comme exemples de langages semi-interprétés Lisp, Java, et C#.
• Un compilateur ou un interpréteur est lui-même un programme qui utilise le code (ou le bytecode) comme donnée.

💡 Astuce mémo

Compilé = Exécutable direct, Interprété = Ligne par ligne, Semi-interprété = Bytecode puis exécution.

📖 3. Variables, types et opérations

🔑 Notions clés & Définitions

• Variable locale : Une variable locale est une variable utilisable uniquement à l’intérieur d’une fonction où elle est définie.
• Variable globale : Une variable globale est définie hors d’une fonction et peut être lue partout dans le programme, y compris depuis ses fonctions.
• Gestion dynamique des types : En Python, le type d’une valeur peut changer pendant l’exécution, contrairement aux langages où les types sont fixés à la compilation.
• Slicing en Python : Le slicing en Python découpe une séquence et renvoie une sous-partie définie par des indices inclus/exclus.

📝 Points essentiels

• Les variables locales n’existent pas dans le code après l’appel : si on les référence hors de la fonction, le programme ne connaît pas ces noms.
• Dans une fonction, pour modifier une variable globale, on doit la déclarer avec le mot clé global avant l’affectation.
• La fonction isinstance(a, t) teste si la valeur a appartient au type t (ou à un tuple de types).
• L’opérateur + dépend des types : entre int il additionne, entre str il concatène, et entre int et list déclenche une exception TypeError.
• Le slicing liste[2:4] renvoie les éléments d’indices 2 inclus à 4 exclus, tandis que liste[:-1] exclut le dernier élément.

💡 Astuce mémo

• est « surchargé » : int + int = somme, str + str = concaténation, et int + liste = TypeError.

📖 4. Mise au point d’un programme

🔑 Notions clés & Définitions

• Docstring : La docstring est une documentation placée dans la fonction pour décrire son traitement, ses résultats (postconditions) et les contraintes sur ses arguments (préconditions).
• assertion Python : Une assertion vérifie une condition attendue et arrête l’exécution avec une erreur si la condition est fausse.
• tests unitaires : Les tests unitaires vérifient séparément chaque fonction ou partie du programme pour repérer rapidement les défauts localement.
• try/except : Le couple try/except exécute un bloc en gérant certaines exceptions afin d’éviter un arrêt brutal du programme.

📝 Points essentiels

• Les points de contrôle servent à détecter tôt des erreurs typiques comme indices invalides, conditions incomplètes, mauvais types en entrée et erreurs non gérées venant d’autres modules.
• Une docstring est écrite juste après le def avec des triples guillemets, et help(nom_fonction) affiche sa description dans la console.
• Une assertion s’écrit avec assert condition, et si la condition échoue Python lève une AssertionError et stoppe l’exécution.
• Les tests se structurent en unitaires, puis intégration, puis tests complets ; ignorer les deux premiers rend les tests complets peu utiles.
• En test d’égalité avec des flottants, des arrondis peuvent faire échouer des comparaisons directes comme 0.1 + 0.2 == 0.3.
• Le bloc try/except exécute try puis saute except si aucune exception n’a lieu, et s’arrête seulement si l’exception n’est pas prévue.

💡 Astuce mémo

Contrôle → Test → Gestion : assert bloque dès que la condition attendue est fausse, tests valident le comportement, try/except évite le crash en cas d’exception.

📖 5. Bibliothèques et modularité

🔑 Notions clés & Définitions

• Modularité : La modularité consiste à découper un programme en composants indépendants afin de les réutiliser et de les modifier plus facilement.
• Module Python : Un module Python est un fichier .py contenant des définitions de fonctions et/ou des instructions réutilisables depuis un autre programme.
• Instruction import : L’instruction import permet d’utiliser le contenu d’un module en précisant tout le module, une fonction, ou toutes les fonctions selon la syntaxe choisie.
• name égal à main : name vaut 'main' quand le fichier est lancé directement comme script, ce qui déclenche le bloc prévu pour l’exécution en tant que programme principal.
• Bibliothèque ou package : Une bibliothèque (ou package) est un ensemble de modules ajoutant des fonctionnalités dans un domaine, souvent installées avec l’IDE ou via pip.

📝 Points essentiels

• Un fichier script et un module ont tous deux l’extension .py : c’est l’usage (lancement direct ou import) qui détermine le rôle du fichier.
• import random puis random.randint(...) exige de préfixer les fonctions avec le nom du module, tandis que from random import randint permet d’appeler directement randint(...).
• from mon_module import * importe toutes les fonctions et est déconseillé car cela rend l’ensemble importé moins lisible et plus source d’erreurs potentielles.
• Pour installer un module hors distribution, on utilise pip, par exemple pip install pep8, puis on s’appuie sur la documentation du module pour connaître ses fonctions.
• Quand un fichier contient if name == "main":, le bloc est exécuté uniquement si le fichier est lancé comme script, pas quand il est importé.
• La documentation indique les signatures et contrats, par exemple random.randint(a,b) renvoie un entier N tel que a <= N <= b (alias de randrange(a, b+1)).

💡 Astuce mémo

Import → règle des préfixes : import module = module.f ; from module import f = f ; from module import * = tout (à éviter).

📖 6. Récursivité et appels récursifs

🔑 Notions clés & Définitions

• Fonction récursive : Une fonction récursive s’appelle elle-même pendant son exécution pour résoudre un problème en le réduisant.
• Cas de base : Un cas de base est une branche du code qui traite un cas simple pour fournir une valeur directement et déclencher l’arrêt des appels.
• Condition d’arrêt : Une condition d’arrêt est la situation du cas de base qui garantit que les appels ne continuent pas indéfiniment.
• Pile d’exécution : La pile d’exécution est une zone mémoire qui empile les contextes lors des appels de fonctions récursives puis les dépile à la fin.

📝 Points essentiels

• Pour une fonction récursive, la présence d’un cas de base est ce qui évite la boucle infinie en imposant un arrêt aux appels.
• Dans la factorielle récursive, le cas de base est n==0 renvoyant 1, puis sinon on calcule n * factorielle_recursive(n-1).
• Python limite le nombre d’appels récursifs et déclenche RecursionError quand la profondeur maximale est dépassée, par exemple avec sys.getrecursionlimit() dont la valeur par défaut est en général 1000.
• Lors d’un appel récursif, chaque appel empile un nouveau contexte dans la pile d’exécution, puis ces contextes sont dépilés en sens inverse après la condition d’arrêt.
• La pile fonctionne selon LIFO (Last In First Out), donc le dernier contexte empilé est dépilé le premier.

💡 Astuce mémo

Cas de base = STOP : dès que l’argument atteint le cas simple, la récursion s’arrête et les contextes se dépilent.

📖 7. Terminaison et correction partielle

🔑 Notions clés & Définitions

• Terminaison : Propriété d’un programme qui garantit qu’il s’arrête après un nombre fini d’étapes.
• Correction partielle : Propriété d’un programme qui garantit qu’il atteint le résultat attendu si l’exécution s’arrête effectivement.
• Variant de boucle : Quantité entière associée à une boucle qui reste positive ou nulle et décroît strictement à chaque itération.
• Invariant de boucle : Propriété $P(i)$ vraie à la fin et au début de chaque itération d’une boucle, donc vraie à l’entrée et à la sortie.

📝 Points essentiels

• La correction totale correspond à la conjonction de la terminaison et de la correction partielle du programme.
• Pour une boucle while, la terminaison se démontre en trouvant un variant de boucle entier qui décroît strictement et reste  positif ou nul tant que la boucle continue.
• Pour prouver la correction partielle, on choisit un invariant de boucle $P(i)$ et on vérifie qu’il est vrai avant et après chaque itération.
• Pour une fonction récursive, la terminaison vient du cas de base et du fait que les appels récursifs mènent vers ce cas d’arrêt.
• Pour la correction partielle d’une fonction récursive, on démontre un raisonnement du type $P(0)$ vrai puis $P(n)\\Rightarrow P(n+1)$, comme en récurrence mathématique.

💡 Astuce mémo

Variant = “baisse” (entier positif qui décroît) ; Invariant = “stabilité” (vrai tout au long des itérations).

📖 8. Preuves des fonctions récursives

🔑 Notions clés & Définitions

• Cas récursif : Le cas récursif est la partie où la fonction s’appelle elle-même, chaque appel devant conduire vers un cas de base.

📝 Points essentiels

• La terminaison d’une fonction récursive se prouve en montrant l’existence d’un cas de base et que les appels récursifs conduisent vers ce cas de base.
• Pour prouver la correction partielle, on raisonne comme en récurrence : on établit une propriété P(0) puis P(n) ⇒ P(n+1).
• Pour la factorielle récursive, le cas de base n <= 0 renvoie 1, ce qui correspond à 0 !.
• Pour la factorielle récursive, l’invariant choisi est P(i) : factorielle_recursive(i) = i !, puis on prouve que (n+1) ! = (n+1) × n ! assure P(n+1).
• Les preuves de terminaison et de correction partielle se rédigent en démonstration mathématique à partir du code (conditions d’arrêt et liens entre appels).
• Pour conclure à la correction totale d’une fonction récursive, on combine terminaison et correction partielle.

💡 Astuce mémo

Terminaison = cas de base + appels qui descendent; Correction partielle = P(0) puis P(n) ⇒ P(n+1) (comme en récurrence).

Trois types de langages de programmation

⚠️ Pièges & confusions fréquents

1. Confondre variable locale et variable globale : une locale n’existe qu’à l’intérieur de la fonction, donc elle n’est pas connue si on la référence ailleurs.
2. Oublier le mot-clé global : modifier une variable globale dans une fonction sans global ne modifie pas la variable globale attendue.
3. Croire que + a une seule signification : en Python l’opérateur + est surchargé et peut provoquer une TypeError si les types sont incompatibles (ex. int + list).
4. Se tromper dans le slicing : liste[2:4] inclut 2 et exclut 4, et liste[:-1] exclut le dernier élément.
5. Mélanger assertion et gestion d’erreur : assert échoue en produisant une AssertionError et stoppe l’exécution, tandis que try/except sert à gérer des exceptions.
6. Penser que la terminaison d’une boucle while est automatique : il faut trouver un variant de boucle qui décroît strictement et reste positif ou nul.
7. Rater l’étape “cas de base” en récursivité : sans cas de base (condition d’arrêt) la récursion n’a pas de garantie de s’arrêter et Python peut déclencher RecursionError.

✅ Checklist Examen

1. Savoir associer la programmation à l’écriture de code source d’un logiciel (ensemble de programmes) et distinguer logiciel vs programme.
2. Classifier correctement un langage en compilé, interprété ou semi-interprété à partir du rôle du compilateur/interpréteur (exécutable vs exécution ligne par ligne vs bytecode).
3. Savoir expliquer et appliquer la notion de variable locale et globale, y compris le rôle du mot-clé global pour modifier une globale depuis une fonction.
4. Tester le type avec isinstance(a, t) et interpréter correctement les conséquences d’une gestion dynamique des types en Python.
5. Reconnaître une surcharge de l’opérateur + selon les types des opérandes et identifier un cas où Python lève une TypeError.
6. Maîtriser le slicing : comprendre les bornes inclus/exclus et interpréter liste[1:], liste[2:4], liste[:-1].
7. Utiliser docstring correctement : placement juste après def avec triples guillemets, et comprendre l’usage de help(nom_fonction).
8. Écrire des assertions sous la forme assert condition, avec l’idée que l’échec produit une AssertionError et stoppe l’exécution.
9. Choisir un plan de tests adapté : unitaires puis intégration puis tests complets, et savoir rappeler le risque de tests d’égalité sur des flottants (ex. 0.1 + 0.2 == 0.3).
10. Gérer les erreurs avec try/except : comprendre la logique de saut de except si pas d’exception, continuer après le bloc except correspondant, et s’arrêter si exception non prévue.
11. Expliquer l’usage des modules : différence script/module, syntaxes import random vs from random import randint, et effet de if name == "main" lors du lancement direct.
12. Prouver terminaison et correction : distinguer variant de boucle (while) et invariant de boucle P(i), puis appliquer le même principe aux fonctions récursives (cas de base + appels vers l’arrêt, et raisonnement de type P(0), P(n) ⇒ P(n+1)).