π
<-
Chat plein-écran
[^]

tri-piles


Hierarchy of files

 Downloads
 Files created online
 TI-Nspire

 mViewer GX Creator Lua

DownloadTélécharger


LicenceLicense : Non spécifiée / IncluseUnspecified / Included

 TéléchargerDownload

Actions



Vote :

ScreenshotAperçu


Tester en ligne !

Informations

Catégorie :Category: mViewer GX Creator Lua TI-Nspire
Auteur Author: chach76
Type : Classeur 3.6
Page(s) : 6
Taille Size: 449.07 Ko KB
Mis en ligne Uploaded: 05/05/2021 - 06:44:02
Uploadeur Uploader: chach76 (Profil)
Téléchargements Downloads: 1
Visibilité Visibility: Archive publique
Shortlink : http://ti-pla.net/a2735245

Description 

Structure de pile
10
¦ Une structure de données en informatique combine un moyen d’enregistrer des don-
nées sous une forme organisée et de les manipuler. En général, lorsque l’on définit une
structure de données, on en donne aussi une représentation (mathématique, graphique ou
autre) permettant de visualiser comment elle fonctionne. Jusqu’à présent, les structures de
données que l’on a rencontrées en P YTHON sont les listes (et les tuples) et les matrices de
N UMPY.
¦ Lorsque l’on programme une sructure de données, il y a deux choses qui apparaissent :
• La mise en œuvre ou implémentation de cette structure ;
• La liste et le rôle des différentes opérations (primitives) qui sont fournies pour mani-
puler cette structure (c’est l’interface de la structure).
L’utilisateur de la structure de données ne doit connaitre que l’interface. Les détails de l’im-
plémentation n’ont pas à être connus (et peuvent éventuellement changer). L’interface per-
met de séparer l’utilisation de la structure de sa mise en œuvre.
¦ La structure de données qui nous intéresse ici : les piles (stack ou LIFO pour last in first
out i.e. dernier entré premier sorti). On se représente une pile (informatique) comme une
pile d’assiettes : on peut ajouter des éléments et seul le dernier élément ajouté est directe-
ment accessible. Les primitives de manipulation sont :
• pile_vide() définit une nouvelle pile, ne contenant aucun élément ;
• empiler(P,x) modifie la pile P en ajoutant l’élément x au sommet ;
• depiler(P) retire l’élément qui est au sommet de la pile et renvoie sa valeur (pro-
duit une erreur si la pile ne contient aucun élément) ;
• est_vide(P) renvoie True si la pile est vide et False sinon.
Exemple. On peut traiter un exemple sans savoir comment sont programmées ces fonc-
tions. On part par exemple d’une pile vide, on empile la valeur 12 puis la valeur −3, on
dépile ensuite l’élément qui se trouve au sommet :
P = pile_vide() empiler(P,12) empiler(P,-3) x = depiler(P)
−3
12 12 12
P P P P
print(x)
-3




http://alexandre.boisseau.free.fr/Prive/WWW/InfoPCet/piles.pdf
Mise en œuvre de la structure de pile
¦ On programme cette structure en P YTHON en utilisant des listes.

def pile_vide(): def empiler(P,x): def est_vide(P):
return [] P.append(x) return len(P)==0
La fonction dépiler est un peu plus complexe. On utilise la fonction pop qui renvoie le der-
nier élément de la liste et le retire. On ajoute également un test permettant de déclencher
une erreur si la liste est vide :

def depiler(P):
assert not est_vide(P), "La pile est vide"
x = P.pop()
return x
La commande assert c, s teste si la condition c est vraie. Si c’est le cas, alors le programme
continue normalement, sinon une erreur est déclenchée et la chaîne de caractères s est
affichée.

Remarque. Pourquoi utiliser une pile (et pas une liste) ?
• Si un algorithme utilise une pile, alors il peut être programmé dans tout langage qui
dispose de cette structure.
• La structure de pile est plus simple à mettre en œuvre que la structure de liste.
• Les primitives de manipulation des piles ont une meilleure complexité que celles de
manipulation des listes.
• Des structures de piles peuvent être présentes à un niveau assez bas dans la concep-
tion d’un ordinateur.
Quand vaut-il mieux utiliser une liste plutôt qu’une pile ?
• Quand on a besoin d’accéder à n’importe quel élément et pas seulement au dernier.
• Quand on a besoin d’ajouter ou supprimer des éléments à des positions quelconques.
• Quand on a besoin de connaitre le nombre d’éléments présents dans la structure. 


