Algorithmes conditionnels - Licence 1 MASS Introduction à

Algorithmes conditionnelsLicence 1 MASS

Introduction à Java et à l'algorithmique

Sébastien [email protected]

www.i3s.unice.fr/∼verel

Équipe ScoBi - Université de Nice Sophia-Antipolis

30 janvier 2012

Variables et a�ectationsLogique booléenne

Schéma conditionnel

Votre travail ?

Combien d'étagères sont consacrées à la programmation enJAVA à la BU ?

14 ?

Choisir un livre qui vous semble en rapport avec cetenseignement

en java, en algorithmique ?

Trouver au moins un site web en rapport avec l'enseignement

envoyez moi vos propositions par courriel que je mette sur lesite

Installer Processing sur votre ordinateur si vous en avez un

Avoir travailler le cours et TP précédents !

Sébastien Verel Algorithmes conditionnels



Objectifs de la séance 2

1 Ecrire un algorithme avec des a�ectations

2 Ecrire un algorithme qui échange la valeur de deux variables

3 Savoir utilisés les entrées de la souris avec Processing

4 Ecrire un algorithme avec des tests simples

5 Ecrire un algorithme avec un test multiple

6 Ecrire des programmes java avec des tests simples ou multiples

Question principale du jour :

Comment écrire des algorithmes qui prennent en compte dessituations di�érentes ?




Plan

1 Variables et a�ectations

2 Logique booléenne

3 Schéma conditionneltests simplesTests multiples




Utilité des variables

Lors d'un calcul, pendant le traitement de données,quasiment toujours nécessaire de stocker certaines valeursprovisoirement

Des exemples ?

Crible d'Erastothène : nombres rayés ou non

Euclide : nombres a et b du pgcd

..., etc, ...




Utilité des variables

Pour stocker cette information, on emploie des variables

12

A

remarque : L'étiquette est traduite en machine par une adressebinaire (0010010001000101)




Type des variables

Ces variables peuvent être de types di�érents :

nombre entier : int

nombre réel (approché) : �oat, double

caractères : char

chaîne de caractères : String

booléen (dont la valeur est VRAI ou FAUX) : boolean

...

Type : considéré comme un ensemble regroupant des valeurs auquels'applique certaines méthodes spéci�ques.




Expression

Expression

Ensemble de valeurs, reliées par des opérateurs binaires, équivalentà une seule valeur.

Toute expression a un type.




Calcul de types

De quel type sont les expressions suivantes ?

5

int

16.3

�oat

16.0

�oat

-3

int




Calcul de types

De quel type sont les expressions suivantes ?

5 + 12

int

18 / 3

int

15 − 5.3

�oat

5.4 % 2

�oat




Déclaration de variable en java

type nomDeLaVariable ;

Exemples :

int x ;

float a, b;

char premierLettre ;

int sumTotal ;

Toute variable utilisée doit être déclarée

Convention d'écriture en java :première lettre d'une variable est en minuscule et les "mots"suivants commencent par une majuscule.




Arithmétique des nombres �ottants

Combien d'entiers peut-on coder sur 4 octets ?

232 positifs ou 231 signés

Dans un ordinateur, tout est de taille �nie etles �ottants sont codés sur 4 octets.

Quelle est en la conséquence ?

Précision des �ottants




A�ectation

Attribuer à une variable une valeur.

notation en pseudo-code :

var ← expr

A

12 12

A

en java :

var = expr




Exemples en pseudo-code

1. A← 3

1. A← 32. B ← A

1. A← 32. B ← 53. A← B

4. B ← A

1. A← 32. B ← 53. tmp ← A

3. A← B

4. B ← tmp

(ce dernier est à connaitre !)




Exemples en java

int a = 5 ;

int b = a + 3;

int a = 5 ;

int b = a + 3;

a = a + 1;




Dessin en Processing

Il existe 2 méthodes (fonctions) par défaut en Processing :

setup : exécutée une seule fois, le code n'est exécutée qu'uneseule fois

draw : exécutée tous les rafaichissements d'écran (par défaut50 fois par seconde),le code est exécuté f = 50 fois par secondeRemarque : Le paramètre f peut être modi�ée à l'aide de laméthode frameRate

Exemples : Toujours et Point




Souris en Processing

Il est facile de connaitre la position du pointeur de la souris avecProcessing

2 variables de type int contiennent la position relativement auxdimensions de l'écran :

mouseX : abscisse

mouseY : ordonnée

Exemple : Mouse




George Boole

Mathématicien et logicien anglais (1815 - 1864)

but

Traduire des idées et des concepts en équations,leur appliquer des lois (des transformations) ettraduire inversement l'équation en termes de concepts et d'idées.

Il crée une algèbre binaire :

