Algorithmique et structure de données 2

structure de contenu et des liens hiérarchiques entre les rubriques qui la compose Organigramme Structures de données et algorithmique - Exercices - M Benjelloun, E Malengreau Symbole Désignation Début, fin, interruption d'un organigramme Symbole général « traitement » Opération ou groupe d'opérations sur des

SUJET + CORRIGE - Université de Bordeaux

Algorithmes et structures de données Session 1, Année 2010/2011 42 21 nil 13 nil nil 18 9 2 nil nil nil 5 nil nil fg fd fd fg fd fg Figure 1 Un arbre binaire et les clés des n÷uds Question 1 1 (4 oints)p Complétez l'exécution de l'algorithme ParcoursFile(A) sur l'arbre binaire de la gure 1 Réponse : F (42) (21) (21,18) (18) (18,13) non

SUJET + CORRIGE - Université de Bordeaux

Algorithmes et structures de données Session 1, Année 2011/2012 Question 2 5 (2 oints)p Donnez et justi ez la omplexitéc de votre algorithme Réponse : Le tri appelle un nombre de fois déterminé (ici 3) un algorithme de tri stable La omplexitéc du tri arp aseb est donc elcle du tri stable utilisé soit :

Structures de données et algorithmes fondamentaux

données algorithme résultat Pour illustrer ces notions de “problème” et d’“instance”, prenons l’exemple d’un système de navigation GPS : —le problème typique à résoudre serait, étant données deux villes et un réseau routier, de trouver un chemin le plus court possible entre ces deux villes dans le réseau donné;

STRUCTURES DE DONNÉES ET ALGORITHMES FONDAMENTAUX

Nouvelle structure de données : Liste Chaînée Introduction aux Types de Données Abstraits (TAD) TAD=Algorithme Structure = Implantation Plusieurs exemples de TAD (Ensemble, Liste Itérative, Liste Récursive, Pile, File) Pour aller plus loin : livre « Types de Données et Algorithmes », par C Froidevaux, M-C Gaudel et M Soria

Exercices 1 Structures de données - WordPresscom

Exercices 1 Structures de données et renvoyant la liste triée résultant de la fusion de t1et 3 Algorithme de segmentation en place d La structure de

Cours d’Algorithmique et structures de données 1

– La complexité de l’algorithme lui-même, On cherche à mesurer la complexité d’un algorithme indépendamment de la machine et du langage utilisés, c-à-d uniquement en fonction de la taille des données n que l’algorithme doit traiter Par exemple, dans le cas de tri d’un tableau, n est le nombre d’éléments du

Algorithmique et structure de données 2

Faculté des Mathématiques et de l’informatique Département d’informatique Algorithmique et structure de données 2 Chapitre 1 : Les sous-programmes : Fonctions et Procédures Cours Conçu par Dr Omar TALBI Version 1 0 2019-2020 Public concerné: -Etudiants 1ère LMD –MI Année universitaire 2019-2020

COURS DE STRUCTURES DE DONNÉES LICENCE 2 - UNIVERSITÉ CLERMONT 2

COURS DE STRUCTURES DE DONNÉES LICENCE 2 - UNIVERSITÉ CLERMONT 2 MAMADOU MOUSTAPHA KANTÉ Table des matières 1 Niveau de Description 2 1 1 Structure Générale d’un Ordinateur 2 1 2 Mémoire Centrale 3 1 3 Langages 3 2 Algorithmes, Valeurs, Types et Éléments du Langage 4 2 1 Données 5 2 2 Tableaux statiques 5 2 3 La Syntaxe du

Omar TALBI Version 1.0 2019-2020

&}OEuš]}v>XDX >]v u]'µ }u]vWDšZ uš]'µš]v(}OEuš]'µ ^}o}uuµvDšZ uš]'µUušZ uš]'µ‰‰o]'µ š ]v(}OEuš]'µ

í>D^ušOEî

hv]š [v]Pvuvš(}vuvšo Wh&îî

¾ &UpGLWV

¾ &RHIILFLHQW

¾ &RQQDLVVDQFHVSUpDODEOHVUHFRPPDQGpHV

Omar TALBI Version 1.0 2019-2020

1. 2. 3. 4. 5. 1. 2. 3. 4. 1. 2. 3. 4. 5. 6. 7. a. b.

