Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
127 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Agreg interne, leçon 346 : graphes

Envoyé par ronan 
Agreg interne, leçon 346 : graphes
il y a sept semaines
Je dois préparer la leçon d'exercices 346 : "Exemples de problèmes modélisés par des graphes".
J
'habite à 70 km de la BU, mais je peux faire venir des livres à l'IUT qui est proche.
Je travaille à plein temps, donc je ne cherche pas à préparer une super leçon, mais quelque chose qui tienne globalement la route, niveau l2 max.
Avez-vous des références de livres à me conseiller ?



Edité 1 fois. La dernière correction date de il y a sept semaines et a été effectuée par AD.
Re: agreg interne, leçon 346: graphes
il y a sept semaines
avatar
Trouve un livre de mathématiques pour la gestion, un collègues de gestion m’avait prêté un de ses livres avec plein d’applications et leurs algorithmes de résolution.
Gaffe quand même, de mémoire, il y avait peu de preuves.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-



Edité 1 fois. La dernière correction date de il y a sept semaines et a été effectuée par nicolas.patrois.
Re: agreg interne, leçon 346: graphes
il y a sept semaines
J'ai lu un post sur ce forum, d'un un candidat ayant passé cette leçon à l'oral...

Si mes souvenirs sont bons, il avait proposé des exercices de spé maths (niveau TES)...

Il a obtenu plus que 10/20...

Ce genre de leçon peut rapporter gros !
Très peu de candidats vont la travailler...

Bonne préparation.
Re: agreg interne, leçon 346: graphes
il y a sept semaines
avatar
Tu peux parler de parcours de graphes (en largeur ou en profondeur), d’algorithme A* (amélioration de celui de Dijkstra)…

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: agreg interne, leçon 346: graphes
il y a sept semaines
Bonjour,
Au programme TES
Exemples :
- Matrice d'adjacence. Nombre de chaines d'une longueur donnée.
- Transport aériens : chaine eulérienne, cycle eulérien
- Voyageur de commerce : Dijkstra.
- Modèles probabilistes - prédateur proie.
Re: agreg interne, leçon 346: graphes
il y a sept semaines
J'ai vu l'an dernier une excellente leçon sur le sujet, le jury avait l'air d'y prendre un réel plaisir.
Je n'ai pas le niveau de ce candidat (il a très certainement été reçu), mais je dois tout de même pouvoir dépasser le niveau TS.



Edité 2 fois. La dernière correction date de il y a sept semaines et a été effectuée par AD.
Re: agreg interne, leçon 346: graphes
il y a sept semaines
Probabilités, chaînes de Markov, tout ça ?
Re: agreg interne, leçon 346: graphes
il y a sept semaines
avatar
Chaînes de Markov et probabilités, mais il faut quand même que ça cause de graphes.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: agreg interne, leçon 346: graphes
il y a sept semaines
Salut, je pense que les graphes de Cayley peuvent être une bonne illustration de la théorie des groupes.
Re: agreg interne, leçon 346: graphes
il y a sept semaines
Bibliographie : "Processus aléatoires pour les débutants" (Cassini, 15 €, par cher).

Sinon, se procurer un livre de recherche opérationnelle (Roseaux tome 1 chez Dunod par exemple) : ce sera le bonheur...

Pour l'aspect "gestion" : "Aide à la décision. Une approche par les cas" (souvent en occasion chez Bébert). Mais c'est toujours le même domaine fondamentalement (la recherche opérationnelle).
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
B onjour,
j'ai eu beau regarder, je n'ai rien trouvé dans le programme complémentaire sur les graphes.
Je suppose qu'il doit falloir donc suivre les spé de S et de ES, si possible en trouvant des exercices permettant d'utiliser l'algèbre linéaire, Dunford par exemple.
Quelqu'un sait ou trouver de tels exos ?
Qu'est-ce qu'on peut mettre d'autre ?



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Comme dit plus haut par Nicolas Patrois, une chaîne de Markov interprétée en marche aléatoire sur un graphe (éventuellement pondéré), le théorème de Perron à la rescousse pour déterminer « l'état stationnaire » et une référence aux moteurs de recherche puissants pour motiver le tout.