qui n'accepte que deux valeurs numériques 0 et 1 (faux, vrai),

dé�nie dans un ensemble E muni de deux lois de compositionsinterne (et, ou)

satisfaisant un certain nombre de propriétés (associativité,distributivité).

−→ algèbre de Boole




Notations

Il existe plusieurs types de notations :

Vrai ←→ V ←→ 1

Faux ←→ F ←→ 0

NON ←→ eET ←→ ∧OU ←→ ∨ (attention inclusif !)

IMPLICATION ←→ ⇒EQUIVALENT ←→ ⇔

XOR ←→ ⊕ (ou exclusif : fromage ou dessert)




Dé�nitions

Littéral

variable dont la valeur de vérité est soit VRAI soit FAUX.

Proposition

Enoncé auquel est associé une valeur de vérité (VRAI ou FAUX)

Tautologie

Proposition qui est toujours VRAI quelque soit les valeurs de véritéde ces littéraux




Exemples

a OU b

(a OU b) XOR c

a ET a

a OU VRAI

b OU (NON b)

NON( b OU a )

(a ET NON b) OU (b ET NON a)




Tables de vérité

ET Vrai Faux

Vrai

Faux

OU Vrai Faux

Vrai

Faux

XOR Vrai Faux

Vrai

Faux

⇒ Vrai Faux

Vrai

Faux




Tables de vérité

ET Vrai Faux

Vrai Vrai Faux

Faux Faux Faux

OU Vrai Faux

Vrai Vrai Vrai

Faux Vrai Faux

XOR Vrai Faux

Vrai Faux Vrai

Faux Vrai Faux

⇒ Vrai Faux

Vrai Vrai Faux

Faux Vrai Vrai




Zoom sur l'implication

p q ⇒Vrai Vrai Vrai

Vrai Faux Faux

Faux Vrai Vrai

Faux Faux Vrai

A = "je plonge dans la piscine"B = "je suis mouillé"

"SI je plonge dans la piscineALORS je suis mouillé"est un théorème VRAI.

A⇒ B

Lorsque A est VRAI, la conditionest réalisée, donc B est VRAI.

A peut aussi être FAUX et Brestant VRAI.

Peut-on en déduire que lethéorème devient FAUX dans cecas ?




Zoom sur l'implication

L'implication est vraie sil'hypothèse est fausse.

p q ⇒Vrai Vrai Vrai

Vrai Faux Faux

Faux Vrai Vrai

Faux Faux Vrai

Lorqu'un théorème p ⇒ q estvrai,mais que l'on a pas l'hypothèse,alors on ne peut rien en déduiresur q.

Pierre Weis et Xavier Leroy

�on ne peut rien déduire d'unthéorème dont l'hypothèse n'estpas véri�ée��un théorème reste vrai mêmequand il ne s'applique pas�




Tables de vérité

Un connecteur logique booléen est dé�ni par une table de vérité etréciproquement.

Il existe 16 connecteurs logiques binaires (pourquoi ?).

Vrai Faux

Vrai ? ?

Faux ? ?

D'où 2× 2× 2× 2 = 16 connecteurs logiques binaires.




Logiquement équivalent


F est logiquement équivalent à G si et seulement si F ⇔ G est unetautologie.


F est logiquement équivalent à G si et seulement si F et G ont lamême table de vérité.




Exemple

a b a ET NON b b ET NON a (a∧eb) ∨ (b∧ea)Vrai Vrai

Faux Vrai

Vrai Faux

Faux Faux




Exemple

a b a ET NON b b ET NON (a∧eb) ∨ (b∧ea)Vrai Vrai Faux Faux Faux

Faux Vrai Faux Vrai Vrai

Vrai Faux Vrai Faux Vrai

Faux Faux Faux Faux Faux

( (a ET NON b) OU (b ET NON a) )logiquement équivalent à(a XOR b)




Propriétés algébriques

Associativité :p ∨ (q ∨ r)⇔ (p ∨ q) ∨ r

p ∧ (q ∧ r)⇔ (p ∧ q) ∧ r

Commmutativité :p ∨ q ⇔ q ∨ p

p ∧ q ⇔ q ∧ p

Distributivité :p ∨ (q ∧ r)⇔ (p ∨ q) ∧ (p ∨ r)p ∧ (q ∨ r)⇔ (p ∧ q) ∨ (p ∧ r)Loi de De Morgan :e(p ∨ q)⇔eq∧epe(p ∧ q)⇔eq∨epContraposée : (p ⇒ q)⇔ (eq ⇒ep)(p ⇒ q)⇔ (ep ∨ q)Preuve par l'absurde : eep ⇒ p




Une application en biologie

C (x) est VRAIE lorsque x est une celluleV (x) est VRAIE lorsque x est un virus

