Ingénierie des systèmes

Stephane.Maag(at)telecom-sudparis.eu
Les TDs sont individuels
L’examen est à 75% des maths (cf. les TD horribles)
Rendre un rapport à la fin des TD
Slides importants = Dans l’examen
Pas de documents à l’examen

Chemin à avoir en tête :

flowchart TD
    A -- Extraction (DS, UIO, W) --> B
    B -- Détection erreurs --> C
    A -- conf? --> C

A((Spécification système))
B[Scripts Tests TCCN3]
C[(SUT)]

État : Ensemble de variables valuées ou non valuées de l’ensemble du système.
État équivalent : même input = même output

Hypothèses sur l’automate

• Complet (input enable) : dans chaque état de l’automate, je dois traiter tous les inputs possibles du système (évitant le blocage).
• Déterministe : (examen)

---
title: Non-déterministe observable
---
flowchart TD
    1 -- a/x --> 2
    1 -- a/y --> 3

1((1))
2((2))
3((3))

Dans chaque exercice de l’examen, il y aura une hypothèse violée.

Dans le système automate qui représente le système sous test, il peut être aussi moche que possible (deadlock, livelock, non déterministe, non minimal…) contrairement à la spec.

DS

état initial suite entrée suite sortie
s1 a 0
s2 a 1
s3 a 0
Pas distinguant \RA pcq a qui donne 0 apparaît 2x. : donc on doit essayer avec autre chose, par exemple b
état initial suite entrée suite sortie
s1 b 1
s2 b 1
s3 b 0
Toujours pas distinguant, on essaie ab, qui lui est distinguant (cf. slides)

Parfois, il n’existe pas.

flowchart RL
    1 -- t1: a/0 --> 1
    2 -- t2: a/0 --> 1
    2 -- t3: b/1 --> 2
    3 -- t4: b/1 --> 2
    3 -- t5: a/1 --> 3
    1 -- t6: b/0 --> 3

1((s1))
2((s2))
3((s3))

On revient tout le temps sur s1 en partant de s1 et s2, on revient tout le temps sur s2 en partant de s3 et s2, ils sont indistinguables, en commençant la séquence par a ou par b, on arrivera toujours sur un état commun indistinguable.

reset/null : démarrage du système, ce qui suit est l’état initial.

W

Existe toujours.

UIO

Parfois ils n’existent pas (cf. UIO partiel).

On cherche des cas uniques directement sans faire de tableau :
UIO(S2) = a/1
UIO(S3) = b/0
UIO(S1) = a/0 b/1

W : à peu près un ensemble de séquence d’input
UIO : Unique Input Output

Exercices

Page 115

DS

état initial suite entrée suite sortie
s0 aa xy
s1 aa yx
s2 aa yy

Séquence de test

TS_{DS}=(1, \text{bx}, 2) = R/N, a/x, b/x, a/y a/y

UIO pour tous les états

Rapide à trouver, car on a une ds aa.

UIO(S0) = a/x
UIO(S1) = a/y a/x
UIO(S2) = a/y a/y

TS_{UIO}(0, \text{ax}, 1) = R/N, a/x, a/y, a/x

W

Pareil à la DS

Page 116

Exercice du haut

W

état initial suite entrée suite sortie
s0 a y
s1 a x
s2 a x
état initial suite entrée suite sortie
s0 b y
s1 b y
s2 b x
W = \{a, b\}

UIO

UIO(S0) = a/y
UIO(S1) = a/x a/y
UIO(S2) = b/x

Séquence de test

TS_{W}=(1, \text{ax}, 0) = R/N, a/y, a/x et R/N, a/y, b/y
TS_{UIO}=(0, \text{ax}, 2) = R/N, b/y, b/x

Page 117

-- = output null

Complétude = tout les états reçoivent tout les inputs = pas de blocage

Pas de UIO, parce que partiel

On a un PUIO si on a les 5 hypothèses, sinon on va utiliser W.

On prend les transitions sortantes des états et on y rajoute les UIO de ces états
PUIO_{Both} = -2/N, UIO(01) et -1/N, UIO(02)
donc
PUIO_{Both} = -2/N, -1/A et -1/N, -2/A

Séquence de tests

TS_{PUIO}(\text{Only2}, \text{+1/N}, B)= R/N, +2/P, +1/N, -1/N, -2/A et R/N, +2/P, +1/N, -2/N, -1/A

Page 121

R/N, +2/P, +2/N, -2/A
Sur IUT : R/N, +2A, +2A, -2/N : inconclusif
Après fix : R/N, +2/P, +2/A, -2/N
\RA Erreur mixte (transfert et sortie)

Exercice 1 (top)

