Physique, Chimie et Informatique > Terminales Spé. NSI
Méthode « Diviser pour régner »
Au programme
Contenus
Capacités attendues
Commentaires
- Méthode « diviser pour régner ».
Écrire un algorithme utilisant la méthode « diviser pour régner ».
- La rotation d’une image bitmap d’un quart de tour avec un coût en mémoire constant est un bon exemple. - L’exemple du tri fusion permet également d’exploiter la récursivité et d’exhiber un algorithme de coût en nlog2n dans les pires des cas.
On parvient à découper un problème en sous-problèmes indépendants les uns des autres. On poursuit cette démarche jusqu’à aboutir à une situation simple : cas de base.
La solution du cas de base est généralement simple à obtenir et permet la construction de la solution du problème.
Remarque
C’est l’indépendance des sous-problèmes qui permet la construction de la solution globale directe par recombinaison des solutions intermédiaires.
Exemples
Exponentiation rapide
Recherche dichotomique dans un tableau trié, dans une liste triée
Tri rapide d’un tableau
Tri fusion récursif d’un tableau
etc.
Schéma de résolution
À retenir
Diviser
On décompose le problème initial en un ou plusieurs sous-problèmes de plus petites tailles.
Régner
Chaque sous-problème est résolu
Combiner
Les solutions des sous-problèmes sont combinées pour construire la solution du problème initial.
Remarques
Cette procédure se prête naturellement à un traitement récursif des problèmes mais une approche itérative reste possible.
Cette procédure assure que l’algorithme est correct. Il reste à valider sa terminaison (que le cas de base est toujours atteint ).
Exercice : exponentiation rapide
L’algorithme suivant permet de calculer an :
an={1a×an−1if n=0if n>0
Programmer la fonction puissance1 dont la spécification est :
defpuissance1(a:int,n:int)->int:"""
Calcul de a^n.
"""
Penser à écrire quelques tests.
Réponse
defpuissance1(a:int,n:int)->int:"""
Calcul de a^n.
Implémentation de l'algorithme 1.
"""ifn==0:return1else:returna*puissance1(a,n-1)if__name__=="__main__":assertpuissance1(3,2)==9assertpuissance1(5,0)==1assertpuissance1(2,8)==256print("Done!")
Quelle est la complexité de cet algorithme ?
Réponse
Le calcul nécessite n appels récursifs et n+1 multiplications. La complexité est donc en O(n).
L’algorithme suivant permet aussi de calculer an :
an=⎩⎨⎧1(ak)2a×(ak)2if n=0if n=2k (n est pair)if n=2k+1 (n est impair)
Programmer la fonction puissance2 dont la spécification est :
defpuissance2(a:int,n:int)->int:"""
Calcul de a^n.
Implémentation de l'algorithme 2.
"""
Penser à écrire quelques tests.
Réponse
defpuissance2(a:int,n:int)->int:"""
Calcul de a^n.
"""ifn==0:return1calc=puissance2(a,n//2)ifn%2==0:returncalc**2else:returna*(calc)**2if__name__=="__main__":assertpuissance2(3,2)==9assertpuissance2(5,0)==1assertpuissance2(2,8)==256print("Done!")
Justifier que le seconde algorithme met en œuvre le raisonnement « Diviser pour règner ».
Réponse
La première ligne de l’algorithme correspond au cas de base pour lequel n=0 et an=1.
Pour n>0, à partir de la valeur n, le calcul se poursuit avec la valeur ⌊2n⌋. On décompose le calcul de an en celui de a⌊2n⌋, puis celui de a⌊2n⌋/2, etc. jusqu’à atteindre le cas de base. Chaque calcul intermédiaire se fait sur une instance plus petite.
Chaque calcul intermédiaire est aussi indépendant du calcul précédent.
Remarque
⌊2n⌋ est la notation mathématique pour l’opération en Python n // 2, c’est à dire le plus grand entier inférieur au résultat de la division denpar 2.
⌈2n⌉ est la notation mathématique pour l’opération en Python n // 2 + 1, c’est à dire pour le plus petit entier supérieur au résultat de la division denpar 2.
Pourquoi appelle-t-on l’algorithme 2, l’exponentiation rapide ?
Réponse
Soit k le nombre de fois qu’il faut diviser (division euclidienne) n par 2 pour parvenir à la valeur 1. k est tel que
1=2kn⟺2k=n⟺k=log2n
.
Il reste un appel récursif supplémentaire à effectuer pour arriver au cas de base.
La complexité de l’algorithme est donc en O(log2n) ; elle est bien meilleure que celle de l’algorithme 1.
Conclusion
À retenir
La méthode « Diviser pour régner » est le paradigme naturel de la récursivité.
La complexité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » est parfois optimale (exponentiation rapide, recherche dichotomique, tri fusion, etc.) mais pas toujours (recherche du minimum et du maximum dans une liste, somme des éléments d’une liste, recherche dans une liste non triée, etc.).
L’efficacité d’un algorithme qui s’appuit sur le paradigme « Diviser pour régner » dépend de l’implémentation de la récursivité par le langage choisi.
Exercice : recherche dichotomique
Écrire le code de la fonction recherche1 dont la spécification est la suivante :
defrecherche1(liste:list[int],val:int)->int:"""
Retourne l'indice de la valeur dans la liste si cette
dernière est présente, -1 sinon.
HYPOTHÈSE : val est unique si présente.
Algorithme itératif.
"""
Réponse
defrecherche1(liste:list[int],val:int)->int:"""
Retourne l'indice de la valeur dans la liste si cette
dernière est présente, -1 sinon.
HYPOTHÈSE : val est unique si présente.
Algorithme itératif.
"""g=0# indice le plus petitd=len(liste)-1# indice le plus grandtrouve=Falsewhile(g<d)andnottrouve:m=(g+d)//2# indice milieuifliste[m]==val:trouve=Trueelifliste[m]>val:d=m-1else:g=m+1returnmiftrouveelse-1
Tester la fonction recherche1.
Écrire le code de la fonction recherche2 dont la spécification est la suivante :
defrecherche2(liste:list[int],val:int,g:int,d:int)->bool:"""
Retourne l'indice de la valeur dans la liste si cette
dernière est présente, -1 sinon.
HYPOTHÈSE : val est unique si présente.
Algorithme récursif.
"""
Réponse
defrecherche2(liste:list[int],val:int,g:int,d:int)->bool:"""
Retourne l'indice de la valeur dans la liste si cette
dernière est présente, -1 sinon.
HYPOTHÈSE : val est unique si présente.
Algorithme récursif.
"""ifg>d:return-1else:m=(g+d)//2# indice milieuifliste[m]==val:returnmelifliste[m]>val:returnrecursive(liste,val,g,m-1)else:returnrecursive(liste,val,m+1,d)
Tester la fonction recherche2.
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »
Dans cette partie, nous allons essayer de comprendre les principes sur lesquels s’appuie ce tri. Son implémentation, pour des tableaux ou des listes chaînées, sera développée dans les prochaines sections.
Le tri fusion s’appuie sur la méthode Diviser pour régner pour trier les n éléments d’une séquence S :
Diviser : Si la séquence S est composée de 0 ou un élément, retourner S immédiatement ; cette séquence est déjà triée. Si la séquence S est composée de plus de deux éléments, la diviser en deux sous-séquences S1 et S2 contenant chacune environ la moitié des éléments de S ; donc S1 est formée des ⌊2n⌋ premiers éléments de S contient les ⌈2n⌉ derniers éléments de S.
Régner : Trier récursivement S1 et S2.
Combiner : Reformer la séquence S en combinant, dans l’ordre, les éléments des séquences triées S1 et S2.
Info
⌊2n⌋ est la notation mathématique pour l’opération en Python n // 2, c’est à dire le plus grand entier inférieur au résultat de la division denpar 2.
⌈2n⌉ est la notation mathématique pour l’opération en Python n // 2 + 1, c’est à dire pour le plus petit entier supérieur au résultat de la division denpar 2.
Pour bien comprendre la méthode employée, le plus simple est de construire un arbre binaire dans lequel chaque nœud est le résultat d’un appel récursif.
On peut montrer que la hauteur de l’arbre des appels récursifs est voisine (en fonction de la définition choisie pour la hauteur) de log2(n) où n est le nombre d’éléments dans la séquence.
Implémentation du tri fusion pour un tableau
Étudier le code suivant et remplacer les … pour chaque numéro.
deftri_fusion(S:list[int])->None:"""
Implémentation du tri fusion.
La liste S est modifiée en place.
"""n=len(S)# ... (0)ifn<2:returnNone# ... (1)# Diviser, Régner, Combiner ? ... (2)milieu=n//2S1=S[:milieu]# .... (3)S2=S[milieu:]# .... (4)# Diviser, Régner, Combiner ? ... (5)tri_fusion(S1)# ... (6)tri_fusion(S2)# ... (7)# Diviser, Régner, Combiner ? ... (8)fusion(S1,S2,S)# ... (9)
Étudier le code suivant et expliquer comment s’effectue la fusion.
deffusion(S1:list[int],S2:list[int],S:list[int])->None:"""
Combine les éléments des deux listes S1 et S2 dans la liste S (en place).
i est le nombre d'élément(s) de S1 copié(s) dans S.
j est le nombre d'élément(s) de S2 copié(s) dans S.
On doit donc avoir i + j <= len(S).
"""i=0j=0whilei+j<len(S):ifj==len(S2)or(i<len(S1)andS1[i]<S2[j]):S[i+j]=S1[i]i=i+1else:S[i+j]=S2[j]j=j+1
Étudier le comportement du programme complet à l’aide de pythontutor.
Construire la liste à l’aide de l’instruction :
liste=[randint(1,400)foriinrange(5)]
Quelle est la complexité de la fonction fusion ?
Essayer d’évaluer la complexité de l’algorithme sans faire de calcul.
Le tri fusion d’une liste chaînée
Dans cette section, on cherche à adapter l’algorithme de tri fusion à une liste chaînée.
Écrire le code de la classe Cellule permettant d’implémenter une liste chaînée. Cette classe sert juste de structure et définit les champs valeur, de type int, et suivant, de type Cellule, initialisé à None.
Dans la partie principale du programme, écrire le code qui crée la liste chaînée [14, 11, 2, 35, 9, 1].
Définir le code de la fonction tri_fusion dont la spécification est
deftri_fusion(lst:Cellule)->Cellule:"""
Implémente l'algorithme de tri-fusion.
Une nouvelle liste chaînée est créée.
"""
Cette fonction doit utiliser la fonction coupe (définie un peu plus bas), qui découpe une liste chaînée en deux sous-listes, et la fonction fusion (définie elle aussi un peu plus bas) qui réalise la fusion de deux listes triées.
La fonction tri_fusion doit mettre en œuvre le principe « Diviser pour régner ».
Définir la fonction coupe dont la spécification est
defcoupe(lst:Cellule)->Cellule:"""
Découpe la liste L2 est deux sous-listes de même
longueur à un élément près.
"""
Définir la fonction fusion dont la spécification est
deffusion(l1:Cellule,l2:Cellule)->Cellule:"""
Réalise la fusion des deux listes l1 et l2
triées.
Algorithme récursif.
"""
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »
Recherche des plus grand et petit éléments dans un tableau
L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer le maximum et le minimum des éléments dans un tableau.
Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards.
Réponse
Utiliser les fonctions min et max fournies par le langage Python afin d’afficher les maximum et minimum dans la liste.
Réponse
print("Fonctions Python")val_min,val_max=(min(tab),max(tab))print("min = {}, max = {}".format(val_min,val_max))
Écrire le code de la fonction maxmin1 qui, à partir d’un algorithme de « brute force », détermine les maximum et minimum dans la liste passée en argument.
La spécification de la fonction est :
defmaxmin1(tab:List[float])->Tuple[float,float]:"""
Recherche du minimum et du maximum dans le tableau tab.
Paradigme « Brute force »
"""
Réponse
defmaxmin1(tab:List[float])->Tuple[float,float]:"""
Recherche du minimum et du maximum dans le tableau tab.
Paradigme « Brute force »
"""val_max=tab[0]val_min=tab[0]foreltintab:ifelt>val_max:val_max=eltifelt<val_min:val_min=eltreturn(val_min,val_max)
Vérifier le bon fonctionnement de la fonction maxmin1 en affichant les maximum et minimum dans la liste, à la suite de ceux déterminés à l’aide des fonctions fournies par Python.
Réponse
print("Recherche « Brute Force »")val_min,val_max=maxmin1(tab)print("min = {}, max = {}".format(val_min,val_max))
Quelle est la complexité de la fonction maxmin1 ?
Réponse
Il est nécessaire de parcourir tout le tableau, la complexité est donc en O(N).
Comparer l’efficacité de la fonction maxmin1 à celle des fonctions fournies par Python en mesurant les durées d’exécution à l’aide de la fonction time du module time.
Réponse
importtimeif__name__=="__main__":tab=[randint(1,int(1e12))foriinrange(int(1e6))]print("Fonctions Python")t1=time.time()val_min,val_max=(min(tab),max(tab))t2=time.time()print("min = {}, max = {}".format(val_min,val_max))print("Durée de la recherche : {} s".format(t2-t1))print("Recherche « Brute Force »")t1=time.time()val_min,val_max=maxmin1(tab)t2=time.time()print("min = {}, max = {}".format(val_min,val_max))print("Durée de la recherche : {} s".format(t2-t1))
Il existe un rapport 2 entre les durées d’exécution des deux fonctions. Elles sont donc du même ordre de grandeur.
En faisant varier le nombre d’éléments dans le tableau, vérifier si les durées d’exécution de la fonction maxmin1 correspond bien à la complexité établie à la question 5.
La complexité des fonctions max et min fournies par Python vous semblent-elles être en O(N) ?
Écrire et implémenter la fonction maxmin2 qui implémente le raisonnement «Diviser pour régner » pour résoudre ce problème.
Dans un premier temps, écrire une fonction qui se contente de déterminer le maximum dans la liste passée en argument. Compléter ensuite le code de façon à ce que le maximum et le minimum soient retournés.
La spécification de la fonction est :
defmaxmin2(tab:List[float])->float:"""
Recherche du maximum dans le tableau tab.
Paradigme : Diviser pour règner
"""
Réponse
defmaxmin2(tab:List[float])->float:"""
Recherche du maximum dans le tableau tab.
Paradigme : Diviser pour régner
"""# Cas de baseiflen(tab)==1:returntab[0]# Divisermilieu=len(tab)//2max1=maxmin2(tab[:milieu])max2=maxmin2(tab[milieu:])# Régnermaximum=max(max1,max2)# Combinerreturnmaximum
Remarque : on peut aussi développer sa propre fonction max.
Vérifier le bon fonctionnement de la fonction à la suite des précédentes vérifications.
Réponse
print("Diviser pour régner")val_max=maxmin2(tab)print("max = {}".format(val_max))
Modifier la fonction maxmin2 afin qu’elle retourne les maximum et minimum dans la liste.
La spécification de la fonction est :
defmaxmin2(tab:List[float])->Tuple[float,float]:"""
Recherche du minimum et du maximum dans le tableau tab.
Paradigme : Diviser pour régner
"""
Réponse
defmaxmin2(tab:List[float])->Tuple[float,float]:"""
Recherche du minimum et du maximum dans le tableau tab.
Paradigme : Diviser pour régner
"""# Cas de baseiflen(tab)==1:return(tab[0],tab[0])# Divisermilieu=len(tab)//2max1,min1=maxmin2(tab[:milieu])max2,min2=maxmin2(tab[milieu:])# Régnermaximum=max(max1,max2)minimum=min(min1,min2)# Combinerreturn(minimum,maximum)
Quelle est la complexité de cette fonction ?
Réponse
Si on note C(n) la complexité en nombre de comparaisons à effectuer pour résoudre le problème en fonction de la taille du tableau, on obtient la relation suivante :
C(n)=⎩⎨⎧022C(n//2)+2si n=1si n=2si n>2
Dans la suite de cette partie, pour résoudre cette récurrence, on simplifie le problème en posant n=2k (on ne restreint pas la généralité de la conclusion en effectuant cette hypothèse).
On a alors
il faut diviser k−1 fois pour parvenir au cas de base, on a alors
C(n)=2k−1×C(2)+i=1∑k−12i
Comme C(2)=2 et ∑i=1k−12i=2k−2,
C(n)=2k−1×2+2k−2=2k+2k−2
Finalement
C(n)=2n−2
Il faut donc 2n−2 comparaisons pour résoudre le problème. La complexité est donc linéaire.
Vérifier le bon fonctionnement de la fonction à la suite des précédentes vérifications.
Réponse
print("Diviser pour régner")t1=time.time()val_min,val_max=maxmin2(tab)t2=time.time()print("min = {}, max = {}".format(val_min,val_max))print("Durée de la recherche : {} s".format(t2-t1))
La fonction maxmin2 est-elle, théoriquement, plus efficace que la fonction maxmin1 ? Dans la pratique ? Comment expliquer ce comportement ?
Réponse
La fonction maxmin2 n’est théoriquement pas plus efficace que la fonction maxmin1 puisque dans les deux cas, la complexité est linéaire.
En pratique, la fonction maxmin2 peut même être moins efficace que la fonction maxmin1 ! Tout dépend de l’implémentation de la récursivité par le langage.
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »
Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas. Paru d’abord en fascicule en 1889 , il est publié ensuite dans le tome 3 de ses « Récréations mathématiques », parues à titre posthume en 1892. Il annonce que ce problème est dû à un de ses amis, N. Claus de Siam (anagramme de Lucas d’Amiens, Amiens étant sa ville de naissance), prétendument professeur au collège de Li-Sou-Stian (anagramme de Saint Louis, le lycée où Lucas enseignait).
Sous le titre « Les brahmes tombent », Lucas relate que « N. Claus de Siam a vu, dans ses voyages pour la publication des écrits de l’illustre Fer-Fer-Tam-Tam, dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d’airain, hautes d’une coudée et grosses comme le corps d’une abeille.Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d’or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet. C’est la tour sacrée du Brahmâ.Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la tour de la première aiguille sur la troisième, sans s’écarter des règles fixes que nous venons d’indiquer, et qui ont été imposées par Brahma.Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes ! ».
Au début du jeu, les disques sont tous positionnés sur la première tige (du plus grand au plus petit) et l’objectif est de déplacer tous ces disques sur la troisième tige, en respectant les règles suivantes :
Un seul disque peut être déplacé à la fois ;
On ne peut jamais poser un disque sur un disque de diamètre inférieur.
Numéroter chaque disque pour un empilement à 4 disques et écrire l’enchaînement des étapes nécessaires à la réalisation de la tâche.
Faire émerger le raisonnement récursif qui permet de résoudre le problème.
Réponse
Pour pouvoir déplacer le dernier disque (celui du dessous), il est nécessaire de déplacer les n−1 disques qui le couvrent sur la tige centrale. Une fois ces déplacements effectués, on peut le déplacer sur la troisième tige. Il reste alors à déplacer les n−1 autres disques vers la troisième tige.
Écrire le code de la fonction dont la spécification est
defhanoi(n:int,source:str,milieu:str,destination:str)->None:"""
Fonction qui déplace récursivement les disques selon les règles des tours de Hanoï.
"""
Tester cette fonction.
Aide
Info
L’algorithme est le suivant :
Si le nombre de disques est égal à 0, ne rien faire ;
Si le nombre de disques est égal à 1, déplacer directement le disque du piquet A au piquet C ;
Si le nombre de disques est supérieur ou égal à 2, enchaîner les étapes suivante :
Déplacer n−1 disques du piquet A jusqu’au piquet B ;
Déplacer le disque qui reste du piquet A au piquet C ;
Déplacer n−1 disques du piquet B au piquet C.
Indiquer tous les appels de fonctions et toutes les instructions exécutées pour n=3.
Réponse
hanoi(3, "A", "B", "C")
hanoi(2, "A", "C", "B")
hanoi(1, "A", "B", "C")
hanoi(0, "A", "C", "B")
Affichage : 1 de A à C
hanoi(0, "B", "A", "C")
Affichage : 2 de A à B
hanoi(1, "C", "A", "B")
hanoi(0, "C", "B", "A")
Affichage : 1 de C à B
hanoi(0, "A", "C", "B")
Affichage : 3 de A à C
hanoi(2, "B", "A", "C")
hanoi(1, "B", "C", "A")
hanoi(0, "B", "A", "C")
Affichage : 1 de B à A
hanoi(0, "C", "B", "A")
Affichage : 2 de B à C
hanoi(1, "A", "B", "C")
hanoi(0, "A", "C", "B")
Affichage : 1 de A vers C
hanoi(0, "B", "A", "C")
Quelle est la complexité de la fonction ?
Réponse
Récurrence
Si on note xn le nombre de mouvement pour déplacer n disques, on obtient la relation de récurrence :
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »
Problème de la sous-séquence de somme maximale
Ce document étudie le problème de la sous-séquence de somme maximale. Ce problème est intéressant parce qu’il existe nombre d’algorithmes pour le résoudre et la complexité (en nombre d’opérations de somme) de ces algorithmes varie considérablement.
Seulement deux algorithmes seront abordés, un prochain document présentera l’algorithme le plus efficace (cf. programmation dynamique).
Présentation
Info
Étant donné un tableau tab[1..n] d’entiers (positifs et négatifs), déterminer la valeur maximale du sous-tableau tab[g..h] donnant la plus grande somme de tous les sous-tableaux contigus de tab.
Pour plus de commodité, la sous-séquence de somme maximale est 0 si tous les entiers sont négatifs.
Exemples
Pour le tableau tab = [-2, -5, 6, -2, -3, 1, 5, -6], la sous séquence de somme maximale est [6, -2, -3, 1, 5] et sa somme est 7.
Pour le tableau tab = [0, 1, 2, -2, 3, 2], la sous séquence de somme maximale est [1, 2, -2, 3, 2] et sa somme est 6.
Pour le tableau tab = [1, -2, 3, 10, -4, 7, 2, -5], la sous séquence de somme maximale est [3, 10, -4, 7, 2] et sa somme est 18.
Paradigme « Brute force »
On envisage dans un premier temps un algorithme basé sur le paradigme « Brute force » : on évalue la somme de chaque sous-tableau (parmi les n(n+1)/2 sous-tableaux possibles) et à chaque évaluation on mémorise la somme maximale.
Écrire le code de la fonction sous_tab_max dont la spécification est :
defsous_tab_max(tab:List[int])->int:"""
Recherche de la somme maximale dans un tableau.
Paradigme : « Brute force ».
"""
Tester cette fonction.
Réponse
defsous_tab_max(tab:List[int])->int:"""
Recherche de la somme maximale dans un tableau.
Paradigme : « Brute force ».
"""smax=0foriinrange(len(tab)-1):somme=0forjinrange(i,len(tab)):somme+=tab[j]smax=max(smax,somme)returnsmax
Quelle est la complexité de cette fonction ?
Réponse
On retrouve deux boucles imbriquées dans la fonction, la complexité est donc en O(n2).
Paradigme « Diviser pour régner »
Dans la suite, on cherche à mettre en œuvre le paradigme « Diviser pour régner ».
Le tableau initial est scindé en deux parties de tailles à peu près égales (selon que n est pair ou impair) : la plus grande somme se trouve soit dans le sous-tableau B de droite, soit dans le sous-tableau A de gauche, soit à cheval sur les deux sous-parties. Dans ce dernier cas elle est constituée d’une plus grande somme de la partie gauche se terminant à la fin de la partie gauche (c.-à-d. en m), et d’une plus grande somme de la partie droite commençant au début de la partie droite (c’est à dire en m+1).
La procédure est récursive. Pour « sortir » des appels récursifs, il est nécessaire de rencontrer un « couple de données-paramètres » (transmis à l’appel) dont la solution est triviale. C’est le cas si le tableau est composé d’au plus un élément.
Écrire le code de la fonction somme_max dont la spécification est :
defsomme_max(tab:List[int])->int:"""
Recherche de la somme maximale dans un
sous-tableau en appliquant le paradigme
« Diviser pour régner ».
"""
Remarque
Ne pas effectuer le calcul de la somme maximale se trouveant dans la séquence à cheval sur les deux sous-parties. Ce calcul doit être effectué par un appel à la fonction max_sous_tab définie ci-dessous.
Réponse
defsomme_max(tab:List[int])->int:"""
Recherche de la somme maximale dans un
sous-tableau en appliquant le paradigme
« Diviser pour régner ».
"""# Cas de baseiflen(tab)==1:returnmax(0,tab[0])# Divisermilieu=len(tab)//2s_max1=somme_max(tab[:milieu])s_max2=somme_max(tab[milieu:])s_max3=max_sous_tab(tab,milieu)# Régners_max=max(s_max1,s_max2,s_max3)# Combinerreturns_max
Écrire le code de la fonction max_sous_tab dont la spécification est :
defmax_sous_tab(tab:List[float],milieu:int)->float:"""
Recherche la somme maximale entre les deux
sous-tableaux du tableau tab à partir du milieu.
"""
Réponse
defmax_sous_tab(tab:List[float],milieu:int)->float:"""
Recherche la somme maximale entre les deux
sous-tableaux du tableau tab à partir du milieu.
"""# Sous-tableau gauchegmax=0somme=0foriinrange(milieu,-1,-1):somme+=tab[i]gmax=max(gmax,somme)# Sous-tableau droitdmax=0somme=0foriinrange(milieu+1,len(tab)):somme+=tab[i]dmax=max(dmax,somme)returngmax+dmax
Quelle est la complexité de la fonction somme_max ?
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »
Dans ce document on introduit une méthode permettant d’évaluer numériquement une solution de l’équation f(x)=0, avec f une fonction de R dans R (lorsque la solution existe, bien sur) : la méthode de dichotomie.
La méthode de dichotomie est efficace et converge relativement vite. De plus, les conditions de son utilisation sont assez simples : la fonction f doit seulement être continue et changer de signe sur l’intervalle choisi ;
La méthode de Newtonconverge étonnement vite ! Les conditions de son utilisation sont cependant plus contraignantes : la fonction fdoit être dérivable.
Méthode de la dichotomie
Le raisonnement à mettre en œuvre s’appuie sur le théorème des valeurs intermédiaires.
Théorème des valeurs intermédiaires
Soit f:[a,b]→R une fonction continue sur un segment. Si f(a)⋅f(b)⩽0, alors il existe ℓ∈[a,b] tel que f(ℓ)=0.
Principe de résolution du problème
Info
On choisit un intervalle [a,b] dans lequel on pense que la fonction f s’annule une seule fois (il peut donc être nécessaire de limiter la largeur de cet intervalle).
Étape 1. On détermine les coordonnées du point milieu de l’intervalle : 2a+b
Si f(a)⋅f(2a+b)⩽0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[a,2a+b] tel que f(c)=0.
Si f(a)⋅f(2a+b)⩾0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[2a+b,b] tel que f(c)=0.
On est donc parvenu, à l’issu de cette étape, à définir un intervalle dans lequel f(x)=0, de longueur moitié par rapport à l’intervalle initial.
Étape suivante. On répète le processus mis en œuvre dans l’Étape 1 pour l’intervalle [a,2a+b] ou [2a+b,b].
Étapes suivantes. On continue à répéter le processus jusqu’à ce que l’intervalle soit de longueur inférieure à une longueur choisie (arbitrairement).
La méthode converge-t-elle réellement ?
On construit deux suites (an) et (bn) qui évoluent comme les bornes de l’intervalle, et la suite (xn), zéro de f pour chaque intervalle.
Au rang 0. On pose a0=a, b0=b. Comme f(a)⋅f(b)⩽0, il existe une solution, notée x0, de l’équation f(x)=0 dans l’intervalle [a0,b0].
Au rang 1. Si f(a0)⋅f(2a0+b0)⩽0, alors on pose a1=a0 et b1=2a0+b0, sinon on pose a1=2a0+b0 et b1=b0.
Comme f(a1)⋅f(b1)⩽0, il existe une solution, notée x1, de l’équation f(x)=0 dans l’intervalle [a1,b1].
Au rang n. On suppose construit un intervalle [an,bn], de longueur 2nbn−an, contenant une solution xn de l’équation f(x)=0.
Si f(an)⋅f(2an+bn)⩽0, alors on pose an+1=an et bn+1=2an+bn, sinon on pose an+1=2an+bn et bn+1=bn. Comme f(an+1)⋅f(bn+1)⩽0, il existe une solution, notée xn+1, de l’équation f(x)=0 dans l’intervalle [an+1,bn+1].
Étude des suites construites
Par construction :
- an⩽xn⩽bn
- (an) est une suite croissante, (bn) une suite décroissante.
La limite de (bn−an) tend donc vers 0 lorsque n tend vers +∞ :
lim(bn−an)n→+∞0
Les suites (an) et (bn) sont adjacentes. Elles admettent donc une même limite, ℓ.
Par application du théorème des gendarmes, on peut aussi en conclure que
lim(xn)n→+∞ℓ
et, comme f est une fonction continue,
f(ℓ)=n→+∞limf(xn)=n→+∞lim0=0
En conclusion, les suites (an) et (bn) tendent vers la valeur ℓ, solution de f(x)=0.
Remarque
En pratique, on arrête le processus dès que bn−an=2nb−a
est inférieur à la précision souhaitée.
Exemple : Approximation de 10
On définit la fonction f définie par f(x)=x2−10. f est
une fonction continue sur R qui s’annule en 10 et −10.
On limite l’étude à l’intervalle [3;4] puisque : f(3)=32−10=−1<0 et f(4)=42−10=6>0 entraîne 10∈[3;4].
On écrit le processus itératif :
On pose a0=3 et b0=4. f(a0)⩽0 et f(b0)⩾0.
2a0+b0=3,5 donc f(2a0+b0)=f(3,5)=3,52−10=2,25⩾0.
f(a0)⋅f(2a0+b0)⩽0, on en
déduit que 10 est dans l’intervalle [3;3,5].
On pose a1=3 et b1=3,5.
2a1+b1=3,25 donc f(2a1+b1)=f(3,25)=0,5625⩾0.
f(a1)⋅f(2a1+b1)⩽0, on en
déduit que 10 est dans l’intervalle [3;3,25].
On pose a2=3 et b2=3,25.
2a2+b2=3,125 donc f(2a2+b2)=f(3,125)=−0,23⋅⋅⋅⩽0.
f(b2)⩾0, f s’annule sur l’intervalle [3,125;3,25].
À ce stade, on a donc démontré que : 3,125⩽10⩽3,25.
Avec quelques étapes de plus, on obtient :
a0=3
b0=4
a1=3
b1=3,5
a2=3
b2=3,25
a3=3,125
b3=3,25
a4=3,125
b4=3,1875
a5=3,15625
b5=3,1875
a6=3,15625
b6=3,171875
a7=3,15625
b7=3,164062
a8=3,16015
b8=3,164062
En 8 étapes, on obtient donc l’encadrement :
3,160⩽10⩽3,165
ce qui donne les deux premières décimales du résultat.
Nombre d’itérations nécessaires pour atteindre un résultat
La longueur de l’intervalle [an,bn] est 2nb−a puisqu’il a
été nécessaire de découper n fois l’intervalle de départ en deux pour
parvenir à cet intervalle.
On peut alors rechercher le nombre d’itérations nécessaires pour
atteindre une précision choisie lors de la phase préliminaire de l’étude ; il suffit de rechercher le nombre n tel que 2nb−a⩽10−N :
L’objectif de cette activité est l’écriture d’une fonction qui effectue la rotation d’une image bitmap de 90 degrés en utilisant le principe « Diviser pour régner ».
On peut manipuler des images en Python à l’aide du module PIL (Python Image Library). Une première partie de l’activité est consacrée à la prise en main de ce module. Dans un second temps, la fonction de manipulation des bits est développée.
Images numériques
Définition
L’image matricielle
Une image matricielle, ou « carte de points » (de l’anglais « bitmap »), est une image constituée d’une matrice de points colorés, c’est-à-dire, constituée d’un tableau, d’une grille, où chaque case possède une couleur qui lui est propre et est considérée comme un point. Il s’agit donc d’une juxtaposition de points de couleurs formant, dans leur ensemble, une image.
Le codage ou la représentation informatique d’une image implique sa numérisation. Cette numérisation se fait dans deux espaces :
l’espace spatial dans lequel l’image est numérisée suivant l’axe des abscisses et l’axe des ordonnées : on parle d’échantillonnage. Les échantillons dans cet espace sont nommés pixels (« picture element ») et leur nombre va constituer la définition de l’image.
l’espace des couleurs dans lequel les différentes valeurs de luminosité que peut prendre un pixel sont numérisées pour représenter sa couleur et son intensité ; on parle de quantification. La précision dans cet espace dépend du nombre de bits sur lesquels on code la luminosité et est appelée profondeur de l’image.
À retenir
La qualité d’une image matricielle est déterminée par le nombre total de pixels et la quantité d’information contenue dans chaque pixel (souvent appelée profondeur de numérisation des couleurs).
Définition d’une image
On appelle définition le nombre de points (pixels) constituant une image: c’est le nombre de colonnes de l’image que multiplie son nombre de lignes.
La définition d’une image indique donc le niveau de détails qui seront visibles dans l’image. Pour une taille donnée, plus il y aura de pixels, plus il y aura de détails fins visibles.
Exemple. Une image numérisée avec une définition de 640×480 pixels (donc contenant 307 200 pixels) apparaîtra très approximative et sous forme d’un pavage de petits carrés de couleur, par comparaison à une image de 1280×1024 pixels (soit 1 310 720 pixels).
Résolution d’une image
On appelle résolution le nombre de points (pixels) contenus dans une longueur donnée, le pouce (un pouce mesure 2,54cm, c’est une unité de mesure britannique). Elle est exprimée en « points par pouce » (PPP) en français et « Dots Per Inch » (DPI) en anglais.
La résolution permet ainsi d’établir le rapport entre la définition d’une image et la dimension réelle de sa représentation sur un support physique (écran, papier, etc.)
En plus de sa définition, une image numérique utilise plus ou moins de mémoire selon le codage des informations de couleur qu’elle possède. C’est ce que l’on nomme le codage de couleurs ou profondeur des couleurs, exprimé en bits par pixel (bpp) : 1, 4, 8, 16, 24, … bits.
Le codage des informations de couleur est donc le nombre de bits utilisés pour coder une couleur.
Remarque
Les écrans utilisent la synthèse additive pour restituer les couleurs : chaque pixel est composé de trois sous-éléments munis respectivement d’un filtre : rouge, vert, bleu.
Quelques modes de représentation des couleurs
Mode bitmap (noir et blanc) : Avec ce mode, il est possible d’afficher uniquement des images en deux couleurs: noir et blanc. Il présente une profondeur de 1 bpp.
Mode niveau de gris : Avec ce mode, il est possible d’afficher des images utilisant 254 ou 65534 nuances de gris entre le blanc et le noir.
Le niveau de gris représente la luminosité d’un pixel, lorsque les valeurs de ses composantes de couleur sont identiques.
Pour convertir une image couleur en niveau de gris il faut remplacer, pour chaque pixel les trois valeurs représentant les niveaux de rouge, de vert et de bleu, en une seule valeur représentant la luminosité.
Il présente une profondeur de 8 bpp ou 16 bpp.
Mode RVB : Dans ce mode, la couleur de chaque pixel de l’image est codée à l’aide d’un triplet de valeurs pour le rouge, le vert et le bleu. Chaque canal peut être codé sur 8 bits (le plus fréquent) ou 16 bits (appareils de photo modernes).
Exploitation des documents
Déterminer la résolution d’une image de 300×300 pixels mesurant 2 pouces par coté.
Quelle serait la définition en pixels d’une feuille scannée d’une largeur de 8,5 pouces sur une hauteur de 11 pouces en 300 dpi ?
Quel est le poids, en octets, d’une image d’une définition de 640×480, codée sur 1 bit (image en « noir et blanc ») ? codée sur 8 bits (« niveau de gris ») ? codée sur 24 bits (« RVB ») ?
Pourquoi le mode « niveau de gris » divise-t-il par trois le nombre d’octets nécessaire au codage ?
Quelle particularité doivent présenter les sous-éléments de chaque pixel lors de l’affichage d’une image en « niveau de gris » ?
Déterminer le nombre de couleurs que l’on peut coder en mode RVB (8 bpp).
Manipulation d’une image en niveaux de gris avec Python
Étudier le code suivant, essayer de déterminer quel traitement effectue la fonction mystere et le tester.
importPIL.Imageaspidefmystere(im):"""
Cette fonction réalise un traitement qu'il faut deviner, sur
l'image dont l'objet qui la représente est passé en argument.
Paramètre
---------
im: PIL.Image.Image
Objet image
Retour
------
None
"""(largeur,hauteur)=(im.width,im.height)foryinrange(hauteur):forxinrange(largeur):niveau=im.getpixel((x,y))niveau=255-niveauim.putpixel((x,y),niveau)defmain():"""Fonction principale"""# Chemin de l'imageimage="tigrenb.png"# Création de l'objet imageim_nb=pi.open(image)# Visualisation du fichierim_nb.show()# Modification du fichiermystere(im_nb)# Visualisation des modificationsim_nb.show()main()
À partir de la fonction précédente, écrire une fonction nommée noir_et_blanc qui, en fonction d’un seuil s, transforme tous les pixels de valeur inférieure à s en 0 (noir) et tous les autres en 255 (blanc).
En modifiant les couleurs des pixels, il est possible de « dessiner » dans une image. Par exemple, on peut tracer une ligne horizontale blanche dans l’image.
Écrire la fonction ligne_blanche qui trace une ligne blanche horizontale au niveau de l’ordonnée y de l’image et le tester.
Écrire la fonction ligne, évolution de la fonction précédente, qui permet de tracer une ligne horizontale d’une « couleur », codée en niveau de gris, dont le niveau est passé en argument.
On veut maintenant pouvoir assombrir ou éclaircir des images. Pour assombrir une image, on décide de diviser par 2 le niveau de tous les pixels. À l’opposé, pour éclaircir une image, on décide de multiplier par 2 le niveau de tous les pixels, en prenant soin de ne pas dépasser la valeur maximale de 255 (on limite donc les valeurs supérieures à 255).
Écrire la fonction traitement qui réalise ces opérations (la fonction doit être capable d’éclaircir ou d’assombrir l’image).
Écrire la fonction grille qui trace une grille à l’écran. Cette fonction doit recevoir en argument le pas de la grille, la couleur des traits horizontaux et verticaux (en niveaux de gris) et l’objet image.
Manipulation d’une image en couleur avec Python
Étudier le code suivant.
fromPILimportImagedefrecuperation_niveaux(im:Image,pt:tuple)->None:"""
Récupère la couleur du pixel pt.
"""# On vérifie que le point est dans l'image(largeur,hauteur)=(im.width,im.height)ifpt[0]>(largeur-1)orpt[0]<0orpt[1]<0orpt[1]>(hauteur-1):raiseException("Le point indiqué n'est pas dans l'image.")# Récupération des niveaux de couleurtriplet=im.getpixel(pt)returntripletdefmodification_couleur(im:Image,pt:tuple,triplet:tuple)->None:"""
Attribue la couleur (triplet) au pixel pt.
"""# On vérifie que le point est dans l'image(largeur,hauteur)=(im.width,im.height)ifpt[0]>(largeur-1)orpt[0]<0orpt[1]<0orpt[1]>(hauteur-1):raiseException("Le point indiqué n'est pas dans l'image.")# Modification de la couleurim.putpixel(pt,triplet)defgrille(im:Image,pas:int,triplet:tuple)->None:"""
Trace une grille à l'écran, de pas 'pas' dont la couleur
est donnée par le triplet triplet.
"""passdefaugmentation_contraste(im:Image,offset:int)->None:"""
Augmente le contraste de l'image d'une valeur offset.
"""passdefteinte_plus_chaude(im:Image,offset:int)->None:passdefmain():"""Fonction principale."""nom_image="tigre.jpg"# Création de l'objet imageim=Image.open(nom_image)im.show()# Récupération des niveaux de couleurpt=(600,250)(rouge,vert,bleu)=recuperation_niveaux(im,pt)# Affichage du résultatprint("Au point {} : R : {}, V : {}, B : {}".format(pt,rouge,vert,bleu))main()
L’idée de l’algorithme consiste à découper l’image en quatre, à effectuer la rotation de 90 degrés de chacun des quatre morceaux, puis de les déplacer vers leur position finale.
Afin de pouvoir procéder récursivement, définir la fonction (et sa spécification !) rotation_aux(px, x, y, t) qui effectue la rotation de la portion carrée de l’image comprise entre les pixels (x,y) et (x+t,y+t). Cette fonction ne renvoie rien, elle modifie le tableau px pour effectuer la rotation de cette portion de l’image, au même endroit. On suppose que t est une puissance de 2.
Le code de cette fonction est :
Étudier ce code afin de bien le comprendre. En particulier, faire fonctionner à la main la fonction pour une image de définition 8×8.
En déduire la fonction rotation(px) qui effectue une rotation de l’image toute entière, sa dimension étant donnée par le paramètre taille.
Une fois la rotation effectuée, on pourra sauvegarder le résultat dans un autre fichier avec l’instruction im.save("Apres_rotation.png").
Physique, Chimie et Informatique > Terminales Spé. NSI > Méthode « Diviser pour régner »
L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer la somme des n nombres (entiers) d’un tableau.
Écrire le code de fonction somme1 dont la spécification est :
defsomme1(tab:List[float])->float:"""
Calcul de la somme des nombres éléments
de tab.
Algorithme : Récursivité enveloppée
"""
Penser à écrire un jeu de tests.
Réponse
defsomme1(tab:List[float])->float:"""
Calcul de la somme des nombres éléments
de tab.
Algorithme : Récursivité enveloppée
"""iflen(tab)==1:returntab[0]returntab[0]+somme1(tab[1:])if__name__=="__main__":tab=[1,2,3,4,5,6,7]n=tab[len(tab)-1]assertsomme1(tab)==n*(n+1)//2print("Done!")
Réfléchir à un algorithme utilisant le principe « Diviser pour régner » qui résoud le même problème.
Écrire le code de la fonction somme2 qui implémente cet algorithme.
Tester cette fonction.
Réponse
defsomme2(tab:List[float])->float:"""
Calcul de la somme des nombres éléments
de tab.
Algorithme : Diviser pour Régner.
"""# Cas de baseiflen(tab)==1:returntab[0]# Diviserm=len(tab)//2somme_g=somme2(tab[:m])somme_d=somme2(tab[m:])# Régnertotal=somme_g+somme_d# Recombinerreturntotalif__name__=="__main__":tab=[1,2,3,4,5,6,7]n=tab[len(tab)-1]assertsomme1(tab)==n*(n+1)//2assertsomme2(tab)==n*(n+1)//2print("Done!")
Décrire le fonctionnement de l’algorithme pour la liste [1, 2, 3, 4, 5, 6, 7].
Réponse