Agreg interne, leçon 346 : graphes
dans Concours et Examens
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 ?
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 ?
Réponses
-
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.The real danger is not that computers will begin to think like men, but that men will begin to think like computers.
-- Harris, Sidney J. -
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. -
Tu peux parler de parcours de graphes (en largeur ou en profondeur), d’algorithme A* (amélioration de celui de Dijkstra)…The real danger is not that computers will begin to think like men, but that men will begin to think like computers.
-- Harris, Sidney J. -
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. -
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. -
Probabilités, chaînes de Markov, tout ça ?
-
Chaînes de Markov et probabilités, mais il faut quand même que ça cause de graphes.The real danger is not that computers will begin to think like men, but that men will begin to think like computers.
-- Harris, Sidney J. -
Salut, je pense que les graphes de Cayley peuvent être une bonne illustration de la théorie des groupes.
-
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). -
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 ? -
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. -
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é. -
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, [large]D[/large]unford), 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] -
Tu es passé l'an dernier?
-
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 -
Tout à fait, je suis passé (et l'ai enfin eue) l'an dernier.
-
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. -
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à! -
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? -
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.
-
rmn50 écrivait : http://www.les-mathematiques.net/phorum/read.php?6,1938786,1941146#msg-1941146
> 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. -
Go proposer une chaîne de Markov : temps d'atteinte pour le motif FPPFFPF (tu)
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$. -
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 ^^ -
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. -
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 !? -
@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. -
@ 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é. -
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.
-
L'exemple de Doudou le hamster de wikipedia cité par parisse est très clair:
https://fr.wikipedia.org/wiki/Chaîne_de_Markov
une fois que tu as la matrice, c'est de l'algèbre linéaire classique. -
ronan a écrit: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.The real danger is not that computers will begin to think like men, but that men will begin to think like computers.
-- Harris, Sidney J. -
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"
-
merci, j'ai lu le rapport mais cela m'a échappé.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.2K Toutes les catégories
- 61 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 25 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres