Applications

Avant de commencer ...

Ces exercices ci-dessous sont indépendants et peuvent être traités dans un ordre quelconque. Toutefois, ils sont triés par difficulté, et il est donc recommandé de les réaliser dans l'ordre.

Il est également recommandé de prendre des notes et de réaliser des schémas afin de mieux comprendre la plupart des exercices, notamment le troisième sur les files d'attente.

Application 1 : Calculatrice polonaise inverse à pile

Le but de cet exercice est d’écrire un programme Python qui évalue une expression mathématique en notation polonaise inverse (NPI) à l’aide d’une pile.

La notation polonaise inverse est une méthode d’écriture d’expressions mathématiques. Elle est également appelée notation postfixée. Dans cette notation, les opérateurs sont placés après les opérandes. Par exemple, l'expression « 3 + 4 » en notation infixée serait écrite « 3 4 + » en notation postfixée. La NPI est souvent utilisée en informatique pour l'évaluation d'expressions mathématiques à l'aide d'une pile.

L'expression en NPI sera représentée par une liste contenant des entiers et des opérateurs. Par exemple, l'expression « 3 4 + 2 * » (équivalente à (3 + 4) * 2) sera représentée par la liste [3, 4, '+', 2, '*'].

Le programme doit parcourir la liste de gauche à droite et empiler les entiers rencontrés. Lorsqu'un opérateur est rencontré, le programme doit dépiler les deux derniers entiers empilés, effectuer l'opération correspondante et empiler le résultat.

Lorsque l'expression est bien écrite, il reste un seul nombre dans la pile à la fin de l'expression lue, qui est le résultat.

Voici les étapes à suivre pour évaluer l’expression « 3 4 + 2 * » :

  1. Empiler 3.

  2. Empiler 4.

  3. Rencontrer l'opérateur « + » : dépiler 4 et 3, effectuer l'opération 4 + 3 = 7 et empiler le résultat 7.

  4. Empiler 2.

  5. Rencontrer l'opérateur « * » : dépiler 2 et 7, effectuer l'opération 2 * 7 = 14 et empiler le résultat 14.

Le résultat final est 14.

Question

Dans un nouveau fichier calculatrice_polonaise.py, rédiger une fonction calculer() qui prend en paramètre la liste représentant l'expression en NPI, et qui renvoie le résultat de l'opération.

Vous veillerez à renvoyer None dans le cas où l'expression est mal rédigée.

Votre fonction doit prendre en compte les additions, soustractions et multiplications, uniquement avec des nombres entiers.

Indice

Commencez par comprendre comment fonctionne la notation polonaise inverse (NPI) et comment elle est utilisée pour évaluer des expressions mathématiques. Essayez-la sur une feuille avoir d'autres exemples d'expressions, comme par exemple « 2 8 6 - 7 * + » ou « 1 6 2 8 - + * »

Application 2 : Parenthèses équilibrées

