Le mot paradigme représente la façon dont on se représente le fonctionnement du monde. Pour avoir une telle vision du monde, le paradigme s'appuie sur des fondements définis par un modèle, qu'il soit scientifique, philosophique ou même religieux.
Bien entendu, les découvertes scientifiques ont fait évoluer ou disparaître certains paradigmes purement philosophiques ou religieux. On notera par exemple l'ancien paradigme aristotélicien qui plaçait la Terre au centre de l'Univers (un géocentrisme stable et un ordre immuable des éléments) qui a disparu suite aux idées de Galilée et des travaux de Copernic notamment. Le paradigme qui l'a remplacé est basé sur une approche modélisatrice copernicienne de l'Univers, proposant d'adopter l'héliocentrisme et les mouvements satellitaires.
Paradigme de programmation
L'informatique n'explique pas comment fonctionne le monde, mais elle peut être utilisée pour modéliser le monde. Du moins, au moins, un petit problème à la fois !
Un paradigme de programmation explique donc les grands principes qu'on veut voir appliquer dans le programme. Il s'agit bien également d'une sorte de philosophie, mais une philosophie de conception.
Un paradigme de programmation est la façon de formuler et traiter les problèmes.
La plupart des langages permettent d'utiliser plusieurs paradigmes de programmation, tout en en mettant souvent un en avant.
Ce paradigme est le premier que vous ayez rencontré en NSI : la résolution du problème est basée sur l'exécution progressive d'une suite d'instructions qui vont modifier l'état des variables du programme.
Grands principes
Les principes importants du paradigme impératif sont :
la séquentialité (séquence d'instructions à suivre)
les variations d'états des variables (on peut affecter des valeurs aux variables et faire varier cet état)
les opérations de branchements (qui permettent de rompre la séquentialité pure) dont l'instuction fondamentale est le jump/goto/branch
Ce paradigme est fortement lié à l'assembleur et au langage machine en lui-même.
Exemple 1 avec de l'assembleur type ARM 32 bits(on considérera la simplification suivante : chaque instruction prend 32 bits d'espace mémoire)
MOVR0#0// on place 0 dans le registre 0MOVR1#5// on place 5 dans le registre 1CMPR0R1// on compare le contenu de R0 et de R1 via l'accumulateurJEQ0x00010000// si c'est égal, partir à l'adresse donnéeADDR0#1// on incrémente R0 de 1JMP0x00010008// on part à cette adresseMOVR7#1// on stocke 1 dans le registre qui contient l'ordre à faire (1 pour exit)MOVR0#0// on place 0 dans le registre qui contient la réponse (0 pour tout c'est bien passé)SVC0// supervisor call : demande d'appel système basé sur l'ordre dans R7(exit)
Assez rapidement, on a rajouté d'autres types d'instructions de branchement, permettant de remplacer les JUMP/GOTO directs, sans nécessité de connaître l'adresse exacte en RAM de la prochaine instructions voulues !
les instructions conditionnelles (if-elif-else) ;
les boucles bornées et non bornées (for, while, do ... while) ;
la déclaration et l'appel de fonction (qui permet d'organiser le code mais avec un appel qui provoque un retour exactement à l'endroit d'où on est parti).
Exemple 2 : programme Python équivalent au programme 1
1
2
3
4
k=0// on place 0 dans la variable km=5// on place 5 dans la variable mwhilek!=m:k=k+1
vie_a=400# Points de viefor_a=60# Forceres_a=63# Résistance / Armurenom_a="Alice"# Nom du personnagevie_b=300for_b=70res_b=54nom_b="Bob"whilevie_a>0andvie_b>0:vie_a=vie_a-for_b+res_avie_b=vie_b-for_a+res_bifvie_a>0:gagnant=1elifvie_b>0:gagnant=2else:gagnant=0ifgagnant==0:print("Aucun gagnant : les deux combattants sont ko")elifgagnant==1:print(f"{nom_a} a gagné et il lui reste {vie_a} PV")else:print(f"{nom_b} a gagné et il lui reste {vie_b} PV")
2.2 Le fameux GOTO
Le langage machine et l'assembleur qui en est une sorte de traduction mot à mot sont basés sur ce paradigme . Ils comportent d'ailleurs des JUMP/GOTO directs permettant d'atteindre une ligne particulière sans devoir revenir au point de départ du saut comme avec une fonction.
Voici un exemple de programme utilisant un Python imaginaire intégrant ce principe de goto :
vie_a=400for_a=60res_a=63nom_a="Alice"vie_b=300for_b=70res_b=54nom_b="Bob"ifvie_a<=0orvie_b<=0:goto17vie_a=vie_a-for_b+res_avie_b=vie_b-for_a+res_bgoto11ifvie_a>0:gagnant=1elifvie_b>0:gagnant=2else:gagnant=0ifgagnant==0:print("Aucun gagnant : les deux combattants sont ko")elifgagnant==1:print(f"{nom_a} a gagné et il lui reste {vie_a} PV")else:print(f"{nom_b} a gagné et il lui reste {vie_b} PV")
Il s'agit donc bien qu'une boucle TANT QUE réalisée avec un branchement goto.
Pourquoi faire disparaître goto ?
Pourquoi avoir fait disparaître une instruction aussi puissante de Python plutôt que de la laisser ? Reprenons le même exemple mais dans lequel nous avons inséré quelques commentaires.
# Initialisation des variables définissant l'état au débutvie_a=400for_a=60res_a=63nom_a="Alice"vie_b=300for_b=70res_b=54nom_b="Bob"# Evolution séquentielle des états des variablesifvie_a<=0orvie_b<=0:goto23vie_a=vie_a-for_b+res_avie_b=vie_b-for_a+res_bgoto15# Résolution du problème une fois l'état final atteintifvie_a>0:gagnant=1elifvie_b>0:gagnant=2else:gagnant=0# Affichage du résultat (ou inscription dans un fichier ou autre)ifgagnant==0:print("Aucun gagnant : les deux combattants sont ko")elifgagnant==1:print(f"{nom_a} a gagné et il lui reste {vie_a} PV")else:print(f"{nom_b} a gagné et il lui reste {vie_b} PV")
Si on insérait une nouvelle ligne, il fallait changer toutes les valeurs associées à un goto !
La compréhension du programme n'est vraiment pas facilité par ces sauts ;
il est difficile de prouver la correction d'un programme comportant des sauts car il faut gérer tous les cas.
Historiquement, les premières versions de FORTRAN ou le langage BASIC en contiennent.
Le langage C et C++ permettent de faire des gotos mais en version améliorée : on désigne la ligne désirée à l'aide d'un label et pas de son numéro qui peut varier.
# Initialisation des variables définissant l'état au débutvie_a=400for_a=60res_a=63nom_a="Alice"vie_b=300for_b=70res_b=54nom_b="Bob"# Evolution séquentielle des états des variablesDEPART: ifvie_a<=0orvie_b<=0:gotoSORTIEvie_a=vie_a-for_b+res_avie_b=vie_b-for_a+res_bgotoDEPART# Résolution du problème une fois l'état final atteintSORTIE: ifvie_a>0:gagnant=1elifvie_b>0:gagnant=2else:gagnant=0# Affichage du résultat (ou inscription dans un fichier ou autre)ifgagnant==0:print("Aucun gagnant : les deux combattants sont ko")elifgagnant==1:print(f"{nom_a} a gagné et il lui reste {vie_a} PV")else:print(f"{nom_b} a gagné et il lui reste {vie_b} PV")
2.3 Evolutions
Il existe de nombreuses évolutions depuis le paradigme impératif de base. Vous n'avez pas à connaître leurs noms ou la classification exacte, je ne les propose ici qu'au titre de l'histoire de l'informatique :
Sans goto : on les remplace par les boucles et les instructions conditionnelles de façon à obtenir une programmation plus structurée.
Avec des routines : on encapsule les tâches dans des routines - procédures (routines sans retour) - fonctions (routines avec retour) ne dépassant pas quelques dizaones de lignes.
Avec des modules : on encapsule encore plus les tâches en le plaçant cette fois dans des fichiers séparés.
Ces évolutions ne sont pas propres à ce paradigme et on retrouvera des choses similaires dans les deux autres paradigmes que nous allons rencontrer aujourd'hui.
01° Etudier le code suivant puis répondre aux questions :
ta est-elle une variable globale ou locale ?
tb est-elle une variable globale ou locale ?
tc est-elle une variable globale ou locale ?
En Python, quelle va être la différence entre les lignes 4 et 5 ?
quel va être le contenu du tableau ta après l'appel de la fonction ?
1
2
3
4
5
6
7
8
9
10
11
defmystere():"""Agit (ou pas ?) sur le tableau-paramètre p reçu"""tb=[vforvinta]tc=tatb[0]=100tc[1]=200ta=[10,20,30]mystere()
...CORRECTION...
ta est-elle une variable globale ou locale ? Globale, son espace des noms est le programme principal (le "main")
tb est-elle une variable globale ou locale ? Locale, elle n'appartient qu'à l'espace des noms de la fonction
tc est-elle une variable globale ou locale ? Locale, elle n'appartient qu'à l'espace des noms de la fonction
En Python, quel va être la différence entre les lignes 4 et 5 ?
Ligne 4 : on crée une copie du tableau - on obtient deux espaces-mémoires qui vont contenir la même chose.
Ligne 5 : on crée juste un alias - on obtient deux variables qui pointent vers la même zone mémoire.
quel va être le contenu du tableau ta après l'appel de la fonction ? Puisque tc réference la même zone mémoire que ta, lorsque modifie la case numéro 1 en ligne 7, on modifie directement le tableau auquel ta fait référence. Du coup, la variable ta fait référence à [10, 200, 30] après le passage de cette ligne.
02° Comment se nomme l'effet qui permet de modifier le tableau ta ?
Expliquer le phénomène en utilisant les mots variables, alias et zone mémoire.
...CORRECTION...
Il s'agit de l'effet de bord.
Ce phénomène apparaît lorsque deux variables sont simplement des alias vers la même zone-mémoire : si on modifie la zone mémoire, on "modifie" nécessairement les deux variables puisque les deux référencent les mêmes cases.
On peut donc modifier une même zone mémoire en utilisant un alias de cette zone. Ca peut être pratique. Ou pas.
03° Que devrait afficher ce programme ?
Attention : en Python, l'évaluation du range de la boucle ne se fait qu'au départ.
Les effets de bord sont donc les modifications d'une même zone mémoire référencée par plusieurs variables, qu'on nommera des alias.
Avantage : comme on ne transfère que l'adresse ou la référence, il n'est pas plus compliqué de "transférer" un tableau de 1 millions d'éléments à une fonction qu'un tableau de 10 éléments.
Désavantage : on peut finir par modifier quelque chose qu'on ne voulait pas vraiment modifier !
Conséquence : il faut indiquer dans la documentation de vos fonctions lorsqu'il y a modification d'un paramètre par effet de bord.
C'est pour cela que nous avions vu en 1er deux façons de créer des fonctions gérant les tableaux :
2.5 Modifier un tableau par effet de bord depuis une fonction
Dernier exemple qui vous permettra de voir qu(il existe parfois des effets de bord non désirés.
05° Mettre le programme en mémoire puis utiliser les instructions consoles fournies. Que va afficher la dernière commande ?
1
2
3
4
5
6
7
entrees=['tarte au saumon','crudités']plats=['steak frites','ratatouille']menus=[entrees,plats]entrees2=entreesplats2=['Pates aux épinards','Gratin de brocolis']menus2=[entrees2,plats2]
>>> menus
[['tarte au saumon', 'crudités'], ['steak frites', 'ratatouille']]>>> menus2
[['tarte au saumon', 'crudités'], ['Pates aux épinards', 'Gratin de brocolis']]>>> menus2[0].append('Oeufs mayo')
>>> menus2
[['tarte au saumon', 'crudités', 'Oeufs mayo'], ['Pates aux épinards', 'Gratin de brocolis']]>>> menus
???
...CORRECTION...
On a modifié le contenu de menus en modifiant le contenu de menu2 !
On a ici le cas d'un tableau de tableaux. Nos menus ne contiennent en réalité par les tableaux mais juste les références-mémoire vers les vrais tableaux.
Conclusion : il faut faire très attention aux copies lorsqu'on utilise un langage qui utilise un paradigme impératif : beaucoup d'objets sont des objets mutables et en faire des "copies" avec une simple affectation ne permet que de recopier la référence-mémoire !
2.7 Copie d'objets mutables avec Python
1 - Copie superficielle
On crée bien deux strctures différentes mais les éléments référencent les mêmes zones mémoires.
Si les éléments sont immuables, pas de problèmes. Par contre, si les éléments sont mutables, on peut modifier le "contenu" de l'autre variable en modifiant le contenu de la première !
>>> a = [10, [20], 30]
>>> b = [e for e in a]
>>> b[0] = 100
>>> b[1][0] = 200
>>> b
[100, [200], 30]>>> a
[10, [200], 30]
Il existe aussi une méthode copy() qui permet de faire pareil que la création par compréhension. Autant utiliser la création par compréhension car elle est au programme.
>>> a = [10, [20], 30]
>>> b = a.copy()
>>> b[0] = 100
>>> b[1][0] = 200
>>> b
[100, [200], 30]>>> a
[10, [200], 30]
2 - Copie profonde
Cette fois, on copie récursivement tous les contenus en tant que nouveau contenu.
Le plus simple est d'utiliser une méthode Python qui se nomme deepcopy (on peut aussi le coder directement à la main bien entendu).
>>> import copy
>>> a = [10, [20], 30]
>>> b = copy.deepcopy(a)
>>> b
[10, [20], 30]>>> b[0] = 100
>>> b[1][0] = 200
>>> b
[100, [200], 30]>>> a
[10, [20], 30]
En conclusion : la programmation itérative est simple à prendre en main, mais il faut faire attention aux effets de bords indésirables.
La programmation orientée objet ou POO a été créée notamment pour contrôler un peu plus ces effets de bords problématiques.
La POO est basée sur les effets de bord. Le but n'est pas de les éviter mais de bien les gérer.
3.1 Paradigme objet
Idée générale
On ne crée pas un programme principal et des fonctions effectuant les tâches qu'on doit effectuer : on gère juste les interactions entre des objets qui possèdent :
leurs variables : les attributs
leurs fonctions : les méthodes
Les grands principes : encapsulation et notion de public/privée
Pour garantir le bon fonctionnement de l'objet mutable, on travaille sur l'encapsulation des objets et en considérant les données comme privées :
seul un objet d'une classe B a le droit de modifier directement les attributs d'un objet d'une classe B. Les attributs sont privés ;
les autres objets doivent utiliser les méthodes d'interface publiques pour modifier les attributs ;
ces méthodes d'interface vérifient la validité des modifications avant d'appliquer les modifications : l'effet de bord existe toujours mais on surveille de près les demandes venant de l'extérieur.
On peut même aller plus loin si on le désire, et dire que seul l'objet lui-même peut modifier ses propres données.
classPersonnage:"""Classe définissant le personnage"""def__init__(self,nom:str,pv:int,fo:int,re:int):"""Méthode initialisateur ou constructeur"""self.nom=nomself.vie=pvself.force=foself.resistance=redefsubir_degats(self,dgt:int):"""(privée) Modifie les pv du personnage"""iftype(dgt)==intanddgt>0:self.vie=self.vie-dgtifself.vie<0:self.vie=0defcombattre(self,adversaire):"""(privée) Self subit l'assaut de l'adversaire"""degats=adversaire.obtenir_force()-self.resistanceself.subir_degats(degats)defobtenir_nom(self)->str:"""Renvoie le nom du personnage"""returnself.nomdefobtenir_vie(self)->int:"""Renvoie le nombre de vie restante"""returnself.viedefobtenir_force(self)->int:"""Renvoie la force du personnage"""returnself.forcedefobtenir_resistance(self)->int:"""Renvoie la résistance du personnage"""returnself.resistancedeflancer_combat_avec(self,adversaire)->str:"""Lance un combat entre 2 personnages et renvoie le gagnant"""whileself.obtenir_vie()>0andadversaire.obtenir_vie()>0:self.combattre(adversaire)adversaire.combattre(self)ifself.obtenir_vie()>0:returnself.nomelifadversaire.obtenir_vie()>0:returnadversaire.nomelse:return"Aucun gagnant"if__name__=='__main__':a=Personnage("Alice",400,60,63)b=Personnage("Bob",300,70,54)a.lancer_combat_avec(b)
Vous remarquerez que l'un des problèmes de la POO pour les petits programmes est son côté verbeux : même en Python et sans vraiment respecter toutes les règles du paradigme, on a un code très long par rapport au même programme en impératif.
Langages adaptés
Une grande majorité des langages modernes permettent de faire de la POO mais avec une souplesse variable.
Certains imposent l'objet en mode privé-public dès les premières lignes (Java pour exemple, où même le "programme principal" est un objet)
D'autres permettent de faire de l'objet en mode privé-public si on veut (C++ par exemple)
D'autres permettent de travailler avec des objets mais sans permettre le mode privé-public. Python est l'un d'entre eux.
Enfin, certains langages ne permettent pas de faire de la programmation objet. Le C par exemple.
06° Associer le bon vocabulaire aux noms suivants :
Personnage
a
__init__
obtenir_vie
self
force
...CORRECTION...
Personnage -> Classe
a -> objet ou instance
__init__ -> méthode constructeur ou méthode initialisateur
obtenir_vie -> méthode
self -> objet en cours d'utilisation
force -> attribut
07° Expliquer ce que recoivent les deux paramètres self et adversaire de la méthode lacer_combat_avec lorsqu'on lance ceci :
>>> a.lancer_combat_avec(b)
'Alice'
08° Expliquer ensuite rapidement le comportement de cette méthode.
3.2 Attendus du BAC
Très peu de choses en réalité.
Vous devez :
Etre capable de reconnaître une Classe : le code qui permet de créer les objets
Etre capable de reconnaître un objet : un objet est une instance d'une Classe, une création concrète basée sur la Classe
Etre capable de reconnaître un attribut : il s'agit d'une variable stockée dans un objet (variable d'instance) ou dans la classe directement (variable de classe)
Etre capable de reconnaître une méthode : il s'agit d'une fonction stockée dans un objet. Contrairement à une fonction classique, elle a besoin d'au moins un premier paramètre qu'on nomme souvent self : l'instance de l'objet sur lequel elle doit travailler.
Accéder à une méthode : savoir faire appel à une méthode : reference.methode(...), le paramètre self recevant automatiquement reference.
Accéder à un attribut : lire ou modifier un attribut : reference.attribut ou reference.attribut = ...
Savoir définir seul une Classe et donc :
Connaître la syntaxe de déclaration de la Classe (majuscule pour la première lettre du nom)
Savoir déclarer la méthode constructeur
Savoir déclarer des méthodes
Comprendre les principes généraux et l'intérêt de l'encapsulation mais sans maitrise réelle de ces principes : aucune question sur privée, publique, accesseur, mutateur par exemple. En Python, vous pouvez créer des programmes qui modifient ou lisent les attributs d'un objet sans devoir passer par des méthodes publiques.
Le paradigme impératif qui permet des sauts dans l'exécution et des effets de bord non surveillés, ce qui rend les programmes difficiles à vérifier.
Le paradigme objet qui se base sur des règles d'utilisation encadrées des effets de bords liés aux objets mutables. Le système peut être stable mais les démonstrations formelles de cette stabilité ne sont pas faciles à réaliser non plus...
Moralité : on voudrait un paradigme qui permette "facilement" de prouver la correction de notre programme. Or, ce sont les effets de bord qui posent problème.
4.1 Paradigme fonctionnel
Une fonction pure est une fonction qui calcule sa réponse uniquement à partir des paramètres qu'elle a reçu, comme une fonction mathématique. A chaque fois qu'on l'appelle en lui fournissant les mêmes arguments, elle fournit le même résultat.
Grands principes du paradigme fonctionnel
Les principes importants du paradigme fonctionnel sont :
Un refus d'utiliser les effets de bord ;
Il existe des fonctions d'ordre supérieur : des fonctions capables de recevoir des fonctions en tant que paramètes ou des fonctions qui renvoient l'adresse d'une fonction.
Les variables ne sont pas utilisées : on utilise uniquement des constantes.
Les fonctions sont toutes des fonctions pures :
Les structures de données sont immuables : si on veut modifier un tableau, il faut créer un nouveau tableau.
du récursif (programmation récursive) plutôt que des boucles (programmation itérative) puisqu'on ne veut pas utiliser de variables de boucles, qui par définition doivent varier.
# Déclaration des fonctionsdefnv_pv(df:tuple,at:tuple)->int:"""Calcule le pv du défenseur df après attaque de l'attaquant at"""returndf[0]-max(0,at[1]-df[2])defmaj(df:tuple,at:tuple)->tuple:"""Renvoie les nouvelle caractéristiques mise à jour du defenseur df après attaque de at"""return(nv_pv(df,at),df[1],df[2],df[3])defest_hors_jeu(p):"""Prédicat qui renvoie True si le personnage p à 0 pv ou moins"""returnp[0]<=0deflancer_combat(a:tuple,b:tuple)->str:"""Lance le combat entre a et b et renvoie le nom du gagnant ou "Aucun gagnant""""ifest_hors_jeu(a)orest_hors_jeu(b):# Condition d'arret et cas de baseifnotest_hors_jeu(a):# a a gagné car il lui reste des pvreturna[3]elifnotest_hors_jeu(b):# b a gagné car il lui reste des pvreturnb[3]return"Aucun gagnant"else:# Cas recursifreturnlancer_combat(maj(a,b),maj(b,a))# ETAT DU SYSTEME# Chaque personne est un tuple (vie-0, force-1, resistance-2, nom-3) a=(400,60,63,"Alice")b=(300,70,54,"Bob")
Programmation fonctionnelle et récursivité
Les méthodes de preuve de correction s'appliquent bien à la récursivité.
De plus, la récursivité permet de se passer des boucles et des variables variables.
La récursivité est donc centrale dans ce paradigme.
Création par compréhension en Python
Puisqu'on tente de limiter fortement les variables en fonctionnel, renvoyer un tuple, une liste ou un dictionnaire via une déclaration en compréhension est courant.
Sans boucle FOR, difficile de lire un tableau case par case ? Non, les langages fonctionnels possèdent des fonctions natives dont c'est le travail (map, filter, reduce en Python, mais elles ne sont pas au programme) : map() permet ainsi d'appliquer une fonction fournie en paramètre sur une structure itérable fournie en paramètre. Voici par exemple comment obtenir une copie d'un tableau dont tous les éléments ont été multipliés par deux par rapport au tableau initial :
Plutôt que d'apprendre à utiliser les fonctions qui permettent de se passer des boucles for lorsqu'on travaille sur les tableaux, nous allons faire une petite entorse au paradigme fonctionnel : nous allons autoriser la boucle for mais uniquement dans les créations par compréhénsion :
123456
t=[5,10,20]t2=[v*2forvint]print(t)print(t2)
09° Voici une fonction plus2(). S'agit-il d'une version impérative ou fonctionnelle ?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
defplus2(t:list)->None:"""Modifie t par effet de bord en rajoutant 2 à chaque valeur :: param t(list) :: le tableau qu'on veut modifier :: return(None) :: fonction-procédure :: exemple :: >>> test = [1, 2, 3] >>> plus2_iter(test) >>> test [3, 4, 5] """foriinrange(len(t)):t[i]=t[i]+2
...CORRECTION...
Il s'agit clairement d'une version itérative : on modifie le tableau par effet de bord.
10° Voici une fonction plus2(). S'agit-il d'une version impérative ou fonctionnelle ?
1
2
3
4
5
6
7
8
9
10
11
12
defplus2_fonc(t:list)->list:"""Renvoie une copie du tableau où toutes les valeurs sont augmentées de 2 :: param t(list) :: le tableau qu'on veut modifier :: return(list) :: la nouvelle version du tableau :: exemple :: >>> plus2_fonc([1, 2, 3]) [3, 4, 5] """return[v+2forvint]
...CORRECTION...
Il s'agit d'une version fonctionnelle : on crée une copie et on renvoie le résultat.
Autre exemple : comment rajouter un élément dans un tableau en Python ? Nous allons regarder d'un peu plus près comment fonctionne Python.
11° Voici trois codes permettant de rajouter un élément dans un tableau Python. Quelle version pourrait correspondre le plus à une version fonctionnelle ? Quelle est néanmoins son gros défaut du point de vue fonctionnel ?
>>> a = [4, 8]
>>> id(a)
140030316223048>>> a.append(12)
>>> a
[4, 8, 12]>>> id(a)
140030316223048
>>> a = [4, 8]
>>> id(a)
140030316223304>>> a = a + [12]
>>> a
[4, 8, 12]>>> id(a)
140030316783822
>>> a = [4, 8]
>>> id(a)
140030316223368>>> a += [12]
>>> a
[4, 8, 12]>>> id(a)
140030316223368
...CORRECTION...
La seule version "correcte" pour faire du fonctionnel est la version a = a + [12] : c'est la seule qui modifie bien la référence de la variable : on crée donc un nouveau tableau qui écrase l'ancien.
Mais attention, même cette version ne convient pas : a reste une variable dont le contenu à varier.
12° Créer la fonction ajouter_elt(t, elt) qui renvoie un nouveau tableau semblable à celui reçu mais en lui rajoutant un nouvel élément.
>>> ajouter_elt([1,2,3], 12)
[1, 2, 3, 12]
...CORRECTION...
1
2
defajouter_elt(t:list,elt)->list:returnt+[elt]
Attention, tout cela est artificiel : les tableaux de Python de type list sont mutables. Donc, on doit faire attention. Avec un langage purement fonctionnel, les structures de données seraient immuables.
Les tuples de Python permettent beaucoup plus facilement de gérer ce type de demandes.
13° La fonction somme ci-dessous peut-elle être considérée comme fonctionnelle ?
15° Faire la même chose avec un exposant plus conséquent :
>>> 15**135478415797
Question : est-ce rapide ?
...CORRECTION...
Cette fois, ça ne répond pas immédiatement. En tous cas, pas assez rapidement pour être utilisable !
Comment faire alors ?
Comme d'habitude en informatique, nous allons "tricher". C'est à dire en réalité que nous allons refléchir à ce qu'on désire faire.
La méthode que nous allons utiliser se nomme l'exponentiation rapide : nous allons chercher à calculer des mises au carré successives.
En voici le principe :
Calcul normal
Calcul normal de 15140 = 15*15*15*15*...15 : on a donc 139 étapes et multiplications à faire.
Calcul avec exponentiation rapide
Cette fois, nous nous rendons compte de ceci :
15140 = (152) 70
Or x70 = (x2) 35
Notre calcul devient ( (152)2 ) 35 ou encore ( 154 ) 35
Or x35 = x * x34 = x * (x2) 17
Notre calcul devient 154 * ( (154)2 ) 17 ou plus simplement 154 * ( 158 )17
Or x17 = x * x16 = x * (x2)8
Notre calcul devient 154 * 158 * ((158)2)8 ou plus simplement 154 * 158 * ( 1516 )8
Or x8 = (x2)4
Notre calcul devient 154 * 158 * ( 1532 )4
Or x4 = (x2)2
Notre calcul devient 154 * 158 * ( 1564 )2
Or x2 = (x2)1
Notre calcul devient 154 * 158 * 15128
16° Calculer 2**140 et 154 * 158 * 15128
17° Créer la fonction exp_rapide qui se base sur ce principe :
Pour cela, répondre à ces questions :
Quelle est la condition d'arrêt et le cas de base ?
Quelles sont les cas récursifs ?
Ecrire votre fonction
1
2
3
4
defexp_rapide(x:int,n:int)->int:"""Permet de calcul rapidement x**n par exponentiation rapide"""pass
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
defexp_rapide(x:int,n:int)->int:"""Permet de calcul rapidement x**n par exponentiation rapide"""ifn==1:returnxelse:ifn%2==0:returnexp_rapide(x**2,n//2)else:returnx*exp_rapide(x**2,n//2)
Nous pouvons maintenant réaliser de gros calculs comme 151000000 :
RSA ne demande pas de faire ce calcul en intégralité : on veut le modulo.
Et là, c'est intéressant : nous allons faire toutes les étapes mais en réalisant le modulo n à chaque étape, les nombres à traiter seront bien plus courts.
Nous allons donc avoir un paramètre supplémentaire : le module de chiffrement.
18° Créer la fonction exp_rapide propre à RSA : on attend trois paramètres :
1
2
3
4
defexp_rapide_rsa(m:int,e:int,n:int)->int:"""Permet de calcul rapidement m**e %n par exponentiation rapide"""pass
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
defexp_rapide_rsa(m:int,e:int,n:int)->int:"""Permet de calcul rapidement m**e %n par exponentiation rapide"""ife==1:returnmelse:print(e)ife%2==0:return(exp_rapide_rsa(m**2%n,e//2,n))%nelse:return(m*exp_rapide_rsa(m**2%n,e//2,n))%n
19° Calculer la transformation de m = 190000 en utilisant les valeurs suivantes
20° Créer une fonction qui respecte le paradigme fonctionnel et qui permet d'obtenir un tableau dont le contenu est doublé par rapport à un tableau fourni en entrée.
21° Créer une fonction qui modifie le tableau en multipliant les valeurs par deux. Est-encore compatible avec le paradigme fonctionnel ? Justifiez.
22° Expliquer en quoi la fonction maximum respecte bien le paradigme fonctionnelle. Expliquer son fonctionnement.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
defmaximum(t):"""Renvoi le maximum du tableau t"""iflen(t)>0:returntrouver_maximum(t,t[0])deftrouver_maximum(t,maxi):iflen(t)==0:returnmaxielse:t2=[t[i]foriinrange(len(t))ifi>0]ift[0]>maxi:returntrouver_maximum(t2,t[0])else:returntrouver_maximum(t2,maxi)
importmathdefmaximum(t):"""Renvoi le maximum du tableau t"""iflen(t)>0:returntrouver_maximum(t,t[0])deftrouver_maximum(t,maxi):iflen(t)==0:returnmaxielse:t2=[t[i]foriinrange(len(t))ifi>0]ift[0]>maxi:returntrouver_maximum(t2,t[0])else:returntrouver_maximum(t2,maxi)defmaximum_fonction(f,intervalle):"""Renvoie le maximum d'une fonction sur un ensemble de valeurs entières"""returnmaximum([f(x)forxinintervalle])defcarre(x):returnx*xdefracine(x):returnmath.sqrt(x)
Quels vont être les types de paramètres de la fonction maximum_fonction lors de cet appel ? Qu'est-ce qui devrait (au moins un peu) vous surprendre ?
>>> maximum_fonction(carre, [x for x in range(1000)])
19
defmaximum_fonction(f,intervalle):
Fonctions-paramètres
On peut donc transmettre la référence d'une fonction (sans ses paramètres donc, juste la référence mémoire du code de la fonction) à une autre fonction.
Les fonctions ne sont finalement que des données comme les autres. Souvenez-vous qu'elles sont de toutes manières stockées dans la même mémoire que les données. Rien d'étrange en réalité.
Il s'agit également de l'un des fondamentaux de la programmation fonctionnelle : le passage de fonctions-paramètres et pas simplement l'appel de fonctions !
Dernière remarque (et hors programme en terme de connaissances pour le DS ou le BAC) : il est parfois pénible de transmettre une fonction à une autre fonction alors qu'on ne veut finalement que l'utiliser une seule fois. Surtout en mode console par exemple.
Il existe heureusement un type de fonction qu'on peut créer à la volée : les fonction lambda
Si cela vous intéresse, direction la FAQ ci-dessous, sinon, c'est fini !
J'ai entendu parler des lambda-fonctions. C'est quoi ?
Contrairement aux fonctions normales, elles ne portent pas de nom et on ne les déclare pas avec def mais avec ... lambda.
Si on veut créer une fonction identité x → x à la volée : lambda x: x
Si on veut créer une fonction carrée x → x2 à la volée : lambda x: x**2
Si on veut créer une fonction racine carrée x → x2 à la volée : lambda x: math.sqrt(x)
Du coup, on peut faire des appels à notre fonction maximum_fonction de cette façon :
>>> maximum_fonction(lambda x: x, [x for x in range(1000)])
999
>>> maximum_fonction(lambda x: x*x, [x for x in range(1000)])
998001
>>> maximum_fonction(lambda x: x**2 - 300*x, [x for x in range(1000)])
698301
Programmation itérative et impérative, c'est pareil ?
Lorsque le paradigme impératif a évolué en mettant de côté le goto, remplacé par des for et des while, on a parlé de programmation itérative.
Pendant longtemps, la plupart des langages basés sur le paradigme impératif ont surtout été utilisés en programmation itérative.
On continue donc à les associer mais les langages modernes impératifs permettant également d'autres types de programmation.
Et on peut alors faire ceci pour tracer des courbes à la volée :
>>> trace(lambda x: x**2, -10, 10)
>>> trace(lambda x: math/log2(x), 1, 100)
>>> trace(lambda x: exp(x), 1, 10)
Programmation récursive et fonctionnelle, c'est pareil ?
Lorsque le paradigme fonctionnelle a émergé en mettant de côté les effets de bord ET le for-while, il a bien fallu trouver un moyen de remplacer les itérations via les boucles.
Pour cela, la programmation récursive est une solution très adaptée.
Mais attention, on peut aussi faire de la programmation récursive avec d'autres paradigmes.
Activité publiée le 07 03 2021
Dernière modification : 08 03 2021
Auteur : ows. h.
