Université PARIS-SUD - Licence MPI - S1 1 Introduction à linformatique Chapitre 1: Algorithmes et Programmes

Université PARIS-SUD - Licence MPI - S1 1

Introduction à l’informatiqueIntroduction à l’informatique

Chapitre 1: Algorithmes et Programmes

Université PARIS-SUD - Licence MPI - S12

Algorithmes et ProgrammesAlgorithmes et Programmes

Vie d'un programme Algorithme Programmation : le langage Exécution et test des programmes


Cycle de vie d'un programme (d'un logiciel)Cycle de vie d'un programme (d'un logiciel) Conception - Modélisation

Analyse du problème Solution algorithmique

langage d'algorithmes Programmation

Programme langage de « haut niveau »

Compilation – Interprétation Exécution sur machine

langage machine de « bas niveau » assembleur et code machine

Mise au point Vérification par test pour corriger Evaluation du coût pour optimiser


Cycle de vie d'un programme (d'un logiciel)Cycle de vie d'un programme (d'un logiciel) Conception - Modélisation

Langage de description d'algorithme simplicité , précision indépendant de la programmation et de la machine Exemple : diagramme , pseudo C, ...

Programmation Exécution


Conception - Modélisation Programmation

Langage de programmation (langages « évolués ») syntaxe contraignante, différents styles d'abstraction indépendant de la machine

Types de langages impératifs : Fortran, Cobol, Pascal, C fonctionnels : Lisp, ML, Caml logiques : Prolog objets : C++, Java

Exécution

Cycle de vie d'un programme (d'un Cycle de vie d'un programme (d'un logiciel)logiciel)


Conception - Modélisation Programmation Exécution

Langage assembleur dépendant de la machine, du processeur Exemples : Assembleur pour PC (IA-32), PowerPC,

MIPS, SPARC, etc.

Cycle de vie d'un programme (d'un Cycle de vie d'un programme (d'un logiciel)logiciel)


Conception - Modélisation Analyse du problème

Un nombre N est pair si le reste de la division de N par 2 est nul

Solution algorithmique 1. calculer le reste R de la division de N par 2 2. si R est égal à 0 alors N est pair 3. sinon N n'est pas pair

L'entier N est-il pair ?L'entier N est-il pair ?


Programmation Programme C

main () {// début du programme principal

int nombreateste ; printf("Donner un nombre :") ; scanf("%d", & nombreateste) ; if ((nombreateste % 2) == 0) printf("%d est pair \n", nombreateste); else printf("%d n'est pas pair \n", nombreateste);} // fin du programme principal

L'entier N est-il pair ?L'entier N est-il pair ?


L'entier N est-il pair ?L'entier N est-il pair ? Compilation - Codage

9de3bfc0 21000000 a0142000 d2040000

90000000 80a24000 02800009 01000000

….

808a6001 02800003 01000000 90022001

load N modi 2 jzer P...halt

Assembleur Code machine


() Recette, règle, mécanisme, procédé, procédure, méthode,

(=) Description d'une procédure de calcul par une suite d'étapes de calcul, d'actions (plus ou moins) élémentaires.

Un algorithme n'est pas forcément destiné à décrire la solution d'un problème pour la programmation et l'informatique ... Un algorithme en cuisine s'appelle une recette Un algorithme en musique s'appelle une partition Un algorithme en tissage s'appelle un point

AlgorithmeAlgorithme


Peu de mécanismes de basePeu de mécanismes de base Faire A ; Faire B ; Faire C … en séquence a←10 affectation + - * / operations de math {Faire A ; Faire B };{Faire C ; Faire D} groupés Si (…) Alors {…} Sinon Tant que (…) Faire {…} Pour i allant de 0 jusqu’à 100 faire {…i…} f(a, b, c) Fonctions (appel et déclaration)

Comment est-ce possible que l’informatique tienne en si peu de mécanismes de base ?


Variables : codage des données Variables : codage des données Soit n1, n2, n3,…n17 les 17 notes d’un étudiant Soit r le nombre de redoublements (0 si aucun) Soit sma une variable qui vaut vrai si l’étudiant

suit des cours d’anglais facultatifs et faux sinon (n1+2*n2) / 3 sa moyenne de module m1 … Soit lps une liste de poursuite d’étude possible Pour chaque poursuite d’étude considérons les

conditions d’admission (m1>12) et le nb max… Soit d le désir de l’étudiant (d=1 il veut faire des

math, d=2 de la physique et d=3 de l’info.)


Infor…MatiqueInfor…Matique Infor comme information : il y a des données

stockées numériquement auxquelles l’ordinateur a accès TRES TRES vite

Matique comme Automatique : L’ordinateur traite automatiquement TRES TRES vite et sans jamais se tromper


Algorithme (historique)Algorithme (historique) Les premières formulations de règles précises pour la

résolution de certains types d'équations remontent aux Babyloniens (époque d'Hammurabi, (1800 avant J.C.).

Depuis l'antiquité : algorithmes sur les nombres. Exemple : l'algorithme d'Euclide qui permet de calculer le

p.g.c.d. de deux nombres entiers. Le mot algorithme est plus récent, il vient du nom d'un

mathématicien perse du IXe siècle: Muhammad ibn Musa al-Khowârizmî.

La signification du mot évolue au cours des temps : pratique de l'algèbre (d'Alembert, XVIIIe siècle) méthode et notation de toute espèce de calcul tout procédé de calcul systématique, voire automatique


Algorithme de la mousse au chocolat Algorithme de la mousse au chocolat (6 p)(6 p)

Ingrédients : 250g de chocolat, 125g de beurre, 6 œufs, 50 g de sucre,

café Etapes :

Si chocolat a dessert faire fondre le chocolat avec 2 cuillères d'eau

Sinon Faire tièdir le chocolat liquide au micro-onde

Ajouter le beurre, laisser refroidir puis ajouter les jaunes Ajouter le sucre et comme parfum un peu de café Battre les blancs jusqu’à former une neige uniforme Ajouter au mélange.

A partir des ingrédients (données en entrée), appliquer la recette (les étapes) va produire une mousse au chocolat (le résultat).

L’abus de mousse au chocolat est déconseilléL’abus de mousse au chocolat est déconseillé


Traitement différéTraitement différé Un programme ne peut pas être écrit au fur et a

mesure qu’il est exécuté C’est un humain qui doit écrire le programme

(les ordinateurs en sont incapables) C’est un ordinateur qui exécute le programme a

raison de plusieurs milliards d’instructions par seconde

Nécessité d’écrire un programme sans ambigüité que l’ordinateur puisse exécuter sans intervention humaine