état initial suite entrée suite sortie
s0 a x ✅
s1 a y
s2 a y
s3 a y
état initial suite entrée suite sortie
s0 aa -
s1 aa yy
s2 aa yy
s3 aa yx✅
état initial suite entrée suite sortie
s0 aaa -
s1 aaa yyy✅
s2 aaa yyx✅
s3 aaa -
W = \{a, aa, aaa\}

TS_{W}(3, \text{a/y}, 0) = // TODO

Exercice 1 (bot)

Il y a blocage : il n’est pas complet (on ne peut pas faire c depuis partout) : il faut le compléter (à mentionner !!)
UIO(S0) = a/x c/x
UIO(S1) = c/x
UIO(S2) = a/y a/x a/y c/x : on se rapproche du c/x qui est unique
UIO(S3) = a/x a/y c/x
UIO(S4) = a/y c/x

TS_{UIO}(4, \text{a/y}, 1) = R/N a/x a/x a/y a/x a/y c/x

Exercice 2a

état initial suite entrée suite sortie
s0 cc xx
s1 cc yx
s2 c xy
W = \{cc\}
UIO(S0) = c/x c/x
UIO(S1) = c/y
UIO(S2) = c/x c/y

Exercice 2b

On prend l’état de départ, on regarde l’input/output

TS_{UIO}(2, \text{a/x}, 0) = R/N c/x a/x c/x c/x

Exercice 3

Question 1

a

état initial suite entrée suite sortie
s1 c z✅
s2 c x✅
s3 c y
s4 c y
s5 c y
état initial suite entrée suite sortie
s3 b x✅
s4 b z✅
s5 b y✅
W = \{c,b\}
UIO(S1) = c/z
UIO(S2) = c/x
UIO(S3) = b/x
UIO(S4) = b/y
UIO(S5) = a/y

b

TS_{UIO}(\text{S2, by, 2}) = R/N a/x b/y, b/y, c/x

Question 2

a

5 propriétés majeures de l’automate :

Il faut minimiser l’automate. Attention, il faut toujours minimiser par paire, pour éviter du non déterministe.
exo3-2b

Là, il y a un cycle : DS : aaa

état initial suite entrée suite sortie
s1 aaa yxxx
s2,3 aaa xxxy
s4,5 aaa xxyx
s6 aaa xyxx
W = \{aaa\}

UIO(S1) = a/y
UIO(S2/S3) = a/x a/x a/x
UIO(S4/S5) = a/x a/x a/y
UIO(S6) = a/x a/y

b

Stratégie de notre choix = très souvent les UIO

Ici S2 équivaut à S2/S3

TS_{UIO}(\text{S1, ay, S2}) = R/N, a/y, a/x a/x a/x

3

On minimalise le système :
exo3-3a

On minimalise encore
exo3-3a2

b

TS_{DS}(\text{S2, by, S2}) = R/N a/x, b/y, b/y

c

On travail toujours sur le dernier système, donc celui qu’on a dessiné. Pas celui de l’énoncé

Inconclusif : problème dans le préambule
+ On n’a pas le bon nombre de sorties

4

a

état initial suite entrée suite sortie
s1,s4 aaa xyx
s2,s5 aaa yxx
s3 aaa xxx
s6 aaa xxy
W = \{aaa\} (merci le cycle)

UIO(S1/S4) = a/x a/y
UIO(S2/S5) = b/y ou a/y
UIO(S3) = a/x b/x
UIO(S6) = b/x

b

TS_{W}(\text{1, a/x, 2}).(\text{2, b/y, 3}) = R/N, ax, ay, bx, ax, by, ax bx

R/N, ax, ay, bx, ax, by, ax bx
---  --  --  --  --  --  -----
|    |   |   |   |   |   |> UIO(3)
|    |   |   |   |   |> b/y
|    |   |   |   |> Deuxième préambule
|    |   |   |> Postambule (court chemin pour revenir à l'état initial)
|    |   |> UIO(2)
|    |> a/x
|> Préambule

c

x y x x y x x \ra PASS

Mais si on a une autre écriture : R/N, ax, by, ax, bx, ax, by ax bx on a un INCONCLUSIVE.
Mais si on a une autre écriture : R/N, ax, ay, ax, ax, by, ax bx on a un PASS.

d

Ou alors au lieu du postambule, on met un R/N : R/N, ax, ay, R/N ax, by, ax bx ax on a un FAIL pour erreur mixte.

R/N, ax, ay, R/N ax, by, ax bx ax
---  --  --  ------  --  --------
|    |   |   |       |   |> UIO(3) + ax qui permet de rallonger
|    |   |   |       |> b/y
|    |   |   |> Deuxième préambule
|    |   |> UIO(2)
|    |> a/x
|> Préambule

Mais si on a une autre écriture : R/N, ax, by, R/N ax, by, ax bx ax on a un FAIL pour erreur mixte

Lien vers le projet