L3 MIASHS, Algorithme et Programmation 3, année 2022

• Vous devez rendre un unique fichier sur Moodle
• Les notebooks ne seront pas corrigés (uniquement les fichiers *.py)
• Vous pouvez utiliser un ou plusieurs fichiers
• N’oubliez pas de commenter votre code
• Un bout de code qui ne fonctionne sera corrigé si et seulement s’il est commenté.
• Les documents et internet sont autorisés
• Toute communication est interdite et entraine directement un 0 à l’UE et un signalement pour triche

L’examen est sur un barême supérieur à 20. La note finale ne sera pas remise sur 20, n’essayez pas de faire tout les exercices.

Des itérateurs (6pts)

1. Écrire un morceau de code qui produit un itérateur retournant tous les nombres pairs jusqu’à 100.

2. Écrire un morceau de code qui produit un itérable retournant tous les nombres pairs jusqu’à 100.

3. Écrire un morceau de code qui produit un itérateur retournant toutes les chaines de caractères utilisant les caractères 'abcdefghijklmnopqrstuvwxyz'

Héritage (6pts)

Écrire une classe list_inv qui surcharge la classe list:

• en ajoutant une méthode prepend qui ajoute un élément au début de la liste.
• en ajoutant une méthode iter_rev qui retourne un itérateur de la fin vers le début.
• Faites en sorte que l’opération -L retourne la liste inversée

Une chaine circulaire (8pts)

Une chaine circulaire est une structure de données chainée où chaque maillon:

• Pointe vers un successeur
• Contient une valeur

À la différence d’une liste chainée, une chaine circulaire n’a pas de début ni de fin: en suivant les successeurs on revient forcément à la case départ. Par exemple, pour une chaine circulaire C de taille 3, on a C.next.next.next.next qui est l’élément C.

1. Écrire une classe ChaineCirculaire avec les contraintes suivantes:

• Elle n’hérite d’aucune classe
• Elle doit avoir une méthode check qui vérifie qu’il s’agit bien d’une chaine circulaire.
• Elle doit avoir des méthodes ajout_maillon et supprime_maillon qui ajoute et supprime un maillon de la chaine circulaire

2. Implementer la classe abstraite MutableSet avec une chaine circulaire, indiquer la complexité de chaque opération.

Des caches (10pts)

Un cache est une structure de donnée qui permet d’éviter de stocker des calculs intermédaires ou des ressources souvent utilisés qui sont sur un serveur distant. Il n’est pas rare qu’une application Web dispose d’un cache devant une base de donnée pour éviter de la surcharger avec des requêtes qui sont utilisée très fréquemment.

Un cache peut grossir arbitrairement pour prendre toute la place en mémoire et finir par faire cracher un système. Pour éviter ça, les caches disposent de politique d’évictions qui supprime de la mémoire les éléments les moins importants.

Dans cet exercice, les caches vont être des MutableMapping implémentés avec des politiques d’evictions particulaire. Pour chaque implémentation, vous pouvez utilisé les structures de données standard dict, list, set comme vous le souhaitez.

Pour chaque version implémenté, donner des exemples.

Un cache randomisé

Implémenter une classe RandomCache qui surcharge MutableMapping avec les contraintes suivantes:

• L’init de classe prend un paramètre max_size qui est le nombre maximal d’élément dans le cache
• Une fois que le cache contient max_size élément, il doit supprime un élément au hasard dans le cache.

Un cache Fifo

Implémenter une classe FifoCache qui surcharge MutableMapping avec les contraintes suivante:

• L’init de classe prend un paramètre max_size qui est le nombre maximal d’élément dans le cache
• Une fois que le cache contient max_size élément, il supprime l’élément le plus ancien dans le cache

Un cache LRU

Implémenter une classe LRUCache qui surcharge MutableMapping avec les contraintes suivante:

• L’init de classe prend un paramètre max_size qui est le nombre maximal d’élément dans le cache
• Une fois que le cache contient max_size élément, il supprime l’élément le moins accédé dans le cache

Compiled the: dim. 07 janv. 2024 23:19:07 CET