Algorithmes conditionnels - Licence 1 MASS - … · Vriablesa et a ectations Logique booléenne...

Algorithmes conditionnelsLicence 1 MASS - Introduction à Java et à l'algorithmique

Olivier Dalledalle@unice.fr

<deptinfo.unice.fr/�dalle/>NB: Ce cours a été mis au point par mon collègue Sébastien

Vérel, actuellement en congé de recherche.

Équipe Mascotte, commune I3S - CNRS/UNS & INRIASophia Antipolis

Variables et a�ectationsLogique booléenne

Schéma conditionnel

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 utiliser 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 ?

Olivier Dalle Algorithmes conditionnels

3 Savoir utiliser les entrées de la souris avec Processing

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

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, ...

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, ...

Pour stocker cette information, on emploie des variables

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.

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

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 ?

�oat

Calcul de types

�oat

Calcul de types

�oat

Calcul de types

�oat

Calcul de types

�oat

Calcul de types

5 + 12

16 / 3

15 − 5.3

�oat

5.4 % 2

�oat

Calcul de types

5 + 12

16 / 3

15 − 5.3

�oat

5.4 % 2

�oat

Calcul de types

5 + 12

16 / 3

15 − 5.3

�oat

5.4 % 2

�oat

Calcul de types

5 + 12

16 / 3

15 − 5.3

�oat

5.4 % 2

�oat

Calcul de types

5 + 12

16 / 3

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 octects.

Quelle est en la conséquence ?

Précision des �ottants

A�ectation

Attribuer à une variable une valeur.

notation en pseudo-code :

var ← expr

en java :

var = expr

A�ectation

var ← expr

en java :

var = expr

A�ectation

var ← expr

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. C ← A

3. A← B

4. B ← C

(ce dernier est à connaitre !)

1. A← 3

1. A← 32. B ← A

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

4. B ← A

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

3. A← B

4. B ← C

1. A← 3

1. A← 32. B ← A

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

4. B ← A

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

3. A← B

4. B ← C

1. A← 3

1. A← 32. B ← A

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

4. B ← A

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

3. A← B

4. B ← C

1. A← 3

1. A← 32. B ← A

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

4. B ← A

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

3. A← B

4. B ← C

Exemples en java

int a = 5 ;

int b = a + 3;

int a = 5 ;

int b = a + 3;

a = a + 1;

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

draw : exécutée tous les rafaichissements d'écran (1/50s)dé�ne par la mé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)

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)

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 on associe une valeur de vérité (VRAI ou FAUX)

Tautologie

est une formule qui est toujours VRAI quelque soit les valeurs devérité des littéraux

Dé�nitions

Littéral

Proposition

Tautologie

Dé�nitions

Littéral

Proposition

Tautologie

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

OU Vrai Faux

XOR 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

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

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

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 ?

Vrai Faux Faux

Faux Vrai Vrai

Faux Faux Vrai

A⇒ B

Vrai Faux Faux

Faux Vrai Vrai

Faux Faux Vrai

A⇒ B

Vrai Faux Faux

Faux Vrai Vrai

Faux Faux Vrai

A⇒ B

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

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�

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

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.

Tables de vérité

Vrai Faux

Vrai ? ?

Faux ? ?

Tables de vérité

Vrai Faux

Vrai ? ?

Faux ? ?

Logiquement équivalent

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

Logiquement équivalent

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)

Exemple

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

(a XOR b)

Exemple

( (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

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

p ∧ q ⇔ q ∧ p

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

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

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

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∨ep

Contraposée : (p ⇒ q)⇔ (eq ⇒ep)(p ⇒ q)⇔ (ep ∨ q)Preuve par l'absurde : eep ⇒ p

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

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

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

p ∧ q ⇔ q ∧ 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