Algorithmiques avancées 2001 Génie Informatique Université de Technologie de Belfort Montbéliard

Gaber

Description

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Algorithmiques avancées 2001. Retrouvez le corrigé Algorithmiques avancées 2001 sur Bankexam.fr.

Sujets

• 2001

Informations

• Publié par: bankexam
• Publié le: 15 août 2008
• Nombre de lectures: 21
• Langue: Français

Extrait

AG51

16 janvier 01

Documents non autorisés

Exercice 1

Pour résoudre un problème d’optimisation combinatoire de grande taille, on peut utiliser la

méthode exacte, des méthodes heuristiques ou des méthodes basées sur les réseaux de

neurones. Décrire chacune de ces méthodes en précisant leurs avantages et leurs

inconvénients.

Exercice 2

Considérons le problème du voyageur de commerce (1-TSP).

Q1.

Décrivez un algorithme génétique permettant de résoudre ce problème.

Q2.

Décrivez un algorithme basé sur un réseau de neurones de type Hopfield permettant de

résoudre ce problème.

Exercice 3

Considérons le problème d’optimisation suivant : vous avez un temps libre égale à

T

, dans

lequel vous pouvez réaliser des tâches. Un ensemble de tâches différentes sont disponibles et

vous avez à choisir lequel vous devez exécuter. Vous avez la durée de chacune des tâches. Le

but est d’utiliser le maximum de votre temps

T

. Le problème consiste donc à sélectionner un

1

sous-ensembles de tâches où leurs somme ne dépasse pas

T

et soit la plus proche possible de

T

.

Vous ne pouvez pas exécuter plusieurs tâches en parallèle. Toutes les durées des tâches sont

des entiers. Les tâches sont numérotées

1, 2, …, n

et

d[i]

représente la durée de la tâche

i

.

Q1.

Supposons que la méthode choisie pour résoudre ce problème est la méthode exacte.

-

Donnez l’arbre de recherche associée pour

n=4

.

-

Calculez la taille de l’arbre de recherche pour

n

donné. Quelle set votre conclusion ?

Q2.

Décrivez un algorithme génétique permettant de résoudre ce problème de gestion du

temps de travail.

Exercice 4

Considérons le problème de la composition de tournées postales avec flotte homogène : la

collecte du courrier postal auprès d'un portefeuille de clients répartis dans une agglomération.

Une flotte de véhicules identiques est disponible au dépôt. Le problème consiste alors à

choisir la meilleure composition de la flotte et à élaborer les tournées de ramassage.

Donner un algorithme permettant de résoudre ce problème.

Exercice 5

Considérons maintenant le problème de la composition de tournées postales avec flotte

hétérogène : la collecte du courrier postal auprès d'un portefeuille de clients répartis dans une

agglomération. Le courrier doit être ramassé dans une fenêtre de temps définie par contrat

entre chaque client et la Poste. Une flotte de véhicules de différentes capacités, vitesses, coût

fixe et variable est disponible au dépôt. Le problème consiste alors à choisir la meilleure

composition de la flotte et à élaborer les tournées de ramassage. En d’autres termes,

le

problème consiste à déterminer la flotte mixte la plus économique (du point de vue des coûts

2

3

fixes attachés aux véhicules, à l'attente du conducteur et des coûts variables liés aux

kilomètres parcourus) tout en respectant les contraintes de fenêtres de temps et de capacité.