Jean HENRI                     Devoir d'algorithmique   mardi 1er octobre 2002
STS IG 2                                durée : 2 heures

Calculatrice autorisée, bien que non indispensable

Exercice 1 – Cours d'algorithmique

Décrivez les structures de boucle que vous connaissez et indiquez comment se fait le choix de ces structures.

Exercice 2 – Zone bleue

La police municipale vous demande de rédiger une application permettant de contrôler les véhicules qui stationnent sur un parking avec une durée de stationnement limitée (vous n'avez pas à gérer cette durée).

Le parking contient un nombre limité de places (représenté par la constante NbPlacesMax). L'application doit mémoriser les véhicules stationnés (au moyen de l'immatriculation du véhicule), le numéro de la place utilisée (compris entre 1 et NbPlacesMax) et l'heure de saisie de l'enregistrement par l'agent.

L'agent passe plusieurs fois par jour sur le parking, relève les nouveaux véhicules et contrôle que les autres véhicules n'ont pas dépassé la durée limitée.

Le fonctionnement de l'application commencera toujours par la saisie de la place et de la plaque d'immatriculation. Il y a alors 3 cas possibles :

–le véhicule saisi vient d'arriver dans le parking et occupe une place qui était libre jusqu'à présent. L'application mémorise les informations (y compris l'heure système).

–Le véhicule saisi vient d'arriver dans le parking et occupe une place qui était occupée lors du précédent passage de l'agent. L'information du véhicule précédent est supprimée et remplacée par le nouveau véhicule (vous ne prévoirez aucune historisation des informations), ainsi que l'heure système.

–Le véhicule saisi était déjà présent dans le parking lors du précédent passage de l'agent. L'application indique donc la place et l'heure du précédent enregistrement. Si la place actuelle est différente de la place mémorisée (l'automobiliste a quitté le parking et est revenu entre 2 passages de l'agent), l'information sera simplement mise à jour (y compris l'heure système). Sinon, l'agent décidera de lui-même s'il doit dresser un procès-verbal ou pas (selon que l'horaire est dépassé ou pas) et aucune information ne sera modifiée.

Aucun stockage dans un fichier n'est à prévoir, l'appareil utilisé par l'agent restera allumé tout au long de la journée.

On vous donne les informations suivantes :

T_date est une structure
                 Jour, Mois, Annee,
                 Heure, Minute, Seconde sont entiers
               fin structure

fonction DateSysteme renvoie un T_date // La valeur renvoyée correspond
                                       // à l'heure actuelle de l'appareil.

NbPlacesMax est une constante entière qui vaut 150

 

Travail à faire

 

Rédiger les algorithmes nécessaires pour réaliser cette application. Vous prendrez soin de préciser les hypothèses éventuelles qui vous seraient nécessaires.

DOSSIER 2 : SUIVI DE L'UTILISATION DU RÉSEAU
(tiré du sujet de BTS option réseau, session 1999)

 

Annexes à utiliser : annexes 2 et 3

 

Le réseau étant devenu opérationnel, Monsieur YBOUX voudrait connaître la durée pendant laquelle chaque utilisateur du siège s'est connecté au serveur au cours d’une période donnée. Un utilitaire du système d'exploitation du réseau alimente un fichier dans lequel les connexions et les déconnexions des utilisateurs sont enregistrées. Ce fichier possède une organisation séquentielle. Chaque enregistrement du fichier mentionne le nom de l'utilisateur (NomUtilisateur), la date (DateCnx), l'heure (HeureCnx) et le type d'événement (TypeCnx) sur un caractère : "C" pour une connexion ou "D" pour une déconnexion.

 

L'annexe 2 fournit un exemple commenté de ce fichier.

 

On fait les hypothèses suivantes sur ce fichier :

 

·Le fichier commence toujours par l’enregistrement d’une connexion.

·à toute connexion enregistrée correspond toujours une déconnexion.

·À tout instant, un utilisateur a au plus une connexion en cours (il n'a jamais plusieurs connexions simultanées).

·Le fichier étant constitué chronologiquement, une déconnexion figure toujours après la connexion correspondante et avant la connexion suivante du même utilisateur.

·Le nombre d’enregistrements est tel que les constantes MAXLOG et MAXUSER (voir annexe 3) sont suffisamment dimensionnées pour permettre le chargement complet des données dans les tableaux utilisés.

 

Au regard de ces hypothèses, on suppose que les contrôles correspondants ne sont pas nécessaires puisque le fichier ne comporte aucune erreur.

 

L'algorithme fourni en annexe 3 vise à calculer la durée pendant laquelle chaque utilisateur s’est connecté au serveur. Vous êtes chargé(e) de le compléter.

 

Travail à faire

 

2.1.      Étudier la fonction chercher_déconnexion :

 

            a) Expliquer l'initialisation de la variable locale j.

 

            b) Dire pourquoi on peut s'abstenir de contrôler un débordement d'indice du tableau tab_connect.

 

2.2.      Expliquer le rôle de la fonction init_tab, décrire son fonctionnement.

 

2.3.      Rédiger l'algorithme de la fonction chercher_utilisateur.

 

ANNEXE 2 : Extrait du fichier de traces

 

 

Extrait du fichier de traces :

MARDUP;12/04/1998;09:20:32;C

BRIMEN;12/04/1998;09:35:12;C

XAVVIR;12/04/1998;10:21:04;C

MARDUP;12/04/1998;10:54:45;D

BARNAB;12/04/1998;11:02:35;C

MARDUP;12/04/1998;11:43:08;C

XAVVIR;12/04/1998;11:48:54;D

BRIMEN;12/04/1998;12:23:05;D

BARNAB;12/04/1998;13:04:35;D