InteractionInteraction L’ordinateur peut arrêter l’exécution du

programme pour demander des précisions a l’utilisateur qui n’est pas le programmeur

L’utilisateur peut avoir l’impression que le programme/ordinateur est intelligent mais c’est en fait l’intelligence du programmeur qui est perçue au travers de l’exécution du programme

Un humain munit du bon ordinateur/programme peut passer pour plus intelligent aux yeux de ses semblables


Algorithme : un peu de méthodologieAlgorithme : un peu de méthodologie identifier les données fournies / nécessaires

(données en entrée) identifier le résultat (données en sortie) déterminer les actions ou opérations

élémentaires spécifier l'enchaînement des actions

langage d'algorithmes = langage de description des données, des actions et des enchaînements


Langage de description d'algorithmesLangage de description d'algorithmes Algorithme titre

% commentaire Lexique : variables // entrée : variables // sortie

: variables // auxiliaire actions : noms des opérations début liste d'instructions fin


Calculer les intérêts d’un prêt bancaireCalculer les intérêts d’un prêt bancaire Analyse

ValF = (ValIni * (1+interet/100) )* (1+interet/100)… 30 fois Interet = 4% si valeur<10000 et 5% si >=10000

Algorithme InteretsBanquairesVariables %Calcul des interets qnnee qpres qnneeLexique : ValIni entier // Entrée

ValF entier //Auxiliaire

Action : +, *, /, lire ,ecrireDébut

Lire ValIni //Demander ValIni a l’utilisateurFaire 30 fois : Si ValF<10000 Alors ValF ← ValF *1.04 Sinon ValF ← ValF *1.05Ecrire “a la fin des 30 ans vous avez : “, ValF, “ euros”

Fin

CommentairesCommentaires


Calculer les intérêts d’un prêt bancaireCalculer les intérêts d’un prêt bancaire Algorithme InteretsBanquairesVariables

%Calcul du carré d'un entierLexique : ValIni entier // Entrée



Lire ValIni //Demander ValIni a l’utilisateurFaire 30 fois : Si ValF<10000 Alors ValF ← ValF *1.04 Sinon ValF ← ValF *1.05Ecrire “a la fin des 30 ans vous avez : “, ValF, “ euros”

Fin

InteractionsInteractions


Pour aller plus loin …Pour aller plus loin … Poursuite de l’analyse

Les valeurs intermédiaires permettraient à l’utilisateur de voir qu’au bout de x années il est a 9998,4 euros et qu’en ajoutant quelques euros a sa mise initiale il bénéficie du taux de 5% plus vite






Lire ValIni //Demander ValIni a l’utilisateurFaire 30 fois : Si ValF<10000 Alors ValF ← ValF *1.04 Sinon ValF ← ValF *1.05 Ecrire “nouvelle valeur :”,ValFEcrire “a la fin des 30 ans vous avez : “, ValF, “ euros”

Fin

Dans la boucle Faire mais Dans la boucle Faire mais en dehors du siAlorsSinonen dehors du siAlorsSinon


Pour aller plus loin …Pour aller plus loin … Poursuite de l’analyse

Mais comment afficher le nombre d’années en face de chaque valeur intermédiaire ?




ValF, A entier //Auxiliaire


Lire ValIni //Demander ValIni a l’utilisateurA ← 2008Faire 30 fois : Si ValF<10000 Alors ValF ← ValF *1.04 Sinon ValF ← ValF *1.05 A ← A+1 Ecrire “en “, A, “la nouvelle valeur est ”,ValF, “ euros“Ecrire “a la fin des 30 ans vous avez : “, ValF, “ euros”

Fin

Dans la boucle Faire mais Dans la boucle Faire mais en dehors du siAlorsSinnonen dehors du siAlorsSinnon


Variable (ICI)Variable (ICI) Une variable est le nom d'un «récipient» destiné à

contenir une valeur. Lorsque nous nous intéresserons un peu plus à l'ordinateur, le récipient sera une «zone» mémoire.

Le type d'une variable sert à préciser la nature des valeurs acceptables par le récipient. Un type est un nom pour un ensemble de valeurs. Exemple : A est une variable de type entier. La valeur de

(dans) A est un entier. La valeur de Carré ne peut être un caractère (‘a’, ‘b’, ‘c’…) ou un réel (2008,3)


Affectation par une valeurAffectation par une valeur L'affectation variable ← valeur est une instruction qui

permet de changer la valeur d'une variable. L'affectation modifie le contenu du récipient désigné par la variable. La valeur de la variable à gauche de ← est remplacée par la

valeur à droite de ←. Exemple : Carré ← 0 « se lit » le récipient Carré reçoit la

valeur 0. Avertissement

L'affectation est une instruction qui est dite «destructrice». L'ancienne valeur de la variable est détruite, écrasée, effacée

par la nouvelle valeur ! Carré ← N Copie de la valeur de N. La valeur de N (par

exemple 7) existe en double


Affectation par une expressionAffectation par une expression L'affectation variable ← expression est effectuée par :

1. évaluation de l'expression 2. placement du résultat dans le récipient désigné par la

variable à gauche. Attention

A droite de ←, dans l'expression, les variables sont abusivement utilisées pour désigner les valeurs qu'elles contiennent. Ceci est une convention.

Exemple : Carré ← Carré + N a pour effet de mettre le résultat de la somme de la valeur de Carré avec la valeur de N dans le récipient Carré.

La valeur de Carré évolue dans le temps Contrairement en math bien souvent L’ évolution n’est JAMAIS continu


Tester si N est un carré parfaitTester si N est un carré parfait Analyse

N est un carré parfait si il existe un entier J dont le carré vaut N. (16 en est un, 23 non !)

Algorithme Algorithme Test-Carré-Parfait Lexique :

N entier Réponse booléen Actions : + , * , , = Auxiliaire : I, J entier

(* voir page suivante *)


Début1. I←0

Répéter2. J←I*I3. I←I+14. jusqu’à J N5a. Si J = N 5b alors Reponse ← Vrai5c sinon Reponse ← Faux

FinsiFin

Tester si N est un carré parfaitTester si N est un carré parfait

Attention: Attention: toute la subtilité toute la subtilité est dans est dans


Algorithme = Abstraction de séquences de calculAlgorithme = Abstraction de séquences de calcul

Instruction Expression évaluée Valeur de i Valeur de J Valeur de réponse

1 0

2 I*I 0

3 I+1 1

4 J 7 ?

2 I*I 1

3 I+1 2

4 J 7 ?

2 I*I 4

3 I+1 3

4 J 7 ?