I (x , y) est VRAIE lorsque x est infecté par y .R(x , y) est VRAIE lorsque x a reconnu y

Toutes les cellules infectées par un virus ne le reconnaissent pas

∀x∃y , (C (x) ∧ V (y) ∧ I (x , y))⇒eR(x , y)

Il n'existe pas de virus qui peuvent infecter toutes les cellules

6 ∃y , V (y)⇒ (∀x C (x) ∧ I (x , y))

−→ technique de �model checking� : véri�cation de la formulelogique par parcours astucieux des états possibles




tests simplesTests multiples

Quand utiliser un test ?

"SI j'ai tes clés ALORS je vais pouvoir rentrer tout seul chez toi."

"SI la voie rapide est bouchée ALORS je prends la prom."

"SI il y a de la neige ALORS je ne viens pas SINON je passe teprendre."

"SI b 6= 0 ALORS calculer a

bSINON la division est impossible."

test

Exécution d'un morceaux d'algorithme selon la situation





Tests simples

si booléen alors

morceaux d'algo 1

�n si

si booléen alors

morceaux d'algo 1

sinon

morceaux d'algo 2

�n si

booléen est une expression dont la valeur est soit Vrai soit Faux

Cette expression peut être :

une variable booléenne

une condition

une suite �nie de booléens relier par des connecteurs logiquesbinaires





Tests simplesen Java

if (boolean) {

morceaux de prog 1

}

if (boolean) {

morceaux de prog 1

} else {

morceaux de prog 2

}

'Boolean' est une expression qui peut être :

true : dans ce cas le morceau de programme 1 s'exécute

false : dans ce cas le morceau de programme 2 s'exécute





Bloc en java

if (a < 0) {

println("un");

println("nombre");

println("négatif");

}

if (a < 0)

println("negatif");

else

println("positif");

Les accolades servent à créerun bloc d'instructions (=suite d'instructions)

Lorsqu'il y a une seuleinstruction, on peut omettreles accolades.

Remarque : décalage et alignement des instructions d'un mêmebloc (indentation) pour éviter les erreurs classiques d'accolades





Conditions

T < 100

Une condition est composée de trois éléments :

une expression ayant une valeur dans un ensemble ordonné

un opérateur de comparaison sur cet ensemble

une expression ayant une valeur dans le même ensemble

Les opérateurs de comparaison sont : =, 6=, <, >, ≤, ≥, etc.

Les ensembles ordonnées peuvent être par exemple les nombresentiers, les nombres réels, les mots,...

Attention ! 60 < T < 100 n'est pas une condition.





Opérateur binaire logique en java

Les opérateurs de comparaison :

pseudo-code java

= ==6= ! =< <> >≤ <=≥ >=

Les connecteurs logiques :

pseudo-code java

AND &&OR ||NOT !





Tests simplesExemple

Algorithme valeurAbsolue(x : réel) : réeldébut

si x < 0 alors

écrire(−x)sinon

écrire(x)�n si

�n





Tests simplesExemple

Algorithme comparaison(a, b : entier) : riendébut

si a < b alors

écrire(�a est strictement plus petit que b�)sinon

écrire(�b est plus petit que a�)�n si

�n





Tests simplesExemple java

int a = 5;

int b = 12;

if (a < b) {

print("a est strictement plus petit que b") ;

} else {

print("b est plus petit que a") ;

}

a est strictement plus petit que b





Une équivalence

Algorithme test1(x : réel) :booléen

début

si x ≥ 10 alors

écrire(Vrai)sinon

écrire(Faux)�n si

�n

Algorithme test2(x : réel) :booléen

début

écrire(x ≥ 10)�n

Les deux algorithmes test1 et test2 sont strictement équivalents.Puisqu'ils produisent les mêmes résultats pour les mêmes données,pourtant l'un est plus court à écrire que l'autre.





Tests multiples

Test multiples imbriqués

si booléen1 alors

partie a

sinon

si booléen2 alors

partie b

sinon

partie c

�n si

�n si

lorsque booléen1 est vrai, lapartie a s'exécute (quelquesoit la valeur de booléen2)

lorsque booléen1 est faux etque booléen2 est vrai, lapartie b s'exécute

lorsque booléen1 est faux etque booléen2 est faux, lapartie c s'exécute





Tests multiples

Attention : ce n'est pas équivalent à la succession de 2 tests simples

si booléen1 alors

partie a

�n si

si booléen2 alors

partie b

sinon

partie c

�n si

lorsque booléen1 est vrai, lapartie a s'exécute

Par contre la partie b

s'exécute seulement lorsquebooléen2 est vrai (quelquesoit la valeur de booléen1)





Tests multiples / imbriquésExemple

Algorithme degreDeCorpulence(T : réel, m : réel) :début

