Bibliothèque de médias

On souhaite gérer une bibliothèque de fichiers musicaux. Chaque fichier doit être identifié par un chemin ou une URL et on souhaite également y associer un nom d’artiste et un nom de morceau. On veut écrire des fonctions permettant de faire des recherches dans cette bibliothèque.

  1. Décrire le type à utiliser pour stocker cette bibliothèque
  2. Écrire une fonction qui renvoie tous les chemins des fichiers d’un artiste donné.
  3. Écrire une fonction qui renvoie une sous-bibliothèque composée des morceaux dont le nom contient une chaîne donnée (par exemple tous les morceaux qui contiennent "summer").
  4. Écrire une fonction qui trie une bibliothèque par nom d’artiste.

Recharge de véhicule électrique

Un véhicule électrique n’a pas assez d’autonomie pour parvenir à sa destination sans faire de recharge. Étant données la distance à parcourir, la consommation (en % par km), le tableau des distances auxquelles on rencontre des stations de recharge et les coûts de recharge (en € par %), on veut calculer les arrêts à faire et le coût total du trajet.

Proposer des stratégies simples de recharge et pour chacune, écrire un programme qui calcule une solution possible s’il y en a.

Optimiser le coût.

Problème du sac à dos

On dispose d’un sac à dos pouvant contenir un poids maximal capacite et d’un ensemble d’objet dont on connaît les poids poids_1, poids_2, … On cherche à mettre dans le sac les objets qui maximiseront le poids transporté.

Par exemple, si la capacité est 14 et la liste des poids [ 9, 12, 7, 5, 4 ], le meilleur choix est de prendre les objets ayant pour poids 9 et 4.

  1. Écrire un algorithme glouton qui va essayer de mettre les objets dans le sac en commençant par le plus lourd.
  2. L’algorithme glouton ne donne pas la bonne solution sur l’exemple donné. Écrire un algorithme qui va générer tous les sous ensembles de poids possible, calculer leurs sommes et renvoyer le sous-tableau donnant le plus grand poids inférieur à la capacité.
  3. Écrire un algorithme qui prend le dernier élément du tableau, teste l’algorithme sur le tableau privé de ce dernier élément dans le cas où on place le dernier élément dans le sac (diminuant ainsi sa capacité) et le cas où on ne place pas le dernier élément dans le sac.

Plus longue sous chaîne commune

Pour évaluer des réponses dans une application d’apprentissage de l’orthographe, on souhaite mesurer si deux mots sont proches l’un de l’autre. On décide que la longueur de la plus longue sous-chaîne commune est une façon de mesurer cette proximité (on appelle cette valeur la distance de délétion). Une sous-chaîne d’un mot comprend des lettres de ce mot dans le même ordre mais qui peuvent ne pas se suivre. Par exemple la plus longue sous-chaîne commune entre chat et chien est ch ; la plus longue sous-chaîne commune entre chat et cat est cat donc cat est une meilleure réponse que chien.

Écrire une fonction donnant la plus longue sous-chaîne de deux mots. Le nombre de caractères d’une chaîne ch s’obtient avec ch.length(). On peut accéder au i-ème caractère de la chaîne ch avec la méthode ch.charAt(i).

Tester cet algorithme sur les mots "abcdbab" et "bdcaab" (la plus longue sous-chaîne est de longueur 4).