Exercices corrigés de NSI : langages et programmation

a) L'appel fact(4) empile un cadre, constate que 4 est supérieur à 1 et appelle fact(3) : un deuxième cadre est empilé, puis un troisième pour fact(2), puis un quatrième pour fact(1). C'est à ce moment, et seulement à ce moment, que le premier résultat apparaît : fact(1) atteint le cas de base et renvoie 1 sans rien appeler. Le dépilement suit alors l'ordre INVERSE de l'empilement : fact(2) reçoit 1 et renvoie $2 \times 1 = 2$ ; fact(3) reçoit 2 et renvoie $3 \times 2 = 6$ ; fact(4) reçoit 6 et renvoie $4 \times 6 = 24$. Rien n'est calculé à la descente, tout l'est à la remontée : c'est exactement ce que montre la colonne de droite de la figure.

b) Le cas de base est n inférieur ou égal à 1, qui renvoie 1 sans appel récursif. Sans lui, chaque appel en déclencherait un autre indéfiniment, avec des valeurs de n de plus en plus petites qui ne rencontreraient jamais de condition d'arrêt. La pile grossirait jusqu'à saturation, et Python lèverait une RecursionError, avec le message « maximum recursion depth exceeded ». Le programme ne bouclerait donc pas éternellement : il s'arrêterait par épuisement de la pile, ce qui est une chance, car cela donne un message au lieu d'un gel.

c) Pour fact(n), la pile contient au plus n cadres, un par valeur de n jusqu'au cas de base. Python fixe par défaut une profondeur maximale de récursion de l'ordre de 1 000 : un appel à fact(1500) échoue donc, alors que le calcul lui-même n'aurait rien d'impossible. Cette limite existe parce que la pile d'exécution occupe une zone mémoire de taille fixe, réservée au démarrage du fil : sans garde-fou, une récursion incontrôlée l'écraserait et corromprait les données voisines. Mieux vaut une erreur nette qu'un comportement imprévisible.

d) Version itérative : on initialise un résultat à 1, puis pour k allant de 2 à n on multiplie le résultat par k, et on renvoie le résultat. Comparaison. LISIBILITÉ : la version récursive colle à la définition mathématique, la version itérative demande d'inventer un accumulateur ; avantage au récursif pour la factorielle. MÉMOIRE : la version récursive consomme n cadres de pile, la version itérative une seule variable ; avantage net à l'itératif. ROBUSTESSE : la version itérative fonctionne pour n valant un million, la récursive échoue au-delà de mille ; avantage net à l'itératif. On retient que la récursivité est un outil d'EXPRESSION, excellent quand le problème est naturellement récursif, comme un arbre, et coûteux quand une simple boucle suffit.

e) La fonction : si la chaîne est vide, renvoyer la chaîne vide ; sinon renvoyer l'inverse de tout sauf le premier caractère, suivi du premier caractère. En Python : return inverse(s[1:]) + s[0]. Trace sur « abcd » : inverse('abcd') appelle inverse('bcd') et gardera 'a' ; inverse('bcd') appelle inverse('cd') et gardera 'b' ; inverse('cd') appelle inverse('d') et gardera 'c' ; inverse('d') appelle inverse('') et gardera 'd' ; inverse('') renvoie ''. À la remontée : 'd', puis 'dc', puis 'dcb', puis 'dcba'. Le résultat est 'dcba'. On note au passage que chaque appel construit une nouvelle chaîne, donc cette version coûte un temps quadratique en la longueur, ce que la version itérative évite.

a) L'arbre compte 9 appels au total pour fib(4). Les sous-problèmes répétés : fib(2) apparaît DEUX fois, une fois sous fib(3) et une fois directement sous fib(4) ; fib(1) apparaît TROIS fois ; fib(0) apparaît deux fois. Aucun résultat n'est conservé, si bien que chaque occurrence est entièrement recalculée. Ce gaspillage n'est pas anecdotique : c'est lui qui rend le coût exponentiel.

b) Un appel à fib(n) pour n supérieur à 1 fait un appel pour lui-même, plus tous ceux de fib(n-1) et de fib(n-2) : donc $T(n) = 1 + T(n-1) + T(n-2)$, avec $T(0) = T(1) = 1$. Calculs : $T(2) = 1 + 1 + 1 = 3$ ; $T(3) = 1 + 3 + 1 = 5$ ; $T(4) = 1 + 5 + 3 = 9$, ce qui confirme la figure ; $T(5) = 1 + 9 + 5 = 15$ ; $T(6) = 1 + 15 + 9 = 25$.

c) $T(30) = 2 \times F(31) - 1 = 2 \times 1\ 346\ 269 - 1 = 2\ 692\ 537$ appels. Vérification de la formule sur un petit cas : pour $n = 5$, $F(6) = 8$ donc $T(5) = 2 \times 8 - 1 = 15$, ce qui coïncide avec le calcul de la question b. Près de trois millions d'appels pour un résultat qui tient sur six chiffres : la croissance est exponentielle, de raison le nombre d'or, environ $1{,}618$.

d) La fonction mémoïsée : on crée un dictionnaire vide en dehors de la fonction, ou passé en argument par défaut ; à chaque appel, si n figure déjà comme clé, on renvoie la valeur enregistrée ; sinon on calcule comme avant, on enregistre le résultat sous la clé n, et on le renvoie. Pour n valant 30, chaque valeur de 0 à 30 n'est calculée qu'une seule fois, soit 31 calculs, les autres appels se réduisant à une lecture dans le dictionnaire. Le facteur de gain vaut $2\ 692\ 537 / 31 \approx 86\ 856$, soit près de quatre-vingt-sept mille fois moins de travail. Le code n'a pourtant changé que de deux lignes.