2 I*I 9

3 I+1 4

4 J 7 ?

5 J=N

5c faux Faux

Test du carré parfait (N=7)


Instruction conditionnelleInstruction conditionnelle Si « condition » alors faire liste d'instructions

sinon faire liste d'instructions

FINSI Exemple : l'instruction 5 de l'algorithme Test-Carré-

Parfait est une conditionnelle. Condition est une expression booléenne

Exemple : Reprenons l'exécution de Test-Carré-Parfait pour N=7. La première évaluation de la condition J 7 produit la

valeur booléenne «faux» donc les instructions 2. et 3. sont exécutées.


Algèbre de BooleAlgèbre de Boole Un ensemble = {0, 1} muni de l'ordre total (0 < 1) et

des opérations suivantes : Addition : x + y = max(x,y) Multiplication : x.y = min(x,y) Complémentation :

propriétés l'addition et la multiplication sont commutatives 0 est élément neutre de l'addition 1 est élément neutre de la multiplication l'addition est distributive sur la multiplication et vice versa. Propriété des compléments : 1 et . 0x x x x+ = =

0 si 1 et 1 si 0x x x x= = = =


Fonctions booléennes – tables de véritéFonctions booléennes – tables de véritéUne fonction booléenne f est une application de 2 dans cas n=1.

Il existe 4 fonctions booléennes de { 0, 1 } dans { 0, 1 } : l'identité, la complémentation et ...

cas n=2. Il existe 24 fonctions booléennes de { 0, 1 }2 dans { 0, 1}

x y f0 f1 f2 f3 f4 f5 … f9 … f13 f14 f15

0 0 0 0 0 0 0 0 1 1 1 1

0 1 0 0 0 0 1 1 0 1 1 1

1 0 0 0 1 1 0 0 0 0 1 1

1 1 0 1 0 1 0 1 1 1 0 1


Algèbre de Boole et LogiqueAlgèbre de Boole et Logique Utiliser faux et vrai (ou F et V) à la place de 0 et 1 Renommer l'addition, la multiplication et la

complémentation par ou, et et non respectivement appelée disjonction, conjonction et négation.

Attention au « OU » ≠ fromage ou dessert

x y ou et Non (x)

F F F F V

F V V F V

V F V F F

V V V V F


Condition et Expression booléenneCondition et Expression booléenne Expression booléenne élémentaire par l'exemple

(J < 7) est une expression booléenne élémentaire. J est de type entier, 7 est un entier et la comparaison < est un

opérateur de N x N dans { F, V }.

(Réponse) est une expression booléenne élémentaire. Réponse est de type booléen.

(Lettre = `a`) est une expression booléenne élémentaire si la variable Lettre est de type caractère.

Remarque Les mêmes symboles (=, <, etc.) sont utilisés pour la

comparaison d'entiers, de caractères, de booléens.


Condition et Expression booléenneCondition et Expression booléenne Expression booléenne élémentaire par l'exemple

(J < 7 et J > 4) est une expression booléenne. C'est la conjonction de deux expressions booléennes

élémentaires. Elle est évaluée à vraie si la valeur de la variable J