Une séquence de parenthèses est dite équilibrée si chaque parenthèse ouvrante a une parenthèse fermante correspondante. Par exemple, (()()) est une séquence équilibrée, mais ((()) ne l’est pas car il manque une parenthèse fermante.

Afin de vérifier le bon équilibrage d'une chaîne de caractères, il suffit de parcourir la chaîne de caractères et :

  • en cas de parenthèse ouvrante, on empile cette parenthèse dans une pile ;

  • en cas de parenthèse fermante, on dépile une parenthèse de la pile et on vérifie si elle est de même type.

Question

Dans un nouveau fichier parentheses_equilibrees.py, rédiger une fonction verifier() qui prend en paramètre une chaîne de caractères, et qui renvoie True si les parenthèses sont correctement équilibrées, False sinon.

Votre fonction devra traiter les cas suivants :

  • Une chaîne de caractères peut ne pas comporter de parenthèses (par exemple elle peut comporter des lettres) qu'il ne faudra donc pas traiter.

  • Il existe plusieurs types de parenthésages à traiter et à vérifier :

    • les parenthèses « ( » et « ) » ;

    • les crochets « [ » et « ] » ;

    • les accolades « { » et « } » ;

    • les chevrons « < » et « > » ;

Indice

Pour chaque caractère de la chaîne de caractères, on doit vérifier s’il s’agit d’une parenthèse ouvrante ou fermante.

  • Si c’est une parenthèse ouvrante, on l’empile dans la pile.

  • Si c’est une parenthèse fermante, on dépile une parenthèse de la pile et on vérifie si elle est de même type. Si ce n’est pas le cas, on peut renvoyer False immédiatement.

Indice

Si la pile est vide à la fin de la chaîne de caractères, cela signifie que toutes les parenthèses ont été correctement équilibrées. Dans ce cas, on peut renvoyer True.

Application 3 : File d'attente

Vous êtes le responsable d’une banque qui dispose de N guichets pour accueillir les clients. Vous voulez optimiser le temps d’attente des clients, car vous savez que c’est un facteur important de satisfaction.

Vous avez donc décidé de tester différentes stratégies pour organiser les files d’attente. Par exemple, vous pouvez faire une seule file d’attente pour tous les guichets, ou une file d’attente par guichet. Vous pouvez aussi orienter les clients vers le guichet le moins occupé, ou les laisser choisir au hasard.

Pour comparer ces stratégies, vous avez besoin de simuler le fonctionnement de votre banque sur une période donnée, en tenant compte de l’arrivée des clients, du temps de traitement de chaque client, et du temps d’attente de chaque client.

On modélise le temps par une variable globale, qui est incrémentée à chaque tour de boucle. Quand un client arrive, il est placé dans une file sous la forme d’un entier égal à la valeur de l’horloge, c’est-à-dire égal à son heure d’arrivée. Quand un client est servi, c’est-à-dire quand il sort de sa file d’attente, on obtient son temps d’attente en faisant la soustraction de la valeur courante de l’horloge et de la valeur qui vient d’être retirée de la file (qui représente donc l'heure d'arrivée du client). L’idée est de faire tourner une telle simulation relativement longtemps, tout en totalisant le nombre de clients servis et le temps d’attente cumulé sur tous les clients. Le rapport de ces deux quantités nous donne le temps d’attente moyen.

Pour simuler la disponibilité d’un guichet, on se donne un tableau d’entiers dispo de taille N. La valeur de dispo[i] indique le nombre de tours d’horloge où le guichet i sera occupé. En particulier, lorsque cette valeur vaut 0, cela veut dire que le guichet est libre et peut donc servir un nouveau client. Quand un client est servi par le guichet i, on choisit un temps de traitement pour ce client, au hasard entre 0 et N, et on l’affecte à dispo[i] . À chaque tour d’horloge, on réalise deux opérations :

  • on fait apparaître un nouveau client ;

  • pour chaque guichet i :

    • s’il est disponible, il sert un nouveau client (pris dans sa propre file ou dans l’unique file, selon le modèle) ;

    • sinon, on décrémente dispo[i].

Question

Dans un nouveau fichier file_attente.py, écrire un programme qui effectue une telle simulation, sur 100​​​​ 000 tours d’horloge, et affiche au final le temps d’attente moyen.

  • Comparer avec différentes stratégies.

  • Comparer avec plusieurs valeurs de N.

  • Comparer en définissant une variable aléatoire pour déterminer si un client arrive ou non à chaque tour d'horloge.

Indice

Pour choisir une file d’attente au hasard parmi plusieurs, vous pouvez utiliser une fonction aléatoire qui renvoie un entier entre 0 et N-1.

Par exemple, vous pouvez utiliser la fonction randint(0, N-1) qui renvoie un tel entier.

Indice

Pour choisir la file d’attente où il y a le moins de clients, vous pouvez utiliser une fonction qui parcourt toutes les files et qui renvoie l’indice de la file la plus courte.

Par exemple, vous pouvez utiliser la fonction min() avec un argument key qui spécifie la fonction à utiliser pour comparer les éléments. Par exemple, min(liste_de_files, key=len) renvoie la file qui a la plus petite longueur.

Indice

Pour faire apparaître un nouveau client à chaque tour d’horloge, vous pouvez utiliser une fonction aléatoire qui renvoie vrai ou faux avec une certaine probabilité.

Par exemple, vous pouvez utiliser la fonction random() qui renvoie un nombre réel entre 0 et 1, et comparer ce nombre à un seuil qui représente la fréquence d’arrivée des clients. Si le nombre est inférieur au seuil, alors un nouveau client arrive.

Solution

Piste de résolution

Voici ci-dessous un exemple de code Python qui implémente la stratégie d’une seule file d’attente pour tous les guichets :

1
from random import random, randint
2
from File import File
3
4
# Nombre de guichets
5
N = 5
6
7
# Tableau des disponibilités des guichets
8
dispo = [0] * N
9
10
# File d'attente unique
11
file = File()
12
13
# Horloge
14
temps = 0
15
16
# Nombre de clients servis
17
nb_clients = 0
18
19
# Temps d'attente cumulé
20
attente_totale = 0
21
22
# Fréquence d'arrivée des clients
23
frequence = 0.2
24
25
# Durée de la simulation
26
duree = 100000
27
28
# Boucle principale
29
for i in range(duree):
30
    # On fait apparaître un nouveau client avec une certaine probabilité
31
    if random() < frequence:
32
        # On ajoute le client dans la file avec son heure d'arrivée
33
        file.enfiler(temps)
34
    
35
    # Pour chaque guichet
36
    for j in range(N):
37
        # Si le guichet est disponible
38
        if dispo[j] == 0:
39
            # Si la file n'est pas vide
40
            if not file.est_vide():
41
                # On sert le premier client de la file
42
                heure_arrivee = file.defiler()
43
                # On calcule son temps d'attente
44
                attente = temps - heure_arrivee
45
                # On met à jour le nombre de clients servis et le temps d'attente cumulé
46
                nb_clients += 1
47
                attente_totale += attente
48
                # On choisit un temps de traitement au hasard entre 0 et N
49
                traitement = randint(0, N)
50
                # On affecte ce temps au guichet
51
                dispo[j] = traitement
52
        # Sinon, on décrémente le temps de disponibilité du guichet
53
        else:
54
            dispo[j] -= 1
55
    
56
    # On incrémente l'horloge
57
    temps += 1
58
59
# On calcule le temps d'attente moyen
60
attente_moyenne = attente_totale / nb_clients
61
62
# On affiche le résultat
63
print(f"Temps d'attente moyen: {attente_moyenne:.2f}")