Forum de mathématiques - Bibm@th.net

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.

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

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.

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.

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

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

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

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

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."

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.

Bonjour,

Cette leçon a droit à un paragraphe dans le rapport du jury 2017 :
"Son intitulé incite à sortir du cadre linéaire (équations ou inéquations s’y ramenant, mais aussi équations ou inéquations trigonométriques). Les exemples proposés doivent illustrer des méthodes de résolution différentes. ".

Capesman.