Examen1 d'informatique

Première session 2001

Durée : 3h. Cours manuscrits, correction des TP et documents distribués en cours autorisés.

Un groupe d'anciens étudiants fraîchement diplômés aimeraient développer un logiciel de planification spécifique à la démarche de certification qualité. Ils décident de créer une petite société pour créer le logiciel, le commercialiser, mais aussi former et assister le client.

Les questions ci dessous ne tenteront évidement pas de résoudre la globalité du problème, mais chaque partie traitera un point particulier, avec des hypothèses simplificatrices qui ne sont pas les mêmes pour chaque partie. Les trois parties sont donc indépendantes et peuvent être traitées dans l'ordre qui vous convient (et même les questions, à condition de bien les numéroter).

Un outil bien utile pour toute planification est le diagramme de Gantt. Un tel diagramme comporte des "blocs" décrivant chacun une tâche à effectuer : le nom de cette tâche, mais aussi quelles ressources (humaines et matérielles) elle nécessite, et obligatoirement une estimation de sa durée (avec si possible un intervalle de tolérance). De plus on impose, entre ces tâches, des relations d'antériorité (quelles sont les tâches qui doivent être terminées pour pouvoir entamer une tâche donnée).

Première Partie

Dans un premier temps, il faut décider d'un "modèle de données", c'est à dire décider comment on représentera les tâches et leurs antériorités dans notre programme.

Question 1.1 :

Question 1.2 :

Seconde Partie

Comme vous l'avez remarqué (et peut-être même m'avez vous déjà posé la question avant de lire cette ligne), le diagramme de Gantt donné plus haut comporte une antériorité redondante, mais ceci n'est pas gênant car cohérent. Dans cette partie nous allons analyser la cohérence des antériorités d'un diagramme de Gantt. Pour simplifier, supposons avoir N<20 tâches (numérotées entre 0 et N-1). Chaque tâche peut avoir au maximum deux antériorités. Pour les stocker, on utilise deux tableaux, appelés A1 et A2. Quand un tâche i n'a qu'une antériorité, alors elle est stockée dans A1, et A2[i] sera mis à -1. Quand une tâche n'a aucune antériorité, A1[i] = A2[i] = -1.

Exemple :

Question 2-1 :

Question 2-2 :

Question 2-3 :

les tâches n'ayant aucune antériorité sont notées comme étant "valides". Puis on parcourt toutes les tâches, celles ayant toutes leurs antériorités valides sont également valides. On recommence jusqu'à ce qu'on aie parcouru les N tâches sans avoir trouvé de nouvelle tâche à valider. On retourne alors le nombre de tâches non valides.

Vous pourrez, si vous en avez besoin, créer des tableaux temporaires, par exemple pour ne pas écraser le contenu de A1 et A2.

Question 2-4 :

Ces deux dernières questions seront bien évidement mieux notées que les deux précédentes.

Troisième Partie

On va aborder ici la gestion des ressources. Pour simplifier le problème, nous supposons ne disposer que de trois ressources, nommées A,B et C (variable de type "char"). Supposons avoir à effectuer N<100 tâches, chacune pouvant utiliser une ou deux ressources (si elle n'en utilise qu'une, r2 contiendra un ). Ces tâches sont actuellement listées dans un tableau, dans l'ordre de leur réalisation.

On a les déclarations suivantes :

#define MAX 100 typedef struct tache { float duree; char r1; char r2; }tache; typedef tache tab[MAX]; tab t; int N;

Question 3-1 :

Question 3-2 :

Question 3-3 :
On accepte de modifier légèrement l'ordre des tâches : chaque tâche peut être déplacée au maximum d'un cran dans l'ordre initialement prévu (soit avancée, soit reculée d'un cran). Proposez (en quelques mots) une méthode pour minimiser la durée totale. S'il vous reste du temps, écrivez le code C correspondant. Ecrivez une fonction capable d'échanger une tâche du tableau t et sa suivante. On suppose que t et N sont déjà saisis. Ecrivez le morceau de programme qui permet de calculer la durée totale nécessaire pour faire les N tâches, sachant qu'on peut effectuer en même temps des tâches n'utilisant pas la même ressource. Si vous en êtes capables, organisez ce calcul sous forme d'une fonction retournant un flottant. On désire maintenant trier les tâches. Vous devez écrire une fonction qui crée un tableau des numéros de tâches, trié de telle manière à ce qu'on ne retrouve jamais dans ce tableau une tâche qui soit placée avant une de ses antériorités. On supposera bien sûr que les données sont cohérentes. Ecrivez une fonction nommée incoherence qui reçoive en arguments N, A1 et A2, et retourne 0 si ces données sont cohérentes, un entier non nul sinon. Vous utiliserez obligatoirement l'algorithme suivant : Ecrivez une fonction nommée affiche qui est capable d'afficher un tableau. Que doit-on rajouter en fin du programme main pour que A1 puis A2 soient affichés ? Ecrivez en C un programme (main) qui demande N, puis saisit les deux tableaux A1 et A2. Vous définirez auparavant le type de A1 et A2 (que vous appellerez tableau).Donnez (en français) quelques idées (mais pas besoin de donner les déclarations en C) pour prévoir une structuration (dite "descendante") des tâches, c'est à dire que le projet est composé de tâches générales, chacune d'elle pouvant être décrite comme un ensemble de sous-tâches elles aussi ordonnées, etc...Décrivez (en français) comment vous pensez qu'il faudrait organiser ces données. Le nombre total de tâches ne dépassera jamais 1000. Expliquez vos choix. Donnez en C les déclarations de types (typedef) qui correspondent à votre proposition.