i ← m/T2

si i < 20 alorsécrire( "poids inférieur à la normale")

sinonsi i < 25 alors

écrire( "poids normal")sinon

si i < 30 alorsécrire( "surcharge pondérale")

sinonsi i < 40 alors

écrire( "adiposité")sinon

écrire( "obésité"")�n si

�n si�n si

�n si�n





Tests multiplesExemple

Algorithme test(x : réel) :début

si 0 ≤ x alorsécrire( "le nombre est positif")si i ≤ 10 alors

écrire( "le nombre est compris entre 0 et 10.")sinon

si i ≤ 15 alorsécrire( "le nombre est compris entre 10 et 15.")

sinonsi i ≤ 20 alors

écrire( "le nombre est compris entre 15 et 20.")sinon

écrire( "le nombre est strictement supérieur à 20.")�n si

�n si�n si

sinonécrire( "le nombre est strictement négatif")

�n si�n





Connecteurs logiquesExemple

Algorithme ordonner ?(a,b,c : réel) : booléendébut

si a ≤ b ET b ≤ c alors

écrire(Vrai)sinon

écrire(Faux)�n si

�n





Connecteurs logiquesExemple en java

int a, b, c;

a = 10;

b = 3;

c = 5;

if ((a <= b) && (b <= c))

println(true);

else

println(false);





EquivalenceExemple en java

int a, b, c;

a = 10;

b = 3;

c = 5;

println((a <= b) && (b <= c));





Tests multiplesExercice

Ecrire en java le programme suivant :début

rep : entierrep ← 2si rep = 1 alors

écrire("Vous avez sélectionné le premier choix")si rep = 2 alors

écrire("Vous avez sélectionné le deuxième choix")sinon

si rep = 3 alorsécrire("Vous avez sélectionné le troisième choix")

sinonécrire("Votre choix est inconnu")

�n si�n si

�n si�n





Traduction en java

int x = 2 ;

if (x == 1)

println("Vous avez sélectionné le premier choix");

else

if (x == 2)

println("Vous avez sélectionné le deuxième choix");

else

if (x == 3)

println("Vous avez sélectionné le troisième choix");

else

println("Votre choix est inconnu.");





Equivalence avec switch

int x = 2 ;

switch (x) {

case 1 : println("Vous avez sélectionné le premier choix");

break;

case 2 : println("Vous avez sélectionné le deuxième choix");

break;

case 3 : println("Vous avez sélectionné le troisième choix");

break;

default :

println("Votre choix est inconnu.");

}





Equivalence avec switch

instruction porte sur une variable de type byte, short, char ouint.

Lorsque la variable a la valeur indiquée après case :

exécution à partir des " :"

jusqu'à l'instruction "break" qui permet la reprise d'exécution

après le bloc

voir aussi : http://java.sun.com/docs/books/tutorial/java/nutsandbolts/switch.html


http://java.sun.com/docs/books/tutorial/java/nutsandbolts/switch.html

http://java.sun.com/docs/books/tutorial/java/nutsandbolts/switch.html




Arbres de décision

Schema qui représente un algorithme avec des tests imbriqués

Base des systèmes experts : applications médicales, conseils,�ltrage, ...

Ces arbres s'établissent à l'aide d'algorithmes d'apprentissage





Exercice

a - Rappeler les deux lois De Morgan.

b - Démontrer que ces deux lois sont logiquement équivalentes àl'aide de tables de vérités.





Exercice

Dans un pays lointain, deux tribus existent. La tribu des purs quidisent toujours la vérité et la tribu des pires qui mentent toujours.Un jours en voyageant dans ce pays un peu étrange, j'ai rencontréAlain et Bob. Alain m'a déclaré 2 choses :

"l'un de nous deux est au moins un pire"

"l'un de nous deux au plus est un pire"

Je les ai salué en partant et je me demande toujours de quelle tribupouvait bien appartenir Alain et Bob ?Questions :

a - Répondre à la question en résonnant de manière informelle.

b - Con�rmer votre résultat à l'aide d'une table de vérité.





Objectifs de la séance 2

1 Ecrire un algorithme avec des a�ectations

2 Ecrire un algorithme qui échange la valeur de deux variables

3 Savoir utilisés les entrées de la souris avec Processing

4 Ecrire un algorithme avec des tests simples

5 Ecrire un algorithme avec un test multiple

6 Ecrire des programmes java avec des tests simples ou multiples

Question principale du jour :

Comment écrire des algorithmes selon des situations di�érentes ?





Travail pour la semaine prochaine

Fabriquer ses petits programmes d'exemple

Explorer les exemples de Processing

travailler le cours à l'aide du TP !


Documents

Algorithmes conditionnels - Licence 1 MASS Introduction à