e) Version itérative : on garde deux variables a et b valant 0 et 1, et on répète n fois l'affectation simultanée a, b devient b, a + b ; on renvoie a. Son coût est LINÉAIRE en temps, n additions, et CONSTANT en mémoire, deux variables. Je choisirais celle-là. Argument contre la version naïve : elle est exponentielle, donc inutilisable au-delà d'une quarantaine. Argument contre la version mémoïsée : elle est correcte et rapide, mais elle consomme n cadres de pile et n entrées de dictionnaire, donc une mémoire linéaire pour un problème qui n'en demande aucune, et elle reste soumise à la limite de profondeur de récursion. La leçon générale : la mémoïsation sauve un algorithme récursif, elle ne le rend pas meilleur qu'une itération quand celle-ci existe.

a) La CLASSE est le modèle : elle décrit ce que tout compte possède et ce qu'on peut lui faire. Une INSTANCE est un objet créé d'après ce modèle, avec ses propres valeurs. Un ATTRIBUT est une donnée portée par l'instance, ici titulaire et solde. Une MÉTHODE est une fonction définie dans la classe et appelée sur une instance. Les deux expressions créent DEUX objets distincts, chacun avec son propre titulaire et son propre solde : modifier l'un ne touche pas l'autre, contrairement à ce qui se passerait avec un alias.

b) Le paramètre self désigne l'INSTANCE sur laquelle la méthode est appelée : c'est par lui que la méthode accède aux attributs de cet objet-là plutôt qu'à ceux d'un autre. Quand on écrit c.deposer(50), Python appelle en réalité Compte.deposer(c, 50), et c'est c qui arrive dans self. Si on l'oubliait dans la signature, l'appel passerait quand même l'instance comme premier argument, qui se retrouverait dans montant, et l'ajout de 50 n'aurait aucun destinataire : Python lèverait une TypeError signalant que la méthode prend un argument et en reçoit deux.

c) Après la création, le solde vaut 100. Après le dépôt de 50, il vaut 150. Le retrait de 200 déclenche la condition montant supérieur au solde, donc la méthode lève une ValueError portant le message « solde insuffisant » et n'exécute PAS la soustraction. L'état final est donc un solde de 150, inchangé, et une exception remontée à l'appelant. Le point important est que l'objet reste COHÉRENT : il vaut mieux une exception qu'un compte à moins 50 que personne n'aurait remarqué.

d) Le tiret bas initial est une CONVENTION qui signale aux autres programmeurs que l'attribut est interne et qu'il ne faut pas y toucher depuis l'extérieur. Python ne l'interdit pas : l'écriture c._solde = -1000 fonctionne parfaitement et casse l'invariant. L'encapsulation ne garantit donc pas l'impossibilité, elle garantit la RESPONSABILITÉ : tant qu'on ne passe que par les méthodes publiques, aucun état incohérent n'est atteignable, et si un tel état apparaît, on sait où chercher. C'est un contrat entre programmeurs autant qu'un mécanisme du langage, et les langages qui l'imposent réellement, comme Java avec le mot-clé privé, ne font que déplacer la question, puisque la réflexion permet encore de contourner.

e) L'invariant de classe : le solde est toujours supérieur ou égal à zéro. Vérification méthode par méthode. Le CONSTRUCTEUR le préserve si le solde initial est positif ou nul, ce qui n'est pas vérifié dans le code proposé : c'est un défaut, il faudrait rejeter un solde initial négatif. DEPOSER n'ajoute qu'un montant strictement positif, donc il ne peut pas rendre le solde négatif. RETIRER refuse tout montant supérieur au solde, donc le résultat reste positif ou nul. SOLDE ne modifie rien. Trois méthodes sur quatre préservent l'invariant, et l'analyse a mis au jour le trou du constructeur, ce qui est exactement à quoi sert un invariant : il transforme une relecture vague en une vérification finie.

a) La classe Cercle : elle hérite de Forme ; son constructeur reçoit self et r, et enregistre self.r = r ; sa méthode aire renvoie $\pi \times r^{2}$, ce qui s'écrit pi * self.r ** 2 après avoir importé pi. La classe Carre : elle hérite de Rectangle ; son constructeur reçoit self et c, et appelle le constructeur de la classe parente avec c et c, ce qui s'écrit super().__init__(c, c). Elle ne redéfinit pas aire : celle de Rectangle convient déjà, puisqu'un carré est un rectangle dont les deux côtés sont égaux. C'est exactement l'intérêt de l'héritage, ne pas réécrire ce qui est déjà juste.

b) Rectangle de 6 sur 4 : aire $= 6 \times 4 = 24$. Carré de côté 5 : le constructeur appelle celui de Rectangle avec 5 et 5, donc aire $= 5 \times 5 = 25$. Cercle de rayon 3 : aire $= \pi \times 3^{2} = 9\pi \approx 28{,}27$. Les trois objets répondent à la même méthode decrire, qui appellera pour chacun la bonne version de aire.

c) Le mécanisme s'appelle le POLYMORPHISME. Il repose sur le fait que l'appel self.aire() est résolu à l'EXÉCUTION, en fonction de la classe réelle de l'objet, et non à l'écriture en fonction du type déclaré. Quand decrire s'exécute sur un cercle, self.aire() trouve la méthode aire de Cercle ; sur un carré, il trouve celle de Rectangle, héritée. La méthode decrire n'a donc jamais besoin de savoir à quelle forme elle a affaire, et l'ajout d'une classe Triangle demain ne demandera aucune modification. C'est le principal bénéfice pratique de l'objet : on ajoute des cas sans toucher au code existant.