Une démonstration ou une monstration de la formule d'Euler $s-a+f=2$ pour les graphes planaires et la démonstration que $K_5$ et $K_{3,3}$ ne sont pas planaires.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
merci,
mes études datent de plus de 25 ans, et je n'ai pas souvenir d'avoir côtoyé les graphes,
j'ai regardé un livre sur le sujet et si j'ai bien repéré les K5et K3,3, j'avoue que ça m'a un peu dérouté.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Wronskien: c'est peut-être de moi dont tu parles, j'avais posté un message en juin sur mon oral 2 et cette leçon 346 – Exemples de problèmes modélisés par des graphes. Je n'avais proposé en effet que des exercices niveau Terminale S/ES.
Petit-compte rendu / plan ci-dessous.

Partie 1 : Chaîne eulérienne. (L'exercice des ponts de Königsberg)

Partie 2 : Nombre de chemins. Un exercice.

Partie 3: Graphes probabilistes. Deux exercices. (Une matrice diag, une matrice trig de mémoire).

Partie 4 : Plus court chemin. Un exercice sur l'algorithme de Dijkstra.

J'ai soigné la partie Motivation des exercices et ai détaillé en 4 parties les notions relatives aux graphes présentes dans mes exercices, et les théorèmes, propriétés et méthodes d'algèbre linéaire utilisés. J'ai mis l'accent, même si j'ai précisé que ce n'était pas le cœur de la leçon, sur les éléments propres d'un endomorphisme (vp et poly caractéristique et les diverses façons de les obtenir), la réduction (diag, trig, Dunford), les puissances de matrices (idem). J'ai tenu 9 minutes.

J'ai développé l'exercice 2. Le plus « dur » consistait à calculer Ap. J'ai proposé deux méthodes : la réduction (j'avais retenu par cœur tous les éléments propres et inverse de P, mais avait ouvert XCAS par précaution), et le théorème de Cayley-Hamilton (division euclidienne). Je finis en 15 minutes pile poil.

Partie Questions : je ne me souviens plus de grand chose. J'avais l'impression que le jury me testait au début (des questions précises sur les graphes et l'algèbre linéaire), et ensuite j'ai eu le sentiment de « discuter » avec eux... c'était très étrange. Des questions plus difficiles à la fin.

Note obtenue: 17/20.

[Nelson Dunford (1906-1986) prend toujours une majuscule. AD]



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Tu es passé l'an dernier?
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Quelques pointeurs pour illustrer cette lecon avec Xcas:
La commande plotproba permet de representer sous forme de graphe probabiliste une matrice stochastique.
La commande matpow permet de calculer la puissance n-ieme d'une matrice.
Si on cherche Dijkstra dans le menu Aide>Rechercher un mot dans l'aide, on trouve une page expliquant l'algorithme avec un programme. Attention, pour utiliser ce programme, il faut le renommer en Dijkstra, car depuis une commande dijkstra a ete ajoutee dans Xcas.
Le menu Aide>Exemples>spects contient egalement une session Xcas pagerank.xws pour illustrer un graphe probabiliste.
Et pour ceux qui veulent aller plus loin, il y a tout le package Giac/Xcas de theorie des graphes de Luka Marohnic, avec son manuel (en anglais) qui se trouve dans le menu Aide>Manuels et la liste des commandes les plus utiles dans le menu Cmds>Graph Theory
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Tout à fait, je suis passé (et l'ai enfin eue) l'an dernier.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Alors je pense que j'ai assisté à ton oral.
Tu avais bluffé le jury en calculant l'inverse, mais ils étaient déjà très favorables.
Ça m'intéresse que tu me donnes les références de tes exercices,
J'ai du mal à trouver des références.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Alors, je m'en suis beaucoup voulu lors de l'oral de ne pas avoir pris de manuel de Term ES avec la spé...
je n'avais qu'un manuel de Term S (avec Spé), et ai trouvé mes exercices peu diversifiés sur la forme.
On peut faire mieux en regardant dans les manuels de ES.

Mon manuel de Terminale S était très classique: maths repères. C'est celui que j'avais acheté pour le CAPES, ce doit être l'édition 2012-2013 du coup.

Pour la chaîne eulerienne (exercice 1), c'est l'exercice des ponts de Konigsberg (dont je n'avais l'énoncé que dans mes souvenirs) et si tu te souviens bien, l'un des membres du jury m'a reproché de ne pas avoir fourni le plan exact de la ville. J'étais tout à fait d'accord avec lui.

Pour l'exercice 2, il était issu du maths repère, mais on peut mieux faire dans un livre de Term ES.

L'exercice 3 était de mémoire un exercice du livre numérique de SKANDALIS (j'ai fait quasiment toutes mes leçons avec les deux manuels de Georges Skandalis): un état stable dans un triangle (la matrice devait être diagonalisable)
L'exercice 4 était issu du maths repère (la matrice n'était pas trigonalisable, mais était trigonalisable - on pouvait utiliser la réduction de Dunford aussi)

