Travaux Dirigés dalgorithmique no4 PDF

SUJET + CORRIGE

16 déc. 2011 Exercice 1 (Files à l'aide de Piles (8 points)). Nous avons vu en cours une implémentation d'un pile par un tableau borné. CreerPileVide (N){.

Algorithmique et Structures de données 1 Piles

Dans les exercices suivants on consid`ere les types abstraits : type_Pile = Pile de objet;. type_File = File de objet; définis en cours. 1 Piles.

Corrigé de la série de TD N 03 de Structures de Données

Supprimer toutes les villes ayant plus de 10.000 habitants. Exercice n. ◦. 02: Piles. Soit P une Pile représentée par une liste

PILES FILES ET LISTES CHAÎNÉES

• Le temps d'exécution de cet algorithme est (ouf!) O(n. 2. ). Pourquoi? Page 7. 3.7. Piles files et listes chaînées. Une pile peut aider! • Nous voyons que si.

Langage C : énoncé et corrigé des exercices IUP GéniE

Langage C : énoncé et corrigé des exercices. 1.5. P ILE E T FILE. Ce s exercice 4 - Affi c h age par éc h ange de pointeurs d 'une pile implémentée en liste c ...

TD1.6 Preuves de correction et de terminaison

algorithme simple. Exercice 1 : Que calcule cet algorithme ? Soit l ... Heureusement ce défaut de notre preuve n'est pas très difficile à corriger. Il ...

TP 9 : LISTES CHAINÉES FILES DATTENTE

http://hebergement.u-psud.fr/mkowalski/doc/L3_IST_306_TP9.pdf

Exercice 1 : piles et files

Exercices dirigés séance n°9 - corrigé. Exercice 1 : piles et files. Un système muti-tâches peut exécuter n tâches en quasi parallélisme. Chaque tâche est

SUJET + CORRIGE

16 déc. 2011 UE : Algorithmes et structures de données. Épreuve : Examen ... SUJET + CORRIGE ... Exercice 1 (Files à l'aide de Piles (8 points)).

Algorithmique et Structures de données 1 Piles

type_File = File de objet; définis en cours. 1 Piles. Exercice 4.1 Ecrire un algorithme pour déplacer les entiers de P1 dans une pile P2 de fa`a§on `a ...

Corrigé de la série de TD N 03 de Structures de Données

Soit P une Pile représentée par une liste chaînée des villes de Boumerdès

TD1.6 Simulation mutuelle : file pile

https://algo.gricad-pages.univ-grenoble-alpes.fr/L3I-S5-algo/TD1-6-corrige.pdf

Travaux Dirigés dalgorithmique no4

Exercice 1. problèmes suivants ; donner la complexité de chaque algorithme. ... Une pile est une structure de donnée qui enregistre des informations ...

Langage C : énoncé et corrigé des exercices IUP GéniE

1.5 PILEET FILE . Les exercices 1 à 1 6 20 à 2 5

TD – Piles et files - Corrigé

TD – Piles et files. Corrigé. Piles. Exercice N°1 – Copie d'une pile Illustrons le principe général de l'algorithme à partir de l'exemple fourni dans ...

Exercices et problèmes dalgorithmique

3.2.3 Manipulation d'une file (méthode avec deux pointeurs) . comme référence pour le langage algorithmique utilisé dans les corrigés.

Algorithmique et structures de données en langage C 2ème année

et fonctions pour manipuler des listes piles

Algorithmes et structures de données : TD 9 Corrigé

Dans cet exercice on écrira les fonctions et procédures nécessaires pour implémenter une pile. Pour cela

Travaux Dirigés d"algorithmique n

Cours d"algorithmique-Licence CFA / Troisième Année-xExercice 1. (Recherches et accumulations dans les tableaux)

On dispose d"un tableaux d"entierstabde tailletaille. Écrire un algorithme pour résoudre les problèmes suivants; donner la complexité de chaque algorithme.

1. Calculer le nombre d"entiers pairs dans le tableaux;

2. Le tableau contient-il un entier pair?

3. Étant donné un entieri, trouver un l"entier le plus proche deidans le tableau.

4. Le tableau est-il trié? C"est-à-dire, l"assertion suivante est-elle vrai?

pour touti tab[i+ 1]: xExercice 2. (Manipulations de base des tableaux)

On travaille sur les données suivantes :tabest tableau pour lequel on a allouémax_tailleélé-

ments; Les éléments0i inutilisés. Écrire un algorithme pour résoudre les problèmes suivants; donner la complexité.

1. insertion d"un élément à la fin;

2. insertion d"un élément en positioni;

3. insertion d"un élément au début;

4. suppression d"un élément à la fin;

5. suppression d"un élément en positioni;

6. suppression d"un élément au début;

xExercice 3. (Tri par bulles) On dispose d"un tableaux d"entierstabde tailletaille. On cherche à trier le tableau. Pour ceci, on peut utiliser l"algorithme suivant : on parcourt le tableau en cherchant les positionsitelles que

0i tab[i+ 1]:

Quand on a trouvé un teli, on échangetab[i]ettab[i+ 1]et ensuite on continue le parcours. On recommence tant que le tableau n"est pas trié.

1. Écrire l"algorithme du tri par bulle.

2. En fait, on se rend compte que les éléments qui ne sont pas déplacés à la fin d"un parcourt, ne

seront jamais plus déplacés ensuite. Modifier le tri en tenant compte ce cette remarque à l"aide

d"un index qui note le dernier élément à parcourir.

3. On peut encore améliorer le tri par bulle en parcourant alternativement dans un sens et dans

l"autre. Écrire l"algorithme correspondant. On utilisera deux indices, pour le premier et le dernier éléments à parcourir.

4. Pour chacune des trois versions, dire quelle est le cas le pire et la complexité dans ce cas.

1 xExercice 4. (Implantation d"une pile par tableau)

Une pile est une structure de donnée qui enregistre des informations selon le mode dernier entré

premier sorti (LIFO : Last In First Out). On manipule une pile en utilisant les quatres opérations

suivantes :

Création d"une nouvelle pilePileVide() : Pile

Teste si la pile est videEstVide(Pile) : Booleen

Ajout d"un élémentEmpiler(T;Pile)modifie la pile Suppression d"un élémentDepiler(Pile) :Tmodifie la pile Note :Depiler(p)est valide seulement si nonEstVide(p).

1. En utilisant un tableau proposer une structure permettant de stocker une pile; Dans un premier

temps, on supposera que la taille est limitée.

2. Écrire précisément les invariants de la structure.

3. Écrire les quatres fonctions précédentes;

4. Quelle est leur complexité.

5. Comment faire pour que la taille ne soit plus limité sans perdre en complexité.

xExercice 5. (Implantation d"une file par tableau)

Une file est une structure de donnée qui enregistre des informations selon le mode premier entré

premier sorti (FIFO : First In First Out). On manipule une pile en utilisant les quatres opérations