d) Parce que Forme est une classe ABSTRAITE : elle décrit ce que toute forme doit savoir faire, sans savoir le faire elle-même. Renvoyer 0 serait un mensonge silencieux, qui produirait des résultats faux dans les calculs de total sans jamais signaler l'oubli. Lever une exception transforme une erreur de CONCEPTION, une sous-classe qui a oublié d'implémenter aire, en une erreur bruyante et localisée. Si l'on créait une Forme directement, l'objet existerait, mais tout appel à aire ou à decrire lèverait NotImplementedError : le défaut apparaîtrait donc au premier usage, ce qui est le meilleur moment.

e) Argument POUR : un carré n'a qu'un seul paramètre, alors qu'il hérite de deux attributs L et l ; si Rectangle acquiert un jour une méthode qui change une seule dimension, le carré héritera d'une opération qui casse son invariant, car un carré redimensionné dans une seule direction n'est plus un carré. Argument CONTRE : refaire hériter Carre de Forme oblige à réécrire aire, périmètre, et toute autre méthode déjà écrite dans Rectangle, ce qui duplique du code et fera diverger les deux versions à la première correction. Je tranche en faveur du POUR : la duplication se gère, la violation d'invariant ne se gère pas. La règle générale est qu'on hérite quand la sous-classe peut être utilisée PARTOUT où la classe parente est attendue, sans surprendre l'appelant ; ce n'est pas le cas ici dès qu'une méthode de redimensionnement existe. Le carré et le rectangle sont d'ailleurs l'exemple canonique de ce piège.

a) La spécification doit préciser trois choses. La PRÉCONDITION : la liste doit être non vide, et ses éléments doivent être deux à deux comparables. La POSTCONDITION : la valeur renvoyée est un indice valide, et aucun élément n'est strictement supérieur à celui d'indice renvoyé. Le cas des EX AEQUO : si plusieurs éléments sont maximaux, la fonction renvoie l'indice du PREMIER d'entre eux, ce qui est le comportement du code puisque la comparaison est stricte. Écrire ce dernier point n'est pas une formalité : sans lui, un programme appelant ne peut pas savoir sur quel comportement compter, et une réécriture ultérieure pourrait le changer sans que personne ne s'en aperçoive.

b) Six jeux. Un seul élément, [7] : réponse 0, cas limite minimal. Maximum en tête, [9, 3, 5] : réponse 0, vérifie que l'initialisation ne fausse rien. Maximum en fin, [3, 5, 9] : réponse 2, vérifie que la boucle va jusqu'au bout. Maximum au milieu, [3, 9, 5] : réponse 1, cas ordinaire. Ex aequo, [4, 9, 9, 2] : réponse 1, vérifie la règle du premier maximum. Valeurs négatives, [-8, -3, -5] : réponse 1, vérifie qu'aucune hypothèse de positivité ne s'est glissée, erreur fréquente quand on initialise le maximum à zéro au lieu du premier élément.

c) Sur une liste vide, len(t) vaut 0, la boucle ne s'exécute pas, et la fonction renvoie 0 : un indice qui n'existe pas. C'est le pire des comportements, car il ne signale rien et l'appelant provoquera un IndexError beaucoup plus loin, à un endroit sans rapport. Deux traitements possibles. Le premier : lever explicitement une ValueError avec un message clair. Le second : renvoyer une valeur nulle, à charge pour l'appelant de la tester. Le premier respecte mieux la spécification écrite en a, puisque celle-ci pose la non-vacuité en PRÉCONDITION : violer une précondition doit produire une erreur, pas un résultat. Renvoyer une valeur nulle changerait le type de retour et obligerait chaque appelant à un test, ce qui est précisément ce qu'une précondition évite.

d) Oui, le résultat change en cas d'ex aequo : avec une comparaison large, chaque nouvelle occurrence du maximum remplace l'indice, si bien que la fonction renvoie l'indice du DERNIER maximum au lieu du premier. Sur [4, 9, 9, 2], la version stricte renvoie 1 et la version large renvoie 2. La différence n'est visible que sur les jeux de tests comportant des ex aequo : les cinq autres jeux de la question b donneraient exactement les mêmes réponses. C'est la démonstration qu'un jeu de tests sans ex aequo laisserait passer la modification sans rien dire, alors qu'elle change le contrat.

e) Une ASSERTION est une vérification écrite DANS le code, qui s'exécute à chaque passage et interrompt le programme si elle est fausse ; elle sert à documenter et à faire respecter une hypothèse interne, et elle ne peut pas remplacer la validation des données venues de l'extérieur, puisqu'on la désactive souvent en production. Un TEST UNITAIRE est un programme séparé qui appelle la fonction sur des cas choisis et compare au résultat attendu ; il sert à vérifier le contrat et surtout à détecter les régressions lors des modifications futures, mais il ne prouve rien sur les cas non testés. Un POINT D'ARRÊT suspend l'exécution pour inspecter l'état ; il sert à COMPRENDRE un comportement déjà constaté comme faux, et il ne laisse aucune trace, donc il ne protège en rien contre le retour du même défaut. Les trois sont complémentaires : l'assertion documente, le test protège, le point d'arrêt explique.

a) L'invariant : à l'entrée de chaque tour de boucle, la variable imax contient l'indice d'un plus grand élément parmi les éléments d'indices 0 à $i - 1$, c'est-à-dire parmi la zone déjà examinée de la figure, et c'est l'indice du premier d'entre eux en cas d'égalité. Formulé autrement, imax est la réponse correcte pour le préfixe examiné jusqu'ici. Le point de méthode : un invariant utile parle du travail DÉJÀ FAIT, jamais de ce qui reste, et c'est ce qui le rend vrai avant même le premier tour.

