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 ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Gaffe quand même, de mémoire, il y avait peu de preuves.
-- Schnoebelen, Philippe
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.
-- Schnoebelen, Philippe
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.
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.
-- Schnoebelen, Philippe
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).
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 ?
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.
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é.
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]
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
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.
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à!
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 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.
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$.
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 ^^
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.
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 !?
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.
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é.
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.
De mémoire, tu peux sauvegarder tes fichiers.
Demande quand même au webmaster du jury, il passe par ici de temps en temps.
-- Schnoebelen, Philippe