Examen module i133 files d attente c mip s3 fst mohammedia

Examen module i133 files d attente c mip s3 fst mohammedia s

Télécharger PDF

Ce document présente des exercices pratiques sur les structures de données fondamentales en informatique, issus du programme du Département d'Informatique de l'Université Hassan II de Casablanca pour l'année universitaire 2022/2023, Parcours MIP (S3).

Gestion des Files d'Attente en Banque

Cet exercice propose de simuler la gestion des files d'attente devant les guichets d'une agence bancaire. L'agence dispose de 3 guichets, chacun pouvant fournir 4 services différents (S1, S2, S3, S4). Chaque service prend un certain temps d'exécution (T1, T2, T3, T4).

Pour augmenter la rentabilité et réduire le temps d'attente des clients, chaque nouveau client arrivant à l'agence doit être affecté à la file qui présente le temps d'exécution total le plus court. Cette affectation se fait en comparant les temps d'exécution cumulés des trois files.

Les temps d'exécution nécessaires en minutes sont définis comme suit :

T1 : 3 minutes
T2 : 7 minutes
T3 : 10 minutes
T4 : 12 minutes

Déclarations de Structures en C

Pour implémenter cette gestion de files, les structures de données suivantes sont proposées en langage C :

#include <stdio.h>
#include <stdlib.h>

/* Temps d'exécution nécessaire en minutes */
#define T1 3
#define T2 7
#define T3 10
#define T4 12

typedef struct {
    int num; /* le numéro du client */
    int type_serv; /* le service dont le client a besoin (1,2,3 ou 4) */
} Client;

typedef struct element {
    Client cl; /* La donnée que notre file stockera */
    struct element *suivant; /* Pointeur vers l'élément suivant */
} Element;

typedef struct {
    Element *debut; /* Pointeur vers le premier élément */
    Element *fin; /* Pointeur vers le dernier élément */
    int taille; /* Nombre de personnes en file */
    int temps_att; /* Temps d'attente total calculé de la file */
} File;

Ces structures permettent de représenter un client (Client), un maillon de la file (Element) et la file d'attente elle-même (File), incluant sa taille et le temps d'attente cumulé.

Fonctions à Implémenter

Les fonctions suivantes doivent être rédigées pour gérer le système de files d'attente :

Lire les informations d'un client :

Écrire une fonction qui permet de lire les informations d'un client et de le retourner.

Client lire_client()
Obtenir le temps d'exécution du service :

Écrire une fonction qui prend en paramètre un client et retourne le temps d'exécution du service choisi.

int obtenir_temps_execution(Client C)
Allouer de l'espace mémoire pour un nouvel élément :

Écrire une fonction qui permet d'allouer de l'espace mémoire pour un nouvel élément (un nœud de la file).

Element* allouer_element()
Évaluer le temps d'attente minimum :

Écrire une fonction qui prend en paramètre les 3 files et retourne la file qui présente le temps d'attente minimum.

File trouver_queue_temps_attente_minimum(File F1, File F2, File F3)
Enfiler un nouveau client :

Écrire une fonction qui consiste à enfiler un nouveau client (nv) dans la file (F) qui a été déterminée comme présentant le temps d'attente minimum.

File enfiler(File F, Client nv)
Défiler un client :

Écrire une fonction qui prend en paramètre la file d'un guichet et défile le client (C) qui vient d'être servi.

File* defiler(File* F, Client* C)
Imprimer le ticket du client :

Écrire une fonction (imprimer_ticket) qui affiche les informations suivantes sur le ticket du client : son numéro, le nombre de personnes qui le précèdent et le temps d'attente avant de se rendre au guichet (temps d'attente minimum).

void imprimer_ticket(File F, Client C)
Trier les éléments d'une file :

Écrire une fonction qui permet de trier les éléments d'une file selon un ordre croissant des numéros de clients. Cette fonction doit utiliser seulement 2 files : la file F_a (qui contiendra les clients à trier) et la file F_b (une file auxiliaire qui contiendra les clients triés après exécution).

void trier_file(File F_a, File F_b)

Structures d'Arbres Binaires de Recherche

Cette partie explore les arbres binaires de recherche (ABR), une structure de données essentielle pour l'organisation et la recherche efficace d'informations.

Construction d'un Arbre Binaire de Recherche

Dessiner l'arbre binaire de recherche obtenu par insertions successives des éléments de clés 8, 3, 10, 1, 6, 14, 4, 7 et 9, en partant d'un arbre vide.

Parcours d'Arbre Binaire

Pour l'arbre binaire de recherche construit précédemment, donner le résultat des 3 parcours classiques :

Parcours Préfixe : Le nœud courant est visité en premier, suivi de son sous-arbre gauche, puis de son sous-arbre droit.
Parcours Infixe : Le sous-arbre gauche est visité, suivi du nœud courant, puis du sous-arbre droit. Pour un ABR, ce parcours énumère les éléments dans l'ordre croissant.
Parcours Postfixe : Le sous-arbre gauche est visité, suivi du sous-arbre droit, puis du nœud courant.

Suppression d'Éléments dans un Arbre Binaire

Dessiner l'arbre obtenu après la suppression des éléments de clés 4 et 8 de l'arbre binaire de recherche initial.

Foire Aux Questions (FAQ)

Qu'est-ce qu'une file d'attente et comment est-elle utilisée en informatique ?

Une file d'attente (ou "queue" en anglais) est une structure de données linéaire qui suit le principe "Premier Entré, Premier Sorti" (FIFO - First In, First Out). Cela signifie que l'élément ajouté en premier est le premier à être retiré. En informatique, les files d'attente sont utilisées dans de nombreux contextes, comme la gestion des tâches d'un système d'exploitation, les tampons de données, les simulateurs de processus, ou comme illustré ici, la gestion des clients dans un système de service.

Pourquoi est-il important d'optimiser le temps d'attente dans un système de files ?

L'optimisation du temps d'attente est cruciale pour améliorer l'efficacité et la satisfaction des utilisateurs ou clients. Dans un contexte bancaire, cela réduit le temps passé par les clients à l'agence, améliore leur expérience et la perception du service. D'un point de vue système, cela peut améliorer le débit en évitant les goulots d'étranglement et en distribuant la charge de travail de manière plus équilibrée entre les ressources disponibles (ici, les guichets).

Quel est l'intérêt d'un arbre binaire de recherche (ABR) par rapport à une liste simple ?

Un arbre binaire de recherche (ABR) offre des performances bien supérieures à une liste simple pour les opérations de recherche, d'insertion et de suppression, à condition que l'arbre soit équilibré. Alors qu'une liste simple peut nécessiter un parcours linéaire (O(n) dans le pire des cas), un ABR permet d'effectuer ces opérations en temps logarithmique (O(log n)) en moyenne. Cela est dû à sa structure hiérarchique qui divise l'espace de recherche à chaque étape. Les ABR sont donc idéaux pour gérer de grandes quantités de données nécessitant des accès rapides.