b) INITIALISATION : avant le premier tour, $i$ vaut 1 et imax vaut 0. La zone examinée se réduit à l'élément d'indice 0, dont imax est bien l'indice du maximum : l'invariant est vrai. CONSERVATION : supposons l'invariant vrai à l'entrée d'un tour d'indice $i$. Le corps compare t[i] à t[imax]. Si t[i] est strictement plus grand, alors t[i] dépasse tous les éléments de la zone examinée, puisqu'il dépasse leur maximum, et imax prend la valeur $i$ : l'invariant est vrai pour la zone étendue à $i$. Sinon, t[i] ne dépasse pas t[imax], donc l'ancien maximum reste maximal sur la zone étendue et imax est inchangé : l'invariant est encore vrai. Dans les deux cas il est préservé, et la stricte inégalité garantit qu'un ex aequo ne déplace pas imax, donc que le premier maximum est conservé. CONCLUSION : la boucle se termine lorsque $i$ atteint len(t). L'invariant s'applique alors à la zone d'indices 0 à len(t) moins 1, c'est-à-dire à la liste entière : imax est bien l'indice du premier maximum de t. C'est exactement la postcondition annoncée.

c) Un variant de boucle est une quantité entière, positive ou nulle, qui décroît STRICTEMENT à chaque tour. Son existence prouve la terminaison, car une suite d'entiers positifs strictement décroissante est finie. Ici, on peut prendre $\text{len}(t) - i$ : il vaut len(t) moins 1 au départ, il est positif ou nul tant qu'on entre dans la boucle, et il diminue exactement de 1 à chaque tour puisque $i$ augmente de 1. La boucle effectue donc au plus len(t) moins 1 tours et se termine.

d) La CORRECTION PARTIELLE affirme : si le programme se termine, alors son résultat vérifie la postcondition. La CORRECTION TOTALE ajoute qu'il se termine effectivement. En b, on a établi la correction partielle, par l'invariant ; en c, la terminaison, par le variant. Les deux réunies donnent la correction totale. La distinction n'est pas scolaire : un programme peut être parfaitement correct au sens partiel et boucler indéfiniment, auquel cas il n'a jamais l'occasion d'être faux, et il est pourtant inutilisable.

e) Un test qui passe ne prouve PAS la correction : il montre que le programme est juste sur les cas essayés, et rien au-delà. La fonction de l'exercice 5 passe les six tests de la question b sans traiter la liste vide. Ce que la preuve apporte en plus : une garantie sur TOUS les cas, y compris ceux auxquels personne n'a pensé. Une preuve ne dispense pas des tests pour autant. Ce que les tests apportent en plus : ils vérifient que le programme réellement exécuté correspond à celui qu'on a prouvé, ce qui exclut les fautes de frappe, les erreurs de traduction du raisonnement en code, les défauts de l'environnement, dépassement d'entier, arrondi de flottant, bibliothèque qui ne fait pas ce qu'elle annonce. La preuve porte sur le modèle, les tests portent sur la machine, et les deux échouent sur des choses différentes.

a) Les nombres pairs de la liste sont 4, 6 et 2. Leurs carrés valent 16, 36 et 4. La somme vaut $16 + 36 + 4 = 56$. Les deux fonctions renvoient 56, ce qui est le point de départ de l'exercice : elles calculent exactement la même chose.

b) Le paradigme IMPÉRATIF décrit une SUITE D'ÉTAPES qui modifient un état : on part d'un total nul et on le fait évoluer. Le paradigme FONCTIONNEL décrit une EXPRESSION à évaluer, composée de transformations appliquées à des valeurs, sans état modifié. La différence ne porte pas sur le résultat, qui est identique, mais sur la façon de l'obtenir et sur ce qu'on peut en dire : la version fonctionnelle se lit comme la définition du problème, la version impérative se lit comme sa recette.

c) Un effet de bord est une modification observable de l'état extérieur à la fonction : écrire dans une variable globale, modifier un argument, écrire dans un fichier, afficher quelque chose. La version impérative modifie la variable locale total, ce qui n'est pas un effet de bord au sens strict puisque total meurt avec l'appel ; aucune des deux versions n'a d'effet de bord observable, et c'est justement ce qui les rend interchangeables. Une fonction sans effet de bord est plus facile à TESTER parce qu'il suffit de lui donner des arguments et de comparer le résultat, sans préparer ni vérifier un état ; et plus facile à PARALLÉLISER parce que deux appels ne peuvent pas se gêner, aucun n'écrivant dans un emplacement que l'autre lit. C'est exactement le problème de section critique de l'exercice sur la concurrence, qui disparaît par construction.

d) La classe : son constructeur reçoit la liste et l'enregistre dans un attribut ; la méthode somme_carres_pairs parcourt cet attribut et renvoie la somme, par l'un ou l'autre des deux styles précédents. L'intérêt réel n'est pas dans ce calcul, qui n'a pas besoin d'objet : il apparaît dès que l'on veut plusieurs opérations sur la même donnée, un état à maintenir entre les appels, par exemple un cache des résultats déjà calculés, ou plusieurs variantes de série partageant la même interface, par exemple une série paresseuse lisant un fichier au fur et à mesure. L'objet se justifie quand il y a un INVARIANT à protéger ou une famille de variantes à substituer, jamais pour envelopper une fonction unique.