MARDUP;12/04/1998;14:14:56;D

 

 

 

Interprétation de la première ligne :

 

L'utilisateur MARDUP s'est connecté le 12/04/1998 à 9 heures 20 minutes et 32 secondes.

 

Interprétation de la quatrième ligne :

 

L'utilisateur MARDUP s'est déconnecté le 12/04/1998 à 1O heures 54 minutes et 45 secondes.

 

Interprétation de la sixième ligne :

 

L'utilisateur MARDUP s'est connecté le 12/04/1998 à 11 heures 43 minutes et 8 secondes.

 

Interprétation de la dixième ligne :

 

L'utilisateur MARDUP s'est déconnecté le 12/04/1998 à 14 heures 14 minutes et 56 secondes.

 

Résultat : l’utilisateur MARDUP a un temps total de connexion de 245 minutes (les secondes ne sont pas décomptées).

ANNEXE 3 : Algorithme de calcul des durées de connexion (1/2)

 

ALGO Statistiques

 

            CONST MAXLOG 1000

            CONST MAXUSER 50

 

            structure log

                        NomUtilisateur : chaîne de caractères

                        DateCnx : date

                        HeureCnx : heure

                        TypeCnx : caractère /* "C" si connexion, "D" si déconnexion */

            fin structure

 

            structure durée

                        Utilisateur : chaîne de caractères

                        Durée : entier

            fin structure

 

            VAR

                        tab_connect(1:MAXLOG) : tableau de log

                        tab_durées(1:MAXUSER) : tableau de durée

DÉBUT

            VAR x, y, z,  temps : entiers

 

            /* La procédure charge_tab charge le fichier de traces dans le

               tableau tab_connect.

            */

            charge_tab(tab_connect)

 

            /* Procédure init_tab */

 

            init_tab(tab_durées)

 

            /* Par hypothèse, le premier enregistrement est une connexion. */

 

            x <- 1                                        

 

            TANTQUE x < MAXLOG

                        /*          La fonction chercher_déconnexion rend l'indice qu’a dans

                                    tab_connect la déconnexion correspondant à la connexion

                                    contenue à l'indice x

*/

 

                        y ¬ chercher_déconnexion(x, tab_connect)

 

                        /*          La fonction calcul_durée fournit la durée

                                    d'une connexion à partir de la date et de l'heure de

                                    connexion, ainsi que de la date et de l'heure de déconnexion

                                    trouvées dans le tableau tab_connect aux indices x et y

*/

 

                        temps ¬ calcul_durée(x, y, tab_connect)

 

/*     La procédure chercher_utilisateur reçoit en paramètre l'indice d'une ligne dans le tableau tab_connect (paramètre x).

Elle doit rendre comme résultat l'indice de la ligne du tableau tab_durées correspondant à l'utilisateur concerné.

*/

 

                        z ¬ chercher_utilisateur(x, tab_connect, tab_durées)

 

                        tab_durées(z).Durée ¬ tab_durées(z).Durée + temps

 

           /*          La fonction prochaine_connexion rend l'indice de la connexion

                        suivante, à traiter dans le tableau tab_connect.

                 */

 

                        x ¬ prochaine_connexion(x, tab_connect, MAXLOG)

            FIN TANT QUE

FIN
ANNEXE 3 : Algorithme de calcul des durées de connexion (2/2)

 

Fonction chercher_déconnexion(i : entier, tab_connect (1 :MAXLOG) : tableau de log) : entier

/*   Cette procédure reçoit en paramètre l'indice d'une ligne du tableau tab_connect correspondant à une connexion.       
Elle rend en résultat l'indice de la ligne où on trouve la déconnexion correspondant à cette connexion. */

DÉBUT

           j : entier

 

          j ¬ i+1

           TANTQUE tab_connect(j).NomUtilisateur <> tab_connect(i).NomUtilisateur

                  j ¬ j+1

           FTQ

           retourner j

FIN

 

Procédure init_tab (tab_durée (1:MAXUSER) : tableau de durée)

DÉBUT

            i, j, fin_tab_durée : entiers

            User : chaîne de caractères

            Trouvé : booléen

 

fin_tab_durée ¬ 0

            POUR i ¬ 1 A MAXLOG

                        User ¬ tab_connect(i).NomUtilisateur

                        j ¬ 0

                        Trouvé ¬ faux

                        TANT QUE j < fin_tab_durée et non trouvé

                                    Si user = tab_durées(j).Utilisateur alors

                                               Trouvé ¬ vrai

                                    Fin si

                                    J ¬ j+ 1

                        FIN TANT QUE

                        SI non trouvé ALORS

                                    tab_durées(fin_tab_durée).Utilisateur ¬ user

                                    tab_durées(fin_tab_durée).d_durée ¬ 0

                                    fin_tab_durée ¬ fin_tab_durée + 1

                        FIN SI

            FIN POUR

FIN

 

Voici un exemple de tableau tab_connect après exécution de la procédure charge_tab :

 

NomUtilisateur

DateCnx

HeureCnx

TypeCnx

MARDUP

12/04/1998

09:20:32

C

BRIMEN

12/04/1998

09:35:12

C

XAVVIR

12/04/1998

10:21:04

C

MARDUP

12/04/1998

10:54:45

D

BARNAB

12/04/1998

11:02:35

C

MARDUP

12/04/1998

11:43:08

C

XAVVIR

12/04/1998

11:48:54

D

BRIMEN

12/04/1998

12:23:05

D

BARNAB

12/04/1998

13:04:35

D

MARDUP

12/04/1998

14:14:56

D

 

Voici le tableau tab_durées après exécution de la procédure init_tab :

 

Utilisateur

Durée

MARDUP

0

BRIMEN

0

XAVVIR

0

BARNAB

0