UTBM algorithmiques avancees 2001 gi ag51 genie informatique semestre 1 final

Informations

• Publié par: shura
• Nombre de lectures: 177
• 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