e) Oui, la plupart des langages modernes sont multiparadigmes. Pour Python : la boucle for avec affectation relève de l'IMPÉRATIF ; les compréhensions, les fonctions passées en argument et les fonctions anonymes relèvent du FONCTIONNEL ; les classes, l'héritage et les méthodes spéciales relèvent de l'OBJET. Ce qui décide en pratique n'est pas la mode mais la nature du problème : on prend le fonctionnel pour une transformation de données sans état, l'objet dès qu'il y a un invariant à garantir ou des variantes à substituer, et l'impératif quand l'algorithme est intrinsèquement séquentiel ou quand la performance exige un contrôle fin. Un bon programme mélange les trois, chacun là où il est le plus clair.

1) FAUX. Chaque appel empile un cadre, et la pile est de taille finie : le programme s'arrête par épuisement de la pile, avec une RecursionError. Énoncé correct : une récursion sans cas de base s'arrête sur un débordement de pile, ce qui est une chance, car un message d'erreur vaut mieux qu'un gel silencieux.

2) FAUX. Le défaut est ALGORITHMIQUE et non linguistique : le nombre d'appels croît exponentiellement, environ $2\ 692\ 537$ pour n valant 30, parce que les mêmes sous-problèmes sont recalculés. Un langage cent fois plus rapide ne ferait gagner qu'une dizaine de valeurs de n, puisque $1{,}618^{10} \approx 123$. Énoncé correct : la version naïve est lente parce qu'elle recalcule ses sous-problèmes ; la mémoïsation la ramène à 31 calculs, dans le même langage.

3) FAUX. Le tiret bas initial est une convention, pas une barrière : écrire c._solde = -1000 fonctionne. Énoncé correct : l'encapsulation garantit qu'aucun état incohérent n'est atteignable TANT QU'ON PASSE PAR LES MÉTHODES PUBLIQUES ; c'est un contrat entre programmeurs, dont le langage ne fait que signaler l'existence.

4) FAUX. Un test montre que le programme est juste sur les cas essayés, et rien de plus. La fonction indice_max passe les six tests de l'exercice 5 tout en renvoyant un indice inexistant sur une liste vide. Énoncé correct : un jeu de tests détecte des erreurs, il n'établit jamais leur absence ; seule une preuve, invariant et variant, porte sur tous les cas.

5) FAUX, et la confusion est classique. L'indécidabilité du problème de l'arrêt dit qu'aucun programme ne peut décider l'arrêt pour TOUT couple formé d'un programme et d'une entrée. Elle ne dit rien sur un cas particulier : on démontre très bien la terminaison de la plupart des programmes réels, par un variant. Énoncé correct : il n'existe pas de méthode universelle, ce qui n'empêche nullement de prouver la terminaison d'un programme donné.

a) Le problème de l'arrêt demande s'il existe un ALGORITHME qui, recevant en entrée le texte d'un programme et une donnée, répond en un temps fini et à coup sûr par oui ou par non à la question « ce programme s'arrête-t-il sur cette donnée ». On ne peut pas simplement exécuter le programme pour voir, parce qu'après une heure d'attente on ne sait toujours rien : le programme s'arrêtera peut-être dans une minute, peut-être jamais. L'exécution répond « oui » quand la réponse est oui, mais elle ne répond JAMAIS « non ». Or on exige un algorithme qui se termine dans les deux cas.

b) On construit la fonction suivante, appelons-la diagonale, qui prend un programme p en argument : si arrete(p, p) renvoie True, alors diagonale entre dans une boucle infinie ; sinon, diagonale s'arrête immédiatement. Autrement dit, diagonale fait exactement le CONTRAIRE de ce que arrete prédit pour p appliqué à lui-même. On applique alors diagonale à son propre texte. Deux cas, tous deux impossibles. Si diagonale(diagonale) s'arrête, c'est que arrete(diagonale, diagonale) a renvoyé False, donc que diagonale ne s'arrête pas sur cette entrée : contradiction. Si diagonale(diagonale) ne s'arrête pas, c'est que arrete a renvoyé True, donc que diagonale s'arrête sur cette entrée : contradiction encore. Les deux branches sont contradictoires, et il n'y en a pas de troisième.

c) La supposition de départ, l'existence de arrete, conduit à une contradiction dans tous les cas : elle est donc fausse. Aucune fonction arrete, totale et correcte, n'existe. Le résultat NE DÉPEND PAS du langage employé : la construction n'utilise que la capacité à prendre un programme comme donnée, à l'appeler, à tester un booléen et à boucler, capacités que possède tout langage assez expressif pour être utilisable. Tous ces langages calculent d'ailleurs exactement la même classe de fonctions, et un langage qui échapperait à l'argument serait un langage dans lequel on ne pourrait pas écrire diagonale, donc trop pauvre pour programmer.

d) Première conséquence, pour le DÉVELOPPEUR : aucun outil ne pourra jamais garantir, sur tout programme, l'absence de boucle infinie, l'égalité de deux fonctions, ou le fait qu'une ligne soit atteignable. Il faut donc se contenter d'outils qui répondent « oui », « non » ou « je ne sais pas », et écrire soi-même les variants pour les cas qui comptent. Seconde conséquence, pour un ÉDITEUR D'ANTIVIRUS : il n'existe pas et ne peut pas exister de programme qui décide, pour tout fichier, s'il est malveillant, puisque cela reviendrait à décider une propriété du comportement d'un programme. C'est pourquoi les antivirus fonctionnent par SIGNATURES de menaces déjà connues et par heuristiques comportementales, méthodes qui se trompent nécessairement dans les deux sens et qu'il faut mettre à jour sans fin.