L'exercice 5 devait être inventé... On en trouve des dizaines dans les manuels de Term ES.

Pour l'inverse de la matrice, rien de bien impressionnant: quand ils ont pris mon plan dans la préparation pour le photocopier, j'ai appris par coeur les 9 coefficients de la matrice, le polynôme caractéristique, valeurs propres, vecteurs propres^^ C'était ça ou s'en remettre à XCAS en direct (que j'avais ouvert tout de même pour montrer que je l'avais utilisé pendant ma préparation).


Et sinon, je ne savais plus diagonaliser une matrice il y a 4 ans, donc pas de panique, à force de travail, ça passe^^

Voilà!
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Oui, c'est bien ça.
Ne connaissant rien aux graphes, je n'avais pas compris la remarque.
Merci pour le plan.
Tu as mis combien de temps pour l'avoir?
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
J'ai vu que le livre de Mohamed Assilia "1000 challenges d'algèbre" comporte un chapitre consacré aux graphes avec définitions, exemples, propriétés, et toute une série d'exercices.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par Blueberry.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
rmn50 écrivait : [www.les-mathematiques.net]
-------------------------------------------------------
> J'ai développé l'exercice 2. Le plus « dur » consistait à calculer Ap.
> J'ai proposé deux méthodes : la réduction (j'avais retenu par cœur tous les éléments
> propres et inverse de P, mais avait ouvert XCAS par précaution), et le théorème de
> Cayley-Hamilton (division euclidienne). Je finis en 15 minutes pile poil.

Il me semble que c'est un peu hors-sujet sur une leçon sur les graphes que de faire des méthodes de réduction d'endomorphisme pour calculer Ap. Faire les calculs à la machine pour se recentrer sur le thème central de la leçon me parait très pertinent ici et ça peut se faire dans les 15 minutes de présentation du plan, on ouvre la session Xcas avec la matrice et on montre la valeur de Ap. Ensuite on développe un autre exo (le 3 ou le 4 pour vous) vu que sur le 2 il n'y a pas grand chose à développer.
Évidemment, ça suppose d’être à l'aise sur le 3 ou le 4, il vaut sans doute mieux développer quelque chose à la limite du sujet qu'on maîtrise bien que quelque chose au cœur du sujet qu'on ne maîtrise pas, mais je pense que vous avez eu de la chance que le jury ait peu tenu compte de l’adéquation du développement au sujet.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Go proposer une chaîne de Markov : temps d'atteinte pour le motif FPPFFPF thumbs down

