commit 96da26462b45c5fe7ad7086bab0d4587914b91aa
parent a9734ec955a2471af272c6bc3cd84a90f5395144
Author: John Charron <rm_rf_windows@yahoo.fr>
Date: Wed, 20 Oct 2010 16:19:05 +0200
Relecture / corrections, forme seulement (jc)
Diffstat:
| M | rapport.tex | | | 88 | ++++++++++++++++++++++++++++++++++++++++---------------------------------------- |
1 file changed, 44 insertions(+), 44 deletions(-)
diff --git a/rapport.tex b/rapport.tex
@@ -117,80 +117,82 @@
\subsubsection{Question 2}
-Démonstration par construction :
-On éffectue un tri topologique sur le graphe des contraintes de précédence, le graphe resultant est $G' (\{J_{1}\ldots J_{n}\}, E') $ on a donc :
+Démonstration par construction~:
+On effectue un tri topologique sur le graphe des contraintes de précédence. Le graphe resultant est $G' (\{J_{1}\ldots J_{n}\}, E') $. On a donc~:
$$\forall J_{i} \quad \not\exists \ j < i \quad | \quad \exists (J_{j}, J_{i}) \in E'$$
-On transforme ensuite $G'$ en un graphe de flots avec l'algorithme donné dans le sujet.
-Considérons les arcs entre les $v_{i,j}$ :
+On transforme ensuite $G'$ en un graphe de flots à l'aide de l'algorithme fourni dans le sujet.
+Considérons les arcs entre les $v_{i,j}$~:
\begin{itemize}
- \item Arcs d'affectation : ces arcs sont entre des sommets $v_{i,j}$ et $v_{k,l}$ avec $i = k$
- \item Arcs de précédences : ces arcs sont entre des sommets $v_{i,j}$ et $v_{k,l}$ avec $i < k$ à cause du tri topologique.
- \item Arcs auxiliaires : ces arcs ne sont pas entre des sommets $v_{i,j}$.
+ \item Arcs d'affectation~: ces arcs sont entre des sommets $v_{i,j}$ et $v_{k,l}$ avec $i = k$
+ \item Arcs de précédences~: ces arcs sont entre des sommets $v_{i,j}$ et $v_{k,l}$ avec $i < k$ à cause du tri topologique.
+ \item Arcs auxiliaires~: ces arcs ne sont pas entre des sommets $v_{i,j}$.
\end{itemize}
-On va créer une $(s-t)-\mathrm{coupe}$ minimale. Comme cette coupe et minimale, aucun arc de capacité infinie n'a son origine dans $S$ et son extremité dans $\overline{S}$.
+On va créer une $(s-t)-\mathrm{coupe}$ minimale. Etant donné que cette coupe est minimale, aucun arc de capacité infinie n'a son origine dans $S$ et son extremité dans $\overline{S}$.
-TODO : on montre que si c'est une coupe min, il ne sort qu'un et un
-seul arc d'affectation par job. Il faut aussi montrer qu'il existe.
+TODO~: Montrons que s'il s'agit d'une coupe minimale, il ne sort qu'un et qu'un
+seul arc d'affectation par job. Il faut aussi montrer qu'il (il = ?) existe.
\subsubsection{Question 3}
-TODO : Attention à la phrase suivante, ce n'est pas tout à fait ce qu'on a montré dans l'exo 2
+TODO~: Attention à la phrase suivante, ce n'est pas tout à fait ce qu'on a montré dans l'exercice 2
-Dans l'exercice précédent, on a montré que de toute coupe minimale sort un et un seul art d'affectation par job.
+Dans l'exercice précédent, on a montré que de toute coupe minimale sort un et un seul arc d'affectation par job.
On cherche à associer un ordonancement réalisable à toute coupe minimale.
-On va construire cet ordonancement de la manière suivante : à chaque
+On va construire cet ordonancement de la manière suivante~: à chaque
fois qu'un arc d'affectation $v_{i,t}, v_{i,t+1}$ traverse la coupe,
on exécute le job $i$ à l'instant $t$ dans l'ordonancement.
-On cherche un ordonancement, donc une suite de paires
-$(\text{tâche},\text{date de début})$ respectant les dépendances,
-autrement dit chaque tâche apparaît après ses dépendances dans la
+On cherche un ordonancement, une suite de paires
+$(\text{tâche},\text{date de début})$ respectant les dépendances.
+Autrement dit, chaque tâche apparaît après ses dépendances dans la
suite.
Comme chaque arc de précédence a une capacité finie, pour que la coupe
-soit minimale, cela signifie qu'aucun arc de précédence ne sort de la
-coupe. Cela signifie donc qu'à chaque fois qu'on exécute un job (à
+soit minimale, aucun arc de précédence ne doit sortir de la
+coupe. Cela signifie qu'à chaque fois qu'on exécute un job (à
chaque fois qu'un arc d'affectation sort de la coupe), tous les arcs
de précédence entrants dans ce noeud ont leur extrémité déjà présente
-dans la partie \og gauche \fg de la coupe (TODO : on n'a pas prouvé
-ça, on a prouvé pour tous les sortants, mais pas les entrants. Il faut
+dans la partie \og gauche \fg de la coupe
+
+TODO~: on n'a pas prouvé
+cela, on l'a prouvé pour tous les arcs sortants, mais pas les arcs entrants. Il faut
montrer qu'en partant de la source, on est obligié d'avoir tous les
-arcs de précédence entrants.), et donc toutes les tâches dont dépend
-celle-là ont été exécutées à un temps antérieur.
+arcs de précédence entrants et donc que toutes les tâches dont dépend
+celle-là (?) ont été exécutées à un temps antérieur (antérieurement ?).
-On cherche un ordonancement réalisable, c'est à dire pour lequel
+On cherche un ordonancement réalisable, c'est-à-dire pour lequel
toutes les tâches peuvent être menées à bout durant le temps
imparti.
La propriété énoncée dans l'exercice 2 nous indique que dans toute
coupe minimale, un et un seul arc d'affectation par job sort de la
coupe. Cela signifie que chaque job a commencé à être exécuté. Comme
-il exite un noeud pour je job $j$ à l'instant $t$ si et seulement s'il
+il exite un noeud pour le job $j$ à l'instant (à un instant donné ?) $t$ si et seulement s'il
y a le temps de l'exécuter (\ogà chaque date de début possible\fg),
cela signifie que tous les jobs commencés ont eu le temps d'être
-terminés, et comme nous venons de voir que tous les jobs ont pu être
-commencés, ils ont tous pu être terminés. Donc l'ordonancement est
+terminés et, comme nous venons de voir, que tous les jobs ont pu être
+commencés - ils ont tous pu être terminés - et, par conséquent, l'ordonancement est
réalisable.
\subsubsection{Question 4}
On construit la coupe à partir de l'ordonancement de la même manière
qu'on a construit l'ordonancement à partir de la coupe dans l'exercice
-précédent, mais en suivant l'algorithme dans l'autre sens~:
+précédent, mais en suivant l'algorithme dans l'autre sens.
Si on exécute le job $i$ à l'instant $t$ dans l'ordonancement, alors
tous les noeuds $v_{i,t'}$ avec $t' \leq t$ sont dans la partie \og
-gauche\fg de la coupe. De plus, s appartient lui aussi à la partie
+gauche\fg de la coupe. De plus, (sujet de verba manquante ?) s'appartient lui aussi à la partie
gauche de la coupe.
-TODO : et les arcs de précédence ? prouver qu'aucun ne sort de la
+TODO~: et les arcs de précédence ? Prouver qu'aucun ne sort de la
coupe dans notre construction.
La capacité de cette coupe est la somme de la capacité de tous les
-arcs qui sortent de la coupe, autrement dit la somme des capacités des
+arcs qui sortent de la coupe, c'est-à-dire la somme des capacités des
arcs $v_{i,t}, v_{i,t+1}$. Comme la capacité de ces arcs est égale au
-coût d'exécution de la tâche i à l'instant t, on a bien égalité entre
+coût d'exécution de la tâche $i$ à l'instant $t$, on a bien égalité entre
la somme des capacités et la somme des coûts de démarrage des jobs,
donc la capacité de la coupe est égale au coût de l'ordonancement.
@@ -206,11 +208,11 @@ $$
\end{array}
$$
-Cherchons s'il en existe un de cardinal 4. Voici la liste des chemins,
+Cherchons s'il en existe un de cardinal 4. Voici la liste des chemins
obtenue par un parcours en profondeur (en prennant toujours en premier
-les sommets voisins avec le numéro le plus petit possible) :
+les sommets voisins avec le numéro le plus petit possible)~:
-TODO : numéroter les "équations"
+TODO~: numéroter les "équations"
$$
\begin{array}{ccccccccccc}
1 & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 5 & \rightarrow & 6 \\
@@ -225,13 +227,13 @@ $$
$$
Voyons les ensembles qui contiennent le chemin $A$~: On ne peut pas
-prendre les chemins $B$ et $C$, car ils ont l'arc $(1,2)$ en commun
-avec $A$. On ne peut pas prendre non plus les chemin $D$ et $G$, car
-ils ont l'arc $(5,6)$ en commun avec $A$, ni le chemin $E$ à cause de
+prendre les chemins $B$ et $C$ car ils ont l'arc $(1,2)$ en commun
+avec $A$. On ne peut pas prendre non plus les chemin $D$ et $G$ car
+ils ont l'arc $(5,6)$ en commun avec $A$ ni le chemin $E$ à cause de
l'arc $(3,4)$. Il ne reste plus que les chemins $F$ et $H$ qu'on
pourrait peut-être prendre si on prend $A$, mais le cardinal de
l'ensemble serait alors 3, donc on n'améliorerait pas le résultat
-existant, et donc ce n'est pas la peine de chercher si ces chemins
+existant. En conséquence, ce n'est pas la peine de chercher si ces chemins
sont \og compatibles\fg avec $A$.
Procédons de la même manière pour $B$ (sachant que $A$ ne peut pas
@@ -262,14 +264,13 @@ Passons à $F$ avec $A,B,D$ exclus. On ne peut pas avoir~:
\end{itemize}
Donc $F$ n'est pas dans l'ensemble.
-Comme $A,B,D,F$ ne sont pas dans l'ensemble, et que nous avons
+Comme $A,B,D,F$ ne sont pas dans l'ensemble et que nous avons
seulement 8 candidats, la seule possibilité qui reste pour un ensemble
-de cardinal 4 est $C,E,G,H$, or dans cet ensemble, l'arrête $(1,4)$
+de cardinal 4 est $C,E,G,H$. Or, dans cet ensemble, l'arête $(1,4)$
est commune à $G$ et $H$, donc on ne peut pas construire un ensemble
de chemins d'arcs disjoints de taille 4 (donc pas de taille supérieure
à 4 non plus).
-Conclusion : Le nombre maximum de chemins d'arcs disjoints est 3.
-
+Conclusion~: Le nombre maximum de chemins d'arcs disjoints est 3.
-\end{document}
-\ No newline at end of file
+\end{document}