e) Un tel outil ne peut garantir la réponse que sur les programmes qu'il sait analyser ; sur les autres, il devrait dire « je ne sais pas ». Un FAUX POSITIF serait ici de signaler une boucle infinie qui n'existe pas : l'outil réveille le développeur pour rien, ce qui coûte du temps mais ne laisse rien passer. Un FAUX NÉGATIF serait de déclarer sain un programme qui boucle réellement : l'outil endort la vigilance, et le défaut part en production. Un outil sérieux choisit d'accepter les FAUX POSITIFS et refuse les faux négatifs : il est CONSERVATEUR, il refuse ce dont il n'est pas sûr. C'est le principe de tout analyseur statique et de tout vérificateur de type : il rejette des programmes corrects plutôt que d'accepter des programmes faux, et c'est ce choix, et non une quelconque limite technique, qui explique qu'il paraisse parfois trop sévère.

a) La spécification. OPÉRATIONS. Créer une file vide : aucune précondition, postcondition, la file est vide. Enfiler un élément avec une priorité : précondition, la priorité est un entier ; postcondition, la file contient un élément de plus, et l'ordre de service des autres n'est pas modifié. Défiler : précondition, la file n'est pas vide ; postcondition, l'élément renvoyé est de priorité minimale, et parmi ceux de priorité minimale, c'est le plus anciennement enfilé ; la file en contient un de moins. Tester la vacuité : aucune précondition, renvoie un booléen. INVARIANT de structure : le nombre d'éléments est positif ou nul, et pour toute paire d'éléments présents, l'ordre de service est déterminé de façon unique par le couple formé de la priorité et du rang d'arrivée.

b) Implémentation par LISTE TRIÉE : à l'insertion, on parcourt la liste pour trouver la position, ce qui coûte un temps linéaire, puis on insère ; le retrait prend le premier élément, coût constant. Implémentation par LISTE NON TRIÉE : l'insertion ajoute en fin, coût constant ; le retrait parcourt toute la liste pour trouver le minimum, coût linéaire. Les deux échangent donc exactement le même coût entre les deux opérations. Une troisième implémentation, par tas binaire, offre un coût logarithmique pour les DEUX opérations, ce qui est strictement meilleur dès que les deux sont fréquentes.

c) Sur $n$ insertions puis $n$ retraits. LISTE TRIÉE : la $k$-ième insertion parcourt au plus $k - 1$ éléments, soit un total de $1 + 2 + \dots + (n-1) = n(n-1)/2$ opérations ; les $n$ retraits coûtent $n$ opérations. Total de l'ordre de $n^{2}/2$. LISTE NON TRIÉE : les insertions coûtent $n$ ; le $k$-ième retrait parcourt $n - k + 1$ éléments, soit encore $n(n+1)/2$ au total. Total également de l'ordre de $n^{2}/2$. Pour $n = 10\ 000$ : dans les deux cas environ $5 \times 10^{7}$ opérations. Un tas binaire donnerait $2 n \log_{2} n \approx 2 \times 10\ 000 \times 13{,}3 \approx 2{,}66 \times 10^{5}$ opérations, soit environ 188 fois moins. La conclusion est que le choix entre les deux premières implémentations ne se fait pas sur le total mais sur le PROFIL d'usage : si l'on insère beaucoup et retire rarement, la liste non triée gagne, et réciproquement.

d) Six jeux. Un, file vide : défiler doit lever une erreur, et le test de vacuité doit renvoyer vrai. Deux, un seul élément : enfiler puis défiler rend cet élément, et la file redevient vide. Trois, priorités déjà croissantes, enfiler 1, 2, 3 : on doit défiler 1, 2, 3. Quatre, priorités décroissantes, enfiler 3, 2, 1 : on doit défiler 1, 2, 3, ce qui vérifie que l'ordre d'arrivée n'écrase pas la priorité. Cinq, PRIORITÉS ÉGALES, enfiler A puis B tous deux en priorité 5 : on doit défiler A puis B, ce qui vérifie la règle du premier arrivé. Six, entrelacement, enfiler 5, défiler, enfiler 2, enfiler 5, défiler, défiler : vérifie que les insertions faites après un retrait s'ordonnent correctement avec les éléments restants. Le cinquième jeu est le plus important : c'est le seul qui distingue une implémentation correcte d'une implémentation qui utiliserait une comparaison large et servirait le dernier arrivé.

e) INVARIANT de la première implémentation : après chaque opération, la liste interne est triée par priorité croissante, et les éléments de même priorité y figurent dans leur ordre d'arrivée. DÉMONSTRATION. À la création, la liste est vide : l'invariant est vrai, il n'y a aucune paire à vérifier. Pour l'INSERTION, on parcourt la liste jusqu'au premier élément de priorité STRICTEMENT supérieure et l'on insère juste avant lui. Les éléments qui précèdent ont une priorité inférieure ou égale, ceux qui suivent une priorité supérieure ou égale : le tri est préservé. La stricte inégalité place le nouvel élément APRÈS tous ceux de même priorité déjà présents, donc l'ordre d'arrivée est préservé lui aussi. Pour le RETRAIT, on enlève le premier élément : une sous-liste d'une liste triée reste triée, et retirer un élément ne change pas l'ordre relatif des autres. L'invariant est donc préservé par toutes les opérations. Ce que la preuve NE COUVRE PAS : elle porte sur le modèle, pas sur le code réellement exécuté. Elle ne dit rien d'un débordement d'entier sur les priorités, d'une erreur d'indice dans la boucle d'insertion, d'un comportement en présence de plusieurs fils d'exécution, ni du fait que la liste utilisée se comporte réellement comme on le suppose. C'est exactement pour cela que les six jeux de tests de la question d restent nécessaires.

