Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 Re : Leçons de Capes » [Math 14] - Relations métriques et angulaires dans le triangle. » 06-12-2018 21:43:58

Bonjour,

  Il y a beaucoup de choses à dire dans cette leçon, et je ne suis pas sûr que les formules trigonométriques d'addition etc... soient au cœur de cette leçon. A mon avis, on peut en parler mais on peut aussi s'en dispenser.
En revanche, ce dont tu ne peux pas te passer, c'est d'améliorer ton orthographe!

Capesman.

#2 Re : Leçons de Capes » [Info 26] - Exemples d'algorithmes utilisant un générateur... » 27-11-2018 20:56:44

Bonjour,

  Le rapport du jury 2018 donne des pistes pour cette leçon :

"Il  s’agit  dans  cette  leçon  de  présenter  l’utilisation  de  générateurs  pseudo-aléatoires  dans  les algorithmes.  Toute  discussion lancée  sur  le  degré  d’aléatoire  de  ces  générateurs  est explicitement hors sujet. On pourra supposer dans toute la leçon qu’on dispose d’une fonction random() qui fournit un réel aléatoire de l’intervalle [0,1] selon une loi uniforme.

On pourra d’abord présenter des algorithmes qui permettent à partir de cette fonction de fournir un entier aléatoire entre 0 et $N-1$ selon une loi uniforme, puis s’intéresser à la construction d’objets mathématiques classiques, comme un tableau de taille $M$ de nombres entiers aléatoires entre 0 et $N-1$. On pourra aussi s’intéresser à des exemples plus complexes, par exemple utiliser Python pour  créer  une  permutation  aléatoire  des  entiers  de  l’intervalle $[0,N-1]$,  etc.  On  peut  aussi envisager le lien avec la géométrie et utiliser Scratch pour dessiner des figures aléatoires dans le plan.

On  pourra  ensuite  utiliser  le  générateur  aléatoire  dans  le  cadre  d’algorithmes  classiques.  Par exemple,  certains  tris  sont  plus  efficaces  si  on  mélange  aléatoirement  les  données  avant  de  les trier.

Une autre utilisation consiste à tester l’efficacité d’algorithmes classiques sur des jeux de données aléatoires pour évaluer leur complexité en moyenne. La difficulté est ici de bien contrôler la loi de génération des données. Toute discussion avancée sur cette question est explicitement hors sujet, mais il est demandé au candidat d’être conscient du problème.

On peut aussi utiliser l’aléatoire pour des méthodes de résolution de type Monte-Carlo. Un exemple classique est le calcul de $\pi$. L’algorithme peut être facilement programmé en Python ou en Scratch. (Malheureusement, la convergence de la méthode simple est très lente.)

Une autre utilisation réside dans la simulation d’expériences probabilistes."

Capesman

#3 Re : Leçons de Capes » [Info 8] - Exemples d'algorithmes de tri. Comparaison. » 27-11-2018 20:30:05

Bonjour,

  Voici ce que dit le rapport 2018 sur cette leçon, fautes d'orthographe d'origine conservées!

"Cette  leçon  est  sans  doute  l'une  des  plus  attractive,  mais  c'est  aussi  l'une  des  plus  exigeante  à cause de la richesse du matériel disponible.

Une première difficulté est de définir rigoureusement la spécification du tri d'un tableau. En effet, il ne suffit pas que le tableau obtenu soit trié, il faut aussi que ses éléments soient les mêmes que ceux  du  tableau  de  départ.  C'est  un  peu  délicat à  spécifier  à  cause  de  la  présence  éventuelle d'éléments répétés. Une première contribution intéressante est de proposer une fonction qui prend en paramètre deux tableaux de même taille et qui teste si le second est une version triée du premier.

Cette leçon amène à exposer au moins un algorithme de tri élémentaire comme le tri par sélection, ou par insertion, ou à bulle ; développer longuement chacun de ces trois tris n’est en revanche pas attendu.

Ces implémentations sont délicates car la gestion des indices est une source majeure d'erreur. Le candidat devra justifier très soigneusement chacune des bornes par un invariant. Ces algorithmes sont  beaucoup  plus  simples  à  implémenter  en  distinguant  soigneusement  ce  qui  concerne  le parcours  du  tableau  («le  moteur»)  et  la  détection  de  la  terminaison  («l'échappement»).  Le
parcours gagnera à être implémenté par des boucles, alors que la terminaison gagnera à être gérée par des instructions d'échappement (
break ou return).

