Aller au contenu

Exercices d'application

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.

Notation Polonaise Inverse

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.

Une piste ?

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 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 >

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, autrement dit 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 (afin de ne pas se retrouver avec un temps d'attente croissant dans le temps), 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 \(100000\) tours d’horloge, et affiche au final le temps d’attente moyen.

  • Comparer avec différentes stratégies.
  • Comparer avec plusieurs valeurs de N et T.
  • Comparer en définissant une variable aléatoire pour déterminer si un client arrive ou non à chaque tour d'horloge.