Forum de mathématiques - Bibm@th.net

capesman

Modérateur

Inscription : 15-08-2016

Messages : 119

[Info 20] - Exemples d'activité relevant de l'optimisation combi...

Bonjour,

  Cette discussion est ouverte pour parler de la leçon du capes de mathématiques : Exemples d'activité relevant de l'optimisation combinatoire.

Capesman.

Enola

Invité

Re : [Info 20] - Exemples d'activité relevant de l'optimisation combi...

Bonjour,

Comment aborderiez vous cette notion avec des élèves ? Je pensai partir d'un problème comme le voyageur du commerce et essayé d'amener à réfléchir sur différentes façons de résoudre le problème pour ensuite en présenter quelques unes (algorithme glouton, algorithme génétique...) mais j'ai peur que cela devienne vite compliqué à aborder sans sortir des programmes de terminale ISN et BTS ISO.
De plus, dans ce cas, cela diffère peu du thème "Exemples illustrant l’utilisation de différentes méthodes de résolution de problèmes algorithmiques"

Qu'en pensez vous ?

Merci d'avance pour vos avis/conseils

Samy31

Membre

Inscription : 25-04-2017

Messages : 14

Re : [Info 20] - Exemples d'activité relevant de l'optimisation combi...

Bonjour,

Je suis un peu dans le même cas que toi Enola, j'ai également du mal à donner des exemples d'activité sur ce sujet. Comment organiser sa leçon avec ce thème? Une partie théorie est surement nécessaire en début de leçon mais il faut ensuite enchainer sur des activités. Avez-vous des ressources sur ce sujet?

Merci par avance.

Samy

Enola

Invité

Re : [Info 20] - Exemples d'activité relevant de l'optimisation combi...

Bonjour,

Je me demande si la recherche d'un plus court chemin dans un graphe ne peut pas relever de l'optimisation combinatoire avec les algorithmes de Dijkstra, de Bellman-Ford et de Floyd-Warshal.
J'ai du mal à vraiment comprendre la notion d'opimisation combinatoire à vrai dire.

Je n'a rien trouvé de plus de mon côté

Lisana_Lovelace

Invité

Re : [Info 20] - Exemples d'activité relevant de l'optimisation combi...

Bonsoir !!

Je suis un peu coincée sur cette leçon, pour ne pas dire totalement. Est-ce que quelqu'un a plus d'idées à donner ?

Selon ce que j'ai, un problème d’optimisation combinatoire consiste à trouver dans un ensemble discret la ou les meilleures solutions réalisables. Je suppose qu'on peut le relier à la théorie de la complexité, mais j'ai peur que ça se rapproche trop de la leçon "exemple de détermination de la complexité d'un algorithme".

Bref, je suis un peu dans le mal ici. Tout est prenable !

Merci d'avance,

Lisana

Fred

Administrateur

Inscription : 26-09-2005

Messages : 5 004

Re : [Info 20] - Exemples d'activité relevant de l'optimisation combi...

Bonjour,

Je n'y connais pas grand chose, mais pour moi, l'optimisation combinatoire, c'est trouver le meilleur choix parmi un ensemble grand, mais fini, de possibilités. Il est clair que de nombreux algorithmes sur les graphes (recherche du plus court chemin, coloration de graphes, etc...) rentrent parfaitement dans le cadre de cette leçon. J'ai quelques autres idées dont je ne sais pas si elles sont vraiment pertinentes :
* la programmation linéaire dont on peut trouver un exemple simple. Il s'agit de trouver le minimum ou le maximum d'une fonction linéaire sous certaines contraintes.
* les droites des moindres carrés, qui minimise le carré des distances?

C'est peut-être un peu trop mathématique pour l'option info???

Fred.

Lisana_Lovelace

Invité

Re : [Info 20] - Exemples d'activité relevant de l'optimisation combi...

Bonsoir,

Je suis d'accord sur le fait que beaucoup d'algorithmes portant sur les graphes sont des exemples que l'on peut utiliser dans cette leçon. Mais pareil, j'ai peur que cela tourne du coup à une leçon portant uniquement sur les graphes, ce qui n'est clairement pas l'intitulé.

Tes deux dernières propositions, je n'y avais pas pensé. Certes, cela est un peu mathématique, mais considérant que c'est un capes de mathématiques option informatique, et non pas un capes d'informatique pure, je pense qu'il n'y a pas de problème à orienter un peu plus la présentation du côté des maths.

Merci pour tes idées en tout cas, ça me donne de nouvelles pistes à me mettre sous la dent !