Algorithmique et structure de données 2

We have included 957 exercises and 158 problems Each section ends with exer-cises, and each chapter ends with problems The exercises are generally short ques-tions that test basic mastery of the material Some are simple self-check thought exercises, whereas others are more substantial and are suitable as assigned home-work

Parcours de graphes - miashs-wwwu-gafr

Algorithmique - 3ème édition Thomas H Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein Cours avec 957 exercices et 158 problèmes – Dunod juin 2010 Heike Ripphausen -Lipa & Jean-Michel Adam 27

Algorithmique et structure de données 2

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Broché, Dunod, 2010 Rémy Malgouyres, Rita Zrour et Fabien Feschet Inititiation à l’algorithmique et à la programmation en C : cours avec 129 exercices corrigés 2ième Edition Dunod, Paris, 2011

Calcul de coût d’algorithme - POLARIS

[1]Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Dunod, 3e édition edition, 6 2010 [2]Ronald Graham, Donald E Knuth, and Oren Patashnik Mathématiques concrètes International Thomson publishing France, 2e éd edition, 1998

III - Programme détaillé par matière des semestres (1 fiche

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Broché, Dunod, 2010 Rémy Malgouyres, Rita Zrour et Fabien Feschet Iitiatio v à l’algoithiue et à la p og a u uatio e v C : cours avec 129 exercices corrigés 2ième Edition Dunod, Paris, 2011

Canevas d’aedeet - univ-batna2dz

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Broché, Dunod, 2010 Rémy Malgouyres, Rita Zrour et Fabien Feschet Iitiatioàl’algoithiueetàlapogaatioe C : cours avec 129 exercices corrigés 2ième Edition Dunod, Paris, 2011 ISBN : 978-2-10-055703-5

[eBooks] Biochimie Générale 11e édition: Cours Et Questions

Biochimie générale 11e édition: Cours et questions de révision By Jacques-Henry Weil Read Online Share This Previous Post Next Post ‹‹ Newer Post Older Post ›› Meilleur Livre Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes Livre Gratuit Ebook Algorithmique - 3ème édition - Cours avec 957 exercices

[PDF] séquence presse cycle 3

[PDF] algorithmique et programmation exercices corrigés pdf

[PDF] séquence sur la presse

[PDF] séquence 4ème français

[PDF] telecharger livre algorithme gratuit

[PDF] poésie sur l'école

[PDF] poesie ecole maurice careme

[PDF] poème sur l'école d'autrefois

[PDF] poème sur l'école collège

[PDF] poésie école primaire cycle 2

[PDF] poésie école ce2

[PDF] dit de la force de l'amour analyse

[PDF] poèmes engagés

[PDF] vivaldi ete 3eme mouvement

[PDF] vivaldi les 4 saisons l'automne

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 valeur Î Une procédure contrairement à une fonction nas pas de type.

ÎÎ Donc, syntaxique et sémantique de lappel dune procédure se résume uniquement à :

(liste de paramètres effectifs) ;

A retenir

¾ e fonction ou dune procédure, le

Omar TALBI Version 1.0 2019-2020

3. Les variables locales et les variables globales

Structure de Bloc

¾ Présentation

Chaque programme (algorithme) est organisé comme un ensemble de blocs imbriqués.

La structure dun bloc est la suivante :

(algorithme ou fonction/procedure)

(Déclarations de constantes, de type, de variables, de procédures et de fonctions)

Exemples

Algorithme A

63%
'pEXW^%` )LQ^%` 63&
'pEXW^&` )LQ^&` 63'
'pEXW^'` )LQ^'`

Début {A}

Fin {A}.

Algorithme A

63'
'pEXW^'` )LQ^'` 63&
'pEXW^&` )LQ^&` 'pEXW^%` )LQ^%` 63%
'pEXW^$` )LQ^$` 63(
63)
'pEXW^)` )LQ^)` 'pEXW^(` )LQ^(`

Omar TALBI Version 1.0 2019-2020

Cas du langage C

Les fonctions en C sont définies à l'aide de blocs d'instructions. Un bloc d'instructions est encadré d'accolades

et composé de deux parties :

Blocs d'instructions en C

Remarque

On peut avoir en langage C, un bloc d'instructions d'une commande if, while ou for qui peut contenir des

déclarations locales de variables et même de fonctions.

Exemple

La variable I est déclarée à l'intérieur d'un bloc conditionnel. Si la condition (N>0) n'est pas remplie, I n'est

pas défini. A la fin du bloc conditionnel, I disparaît. if (N>0) int I; for (I=0; IVariables locales et variables globales

Règles à retenir

1. Toute variable, avant son utilisation dans un sous-programme, doit être déclarée dans ce sous-

programme ou " ailleurs1 ».

2. Les variables déclarées dans un bloc d'instructions sont uniquement visibles à l'intérieur de ce bloc.

On dit que ce sont des variables locales à ce bloc.

3. Une variable non déclarée dans un sous-programme peut y être utilisée si elle est déclarée dans un

bloc englobant de variables sont appelées des variables globales pour les blocs englobés.

4. Si une variable est déclarée dans les blocs de niveau différents, la déclaration locale est prioritaire

par rapport à la déclaration globale.

1 Bloc englobant de n[importe quel niveau

Omar TALBI Version 1.0 2019-2020

4. Le passage des paramètres

Les paramètres

9 Les paramètres fournissent un mécanisme de remplacement qui permet de répéter un sous-

programme avec des arguments différents2.

9 Les paramètres de e procédure/fonction sont appelés paramètres formels3.

9 .

9 Les paramètres appel de procédure/fonction sont appelés les paramètres effectifs ou réels4.

9 Il existe une correspondance positionnelle et une égalité en nombre entre les paramètres effectifs et

les paramètres formels.

9 Le type de chaque paramètre doit être précisé dans la définition du sous-programme.

-programme

Les paramètres formels sont de deux (02) types

Exemple: procedure somme(a:reel; var b:entier) ;

Transfert par valeur

1. Au du sous-programme, le paramètre effectif correspondant est calculé.

2. La valeur de ce paramètre est passée au sous-programme et devient la valeur initiale du paramètre

formel correspondant qui joue

[PDF] Algorithmique et structure de données 2

Introduction to Algorithms, Third Edition

Parcours de graphes - miashs-wwwu-gafr