Pour ça tu introduis les états $S_1 = \emptyset , S_2 = F , S_3 = FP , S_4 = SPP , ... , S_8 = FPPFFPF $ et tu dessine la matrice associée. Cette matrice se met sous la forme $ \begin{pmatrix} A & \star \\ 0 & I \end{pmatrix} $ puisque $S_8$ est un état absobant, on calcule la matrice fondamentale $N = ( I - A )^{-1} = I + A + A^2 + A^3 + \cdots $ et si $e$ est le vecteur avec que des $1$, l'espérance du temps d'atteinte de $S_8$ est $N e$.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Ronan:
J'ai eu mon CAPES en 2013, ai préparé l'agreg interne deux ans avant de pouvoir la passer (2015/2016: prépa rouennaise et 2016/2017: paris Diderot) ce qui m'a permis de préparer l'intégralité des leçons, l'ai ratée une fois (2017/2018: prépa rouennaise, non admissible) et l'ai eue l'an dernier (prépa rouennaise).

Parisse:
J'ai hésité à développer l'exercice 2 (exercice classique sur les graphes en Terminale) en le résolvant de deux façons différentes, ou bien l'exercice 3 ou l'exercice 4 d'une seule façon (également classique). Au niveau du contenu mathématique c'est du niveau MP pour chacun de ces exercices, et en ce qui concerne les graphes, c'est du niveau Terminale pour chacun des exercices. Donc franchement... peu importe l'exercice a développer.