Suite à une étude de la complexité de l'algorithme élémentaire choisi, on peut évoquer au moins un algorithme de tri plus performant, comme le tri fusion ou le tri rapide. D’autres algorithmes spécifiques, adaptés quand les données ont une taille particulière, peuvent être aussi évoqués avec intérêt (voir par exemple le tri par base, ou radix sort). Un cas souvent négligé est celui où le tableau initial  ne  contient  qu'un  petit  nombre  donné  de  valeurs  qu'il  est  alors  possible  de  trier  en  temps  linéaire  en comptant le  nombre d'occurrences de chaque  valeur puis en reconstituant  le tableau final  à  partir  de  ce  décompte.  On  pourra  remarquer  que  l'utilisation  d'un  dictionnaire  Python  est particulièrement pratique pour programmer ce type d'algorithme.

Le terme « comparaison » utilisé dans l’intitulé peut renvoyer à la comparaison d’un tri de complexité quadratique à un tri de complexité $O(n\ln n)$),  mais peut également conduire le candidat à évoquer la question d’un tri « en place » ou non.


Capesman

#4 Re : Leçons de Capes » [Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications. » 27-11-2018 20:24:23

Bonjour,

  Le rapport du jury 2018 précise les attendus pour cette leçon :

"L'objectif  de  cette  leçon  est  la  présentation  des  algorithmes  classiques  sur  les  graphes.  Aucune connaissance théorique sur les objets manipulés ne sera demandée, mais le recul de niveau M1 doit permettre aux candidats de discuter du coût des algorithmes présentés. On pourra s'intéresser aux graphes orientés ou non orientés.

On pourra considérer plusieurs implémentations des  arbres : à l'aide de matrices d'adjacence, à l'aide de liste d'adjacence entrantes ou sortantes, etc.

Comme pour  les arbres, on pourra s'intéresser  aux algorithmes de parcours : en profondeur,  en largeur, etc.

On  pourra  aussi  s'intéresser  aux  problèmes  de  détermination  de  chemins  optimaux  dans  des graphes valués. L'algorithme le plus
célèbre est certainement celui de Dijkstra. Il en existe d'autres, par exemple l'algorithme de Floyd-Warshall qui ramène le problème au calcul des exposants d'une matrice. On pourra aussi s'intéresser à des problèmes de recherche de flot maximal dans un graphe
valué, quoiqu'ils soient un peu plus complexes.

On  pourra  aussi  envisager  des  problèmes  d'étude  de  la  structure  d'un  graphe,  par  exemple déterminer  la  composante  simplement  (ou  fortement)  connexe  d'un  nœud,  le  nombre  de composantes  connexes,  l'arbre des  composantes  connexes,  ou  encore  calculer  des  paramètres structurels comme le nombre chromatique, la taille de la plus grande clique, etc.

Un algorithme facilement programmable en Python est le parcours en profondeur ou en largeur, qui peut être ensuite utilisé pour compter le nombre de composantes connexes.

Capesman

#5 Re : Leçons de Capes » [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications. » 27-11-2018 20:21:27

Bonjour,

  Le rapport de jury 2018 comporte quelques éclaircissements sur les attendus de cette leçon :

"L'objectif  de  cette  leçon  est  la  présentation  des  algorithmes  classiques  sur  les  arbres.  Aucune connaissance théorique sur les objets manipulés ne pourra être demandée, mais le recul de niveau M1 doit permettre aux candidats de discuter du coût des algorithmes présentés.

On pourra s'intéresser aux algorithmes de parcours: en profondeur, en largeur, etc. On insistera sur les  liens  entre  le  parcours  en  profondeur  et  l'utilisation  d'une  pile,  le  parcours  en  largeur  et l'utilisation d'une file.

On pourra envisager les arbres étiquetés pour gérer arbres de recherche, et poser la question de leur équilibrage.
On pourra aussi faire le lien entre les arbres et la représentation des expressions arithmétiques, par  exemple.  On  pourra  discuter  de  l'interprétation  des  divers  ordres  de  parcours  d'arbres  par rapport à la présentation préfixée, infixée ou postfixée des expressions.

Pour une implémentation en Python, on pourra coder un arbre sous forme d'une liste de listes. Un
nœud est alors une liste contenant une étiquette et une liste de fils, éventuellement vide.

Un  algorithme  facilement  programmable  en  Python  dans  cette  approche  est
le  parcours  en  profondeur. Le parcours en largeur est plus complexe car il fait nécessairement appel à une file.
On  pourra  aussi  facilement  implémenter  les  opérations  sur  les  arbres  de  recherche  (sans rechercher l'équilibrage).

Capesman.

#6 Re : Leçons de Capes » [Info 4] - Exemples d’algorithmes de recherche dans un tableau ou une » 27-11-2018 20:18:06

Bonjour,

  Voici ce que dit le rapport du jury 2018 de cette leçon :

"Cette leçon a pour but de présenter des exemples de diverses situations typiques. Ces situations sont nombreuses et délicates. Il est donc important de prendre des exemples très simples et de les détailler avec la plus grande précision.

On peut s'intéresser d'abord à un tableau à une seule dimension. On peut rechercher un élément avec  une  certaine  propriété.    Il  est  important  que  la  recherche  s'arrête  dès  que  l'élément  a  été trouvé. On peut présenter différentes approches du traitement des conditions d'arrêt et discuter de leurs qualités d'un point de vue pédagogique.

On  peut  ensuite  s'intéresser  à  un  tableau  à  2  dimensions.  La  recherche  d'un  élément  avec  une  certaine  propriété  est plus complexe, puisqu'il faut s'assurer de sortir de l'ensemble des boucles imbriquées. Une méthode assez robuste est de n'utiliser qu'une seule boucle avec une approche orientée échappement.

La  recherche  dans  une  liste  est  souvent  plus  simple à  écrire  de  manière  récursive.  Un  exemple typique facilement programmable est la recherche récursive d'une valeur dans une liste.

On  peut  aussi  s'intéresser  aux  conditions  sur  le  tableau  ou  la  liste  qui  permettent  d'accélérer  la recherche : par exemple chercher une valeur dans un tableau ou une liste triée.

On  peut  aussi  envisager  une  configuration  plus  complexe.  Par  exemple,  chercher  la  première occurrence d'une valeur $a$ suivie d'une autre valeur $b$. La difficulté est ici de gérer les indices pour ne pas accéder à des indices hors des bornes du tableau. Par exemple, on peut se demander si une  image  bitmap  (considérée comme  un  tableau  bidimensionnel)  contient  une  sous-image donnée."

Capesman

#7 Re : Leçons de Capes » [Info 2] - Boucles : principes et exemples » 27-11-2018 20:15:04

Bonjour,

  Voici ce que le rapport du jury 2018 précise sur cette leçon  :

"Cette  leçon  a pour  but de présenter  les différentes structures de contrôle itératives, les relations entre elles et leurs utilisations typiques.

On  peut  commencer  par  distinguer  les  structures  itératives  bornées  et  non  bornées.  Dans  les premières, on connaît initialement le nombre d'itérations avant la terminaison, alors que dans les secondes, la terminaison est déterminée dynamique par un test.

Le modèle de structure itérative bornée est la boucle for. Il est important de souligner que la variable de  boucle  n'est  pas  une  variable  comme  les  autres.  En  Python,  sa  valeur  est  forcée  à  chaque itération. Un exemple typique d'utilisation facilement programmable est le calcul de la factorielle.

Le modèle de structure itérative bornée est la boucle while. Il se peut que l'itération ne termine pas. Un exemple typique d'utilisation est le calcul du logarithme en base 2 d'un entier $a$, le plus grand entier $n$ tel que $2^n\leq a$. On peut remarquer qu'une boucle for
peut s'écrire avec une boucle while, alors que l'inverse n'est pas possible.

On peut remarquer qu'une boucle while peut se réécrire à l'aide d'une fonction récursive. On peut  étudier  cette  transformation  à  partir  d'exemples.  On  peut  alors  s'intéresser  à  la  traduction  de  la boucle for ou se demander si tout fonction récursive peut se réécrire en une boucle while.

Un cas typique d'utilisation de la boucle while est le parcours d'un tableau pour trouver un élément qui vérifie une propriété donnée.  "

Capesman

#8 Re : Leçons de Capes » [Math 34] - Fonctions exponentielle et logarithme. Applications » 27-11-2018 20:10:38

Bonjour,
 
  Cette leçon a droit à un petit paragraphe dans le rapport de jury 2018 :

"Dans le cadre du recul niveau M1 attendu des candidats, des connaissances sur les fonctions logarithmes
autre que le logarithme néperien et leurs applications, ainsi que sur les autres fonctions exponentielles, sont
vivement souhaitées."

Capesman

#9 Leçons de Capes » [Math 7] - PGCD et PPCM dans $\mathbb Z$. Applications » 23-11-2018 11:20:31

capesman
Réponses : 0

Bonjour,

  Cette discussion est ouverte pour parler de la leçon du capes de mathématiques :  PGCD et PPCM dans $\mathbb Z$. Applications


Capesman.

#10 Leçons de Capes » [Math 6] - Multiples et diviseurs dans $\mathbb N$ - Nombres premiers » 23-11-2018 11:19:02

capesman
Réponses : 0

Bonjour,

  Cette discussion porte sur la leçon de capes : Multiples et diviseurs dans $\mathbb N$ - Nombres premiers.

Capesman.

#11 Re : Leçons de Capes » [Info 22] - Problèmes ... du cycle 4 pouvant être résolus... » 01-05-2018 06:19:00

Bonjour,

  En réalité, il y a beaucoup de problèmes aussi au cycle 4 qui peuvent être résolus de manière algorithmique. Tout dépend de la définition que l'on donne à algorithme. Utiliser un algorithme ne veut pas dire forcément se mettre devant un ordinateur et utiliser Scratch ou Python. On peut réaliser des algorithmes à la main, en utilisant un logiciel de géométrie dynamique, un tableur...
  Voici quelques exemples de situation possibles :
* déterminer si un nombre est premier (avec un tableur, en testant le reste dans la division euclidienne par tous les entiers inférieurs à sa moitié), ou déterminer tous les nombres premiers jusque 100 (par le crible d'Erathostène, algorithme que l'on peut mettre très facilement en pratique avec un papier et un crayon)
* problèmes de construction géométrique qui peuvent être simples et résolus à l'aide de Geogebra. On peut aussi penser aux frises et pavages, pour lesquels Scratch est particulièrement approprié
* exemple de résolution d'équation. Cette ressource Eduscol détaille une situation où un problème conduit à une résolution du premier degré $ax+b=cx+d$. Avant que les élèves ne maîtrisent le calcul littéral, un traitement possible du problème est par essais et ajustements.
* étude de fonctions et recherche d'extrema.

Il y en a sans doute beaucoup d'autres....

Capesman.

#12 Re : Leçons de Capes » [Math 16] - Périmètres, aires, volumes » 27-02-2018 20:41:09

Bonjour,

  Procéder comme tu le fais serait démontrer que tu n'as rien compris à ces notions! On ne "définit" pas l'aire d'un carré par $c^2$. L'aire d'un carré est égale à $c^2$!
Evidemment, c'est une leçon très difficile, pour laquelle je me garderai bien de donner des conseils trop précis, n'y ayant jamais passé un temps suffisant de réflexion. C'est une leçon à comprendre avec la thématique "grandeurs et mesures" des cycles 2, 3 et 4. C'est assez facile de définir la longueur d'un segment en prenant une longueur étalant et en utilisant la notion de réduction/agrandissement. Le périmètre de toutes les polygones s'en déduit aisément. C'est sans doute alors le bon moment de définir le nombre pi comme le rapport entre le périmètre d'un cercle (mais qu'est-ce que le périmètre d'un cercle!) et son diamètre. Il est clair qu'une activité avec des approximations de type Archimède du périmètre d'un cercle sont les bienvenus!
Il faut aussi se poser la question de ce qu'est l'aire d'une figure. Qu'est-ce que qui est préservé (par découpage, par isométrie, par agrandissement). Ayant fixé une unité d'aire (un carré unité), on doit être capable de démontrer les formules de l'aire d'un rectangle, d'un triangle... et peut-être même d'un disque???
On peut aussi se poser la question de savoir s'il faut parler d'intégrale dans cette leçon, pour calculer l'aire de domaines un peu plus compliqués????

Bref, beaucoup de questions à se poser!

Capesman.

#13 Re : Leçons de Capes » [Math 35] - Intégrales, primitives. » 28-10-2017 20:23:11

Bonsoir,

  Tu n'as pas l'air d'avoir les idées claires du tout sur cette partie du programme. Il ne faut pas confondre intégrale et primitive :
* une intégrale est un nombre. $\int_a^b f(t)dt$ est définie comme "l'aire sous la courbe" représentative de $f$, entre les droites $y=a$ et $y=b$.
* une primitive est une fonction. C'est l'opération "inverse" de la dérivation. Une primitive de $f$ est une fonction $F$, dérivable, et telle que $F'=f$.

Tout l'intérêt du théorème fondamental, c'est de faire le lien entre ces deux notions qui n'ont a priori rien à voir. Pour calculer $\int_a^b f(t)dt$, il suffit de connaître une primitive $F$ de $f$, et on a alors $\int_a^b f(t)dt=F(b)-F(a)$.
Certes, le théorème fondamental ne s'énonce pas exactement comme ci-dessus, mais c'est bien cela qu'il veut dire!

Capesman.

#14 Re : Leçons de Capes » [Math 18] - Proportionnalité et géométrie » 24-10-2017 06:17:50

Bonjour,

  Pas mal d'idées ont déjà été données plus haut. Il est clair que cette leçon s'articule autour des notions d'agrandissement/réduction, théorème de Thalès et homothétie. Cela occupe une bonne place dans les programmes du cycle 3 et du cycle 4, et cela permet de construire une leçon je pense. Parmi d'autres idées, tu as aussi la proportionnalité entre la longueur d'un arc de cercle, l'aire d'un secteur
angulaire et l'angle au centre (ceci permet par exemple de construire des patrons de cône). Tu as aussi la loi des sinus (dans un triangle, $a/\sin(\widehat A)=b/\sin(\widehat B)=c/\sin(\widehat C)$) par exemple...

Capesman

#15 Re : Leçons de Capes » [Info 17] - Exemples d'activité manipulant des images bitmap » 22-09-2017 20:17:15

Bonjour,

  Voici ce que dit le rapport du jury 2017 de cette leçon :

"l s'agit ici de présenter des activités liées à l'image dans un cadre très simplifié. Une image bitmap peut être considérée comme un
tableau bidimensionnel de valeurs prises dans un ensemble fini : 0/1 pour les images binaires, trois nombres entiers entre 0 et 255 pour les images RVB sur 24 bits, etc.

Les  candidats  peuvent  expliquer  le  lien  entre  les  transformations  classiques  d'images et  les manipulations  des  tableaux  associés.  Ces  transformations  peuvent  être  faites  point  à  point : extraction de composantes, renforcement de couleur, application d'un filtre, etc. Elles peuvent aussi concerner la géométrie de l'image : rotation, symétrie, dilatation, contraction, rognage, etc. Elles peuvent  aussi  concerner  les  objets  représentés  par  l'image :  remplissage  d'une  composante connexe par une couleur, extraction des contours, comptage des composantes connexes, etc.

Les candidats sont bien sûr invités à faire le lien avec leurs expériences de traitement d'images dans les logiciels classiques : Photoshop, Gimp, Paint, etc. Ils peuvent aussi s'intéresser à des actions qui mettent en jeu plusieurs images, par exemple en considérant la transparence
et en superposant les images, etc.

Un exemple d’algorithme adapté à cette leçon est la transformation d'une image carrée par une symétrie centrale, sans utiliser d'image auxiliaire (transformation «en place»). Dans tous les algorithmes présentés, on veille à faire preuve de rigueur dans la définition des
indices de boucles et dans les accès aux pixels de l'image."

Capesman

#16 Re : Leçons de Capes » [Info 16] - Codage et traitement numérique des couleurs » 22-09-2017 20:15:19

Bonjour,

  Voici ce que dit le rapport de jury de cette leçon :
"Cette leçon peut être traitée à différents niveaux et illustrée par toutes sortes d’algorithmes. Dans cette leçon, il est judicieux de s’intéresser aux images en niveaux de gris (les algorithmes pertinents sur ces images pouvant être appliqués sur les composantes d’une image en RVB), mais on ne saurait se limiter à celles-ci.Les notions de synthèse soustractive vs. synthèse additive des couleurs peuvent être illustrées par
des exemples concrets.

Le  modèle  mathématique  du  cube  des  couleurs  est  une  base  conceptuelle  fort  utile  pour  cette leçon. On  peut  consulter  à  ce  sujet  plusieurs  des  ressources pédagogiques  destinées  aux  classes  de Première STD2A"

Voici quelques liens vers les ressources pédagogiques dont le rapport parle :
* Eduscol 1
* Eduscol 2

Capesman

#17 Re : Leçons de Capes » [Info 15] - Programmation événementielle : principe et applications » 22-09-2017 20:11:21

Bonjour,

  Voici ce que dit le rapport de jury 2017 de cette leçon :

"Cette leçon est très ouverte, et son contenu peut librement être adapté à la culture du candidat. Il s'agit essentiellement de présenter les principes de programmation d'un système réactif, dont les actions sont déterminées par le comportement de son environnement. L’environnement Scratch permet d’illustrer assez facilement les événements : contact d’un lutin avec le bord ou avec un autre lutin, appui sur une touche du clavier, réception d’un son fort, etc.

Les questions intéressantes dans ce domaine sont liées à la gestion des événements entrants. Par exemple: Quelle est la nature des événements captés? Que se passe-t-il si deux événements sont détectés en même temps? Comment les gérer en tenant compte de leurs priorités? Que se passe-t-il  si  un  événement  est  perçu  par  deux  capteurs  à  la  fois?  Par  exemple,  deux  boutons  qui  se
recouvrent en Scratch. Que se passe-t-il si un événement attendu ne se produit pas? Combien de temps attendre avant de décider qu'il ne viendra jamais?

Un exemple d’algorithme adapté à cette leçon est une petite tortue Logo en Scratch. Une boucle lit un caractère au clavier et déplace la tortue en fonction des caractères captés. On peut ajouter des caractères pour émettre un miaulement ou encore les événements souris, éventuellement par un processus concurrent."

Capesman

#18 Re : Leçons de Capes » [Info 8] - Exemples d'algorithmes de tri. Comparaison. » 22-09-2017 20:09:19

Bonjour,

  Voici ce que dit le rapport de jury 2017 de cette leçon :

"Cette leçon amène à exposer au moins un algorithme de tri élémentaire comme le tri par sélection, ou par insertion, ou à bulle;  développer longuement chacun de ces trois tris n’est en revanche pas attendu. Suite à une étude de la complexité de l’algorithme élémentaire choisi, on peut évoquer au moins  un algorithme de tri plus performant, comme le tri fusion ou le tri rapide. D’autres algorithmes spécifiques, adaptés quand les données ont une taille particulière, peuvent être aussi évoqués avec intérêt (voir par exemple le tri par base, ou radix sort).

Le  terme  «comparaison»  utilisé  dans  l’intitulé  peut  renvoyer  à  la  comparaison  d’un  tri  de complexité quadratique à un tri de complexité $O(n\ln n)$, mais peut également conduire le candidat à évoquer la question d’un tri «en place» ou non."

Capesman

#19 Re : Leçons de Capes » [Info 11] - Exemples de détermination de la complexité.... » 22-09-2017 20:07:38

Bonjour,

  Voici ce qu'en dit le rapport du jury (2017 et 2018):

"Cette leçon est orientée vers l'utilisation pratique de méthodes d'évaluation de la complexité, avec comme objectif le choix entre plusieurs algorithmes pour résoudre un problème donné. Le candidat précise clairement ce qu’il choisit comme mesure de la complexité : le nombre de comparaisons, le nombre d’appels, etc. Le candidat doit savoir équiper le programme qu’il présente d’un compteur qui permette la mesure expérimentale de sa complexité.

Si le candidat utilise la notion d’ordre de grandeur et la notation de Landau $O(f)$, il doit savoir la définir et justifier l'ordre de grandeur des fonctions classiquement rencontrées dans ce domaine, par exemple que $\frac{n(n+1)}2$ est un $O(n^2)$.

On pourra mettre en évidence que le comportement d'un algorithme dans un cas donné  peut  être très variable,  et éventuellement très différent de son comportement dans le pire cas. Le choix d'un algorithme ne doit pas être seulement dicté par sa complexité en pire cas,
mais  aussi  par  une  définition  soigneuse  de  l'espace  des  cas  considérés.  Par  exemple,  certains algorithmes de tri sont très efficaces si le tableau est déjà «presque trié», alors que c'est indifférent pour d'autres. Un problème  classique  est  bien  sûr  le  tri  d'un  tableau  de  taille  $N$,  mais  on  peut  aussi  penser  à  la recherche  d'un  motif  dans  une  chaîne  de  caractère,  le  calcul  de  suites  numériques  récurrentes (Fibonnaci, etc.), les opérations sur les listes (reverse, etc.), etc."

Capesman

#20 Re : Leçons de Capes » [Info 25] - Exemples d'algorithmes de chiffrement et de déchiffrement » 22-09-2017 20:05:06

Bonjour,

  Voici ce que dit le rapport du jury à propos de cette leçon :
"L'objectif de cette leçon est de présenter des systèmes de chiffrement et de déchiffrement simples en insistant sur l'étude de leurs propriétés, plutôt que sur leur efficacité. Le niveau mathématique attendu pour cette leçon est élémentaire. Toute discussion avancée sur l'arithmétique modulaire, les courbes elliptiques ou l'utilisation des technologies quantiques est catégoriquement hors sujet.

Comme toute leçon d’exemples, le candidat doit présenter plusieurs exemples effectifs. On peut d'abord présenter les systèmes de cryptage lettre à lettre (code de César, ROT13...) et discuter de leur utilisation pratique. La question du déchiffrement est aussi intéressante que celle
du chiffrement.

On  peut  ensuite  présenter  les  systèmes  de  cryptage  à  clé  secrète,  en  particulier  le  XOR  et quelques-unes de ses multiples variantes. On pourra souligner l'aspect involutif du codage XOR. Pour chaque système de cryptage lettre à lettre et pour le cryptage symétrique XOR, on peut présenter les algorithmes de manière détaillée en utilisant un tableau de caractères ou de bits.
Dans le cas des caractères, on peut détailler comment passer d'un caractère A-Z à un code ASCII, puis à un nombre entre 0 et 25 et réciproquement.

Un algorithme facilement programmable dans cette leçon est le chiffre de César. On peut éventuellement présenter les systèmes de cryptage à clé publique et la notion de protocole cryptographique, en séparant bien le principe de ces systèmes des particularités des fonctions
cryptographiques utilisées. On peut montrer que ces systèmes peuvent aussi être utilisés pour l'authentification (signature).

Une autre piste de discussion est la stéganographie qui permet de cacher une donnée dans une image. On peut en décrire l'idée générale, puis détailler l'algorithme qui cache un message dans une image bitmap RVB et qui le retrouve ensuite."

Capesman

#21 Re : Leçons de Capes » [Info 13] - Représentation binaire des nombres : formats... » 22-09-2017 20:02:21

Bonjour,

  Voici ce que dit le rapport du jury 2017 à propos de cette leçon :
"Cette leçon est très ouverte, et son contenu peut librement être adapté à la culture du candidat.

Cependant, elle doit au moins contenir une description précise des décompositions décimales et binaires d'un nombre entier positif sous la forme d'une somme de puissances de la base $b$ avec des coefficients entiers entre 0 et $b-1$. Le candidat peut expliquer que la base 10 et la base 2 sont deux cas particuliers usuels, mais que la base 8 ou la base 16 sont intéressantes et que d'autres bases sont aussi utilisées (60 pour la mesure du temps, par exemple).

Le  candidat  peut  écrire  un  algorithme  pour  convertir  une  écriture  de  base  10  en  base  2 et réciproquement. Il peut comparer le nombre de chiffres de la représentation d'un nombre en base 10 et en base 2.

Le candidat peut également présenter des formats pour les entiers signés (bit de signe, complément à 2, etc.), les réels flottants (format
IEEE 754, etc.), ou s'intéresser aux entiers en précision arbitraire (Python, OCaml BigNum), etc.

Un exemple d’algorithme adapté à cette leçon est celui qui prend en entrée un entier positif et
renvoie la chaîne de caractères qui constitue son écriture hexadécimale."

Capesman

#22 Re : Leçons de Capes » [Info 1] - Logique booléenne et instructions conditionnelles... » 22-09-2017 19:59:21

Bonjour,

Voici ce que dit le rapport du jury à propos de cette leçon :
"Cette leçon a pour but de présenter les bases de la logique booléenne et l'utilisation d'expressions booléennes dans les structures de choix
(if) et itération (for, while). Les deux parties de la leçon doivent donc être fortement liées. Pour la logique booléenne,  le  candidat  peut  présenter les principaux  opérateurs (négation,  conjonction,  disjonction,  etc.) et  l'évaluation  d'une  expression booléenne  construite  à  l'aide  de  ces  opérateurs  ainsi  que  les  principales  équivalences  qui permettent de simplifier les expressions complexes.
Pour   les   instructions   conditionnelles,   les   notions   ci-dessus   peuvent   être   appliquées   à   la simplification des compositions de structures. Par exemple, si b alors P sinon (si b alors Q sinon R) peut être simplifiée en si b alors P sinon R.

De  même  on  peut  illustrer  la  différence  entre  les  opérateurs  &  et  and  de
Python,  en  montrant comment l’un et l’autre pourraient être simulés par des instructions conditionnelles bien écrites.

Un exemple d’algorithme qu’on peut présenter dans le cadre de cette leçon est un algorithme qui
teste si une fonction booléenne $f(a,b,c)$ est vraie quelles que soient les valeurs booléennes de $a$, $b$ et $c$."

#23 Re : Leçons de Capes » [Info 12] - Exemples de démarches...correction d'un algorithme » 22-09-2017 19:55:57

Bonjour,

  Voici ce que dit le rapport du jury 2017 à propos de cette leçon (complété en 2018) :
"Cette  leçon  est  orientée  vers  l'utilisation  pratique  et  concrète  de  telles  démarches  et  méthodes. L'évaluation de la leçon sera fondée sur la précision et la diversité des aspects présentés et non sur la difficulté des développements théoriques. On ne considère ici que des algorithmes itératifs, au moins dans un premier temps."

"Cette leçon doit présenter des utilisations pratiques et concrètes de telles démarches et méthodes en les appliquant à un ensemble d’algorithmes concrets. Le candidat est attentif à la précision et à la diversité des aspects présentés et non à la difficulté des développements théoriques. Le  candidat  peut  s'appuyer  sur  l'introduction  d'assertions  logiques  dans  la  description  de  son
algorithme pour exprimer les propriétés vérifiées aux points de contrôle intéressants.
Dans  le  cas  des  itérations  non  bornées (while),  on  insistera sur  les  notions  de  variant  et d'invariant. Le candidat doit pouvoir exhiber un variant et un invariant des boucles dans les cas classiques: parcours de tableau, tri, calcul de factorielle, etc.

Pour prouver la correction, le candidat peut montrer, sur des exemples simples, comment dériver la spécification du résultat à partir des assertions, en particulier les invariants de boucle. Le candidat peut également faire le lien avec la définition de suites récursives $u_{n+1}=f(u_n)$. Une extension au cas des suites à deux paramètres $u_{n,p}$ est envisageable, mais plus délicate."

#24 Re : Leçons de Capes » [Info 18] - Exemples d'activité manipulant des objets géométriques... » 22-09-2017 19:53:11

Hello,

  Voici ce que dit le jury de capes à propos de cette leçon :

"L'objectif de cette leçon est de présenter des algorithmes de gestion d'objets géométriques dans le plan et dans l'espace, avec des applications aux jeux vidéos et à la synthèse d'images. Le matériel mathématique  pour  ce  sujet  est  donc  essentiellement  celui  des  leçons  de  géométrie  en mathématiques.

On peut commencer par s'intéresser au cas des rectangles définis par les coordonnées de deux sommets opposés et à un algorithme de calcul de l'intersection et de l'enveloppe rectangulaire de deux tels rectangles, en s’attachant à la plus grande précision dans le calcul des indices des pixels. On peut étendre au cas 3D et ou à une liste de rectangles, ou encore à d’autres formes, polyèdres
ou sphères.

On peut aussi s'intéresser au déplacement d'objets géométriques pour déterminer quelle partie de l'écran
doit être redessinée quand on déplace un rectangle dans une pile de rectangles (cette opération est cruciale dans les systèmes de gestion de fenêtres des interfaces graphique). Une autre source d'inspiration est la simulation de phénomènes physiques. Le cas le plus simple est probablement une boule (carrée) qui se déplace sur une table de billard avec une vitesse constante en rebondissant sur les bords, un peu comme dans le jeu Pong. On pourra par exemple s’intéresser au déplacement d’un personnage (rectangulaire ou plus complexe) devant un paysage fixe, ou au contraire au défilement d’un paysage derrière un personnage qui reste fixe sur l’écran.

On peut s'intéresser à ce qui se passe si la vitesse est peu à peu amortie, s'il y a plusieurs boules qui s'entrechoquent, si le billard se déforme avec des trous qui apparaissent, etc."

Capesman

#25 Re : Leçons de Capes » [Math 32] - Théorème des valeurs intermédiaires. Applications. » 13-09-2017 20:54:23

Bonjour,

  Cette leçon a droit à un paragraphe dans le rapport du jury 2017 :
"Cette leçon repose sur un théorème dont il convient, avec un recul de niveau M1, d’étudier la démonstration (en s’appuyant par exemple sur l’axiome de la borne supérieure) et d’en apprécier le caractère existentiel et non-constructif. Au-delà du théorème et de ses applications immédiates, apparaît une interrogation sur les images des intervalles par une fonction continue : que peut-on dire selon le type d’intervalle (ouvert, fermé, borné ou non) et le type d’image (directe ou inverse) ? "

J'avoue ne pas comprendre tout à fait ce que le jury veut dire par "d'en apprécier le caractère existentiel et non-constructif". Il est clair que le jury attend que l'on connaisse une preuve du théorème des valeurs intermédiaires. On peut en donner une preuve à l'aide de l'axiome de la borne supérieure, et là je comprends que c'est "non-constructif". Mais il y a aussi une preuve par dichotomie, à partir de suites adjacentes, et cette preuve est tellement constructive qu'on peut en déduire très facilement un algorithme!

Capesman.

Pied de page des forums