a) hanoi(2) appelle hanoi(1, 'A', 'B', 'C'), qui affiche A -> B ; puis affiche A -> C ; puis appelle hanoi(1, 'B', 'C', 'A'), qui affiche B -> C. Trois déplacements, et la fonction renvoie 3 : le petit disque s'écarte sur B, le grand passe sur C, le petit le rejoint.

b) Les déplacements : A -> C, A -> B, C -> B, A -> C, B -> A, B -> C, A -> C. Il y en a 7. Les trois premiers transportent les deux petits disques sur B, le quatrième déplace le grand disque de A à C, et les trois derniers ramènent les deux petits de B sur C : on reconnaît deux fois la solution pour 2 disques, de part et d'autre du déplacement du plus grand.

c) Pour déplacer $n$ disques, la fonction déplace $n - 1$ disques, puis le plus grand, puis de nouveau $n - 1$ disques : $M(n) = 2\,M(n-1) + 1$, avec $M(0) = 0$. Par récurrence : $M(0) = 2^{0} - 1 = 0$ est vrai ; si $M(n-1) = 2^{n-1} - 1$, alors $M(n) = 2(2^{n-1} - 1) + 1 = 2^{n} - 1$. Donc $M(10) = 2^{10} - 1 = 1\ 023$. On montre d'ailleurs qu'aucune méthode ne fait mieux : cette solution récursive est optimale.

d) $2^{64} - 1 \approx 1{,}84 \times 10^{19}$ secondes. En années : $\frac{1{,}84 \times 10^{19}}{3{,}156 \times 10^{7}} \approx 5{,}8 \times 10^{11}$, soit environ 585 milliards d'années, plus de quarante fois l'âge de l'univers.

e) Chaque appel sur $n$ disques en attend un sur $n - 1$, jusqu'au cas de base : la pile contient au plus $n + 1$ cadres, soit 65 pour $n = 64$. C'est très loin de la limite de profondeur de Python, de l'ordre de 1 000 : le programme ne déborderait jamais de la pile, il tournerait simplement pendant des centaines de milliards d'années. La mémoire utilisée est LINÉAIRE en $n$ alors que le temps est EXPONENTIEL : les deux ressources ne se mesurent pas de la même façon, et un programme peut être très économe en mémoire tout en étant inexécutable.

a) fabrique_puissance(3) construit la chaîne lambda x: x ** 3 et l'évalue : on obtient une fonction qui élève au cube. cube(4) vaut $4^{3} = 64$, et le programme affiche 64. Pour obtenir une fonction qui renvoie toujours 1, il faut $k = 0$, puisque $x^{0} = 1$.

b) Pendant sa construction, source est une DONNÉE : une chaîne de caractères qu'on assemble par concaténation, comme n'importe quel texte. Elle ne devient du code qu'au moment où eval la fait analyser et exécuter par l'interpréteur. Le même objet est donc tour à tour une donnée et un programme, selon ce qu'on en fait : c'est exactement ce que signifie la notion de programme en tant que donnée, et c'est elle qui rend possible la démonstration du problème de l'arrêt, où un programme reçoit le texte d'un programme en argument.

c) Un COMPILATEUR traduit tout le programme source, une fois pour toutes, en un programme équivalent dans un autre langage, souvent le langage machine, qu'on exécute ensuite sans lui. Un INTERPRÉTEUR lit le programme et exécute ses instructions au fur et à mesure, et doit être présent à chaque exécution. Python est habituellement rangé parmi les langages interprétés, mais il fait les deux : il compile d'abord le fichier source en un code intermédiaire, le bytecode, puis une machine virtuelle interprète ce bytecode. Compilateur et interpréteur sont eux-mêmes des programmes dont les données d'entrée sont des programmes.

d) L'utilisateur peut saisir, à la place d'un nombre, n'importe quelle expression Python, qui sera exécutée sur le serveur avec tous ses droits : lire ou effacer des fichiers, lancer des commandes. C'est une INJECTION DE CODE, exactement du même type que l'injection SQL : une donnée fournie par l'extérieur est collée dans un texte qui sera ensuite interprété comme du code. Le remède est le même dans son principe : ne jamais faire interpréter une saisie, mais la convertir et la vérifier comme une donnée, ici avec int(saisie), qui échoue sur tout ce qui n'est pas un entier.

e) Le TÉLÉCHARGEMENT d'une application : le navigateur ou le magasin d'applications copie un fichier d'octets sans l'exécuter, et un antivirus l'analyse comme une donnée avant qu'il soit lancé. Le LANCEMENT d'un programme par le système d'exploitation : celui-ci lit le fichier exécutable sur le disque, le charge en mémoire, puis donne la main à ses instructions. On peut ajouter le compilateur, qui transforme un programme en un autre, et l'éditeur de texte, pour lequel un code source n'est qu'un texte.

a) Aucune erreur : resultat vaut $\frac{36}{3} = 12{,}0$. Le bloc finally affiche fin du calcul, puis la fonction renvoie $12{,}0$, un flottant puisque la division / renvoie toujours un flottant en Python.

b) sum([]) vaut 0 et len([]) vaut 0 : la division lève ZeroDivisionError. La clause correspondante affiche liste vide et met resultat à None, puis finally affiche fin du calcul, et la fonction renvoie None. C'est la division qui a levé l'exception ; l'affectation de son résultat à resultat, dans le bloc try, n'a jamais eu lieu, puisque l'exception interrompt l'instruction avant qu'elle se termine.

c) sum([12, 'abs', 9]) tente d'ajouter une chaîne à un entier et lève TypeError, avant même la division. Le programme affiche valeur non numérique, puis fin du calcul : 2 lignes, et la fonction renvoie None.

