Scribd
Importer
157 vues2 pages

Exercices d'Algorithmique Avancée

Le document présente des exercices de révision en algorithmique avancée, abordant des problèmes tels que le sac à dos, la distance de Levenshtein, l'optimisation de projets et les algorithmes de parcours. Chaque exercice demande des solutions manuelles, l'utilisation de la programmation dynamique, ainsi que la modélisation et la création de classes. Les étudiants sont également invités à réfléchir sur des applications concrètes et des défis liés à l'utilisation de grandes bases de données.

Transféré par

fitiaraherinirina
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
157 vues2 pages

Exercices d'Algorithmique Avancée

Le document présente des exercices de révision en algorithmique avancée, abordant des problèmes tels que le sac à dos, la distance de Levenshtein, l'optimisation de projets et les algorithmes de parcours. Chaque exercice demande des solutions manuelles, l'utilisation de la programmation dynamique, ainsi que la modélisation et la création de classes. Les étudiants sont également invités à réfléchir sur des applications concrètes et des défis liés à l'utilisation de grandes bases de données.

Transféré par

fitiaraherinirina
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

INSTITUT SUPERIEUR POLYTECHNIQUE DE MADAGASCAR

AMBATOMARO - ANTSOBOLO - ANTANANARIVO

Algorithmique Avancée – Informatique et Télécommunication L3

EXERCICES DE REVISION

EXERCICE 1 – Problème du sac à dos


On donne l’instance de problème du sac à dos suivant :

Objet Poids(kg) Valeur(€)


1 4 200
2 6 250
3 2 50
4 7 425
Capacité du sac : 10 Kg

1) Résoudre manuellement ce problème ci-dessus en utilisant la programmation dynamique :


2) On donne le problème suivant :

Objet Poids(kg) Valeur(€)


1 50 000 300
2 130 000 1000
3 70 000 20
4 90 000 700
Capacité du sac : 150 000 Kg

Comment peut-on simplifier ce problème afin de ne pas gaspiller le temps et la mémoire, tout en s’assurant
de l’exactitude du résultat trouvé ?
Donner la version simplifiée du problème. Généraliser.

3) Donner le pseudocode d’un algorithme permettant de retrouver les détails de la solution trouvée (la liste des
objets à emporter) en faisant un parcours inverse du tableau obtenu à la question 1).

EXERCICE 2 – Application de la Distance de Levenshtein


1) Rappeler la formule récursive de la Distance de Levenshtein.
2) En utilisant la programmation dynamique, calculer la distance de Levenshtein entre « CHIEN » et « ACHAT ».
Enumérer les transformations à faire.
3) On veut utiliser la distance de Levenshtein pour trouver une liste de suggestions de mots en cas d’erreur.
Quels sont les difficultés et les défis relatifs à l’utilisation d’un dictionnaire de grande taille (ex : Gutenberg) ?
Quelles solutions proposez-vous ?

1/2
EXERCICE 3 – Problème d’optimisation
Vous êtes le Directeur Général d’une entreprise de développement informatique, on vous propose de choisir parmi
les marchés suivants :

- Le projet 1 : a besoin de 6 jours-hommes pour sa réalisation et rapportera 1000€ de bénéfice,


- Le projet 2 : a besoin de 2 jours-hommes pour sa réalisation et rapportera 150€ de bénéfice,
- Le projet 3 : a besoin de 4 jours-hommes pour sa réalisation et rapportera 600€ de bénéfice,
- Le projet 4 : a besoin de 8 jours-hommes pour sa réalisation et rapportera 1100€ de bénéfice,
- Le projet 5 : a besoin de 10 jours-hommes pour sa réalisation et rapportera 1150€ de bénéfice.

Utiliser la programmation dynamique pour sélectionner les projets à réaliser pour avoir le maximum de profit, si vous
disposez de 15 jours-hommes.

EXERCICE 4 – Algorithmes de parcours


1) Donner, en pseudocodes, l’algorithme de parcours en profondeur (DFS).
2) Proposer une structure de données permettant de stocker un graphe en mémoire.
3) On a le graphe suivant :

Donner l’ordre de parcours si on fait un parcours en largeur à


partir du nœud C.

Note. Pour choisir entre deux nœuds de même priorité, utilisez


l’ordre alphabétique.

4) Donner un Modèle Physique de Données (MPD) d’une base de données pouvant stocker un graphe.

EXERCICE 5 – Application concrète


1) Modéliser, en graphe, deux problèmes pertinents dans la vie quotidienne. Expliquer.
Parmi les deux problèmes, vous pouvez utiliser un exemple parmi ceux vus en cours.
2) Créer une classe dans un langage quelconque de votre choix (à préciser) Noeud pour un problème de votre
choix contenant une méthode getSucc() permettant de générer les successeurs d’un Nœud donné.

2/2

Vous aimerez peut-être aussi