Rappel de Cours

Nombre de mots du Langage de Description

 

Pour deux tâches indépendantes T1 et T2

Le nombre de mots est 6

Démonstration

Soient d1, f1 et d2, f2 les symboles décrivant respectivement les tâches T1 et T2

Nous avons 3 manières de poser d2 par rapport à d1 et f1

  • d1  f1  d2
  • d1  d2  f1
  • d2  d1  f1

Il faut ensuite poser f2 qui est toujours après d2

  • d1  f1  d2  f2  -> 1 seule manière dans le 1er cas

  • d1  d2  f1  f2  -> 2 manières dans le 2è cas
  • d1  d2  f2  f1

  • d2  d1  f1  f2  -> 3 manières dans le 3è cas
  • d2  d1  f2  f1
  • d2  f2  d1  f1

 

Pour trois tâches indépendantes T1, T2 et T3

Le nombre de mots est 6 x 15 = 90

Démonstration

Nous avons vu qu'il y avait 6 manières de mélanger les symboles d1, f2, d2, f2

Notons X X X X un de ces 6 mots

Nous avons 5 manières de poser d3 par rapport à d1, f1, d2 et f2 représentés par les symboles X X X X

  • X  X  X  X  d3
  • X  X  X  d3  X
  • X  X  d3  X  X
  • d3  X  X  X
  • d3  X  X  X  X

Il faut ensuite poser f3 qui est toujours après d3

  • X  X  X  X  d3  f3  -> 1 seule manière dans le 1er cas

  • X  X  X  d3  X  f3  -> 2 manières dans le 2è cas
  • X  X  X  d3  f3 X

  • X  X  d3  X  X  f3  -> 3 manières dans le 3è cas
  • X  X  d3  X f3  X
  • X  X  d3  f3 X  X

  • X  d3  X  X  X  f3  -> 4 manières dans le 4è cas
  • X  d3  X  X  f3 X
  • X  d3  X  f3 X  X
  • X  d3  f3 X  X  X

  • d3  X  X  X  X  f3  -> 5 manières dans le 5è cas
  • d3  X  X  X  f3 X
  • d3  X  X  f3 X  X
  • d3  X  f3 X  X  X
  • d3  f3 X  X  X  X

On a donc (1 + 2 + 3 + 4 + 5) = 15 manières de poser d3 et f3

Ce qui donne au total 6 x 15 = 90 mots dans le langage associé

 

Pour quatre tâches indépendantes T1, T2, T3 et T4

Le nombre de mots est 6 x 15 x (1 + 2 + 3 + 4 + 5 + 6 + 7) = 90 x 28 = 2520

 

Pour quatre tâches T1, T2, T3 et T4 respectant le graphe de précédence suivant

Nous allons considérer en premier lieu le sous-système de tâches T1, T2 et T3

Ce système commence par l'exécution en parallèle des tâches T1 et T2

Le langage associé possède donc 6 mots composés des symboles  X  X  X  X  d3  f3

Le mot  X  X  X  X  étant composé des symboles d1  f1  d2  et  f2

Pour prendre en compte T4, il faut insérer les symboles d4 et f4 avec d4 toujours après f2

 

Les 6 mots du langage associé au système de tâches T1, T2 et T3 sont :

  • d1  f1  d2  f2  d3  f3
  • d1  d2  f2  f1  d3  f3
  • d2  f2  d1  f1  d3  f3
  • d1  d2  f1  f2  d3  f3
  • d2  d1  f1  f2  d3  f3
  • d2  d1  f2  f1  d3  f3

Il faut ensuite poser d4 qui est toujours après f2

  • d1  f1  d2  f2  d3  f3  d4  -> 3 manières dans le 1er cas
  • d1  f1  d2  f2  d3  d4  f3
  • d1  f1  d2  f2  d4  d3  f3

  • d1  d2  f2  f1  d3  f3  d4  -> 4 manières dans le 2è cas
  • d1  d2  f2  f1  d3  d4  f3
  • d1  d2  f2  f1  d4  d3  f3
  • d1  d2  f2  d4  f1  d3  f3

  • d2  f2  d1  f1  d3  f3  d4  -> 5 manières dans le 3è cas
  • d2  f2  d1  f1  d3  d4  f3
  • d2  f2  d1  f1  d4  d3  f3
  • d2  f2  d1  d4  f1  d3  f3
  • d2  f2  d4  d1  f1  d3  f3

  • d1  d2  f1  f2  d3  f3  d4  -> 3 manières dans le 4è cas
  • d1  d2  f1  f2  d3  d4  f3
  • d1  d2  f1  f2  d4  d3  f3

  • d2  d1  f1  f2  d3  f3  d4  -> 3 manières dans le 5è cas
  • d2  d1  f1  f2  d3  d4  f3
  • d2  d1  f1  f2  d4  d3  f3

  • d2  d1  f2  f1  d3  f3  d4  -> 4 manières dans le 6è cas
  • d2  d1  f2  f1  d3  d4  f3
  • d2  d1  f2  f1  d4  d3  f3
  • d2  d1  f2  d4  f1  d3  f3

 

Puis il faut ensuite poser f4 qui est toujours après d4

  • d1  f1  d2  f2  d3  f3  d4  -> + 1
  • d1  f1  d2  f2  d3  d4  f3  -> + 2
  • d1  f1  d2  f2  d4  d3  f3  -> + 3 =  6

  • d1  d2  f2  f1  d3  f3  d4  -> + 1
  • d1  d2  f2  f1  d3  d4  f3  -> + 2
  • d1  d2  f2  f1  d4  d3  f3  -> + 3
  • d1  d2  f2  d4  f1  d3  f3  -> + 4 = 10

  • d2  f2  d1  f1  d3  f3  d4  -> + 1
  • d2  f2  d1  f1  d3  d4  f3  -> + 2
  • d2  f2  d1  f1  d4  d3  f3  -> + 3
  • d2  f2  d1  d4  f1  d3  f3  -> + 4
  • d2  f2  d4  d1  f1  d3  f3  -> + 5 = 15

  • d1  d2  f1  f2  d3  f3  d4  -> + 1
  • d1  d2  f1  f2  d3  d4  f3  -> + 2
  • d1  d2  f1  f2  d4  d3  f3  -> + 3 =  6

  • d2  d1  f1  f2  d3  f3  d4  -> + 1
  • d2  d1  f1  f2  d3  d4  f3  -> + 2
  • d2  d1  f1  f2  d4  d3  f3  -> + 3 =  6

  • d2  d1  f2  f1  d3  f3  d4  -> + 1
  • d2  d1  f2  f1  d3  d4  f3  -> + 2
  • d2  d1  f2  f1  d4  d3  f3  -> + 3
  • d2  d1  f2  d4  f1  d3  f3  -> + 4 = 10