J'ai préféré résoudre l'exercice 2 car cela me permettait de proposer deux façons de trouver le polynôme caractéristique (déterminant ou division euclidienne (thm de Cayley-Hamilton) puis évaluation du polynôme caractéristique en les v.p; c'était aussi l'occasion d'évoquer oralement le cas de la multiplicité des v.p). Ces méthodes sont classiques, et il me semble que les exercices que l'on doit proposer doivent permettre de mettre en place des méthodes plutôt que des astuces (ça doit être écrit à peu près comme ça dans le rapport).

J'avais bien sûr rappelé lors des 10 premières minutes pourquoi chacun des 5 exercices avait sa place dans la leçon et ce qu'il apportait dans la découverte de la théorie des graphes.

Pour mon premier oral, on m'a également dit que j'avais eu beaucoup de chance d'avoir eu une bonne note.
Je pense que la forme de l'oral compte beaucoup (j'ai fait 11 oraux blancs qui m'ont beaucoup apporté).
J'ai toujours tenu les temps à la minute près, n'ai jamais eu besoin de mes notes (y compris pour le plan de ma leçon), regardais constamment le jury, ai répondu a presque toutes leurs questions ou débutais une réflexion au tableau, ai fait très attention à la rédaction.

Pour ce qui est du contenu: je ne suis jamais allé au delà du niveau MP (mais avais refait chaque exercice de mes manuels MP), mais maîtrisais ce que je racontais.

Je ne sais pas si c'est cette préparation qui m'a permis de décrocher le concours, ou bien la chance d'être tombé sur trois membres d'un jury qui étaient tous d'accord pour me mettre 17 ^^
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Capes 1996 (presque le pic de candidats, dur!)

Mode "ouin ouin " on:

pas de maths pendant 20 ans,
on est en gros 10 dans ma prépa perdue en comptant les externes avec lesquels on est mélangés, et en gros 3 à présenter des leçons.
C'est un peu (beaucoup) désespérant. j'ai passé ma journée, et n'ai préparé que deux développements.
A chaque avancée, j'ai la sensation d'agrandir l'étendue de mon ignorance, genre l'image du romain dans Astérix aux jeux olympiques: "non, le balai, c'est encore trop bon pour moi"
si tu en as une liste, voire quelque chose sur les exos, ça m'intéresserait pas mal (en mp).

mode ouin ouin of.

l'an dernier, je suis venu 3-4 jours avant et ai vu beaucoup de leçons,
j'ai souvenir de quelques prestations très intéressantes, dont la tienne, et celle d'une autre candidate sur les idéaux.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Je ne sais pas si ça peut te rassurer Ronan, mais c'est exactement pareil pour moi. Chaque journée de travail qui passe me donne l'impression d'ouvrir les yeux sur l'étendue de ce qu'il me reste à accomplir.

Concernant le témoignage de rmn50, je ne comprends pas trop : le contenu mathématique est niveau mp mais les exercices sont niveau terminale ? Je ne vois pas ce que tu veux dire ?
Tu parles du fait que tu as retenu les éléments propres d'une matrice, donc ce n'était pas niveau terminale !?



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
@rmn50: Est-ce que vous etes d'accord sur le fait que les methodes que vous avez developpees ne sont pas du tout specifiques au theme de la lecon? Ce sont des methodes classiques de reduction d'endomorphismes, pour moi c'est ici essentiellement hors sujet, ca ressemble donc a du recyclage de developpement et je suis un peu etonne que le jury n'ait pas semble le sanctionner (mais peut-etre qu'il l'a un peu fait, et que vous auriez eu 20 en etant au coeur du theme d'une lecon).

Par contre, developper un aspect de reduction d'endomorphisme specifique a une matrice stochastique correspondant a un graphe probabiliste (avec un exemple du genre Doudou le hamster de wikipedia), ca ce serait completement dans le sujet de la lecon : par exemple chercher l'espace propre associe a la valeur propre 1 *sans avoir calcule le polynome caracteristique*, apres avoir montre que 1 est bien valeur propre, car valeur propre de la matrice transposee associee au vecteur propre (1,1...,1), et illustrer la convergence d'une suite vectorielle definie par v_(n+1)=A*v_n vers un vecteur propre associe (dans le cas generique), a vitesse geometrique. Tout ca est je pense a la portee d'un candidat a l'agreg interne.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
@ Romanesco : sur un exercice type terminale, on guide l'élève vers le calcul de la puissance de matrices.
En enlevant cette partie, on peut arriver à de la diagonalisation ou du Dunford par exemple.

@parisse : oui, ça à l'air à la fois simple et intéressant. je vais creuser.

J'ai une question subsidiaire, je ne me souviens pas d'avoir vu beaucoup de candidats utiliser l'ordinateur.
A-t-on le droit d'ouvrir un fichier xcas (ou python) sauvegardé ou doit-on démarrer une nouvelle cession ?

Merci en passant à tous ceux qui m'ont aidé.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
Ok merci . J'avoue que n'ayant pas l'exercice sous les yeux et surtout ne connaissant pas grand chose aux graphes, j'ai du mal à me rendre compte. Désolé de l'intervention sûrement un peu bête.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
L'exemple de Doudou le hamster de wikipedia cité par parisse est très clair:
[fr.wikipedia.org]
une fois que tu as la matrice, c'est de l'algèbre linéaire classique.
Re: Agreg interne, leçon 346 : graphes
il y a six semaines
avatar
Citation
ronan
A-t-on le droit d'ouvrir un fichier xcas (ou python) sauvegardé ou doit-on démarrer une nouvelle cession ?

De mémoire, tu peux sauvegarder tes fichiers.
Demande quand même au webmaster du jury, il passe par ici de temps en temps.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: Agreg interne, leçon 346 : graphes
il y a cinq semaines
Extrait du rapport de jury 2019: "Tous les fichiers qu’il [le candidat] crée sont enregistrés sur le réseau et, sous réserve de s’être deconnecté avant de quitter la salle de préparation, le candidat peut les retrouver dans la salle de jury en se reconnectant au réseau"
Re: Agreg interne, leçon 346 : graphes
il y a cinq semaines
merci, j'ai lu le rapport mais cela m'a échappé.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 140 708, Messages: 1 376 285, Utilisateurs: 25 644.
Notre dernier utilisateur inscrit EPFL.


Ce forum
Discussions: 4 353, Messages: 83 855.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page