HQ&FRXUVDYHFH[HUFLFHVFRUULJpV

GHFRXUV

WUDYDX[SUDWLTXHV

GHWUDYDX[SUDWLTXHV

Omar TALBI Version 1.0 2019-2020

1. Introduction

A partir des deux exemples suivants, nous introduirons la notion de sous-programmes.

Exemple 1 : Soient a, b et c des entiers naturels, écrire un algorithme qui calcule : (a! + b! ) / c!

Solution triviale Remarques

algorithme expression_factorielle; var a,b,c,i,f: entier; exp: reel ; debut lire (a,b,c) ; (*calcul de a !*) fÅ1 ; faire fÅf*i ; ffpour ; expÅf ; (*calcul de b !*) fÅ1 ; faire fÅf*i ; ffpour ; expÅexp+f ; (*calcul de c !*) fÅ1 ; faire fÅf*i ; ffpour ; expÅexp /f; fin. Les suites dinstructions surlignées en jaune sont pratiquement les mêmes.

La question qui se pose est :

Comment procéder pour éviter la répétition dune même séquence dinstructions ? Pour ce faire, nous procédons en deux étapes :

1- Nous Définissons un sous-programme qui

permet de : a. Calculer nimporte quelle factorielle dun nombre entier n donné. b. Récupérer le résultat du calcul.

2- Nous faisons par la suite Appel à ce sous-

programme pour le calcul de a!, de b! et de c!. Ce procédé nous a permis déviter de réécrire plusieurs fois cette même séquence dinstructions.

Nous verrons dans la suite du chapitre comment

écrire ce procédé en algorithme.

Omar TALBI Version 1.0 2019-2020

Exemple 2 : Soient A et B deux entiers naturels, écrire un algorithme qui permet dobtenir un nombre C égal

à la concaténation des deux nombres A et B. Par exemple, si A=13 et B=904 le résultat de la concaténation

serait le nombre C=13904.

Nous nous trouvons en face dun problème assez complexe, la solution consiste alors à réduire (diminuer)

cette complexité. Pour ce faire, on utilise des modules (sous-programmes).

9 Module 1: Comptage du nombre de chiffres du nombre B

9 Module 2: Calcul de 10 à la puissance le nombre de chiffres de B

9 Module 3: Calcul de C= A x (10 à la puissance le nombre de chiffres de B) + B

Ainsi,

¾ Un module désigne une entité de données et d'instructions qui fournissent une solution à une (petite)

partie bien définie d'un problème plus complexe.

¾ Un module peut faire appel à d'autres modules, leur transmettre des données et recevoir des données

en retour.

¾ L'ensemble des modules ainsi reliés doit alors être capable de résoudre le problème global.

Conclusions

Des deux exemples précédents, nous pouvons conclure que lutilisation des sous-programmes nous a permis

de :

¾ Gagner du temps.

¾ Ecrire des algorithmes plus courts et plus structurés.

¾ Appliquer la réutilisation.

2. Définitions

x Un s/s programme est un programme qui permet l séquenc :

9 Avec des données différentes (a, b et c sont des données différentes pour le calcul de la factorielle) à

9 Sans avoir à réécrire cette séquence, il suffit juste de lui faire appel.

9 Cette techniappelée modularisation facilite la programmation.

x Il existe deux types de sous programmes : (1) les Procédures et (2) les Fonctions.

A retenir

¾ Définir le sous-programme.

Omar TALBI Version 1.0 2019-2020

¾ u sous-programme appeler par son nom

accompagné des données sur lesquelles il va agir.

Fonctions

¾ Une fonction est un s/s programme qui retourne un résultat unique.

On adoptera la syntaxe suivante pour :

1- Définir une fonction

fonction (liste de paramètres formels) : fonction> ; ¾ La liste des paramètres formels peut être omise.

Se conformer à la syntaxe déjà étudiée dans la partie déclaration dun algorithme,

à savoir : . debut ; retourner ; fin ;

2- Faire Appel à la fonction

On fait appel à une fonction par le biais de son nom suivi entre parenthèses de la liste des paramètres

effectifs. (liste de paramètres effectifs) ;

Important

Î Lappel dune fonction ( (liste de paramètres effectifs)) dans une instruction nest

autre que lobtention de la valeur retournée par cette même fonction. Cette valeur a pour type

fonction>, à savoir : un type réel, entier, caractère ou logique et obéit donc aux règles sémantiques et

syntaxiques auxquelles devrait se conformer ce type.

Omar TALBI Version 1.0 2019-2020

Exemple dun algorithme qui calcule (a! + b! ) / c! en utilisant une fonction

Solution an LA

algorithme expression_factorielle; var a,b,c: entier; exp: reel ; fonction fact(n :entier) :entier ; var i,f :entier; debut fÅ1 ; faire fÅf*i ; ffpour ; retourner f ; fin; (* Définition de la fonction qui calcule n! , pour n entier, et retourne dans la variable f le résultat du calcul *) debut lire (a,b,c) ;

expÅ(fact(a)+fact(b)) /fact(c); (* Trois Appels de la fonction par son nom fact accompagnée lors de

chaque appel respectivement du paramètre a,b et c *) fin.

Solution en langage C

#include int fact(int n) int i, f=1; for (i=2; i<=n; i++) f=f*i; return f; int main() int a, b,c,d; float s; printf("\nDonner a:");scanf("%d",&a); printf("\nDonner b:");scanf("%d",&b); printf("\nDonner c:");scanf("%d",&c); s=(float) (fact(a)+fact(b))/(fact(c); printf("S= %.2f",s); return 0; Exercice à faire : Reprendre lexemple 2 en utilisant des fonctions.

Omar TALBI Version 1.0 2019-2020

Procédure

¾ Une procédure est un s/s programme qui ne renvoi aucun résultat,

¾ Une procédure permet de modifier des données, ou produire des effets physiques (lecture, écriture).

En LA, on adoptera la syntaxe suivante pour :

1- Définir une procédure

procedure (liste de paramètres formels); ¾ La liste des paramètres formels peut être omise Se conformer à la syntaxe déjà étudiée dans la partie déclaration dun algorithme, à savoir : . debut ; fin ;

2- Faire Appel à la procédure

On fait appel à une procédure par le biais de son nom suivi entre parenthèses de la liste des paramètres

effectifs. (liste de paramètres effectifs) ;

Important

Î Lappel dune procédure ne retourner aucune valeurquotesdbs_dbs10.pdfusesText_16

[PDF] Algorithmique et structure de données 2

Omar TALBI Version 1.0 2019-2020

í>D^ušOEî

¾ &UpGLWV

¾ &RHIILFLHQW

¾ &RQQDLVVDQFHVSUpDODEOHVUHFRPPDQGpHV

Omar TALBI Version 1.0 2019-2020

HQ&FRXUVDYHFH[HUFLFHVFRUULJpV

GHFRXUV

WUDYDX[SUDWLTXHV

GHWUDYDX[SUDWLTXHV

Omar TALBI Version 1.0 2019-2020

1. Introduction

Solution triviale Remarques

La question qui se pose est :

1- Nous Définissons un sous-programme qui

2- Nous faisons par la suite Appel à ce sous-

Nous verrons dans la suite du chapitre comment

écrire ce procédé en algorithme.

Omar TALBI Version 1.0 2019-2020

9 Module 1: Comptage du nombre de chiffres du nombre B

9 Module 2: Calcul de 10 à la puissance le nombre de chiffres de B

9 Module 3: Calcul de C= A x (10 à la puissance le nombre de chiffres de B) + B

Ainsi,

Conclusions

¾ Gagner du temps.

¾ Appliquer la réutilisation.

2. Définitions

9 Avec des données différentes (a, b et c sont des données différentes pour le calcul de la factorielle) à

9 Sans avoir à réécrire cette séquence, il suffit juste de lui faire appel.

9 Cette techniappelée modularisation facilite la programmation.

A retenir

¾ Définir le sous-programme.

Omar TALBI Version 1.0 2019-2020

¾ u sous-programme appeler par son nom

Fonctions

On adoptera la syntaxe suivante pour :

1- Définir une fonction

2- Faire Appel à la fonction

Important

Omar TALBI Version 1.0 2019-2020

Solution an LA

Solution en langage C

Omar TALBI Version 1.0 2019-2020

Procédure

En LA, on adoptera la syntaxe suivante pour :

1- Définir une procédure

2- Faire Appel à la procédure

Important

í>D^ušOEî