appartient à ]4,7[. Considérons les variables cv pour la couleur de ma

voiture, mv pour la marque et div pour l'immatriculation (département). Que signifie l'expression ci-dessous ?

(cv = blanc et mv = peugeot) ou ((cv = noir) et (div=75 ou div=92 ou div = 93 ou

div = 94) )


Algèbre de Boole (suite)Algèbre de Boole (suite) Théorème de De Morgan

non (a ou b) (non a) et (non b) non (a et b) (non a) ou (non b)

Exemple Quel est le contraire de “le prof porte un pantalon

bleu OU il porte un pull beige” ? Si un étudiant soutient une telle affirmation, par

quelle affirmation pouvait vous soutenir exactement l’inverse ? Le prof ne porte pas un pantalon bleu

ET Le prof ne porte pas un pull beige


Algorithmique / CAlgorithmique / C L’algorithmique sert a réfléchir a l’algorithme

Trouver les bonnes variables Imbriquer les boucles dans le bon sens Enchainer les si-alors sinon dans le bon ordre Etc.

Le langage C sert a laisser un programme formel Pour tester l’utilisation des variables, la syntaxe Tester le programme avec des valeurs concrètes Se convaincre de la justesse de l’algorithme Donner le code source de votre programme pour

convaincre vos utilisateurs (open source)


Langage de programmation CLangage de programmation C#include <stdio.h> //bibliothèque

main() { //entête const type nom = valeur ; // bloc déclaration

type1 nom1, nom2 ; type2 nom3 ; instruction; ... //bloc

d'instructions instruction;}


Syntaxe : symboles, mots, règlesSyntaxe : symboles, mots, règles symboles spéciaux

[ ] \{ } . , ; : # =< > - * / ( ) !

mots réservés if else int char float double while for switch

case, const etc.

règles syntaxiques point virgule après chaque instruction accolade ouvrante au début { et fermante } à la fin de

chaque fonction (y compris « main »), de chaque bloc d’instructions

La syntaxe d'un programme est définie par une grammaire.


Autres règlesAutres règles Contraintes imposées par le langage

Toute variable apparaissant dans le bloc d'instructions doit être déclarée.

Contraintes imposées par l'usage Tout programme doit être commenté ! Un commentaire est du texte encadré par des

symboles de début /* et de fin */ ou une ligne commençant par //

Ignoré lors des traitements du programme /* Tout l’algo repose sur la recherche du plus grand

nombre premier après le carré parfait */int i = 0; // sert d’indice dans la boucle


Bloc déclarationBloc déclarationtype nom-variable ; Syntaxe

nom-variable est un identificateur : les caractères sont les lettres (A..Z,a..z) et les chiffres 0..9 et le

soulignement (pas de caractères spéciaux, pas de blancs) mais ne commencent pas par un chiffre

ne commence pas par un chiffre minuscules et majuscules sont différentes fred≠Fred longueur maximum = 31 (plus de caractères sont tolérés, mais ils

sont ignorés)

Déclarer une variable sert à désigner un récipient par son nom spécifier le domaine des valeurs que peut «contenir » cette

variable


TypesTypes Généralités

Un type est un nom pour un ensemble de valeurs. Un type est muni d'opérateurs. Donc :

Déclarer une variable sert aussi à connaître les opérateurs applicables à (la valeur de) la variable

Avertissement Les compilateurs C ne peuvent détecter certaines erreurs de typage.

Exemple un caractère (lettre de l’alphabet, chiffres) sera

représenté par un entier de type char (8 bits) : la lettre ‘a’ sera représentée par l’entier 97 !

Une erreur flagrante de typage ( 4 * ‘a’) ne sera pas détectée !


Les types entiersLes types entiers

Pour manipuler les entiers, C propose 6 types (Table ci-dessous). D’autres existent.

Les opérations sur les entiers sont l’addition +, la soustraction -, la multiplication *, la division / et les comparaisons (==, !=, >; >=, etc.)

TYPE Intervalle Codage

unsigned char [0,255] 1 octet (= 8 bits)

char [-128,127] 1 octet

unsigned short [0, 65536] 2 octets

short [-32768, 32767] 2 octets

unsigned int [0, 4294967295] 4 octets

int [-2147483648, 2147483647] 4 octets


Les types réelsLes types réels Pour manipuler les réels, C propose 2 types (d’autres

existent) présentés dans la table ci-dessous Les opérateurs sur les réels sont l’addition +, la

soustraction -, la multiplication *, la division /, les comparaisons (==, !=, >, >=, etc.)

TYPE Intervalle Codage Chiffres significatifs

float [-2-150, -2128], 0,[+2-150, +2128]

4 octets 7 chiffres décimaux

double [-2-1075, -21024], 0,[+2-1075, +21024]

8 octets 15 chiffres décimaux


Type booléenType booléen


Type caractèreType caractère Le type caractère n’existe pas de manière

indépendante en C Les caractères sont représentés par des « char »

correspondant au codage ASCII des caractères alphanumériques (lettres et chiffres), typographiques (ponctuation), etc.

Ce sont en fait des nombres entre 0 et 255 avec une convention (ASCII ou UNICODE)

Les caractères sont entrés entre quotes ‘a’(==97), ‘b’(==98), ’0’(==48), ’A’(==65), etc.


Déclarations de constantesDéclarations de constantes const type nom-constante = valeur

nom-constante est un identificateur qui sert à nommer une valeur.

Une constante sert souvent à simplifier la lisibilité d'un programme.

Le nom donné à la valeur correspondant à l'utilisation de cette valeur dans un contexte particulier (ici le programme).

Exemples const float PI = 3.14159; // PI est la valeur 3.14159 const float euro 6.56; // euro est le réel 6.56 const int duo = 2; // duo est synonyme de 2

Avertissement Il est impossible de changer la valeur 2 : De la même manière il est impossible de toucher à la

constante duo dans le programme !


AffectationAffectationnom-variable = expression ; sémantique

seule la notation change par rapport au langage algorithmique i←i+1le type de l'expression à droite de = doit être identique au type de la variable

à gauche Exemples

I = 0 ;I = I + 1 ;res = (J = =I*I) ; // res = 1 ou res = 0

Attention : le compilateur C fait des conversions pour que la valeur affectée corresponde au type de la variable à gauche. Exemple :

int n; float x=15.4; n=x; // Les deux types sont différents printf("n=%d \n", n); // résultat affiché : n=15


Instructions d’entrée-sortieInstructions d’entrée-sortiescanf("FORMAT", &nom-variable);

Permet de saisir (lire) des données tapées au clavier FORMAT permet de spécifier le type de la variable lue. Par

exemple, "%d" pour un entier, "%f" pour un réel…( d = décimal, f = floating point )

L'exécution de l'instruction ci-dessus Attend que l'utilisateur tape une valeur au clavier Cette valeur est affectée à la variable (idem au pluriel) La variable doit avoir été declarée (avec le bon type) (const)

Exemple int I= 234 ; scanf ("%d",&I) ;

Si l'utilisateur tape 33, la valeur de la variable I est 33 après exécution des deux instructions.


Instructions d’entrée-sortieInstructions d’entrée-sortiescanf ("FORMATS", liste de variables); Exemple

scanf ("%d %d %d", &I, &J, &N)si l'utilisateur tape 33 44 22, la valeur de la variable I est 33, celle de J est 44 et celle de N est 22 après exécution.

Avertissement Si la valeur saisie n'est pas du type de la variable alors une erreur d'exécution se produit.Si la valeur n'est pas saisie, alors l'exécution du programme attend !


Instructions d’entrée-sortieInstructions d’entrée-sortieprintf ("FORMAT", expression) printf ("FORMATS", liste d'expressions) permet d'afficher des valeurs (résultats de calcul)à l'écran.Exemples float res = 2.2+1.05;

int I =1 ; //la valeur de I est 1printf("%d", I) ; //affichage de 1 à l'écranprintf("%d", 5+7) ; //affichage de 12 à l'écranprintf("valeur de I= %d", I) ; //affichage de valeur de I= 1

printf("pour I= %d res=%f", I, F) ; //affichage de pour I=1 res=3.25 printf ("FORMAT \n", expression) affiche le résultat de l'évaluation

de l'expression puis effectue un retour à la ligne (voir console)


Programmation en C du Test-Carré-ParfaitProgrammation en C du Test-Carré-Parfait


ConditionnelleConditionnelle


ConditionnelleConditionnelleif (condition) instruction1;if (condition) instruction1; else instruction2;if (…);; instruction1; EST TOUJOURS EXECUTE A CAUSE DU ;

Permet d'introduire des branchements d'instructions. L'exécution de l'instruction globale

évalue la condition si la condition est vraie, exécute l'instruction 1 sinon exécute l'instruction 2.

Exemple N = 5; I=2;if (N= =I*I) printf ("L'entier %d est un carre parfait", N);else printf("L'entier %d n'est pas un carre parfait", N);

Affichage à l'écran de L'entier 5 n'est pas un carre parfait


ConditionnelleConditionnelle

if (condition) bloc-instruction1 else bloc-instruction2

Un bloc d'instructions est une liste d'instructions encadrée par les mots clé { et }

Exemple N = 5 ;if (N % 2 = =0) printf("%d est pair", N);else {

N = N-1 ;printf ("%d est pair", N);

}

Affichage à l'écran : 4 est pair

% est le % est le reste de la reste de la division division entièreentière


Reste de la division entièreReste de la division entière 423%100 = 23 (ou 118%8 pages ;-)

Car lorsqu’in cherche à diviser 423 par 100 Il y a 4 blocs de 100 qui se divisent bien par 100 Il reste 23 qui vont faire des chiffres après la virgule

4 est le résultat de la division entière En C elle s’ecrit / (ex int a = 423/100;)

23 est est le reste de la division entière En C elle s’ecrit % (ex int b = 423%100;)

La division réelle s’écrit float c = 423.0f / 100; En base 10 les divisions et reste de division par

10, 100, 1000, etc. = facile! … mais par 9 ou 16


ConditionnelleConditionnelleswitch (expression) {

case expression-constante : bloc-instruction 1; break;case expression-constante : bloc-instruction 2; break; ...case expression-constante : bloc-instruction n; break; default : bloc-instruction; break;

} le cas default est facultatif. Pas de break signifie que les 2 cas sont traités ensemble L'instruction break provoque une sortie immédiate du

switch


ConditionnelleConditionnelle Exemple N=5switch (N%2) {

case 1 : printf ("%d est impair", N) ; break; case 0 : printf ("%d est pair", N) ; break; }

Exemple switch (C) {

case ‘0’ : case ‘2’ : case ‘4’ : case ‘6’ : case ‘8’ : printf("%d est le code d’un chiffre pair" , C); break;

case ‘1’ : case ‘3’ : case ‘5’ : case ‘7’ : case ‘9’ : printf("%d est le code d’un chiffre impair", C); break;

default : printf ("%d n’est pas le code d’un chiffre, c’est %c", C, C);}


ItérationItération


Itération : tant queItération : tant queTant que (expression)

Instructionsfin tant que

Attention Initialiser les variables testées dans l’expression Modifier les variables dans la boucle pour qu’elle s’arrête.

Exemple : calcul de factorielleLexique : N, Res entier;ecrire ("entrez N") ; lire (N);Res←1;Tant que (N>0)

Res←Res*N;N←N-1;

Fin tant que

Exécution pour N=3, N=0.


Itération : Répéter… jusqu’àItération : Répéter… jusqu’àRépéter

Instructionsjusqu’à (expression)

Attention Initialiser les variables testées dans l’expression avant le « répéter » Modifier les variables dans la boucle pour qu’elle s’arrête. On exécute des instructions avant de tester l’expression

Exemple : calcul de factorielleLexique : N, Res entier;ecrire ("entrez N") ; lire (N);Res←1;répéter

Res←Res*N;N←N-1;

jusqu’à (N 0);

Exécution pour N=3, N=0;


Itération : PourItération : PourPour i allant de borne_inf à borne sup (par pas de 1) faire instructionsFin pour

Exemple : calcul de factorielleLexique : N, Res, i entier;ecrire ("entrez N") ; lire (N);Res←1;Pour i allant de 2 à N faire

Res←Res*i;Fin pour

Exécution pour N=3, N=0;


ItérationItération Une écriture concise pour la répétition de blocs

d'instructions Il existe 2 sortes d'itération :

1. Le nombre de répétitions est fixe faire N fois en C : for

2. Le nombre de répétitions n'est pas fixe Il dépend des calculs effectués par les instructions

répétées si ... alors repartir en C : while ou do...while


Itération-whileItération-while Le nombre de répétitions n'est pas fixe

while (condition) bloc-instruction; condition est une expression booléenne

L'exécution de cette itération s'effectue par : 1. évaluation de la condition 2.

si la condition est vraie alors exécution du bloc-instruction et repartir (recommencer) en 1.

si la condition est fausse alors l'exécution est terminée.

Tant que la condition est vraie, le bloc d'instructions est exécuté.

A la sortie de la boucle, la condition est toujours fausse (… ne pas tester)


Itération - do...whileItération - do...whileLe nombre de répétitions n'est pas fixe

do liste-instruction while (condition);

L'exécution de cette itération s'effectue par :1.- exécution de la liste d'instructions

2.- évaluation de la condition

3.- si la condition est vraie alors repartir (recommencer) en 1. si la condition est fausse alors l'exécution est terminée.

Exécuter la liste d'instructions tant que la condition est vraie et toujours au moins une fois !!!


Itération - do...whileItération - do...whileExemple Main () {

scanf("%d", &N); Res = 1;do {

Res = Res * N ;N = N -1 ; // N est modifié

} while (N > 0) ; // N est testéprintf("%d \n", Res);

}

Simulation de l'exécution pour la saisie de 0 et pour la saisie de 5


Itération - forItération - forLe nombre de répétitions est fixe

for (expr1; expr2; expr3;) {bloc-instructions}

L'exécution de cette itération s'effectue par :1. initialiser le compteur d'itération par expr12. Tant que la condition expr2 est vraie, exécuter le bloc d'instructions3. Le compteur est modifié par expr3 à chaque itération

Utilisation typique (boucle pour du langage de description d’algorithme)for (i=0; i<N; i=i+1) {bloc-instructions}

Remarque générale d'utilisation Veiller à ce que l'intervalle [début, fin] soit identifiable avant l'itération.


Itération - forItération - forExemple

scanf("%d", &N) ; res = 1 ;for (I = 2; I <=N; I = I + 1)

res = res * I ;printf("%d \n", res);

Simulation de l'exécution (pour la saisie de 0 et pour la saisie de 5)

Simulation par while

scanf("%d", &N) ; res = 1 ; I = 2 ;while (I <= N)

{ res = res * I ; I = I + 1;}

printf("%d", res);


Itération - forItération - forExemple d'itération avec décrémentation

scanf("%d", &N) ; res = 1 ;for (I = N; I >=2; I = I - 1)

res = res * I ;printf ("%d", res);

Simulation de l'exécution pour la saisie de 0 et pour la saisie de 5

Remarque générale pour l'itération for, on peut mettre plusieurs autres variantes pour les

expressions expr1, expr2 et expr3.


Programmation de Test-Carré-ParfaitProgrammation de Test-Carré-Parfait Rappel de l'algorithme

Début1. I←0

Répéter2. J←I*I3. I←I+14. jusqu’à J N5a. Si J = N alors Reponse ← Vrai5b. Sinon Reponse ← Faux

FinsiFin


Programme Test-Carré-ParfaitProgramme Test-Carré-Parfait#include <stdio.h> ; // bibliothèque main() {

/* Test-Carré-Parfait : Ce programme vérifie si l'entier N est ou non un carré parfait */

int N, I, J ; // bloc déclaration printf ("Donnez l'entier à tester : ");scanf("%d", &N); // saisie de la valeur de N au clavier I = 0; // initialisation de I J = 0 ; while (J<N) {

I = I+1 ; J = I * I ;

}if (J == N)

printf("%d est un carré parfait", N);else

printf("%d n'est pas un carré parfait", N);}


Autres prog. de Test-Carré-ParfaitAutres prog. de Test-Carré-Parfaitmain(){ // Test-Carré-Parfait ...

I = 0; // initialisation de I do {J = I * I ; I = I+1 ;} while (J<N);

...

}main(){ // Test-Carré-Parfait ... // enlever J de la déclaration

I = -1; // initialisation de I do I = I+1 ; while (I * I <N);

...

}main(){ // Test-Carré-Parfait ...

for (I=0; I*I<N; I=I+1); // BOUCLE AUTO-SUFFISANTE ...

}


Imbrication de bouclesImbrication de boucles Supposons que la multiplication soit interdite ! main(){ // Test-Carré-Parfait

...I = 0; // initialisation de I do {

J = 0 ; for (k=1; k <= I; k = k + 1) { J = J + I; // calcul de J=I*I par additions successives }

I = I+1; // incrémentation de I }

while (J<N); ...

La boucle « for » est imbriquée dans la boucle « do...while ».


Tableaux mono-dimensionnelsTableaux mono-dimensionnels Définition

Le type tableau permet de représenter des fonctions à domaine fini

A chaque valeur d'un indice, le tableau associe une valeur ou élément de tableau.

Exemple On peut représenter les N entiers premiers par :

main (){ ...const int N = 10;int Tprem[N];


Tableaux mono-dimensionnelsTableaux mono-dimensionnels

Définitions sur un exemple A chaque case i, le tableau fait correspondre un nombre

premier Accessible par l'opération Tprem[i] On peut changer la valeur d'une case par Tprem[i]=valeur Le type des éléments (ici entier) peut être quelconque Attention : les compilateurs C ne vérifient pas que l’indice

est compris dans l’intervalle défini à la déclaration du tableau. S’il n’est pas dans cet intervalle, il y a généralement erreur à l’exécution.

0 1 2 3 4 5 6 7 8 9

1 11 2 3 19 5 13 17 23 7


Tableaux mono-dimensionnelsTableaux mono-dimensionnels Utilisation

Le programme Tableau est un exemple simple qui affiche sur l'écran tous les éléments du tableau des nombres premiers Tprem

main() { const int N = 10;int Tprem [N];Tprem[0] = 1;Tprem[1] = 2; … Tprem[9] = 2 ; // pas Tprem[10] !!! int i;for (i= 0; i < N; i = i +1)

printf("%d \n", Tprem[i]);}


Tableaux mono-dimensionnelsTableaux mono-dimensionnelsUtilisation (suite)

Le programme TabCar compte et affiche le nombre de 'a' dans le tableau Tcar

main(){ // programme TabCar const int N = 100;char Tcar [N];int i, Nba;Nba = 0;for (i= 0; i < N; i = i +1)

if (Tcar[i] == 'a') Nba = Nba + 1;

printf("le nombre de a est : %d", Nba);}


Tableaux mono-dimensionnelsTableaux mono-dimensionnels

Utilisation (suite) Le programme PremCar vérifie et affiche si 'a' est présent dans le

tableau Tcar

main(){ // programme PremCar

const int N = 100;char Tcar [N];int i ;

i = 0;while ((i < N) && (Tcar[i] != 'a')) i = i + 1;if (i == N) printf("a n'est pas dans le tableau ");else printf("a est dans le tableau à la pos %d " , i);}


Tableaux multi-dimensionnelsTableaux multi-dimensionnels Définition

A chaque valeur d'un couple d’indice, le tableau associe une valeur ou élément de tableau.

Exemple On peut représenter les N*M entiers par :

const int N = 3;const int M = 4;int Matrice[N] [M];


Tableaux multi-dimensionnelsTableaux multi-dimensionnels

Définitions sur un exemple A chaque case i,j le tableau fait correspondre un nombre

entier Accessible par l'opération Matrice[i][j]

i.e : grdnb = Matrice[1][6]; On peut changer la valeur d'une case par Matrice[i][j]=valeur Le type des éléments (ici entier) peut être quelconque

0 1 2 3 4 5 6 7 8 9

1 3 2 3 5 9 11 8 0 1

3 5 8 1 4 9 34 8 2 7

4 5 6 7 8 9 4 3 25 5

7 4 3 7 5 7 8 5 9 3

8 5 33 4 1 2 5 4 6 12

00

11

22

33

44


Boucles imbriquBoucles imbriquéées et tableaux 2Des et tableaux 2D Les boucles imbriquées permettent de parcourir un

tableau multi-dimensions.main () { const int N = 3; //Attention a ne pas se melanger les pinceaux const int M = 4; // entre les 2 dimensions !!!! int Matrice[N] [M]; NbZero/), for (i= 0; i < N; i = i +1) { for (j= 0; j < M; j = j +1) { if (Matrice[i][j] ==0)

NbZero = NbZero+1; } } printf("le nombre de 0 est : %d", NbZero);}


Boucles imbriquBoucles imbriquéées et tableaux 2Des et tableaux 2Dmain () { const int N = 7; const int M = 7; int Mat1[N] [M]; int Mat2[N-2] [M-2]; for (i= 1; i < N-1; i = i +1) { for (j= 1; j < M-1; j = j +1) { Mat2[i-1][j-1] =

(Mat1[i-1][j]+Mat1[i+1][j]+ Mat1[i][j-1]+Mat1[i][j+1])/4; } } for (i= 0; i < N-2; i = i +1) { for (j= 0; j < M-2; j = j +1) { printf("%d ", Mat2[i][j]); } printf( "\n");}

Que fait ce code ?Que fait ce code ?


Tableaux multi-dimensionnelsTableaux multi-dimensionnels Utilisation

Le programme Tableau2 est un exemple simple qui affiche sur l'écran tous les éléments du tableau des nombres Tprem

main() { const int N = 10;const int M = 10;int Matrice [N][M];Matrice [0][0] = 1;Matrice [1][0] = 2; … Matrice [9][0] = 2 ; // pas Tprem[10] !!! Matrice [1][9] = 2; … Matrice [9][9] = 5 ; // pas Tprem[10] !!! int i;for (i= 0; i < N; i = i +1) {

for (j= 0; j < M; j = j +1) { printf("%d ", Matrice [i][j]);

} printf("\n”); }}


Exemple d’analyseExemple d’analyse On souhaite remplir un tableaux des nombres

premiers entre 0 et 100 Comment on s’y prend ?


analyseanalyse On essaye de retourner le problème

Tous les nombres sont premiers sauf ceux qui ne le sont pas !!!

Je crée un tableau de 100 booléens tous à vrai (pour dire que les 100 premiers nombres sont premiers)

Je met a faux ce qui ne le sont pas Je met à faux les multiples de 2 Je met à faux les multiples de 3 …

Je fais une boucle entre 2 et 10 imbriquée avec une autre boucle entre 2 et 10 Je met à faux tous les indices résultat de multiplication


Et c’est tout ?Et c’est tout ? Je parcours le tableaux plein de vrai et de faux Quand je tombe sur un vrai je copie la valeur de l’indice

dans un tableau Je dois donc garder l’indice où écrire le nouveau nombre

premier J’initialise i à 1 J’incrémente i (i=i+1) à chaque vrai Je met TabPrem[i] = j si je suis en train de tester T[j]

L’analyse fait ressortir des étapes qu’on voudrait factoriser avec d’autres problèmes Calculer la table de multiplication Copier les indices d’un tableau de vrai/faux dans un autre

tableau


Généralités sur les fonctions Les fonctions permettent:

de scinder un programme en plusieurs parties, et de décrire le déroulement du programme principal de façon claire

de mettre en commun des ressources entre programmeurs

d’éviter des séquences d’instructions répétitives de spécialiser des séquences d’instructions grâce à

leurs paramètres de calculer des valeurs, et/ou d’agir sur des objets


AlgorithmiqueAlgorithmiqueaction NOM{ DESCRIPTION DE L’ACTION}Données : LES DONNES EN ENTRÉERésultats : LE OU LES DONNES RETOURNEES Début … INSTRUCTIONS (construisant la valeur des

données retournées) … Fin


ExempleExempleaction div{ les variables résultats q et r sont respectivement calculées

comme le quotient et le reste de la division entière }Données : a, b : entier;Résultats : q, r : entier; Début q ←0; tant que a≥b faire a ← a-b; q ← q+1; fin tant que r ← a; Fin

Appel : Appel : div (125, 37, x, y);div (125, 37, x, y);


AlgorithmiqueAlgorithmiquefonction NOM → type de retour

{ DESCRIPTION DE LA FONCTION}

Lexique : LES DONNES LOCALES

Début

…

INSTRUCTIONS

…

retourner variable;

Fin


ExempleExemplefonction puissance → entier{ calcul la puissance n d’un entier a donné }Lexique: res, i : entier;Début res ← 1; pour I allant de 1 a N faire res ← res*a; fin pour retourner res; Fin

Appel : Appel : x=puissance (125, 37);x=puissance (125, 37);


Particularités des fonctions en C Types de modules: les « fonctions » et

« procédures » ne sont pas distinguées Mode de transmission des arguments:

uniquement par valeur Variables globales: accessibles à toutes les

fonctions


Types de modules Les fonctions fournissent un résultat (valeur de retour),

calculé à partir des valeurs de ses paramètres, qui peut ensuite apparaître dans une expression.

Typiquement, les procédures des autres langages réalisent des actions, mais en pratique rien n’empêche les fonctions d’en réaliser également.

En C, il n’existe que la notion de fonction: la valeur de retour d’une fonction peut être ignorée (ex:

printf) une fonction peut ne retourner aucune valeur une fonction peut retourner une valeur non scalaire (ex:

structures) une fonction peut modifier (indirectement) les valeurs de

certains paramètres


Transmission des paramètres En C, la transmission des paramètres se fait uniquement

par valeur: les valeurs des paramètres passés lors de l’appel d’une

fonction sont copiées localement à la fonction, et les copies sont ensuite utilisées en lecture/écriture

toute modification des valeurs est perdue lorsque la fonction se termine

Il est néanmoins possible de modifier les paramètres d’une fonction grâce à la notion de pointeur (variable pointant en mémoire vers un objet d’un certain type): la fonction peut alors opérer en lecture/écriture sur l’objet

pointé par le pointeur les modifications sont alors effectuées sur l’objet d’origine,

et restent donc effectives après la fin de la fonction


Définition d’une fonction Syntaxe générale:

<type-de-retour> <nom>(<liste-paramètres>)<instructions>

Ex:/* définition d’une fonction « abs » retournant un

entier et prenant deux entiers comme paramètres */

int abs(int a, int b) {/* corps de la fonction */

if (a > b)

return (a – b);

return (b – a);

}


Paramètres d’une fonction Tout type d’objet peut être passé comme

paramètre d’une fonction: types de base (variantes de int, float, double, char) structures tableaux pointeurs

Les déclarations des paramètres, séparées par des virgules, associent un spécificateur de type à un déclarateur (nom de variable)

Un liste de paramètres vide est possible


L’instruction return Syntaxe:

return [expression]; Instruction de rupture de séquence:

évaluation de expression si elle est présente conversion dans le type de retour de la fonction si

nécessaire retour à la fonction appelante

Nombre d’occurrences dans une même fonction: plusieurs instructions return sont possibles l’absence d’instruction return provoque un retour à la

fonction appelante à la fin du bloc d’instructions de la fonction

Une fonction qui retourne une valeur doit nécessairement contenir au moins une instruction return.


Déclaration d’une fonction La déclaration d’une fonction est nécessaire pour que

le compilateur puisse ensuite gérer les appels qui lui sont faits.

La définition de fonction vaut déclaration (donc la redéclaration est permise), mais il est en général conseillé d’avoir : les déclarations de fonctions dans les fichiers entêtes (.h ) les définitions de fonctions dans les fichiers sources (.c )

La portée d’une déclaration de fonction: valable pour toute la partie du fichier source qui suit la

déclaration


Exemples de portée des déclarations de fonctions (1/2)

/* déclaration de maFonction */int maFonction(int val); int main() {

/* maFonction est accessible ici */}void autreFonction() {

/* maFonction est accessible ici */}

toto.ctoto.c


Exemples de portée des déclarations de fonctions (2/2)

int main() {/* maFonction n’est pas connue ici */

}

/* déclaration de maFonction */int maFonction(int val);void autreFonction() {

/* maFonction est accessible ici */}

toto.ctoto.c


Prototype de fonction Il est recommandé de déclarer une fonction sous forme de prototype qui spécifie: le type de la valeur de retour le nom de la fonction le type des paramètres de la fonction

Ex:int maFonction(int par1, float par2);/* maFonction retourne une valeur de type int, et prend deux

paramètres de type int et float */

Note: les identificateurs de paramètres sont optionnels dans une déclaration. Ils sont néanmoins recommandés pour rendre les déclarations plus faciles à interpréter.

Note: une fonction ne peut avoir qu’un seul prototype complet valide en C. En C++, la surdéfinition de fonction permet de définir une fonction par son nom et le type de ses arguments.


Passage de paramètres Les paramètres de fonction sont toujours passés par

valeur: si le paramètre est une expression, celle-ci est d’abord

évaluée la valeur du paramètre est si besoin convertie dans le type

précisé par le prototype de la fonction cette valeur est utilisée comme valeur initiale pour le

paramètre formel (celui de la définition de la fonction) toute modification du paramètre formel n’a aucune

incidence sur le paramètre effectif du contexte appelant Cas particuliers:

les tableaux ne sont pas passés par valeur (voir plus loin) les structures sont effectivement passées par valeur, ce qui

implique la recopie de l’ensemble des champs de la structure


Variables locales Les variables locales appartiennent au bloc dans

lequel elles sont déclarées (par exemple, le bloc de définition d’une fonction).

Les paramètres formels se comportent comme des variables locales.

Portée d’une variable locale: elle est visible depuis sa déclaration jusqu’à la fin

du bloc où elle est déclarée elle peut masquer des variables issues des contextes

englobants (cf. exemple suivant)


Exemple de portée des variables localesint a, b; /* variables globales */

void main() {

int b, c; /* variables locales à main */

/* ici b se réfère à la variable locale à main */

{

long a, c;

/* ici a et c se réfèrent aux variables locales au bloc */

/* b se réfère à la variable locale à main */

}

/* ici b et c se réfèrent aux variables locales à main */

/* a se réfère à la variable globale */

}


Qualité d'un programmeQualité d'un programme Le programme est-il une bonne traduction de

l'algorithme ? Le programme produit-il toujours la solution du

problème ? Le programme est-il performant ? Fait-il des actions

inutiles ? Utilise-t-il des variables sans en avoir réellement besoin ?

La validation, vérification, test de programme sont des tâches très complexes qui s'appliquent de façon beaucoup plus générale ... tout au long du cycle de vie du logiciel !


Test de programme - Trouver les fautesTest de programme - Trouver les fautes Test statique (lecture attentive du texte du

programme) le type des variables usage des variables

Test dynamique (exécution du programme)

1. choisir un jeu de tests (les entrées à tester)– test structurel (texte et structure du programme)– test fonctionnel (spécification, algorithme)– test aléatoire ou statistique

2. traitement/exécution du jeu de tests

3. analyse (dépouillement) des résultats du jeu de tests


Test structurel - Trouver les fautes Test structurel - Trouver les fautes Impossible d'essayer toutes les valeurs possibles en entrée !

Un jeu de test est un ensemble représentatif de valeurs d'entrées permettant de générer tous les types d'exécution du programme : de couvrir toutes les instructions et enchaînements d'instructions

Mini-exemple (1) scanf("%d", &I);(2) if (I <= 10) (3) bloc1 ;

else (4) bloc2 ;

- séquence 1.2.3 valeurs test de I : -435 , 10- séquence 1.2.4 valeurs test de I : 832Avertissement 0 est un entier particulier, mais ici ce n'est pas une valeur de test

plus intéressante que -435 !


Un exemple plus élaboréUn exemple plus élaboré(1) scanf("%d", &I); scanf("%d", &J); K= 0; signe = 1;(2) if (I < 0) {(3) signe = -1 ; (4) I = - I;(5)} (6) if (J < 0) { (7) signe = -signe ; (8 ) J = - J;(9) } (10) while (I >= J) {(11) I = I - J ; (12) K = K+1;(13)} (14) K = signe * K; printf("%d", K) ;


Un exemple plus élaboréUn exemple plus élaboré jeu de tests

séquence 1.2.3.4.5.6.7.8 valeurs test : ... séquence 1.2.4.6.8 valeurs test : ... séquence 1.2.3.4.6.8 valeurs test : ... séquence 1.2.4.5.6.8 valeurs test : ...

... ... séquence 1.2.4.6.7.6.8 valeurs test : ... séquence 1.2.3.4.5.6.7.6.8 valeurs test : ...

... ...


Test des conditionsTest des conditions(1) if ( (I==0) || (I==36 ))

(2) bloc1 else

(3) bloc2

Jeu de tests séquence 1.2 valeurs test de I : 0 Ne pas négliger la valeur test 36 pour I afin que le bloc1 soit

testé pour les deux valeurs 0 et 36 qui rendent la condition vraie.

Règle générale Générer les tests qui permettent d'explorer toute la table de

vérité d'une expression booléenne à partir des conditions élémentaires.


Complexité et coûts des algorithmesComplexité et coûts des algorithmes Un problème peut avoir une solution mais pas de

solution algorithmique (on ne sait pas construire la solution).

Exemple (problème de l'arrêt) : Considérons la fonction booléenne à 2 arguments. Le

premier argument est un programme C. Le deuxième argument est une entrée pour ce programme.

Cette fonction vaut vraie si le programme s'arrête pour l'entrée donnée et faux sinon.

Il est impossible d'écrire un algorithme (et un programme C) qui réalise cette fonction.


Complexité et coûts des algorithmesComplexité et coûts des algorithmes Un problème peut avoir une solution

algorithmique mais cet algorithme peut ne pas être raisonnable parce qu'il effectue un nombre très grand d'opérations.

Exemple (programme de jeux): Jeu d'échec. A chaque étape, il existe un nombre

fini de coups possibles. Donc il est possible d'explorer la suite du jeu pour chaque coup. Mais il faut examiner de l'ordre de 1019 coups pour décider de chaque déplacement.


Coût en temps d'un algorithmeCoût en temps d'un algorithme unité de mesure : opération élémentaire

identifier les opérations élémentaires

calcul du coût cas le pire = compter le nombre maximal

d'opérations élémentaires effectuées par une exécution (la pire)

moyenne = considérer toutes les exécutions possibles, pour chacune compter le nombre ...


Algorithme d'EuclideAlgorithme d'EuclideAlgorithme PGCD-1 //Calcul du pgcd de i et jLexique I, J : entier // Entrées

P : entier // Sortiedébut

tant que I ≠ J fairesi I > J alors

I ← I - J sinon J ← J - I;

P ← I; finNombre d'itérations ?


Algorithme d'EuclideAlgorithme d'Euclide

Algorithme PGCD-2 //Calcul du pgcd de i et j Entrée I, J : entier Sortie P : entier Auxiliaire K entier

débuttant que J > 0 faire

K ← I mod J;I ←J ; J ← K ;

P ← I; fin Nombre d'itérations ?


ConclusionsConclusions L’algorithmique repose sur peu de fondements

Les combinaisons sont infinis L’analyse du problème est primordiale Les types de données multiplient les possibilités de

façon exponentielle ! L’algorithmique peut rarement être traitée sous

l’angle du formalisme Bug légers, bug sévères, Optimisations L’analyse laisse souvent la place à des imprécisions Les besoins évoluent souvent en même temps que

l’écriture

Documents

Université PARIS-SUD - Licence MPI - S1 1 Introduction à linformatique Chapitre 1: Algorithmes et Programmes