Exemple. On considère la suite (u n ) définie par def afficher(n):
u 0 = 2 et pour n ∈ N, u n+1 = 2u n − 1. On veut P = pile_vide()
définir une fonction afficher(n) qui affiche empiler(P,2)
les valeurs de u n , u n−1 , . . . , u 1 , u 0 dans cet ordre.
for k in range(n):
Le principe est le suivant : u = depiler(P)
• On crée une pile vide et on empile u 0 ; empiler(P,u)
• L’élément u au sommet de la pile représente empiler(P,2*u-1)
un terme de la suite. On le dépile puis on le re- while not est_vide(P):
met et on empile ensuite 2u − 1 qui est le terme print(depiler(P))
suivant. On répète ceci n fois ; afficher(8)
• La pile contient alors u 0 , u 1 , . . . , u n (dans cet
ordre). On dépile l’élément au sommet, on l’af- 257 129 65 33 17 9 5 3 2
fiche, puis on recommence tant que la pile n’est
pas vide.
Tri fusion
8
¦ Le principe du tri fusion met en œuvre la stratégie « diviser pour régner. » Pour trier un
tableau T , on le scinde en deux tableaux T1 et T2 de même taille (à un élément près) qui
sont triés par un appel récursif. On fusionne alors les deux tableaux triés.

¦ La fonction fusion. On considère un tableau T ainsi que des entiers positifs a, p et q.
Ces entiers délimitent deux parties de T :
• la partie allant de l’indice a à l’indice a + p − 1 (qui contient p éléments) ;
• la partie allant de l’indice a + p à l’indice a + p + q − 1 (qui contient q éléments).
On supposera donc que a + p + q É len(T)). On suppose que ces deux parties du ta-
bleau T sont chacune triées en ordre croissant. On a vu en TP l’écriture d’une fonction
fusion(T,a,p,q) qui modifie le tableau T de sorte que la partie allant de l’indice a
à l’indice a + p + q − 1 soit triée en ordre croissant et dont le temps d’exécution est O(p + q).
Cette fonction utilise une liste intermédiaire U de taille p + q.

¦ L’algorithme du tri fusion. Cet algorithme récursif procède en découpant le tableau T
en deux parties (approximativement de même taille), trie ces deux parties par un appel
récursif et les fusionne avec la fonction fusion.
Algorithme t r i _ f u s i o n ( T , a , n )
T tableau de nombres
Résultat : la partie allant de l’indice a à a + n − 1 est triée en ordre croissant
début algorithme
s i n > 1 alors
p ← bn/2c (partie entière)
t r i _ f u s i o n ( T , a , p ) (appel récursif)
t r i _ f u s i o n ( T , a + p , n − p ) (appel récursif )
fusion ( T , a , p , n − p )
f i n s i (si n = 1, il n’y a rien à faire, c’est le cas de base)
f i n algorithme

Remarque : pour trier un tableau T avec cet algorithme, on doit écrire tri_fusion(T, 0, len(T )).




http://alexandre.boisseau.free.fr/Prive/WWW/InfoPCet/tri_fusion.pdf
¦ Le temps d’exécution de fusion(T,a,p,q) est O(p + q), donc également O(n) où n
est la taille de T. Le temps d’exécution de tri_fusion satisfait la relation de récurrence :
³n ´
Ttri_fusion (n) = 2Ttri_fusion + O(n)
2
et on obtient ainsi Ttri_fusion (n) = O(n ln(n)). Notons que la complexité est la même dans
le meilleur et dans le pire cas.

¦ Le tri fusion est un tri comparatif mais ce n’est pas un tri en place (on utilise des listes
auxiliaires).

¦ À retenir : dans un calcul de complexité, si on obtient la relation de récurrence
³n ´
T (n) = 2T + O(n)
2
alors T (n) = O(n ln(n)).

¦ Illustration graphique. Les traits pointillés correspondent à un appel récursif sur une
sous-liste et les traits pleins correspondent à une étape de fusion.



[1, 2, 5, 4, 7, 9, 1, 6]




[1, 2, 5, 4] [7, 9, 1, 6]




[1, 2] [5, 4] [7, 9] [1, 6]




[1] [2] [5] [4] [7] [9] [1] [6]




[1, 2] [4, 5] [7, 9] [1, 6]




[1, 2, 4, 5] [1, 6, 7, 9]




[1, 1, 2, 4, 5, 6, 7, 9]
Problèmes de tri. Tri par insertion
7
¦ Certains algorithmes sur les listes peuvent être programmés plus effica...

Archive contentsContenu de l'archive

Action(s) SizeTaille FileFichier
1.64 Ko KB readme.txt
457.25 Ko KB tri_piles.tns

Pub / Ads

-
Search
-
Social
-
Featured topics
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Découvre les nouvelles fonctionnalités en Python de l'OS 5.2 pour les Nspire CX II
Découvre les nouvelles fonctionnalités en Python de l'OS 5.5 pour la 83PCE/84+C-T Python Edition
Omega, le fork étendant les capacités de ta NumWorks, même en mode examen !
1234
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...
Donate
Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
589 utilisateurs:
>556 invités
>27 membres
>6 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)

-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)