d) Une clause except sans type attrape TOUTES les exceptions, y compris celles qu'on n'avait pas prévues. Si l'on écrit par erreur sum(note) au lieu de sum(notes), la NameError produite serait avalée et transformée en un résultat None silencieux : le programme continuerait avec une fausse valeur, et le défaut réapparaîtrait bien plus loin, sans aucun indice. Elle attrape même l'interruption demandée au clavier. On n'attrape que les exceptions qu'on sait traiter, et on laisse les autres interrompre le programme.

e) Le bloc finally s'exécute à chaque appel, qu'il y ait une erreur ou non : 4 affichages. Pour la liste vide, si la spécification pose en PRÉCONDITION que la liste est non vide, il vaut mieux laisser remonter l'exception, ou en lever une plus explicite : un appel qui viole le contrat doit produire une erreur, pas un résultat. Renvoyer None oblige chaque appelant à tester ce cas, et celui qui oublie de le faire provoquera une erreur plus loin, à un endroit sans rapport, exactement comme dans l'exercice 5 avec la liste vide.

a) Le dénominateur est négatif : on change les deux signes, num vaut $-6$ et den vaut 8. Puis gcd(-6, 8) vaut 2, et l'on divise : num vaut $-3$ et den vaut 4. La fraction est rangée sous la forme $-\frac{3}{4}$, avec le signe porté par le numérateur.

b) __add__ construit Fraction(1 × 3 + 1 × 6, 6 × 3), soit Fraction(9, 18). Le constructeur calcule gcd(9, 18) = 9 et ramène à num = 1 et den = 2. print affiche 1/2. On retrouve bien $\frac{1}{6} + \frac{1}{3} = \frac{1}{6} + \frac{2}{6} = \frac{1}{2}$.

c) L'invariant : den est strictement positif, et num et den sont PREMIERS ENTRE EUX. Toute fraction a une seule écriture de cette forme, si bien que deux fractions égales ont exactement les mêmes attributs. Sans la simplification, Fraction(1, 2) et Fraction(2, 4) auraient des attributs différents et __eq__ déclarerait fausse l'égalité $\frac{1}{2} = \frac{2}{4}$. Avec l'invariant, Fraction(2, 4) est rangée comme 1/2, et l'égalité est reconnue. Le constructeur étant le seul endroit où l'on crée des fractions, c'est lui seul qui doit garantir l'invariant.

d) $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$, donc la somme se télescope : $\left(1 - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \dots + \left(\frac{1}{9} - \frac{1}{10}\right) = 1 - \frac{1}{10} = \frac{9}{10}$. Le programme obtient Fraction(9, 10), avec num = 9 et den = 10, exactement.

e) L'égalité vaut True. Les fractions sont représentées EXACTEMENT par deux entiers, et les entiers de Python ne sont jamais arrondis : $\frac{1}{10} + \frac{1}{10} + \frac{1}{10}$ donne 3/10 sans aucune perte. Le flottant 0.1, lui, n'a pas d'écriture finie en binaire, et la somme de trois arrondis diffère de l'arrondi de 0.3. Quant à Fraction(1, 2) + 1, la méthode __add__ reçoit l'entier 1 dans autre et tente de lire autre.den : Python lève une AttributeError, un entier n'ayant pas d'attribut den. Il faudrait convertir l'entier en Fraction(1, 1) au début de __add__.

a) La fonction parcourt t : 1 est ajouté ; [2, [3, 4]] est aplatie en [2, 3, 4] ; [] donne [] ; [[5]] donne [5]. Le résultat est [1, 2, 3, 4, 5].

b) Un appel par liste rencontrée : t lui-même, [2, [3, 4]], [3, 4], [], [[5]] et [5]. Cela fait 6 appels. Les entiers ne provoquent aucun appel : ils sont ajoutés directement.

c) profondeur(1) vaut 0, puisque 1 n'est pas une liste. profondeur([2, [3, 4]]) vaut $1 + \max(0, \text{profondeur}([3, 4]))$, et profondeur([3, 4]) vaut $1 + \max(0, 0) = 1$, donc 2. profondeur([]) vaut 1 par le second cas de base. profondeur([[5]]) vaut $1 + \text{profondeur}([5]) = 1 + 1 = 2$. Finalement profondeur(t) vaut $1 + \max(0, 2, 1, 2) = 3$.

d) Pour aplatir, le cas de base est implicite : un élément qui n'est pas une liste est ajouté sans appel, et une liste vide ne provoque aucun tour de boucle. Pour profondeur, deux cas de base : un élément qui n'est pas une liste vaut 0, la liste vide vaut 1. Avec t2, la liste se contient ELLE-MÊME : aplatir(t2) rencontre t2 parmi ses éléments et s'appelle sur t2, indéfiniment, sans jamais atteindre de cas de base. Chaque appel empile un cadre, et Python lève RecursionError. La terminaison reposait sur une hypothèse implicite, que chaque sous-liste soit strictement plus petite que la liste qui la contient, et une structure cyclique la viole.

e) L'expression resultat + aplatir(x) recopie les deux listes dans une troisième : pour une structure contenant $n$ éléments répartis en nombreuses sous-listes, les recopies successives peuvent coûter un temps QUADRATIQUE. L'écriture resultat.extend(aplatir(x)) ajoute les éléments à la liste existante sans la recopier. Sans récursivité, on remplace la pile d'appels par une PILE EXPLICITE : on y place t, puis, tant qu'elle n'est pas vide, on dépile un élément ; si c'est une liste, on empile ses éléments en ordre inverse, sinon on l'ajoute au résultat. C'est ce que fait l'interpréteur pour la version récursive, rendu visible.