La Journée de la Régionale

La Journée de la Régionale APMEP d’Aix-Marseille a eu lieu samedi 18 mai 2019 sur le site Saint-Charles de l’université de Provence à Marseille.

La matinée a été consacrée à deux ateliers-conférences et l’après-midi à une conférence suivie de l’assemblée générale.

Le petit déjeuner du matin ainsi que le repas de midi ont été l’occasion de se retrouver dans un cadre agréable et convivial.

Les trois conférences auxquelles nous avons assistées étaient en prise directe avec les programmes actuels : bien sûr celle de Bernard Egger qui nous a présenté le nouveau système d’options en lycée, mais aussi celle de Gérard Lopez sur de surprenantes propriétés des nombres premiers qui intéresseront les élèves de collège, et enfin la conférence de Kevin Perrot sur l’algorithmique théorique en liaison avec la nouvelle option d’informatique au lycée.

Atelier-conférence de Bernard EGGER

La réforme des lycées qui concerne déjà les élèves entrés en seconde l’année dernière, n’est pas un prolongement de la réforme des collèges, mais présente son originalité propre.

La classe de seconde gardera sa forme indifférenciée (avec de nouveaux programmes dans chaque matière).

Mais pour les classes de première et terminale de la voie générale, ce sera la fin des anciennes filières. Beaucoup d’élèves étaient obligés, avec l’ancien système, de passer par la formation maths-physique-chimie-SVT pour pouvoir accéder à certaines études ayant peu à voir avec ces matières. Le but de la réforme est de casser ce système des séries pour permettre une meilleure adéquation entre les études faites au lycée et celles envisagées par l’étudiant par la suite.

Le principe sera celui d’un enseignement par options : l’élève suivra un enseignement de tronc commun auquel il ajoutera trois spécialités de son choix en première, puis n’en gardera plus que deux en terminale.

Il n’y a (pratiquement) pas de maths dans le tronc commun ; il y aura en première une spécialité mathématiques mais aussi une spécialité « Numérique et science informatique ».

En fin de première, les élèves choisiront pour la classe terminale deux spécialités à conserver.

En ce qui concerne les mathématiques, le système retenu pour la terminale est relativement compliqué car les maths seront en spécialité (6h) et il aura deux options :

1. Une option « mathématiques complémentaires » (3h) pour des élèves n’envisageant pas d’études axées sur les mathématiques (médecine, professeur d’écoles ?, etc.) ; elle ne pourra être prise que si les élèves ont suivi la spécialité maths en première. Le futur programme de cette option devrait s’articuler par thème. Elle sera dans tous les lycées, donc « financée » par les DGH.
2. Une option « mathématiques expert » (3h) qui peut être prise que par les élèves qui ont la spécialité maths en terminale, du coups cela leur fait 9h de maths. Ne sera pas dans tous les lycées, car elle sera prise sur l’enveloppe de fonctionnement des établissement. Enveloppe qui sert pour toutes les options de la seconde à la terminale et pour les dédoublements.

Questionnements :

1. Comment organiser l’enseignement de l’option « mathématiques complémentaires » où seront mélangés des élèves qui veulent s’orienter vers des filières économiques et d’autres scientifiques ?
2. L’option « mathématiques expert » devant être créée sur les fonds propres des établissements ne sera pas garantie partout.
3. Les filières maths-physique des universités et des classes préparatoires pourront-elles exiger pour leur recrutement d’être passé par l’option « math expert » ?

Quelques liens :

1. Sur la réforme du lycée et les mathématiques
2. Sur la réforme du baccalauréat
3. L’APMEP et la réforme
4. Le manifeste commun à l’APMEP et la SMF

Atelier-conférence de Gérard LOPEZ

Quel est le nombre premier qui apparaît le plus souvent comme $k^{ième}$ facteur dans la décomposition d’un nombre entier en produit de facteurs premiers ?

Par exemple pourquoi le nombre 23 qui est le 9^e nombre premier, est le nombre qui apparaît le plus souvent comme 5^e facteur premier d’un entier ?

Dans une première partie Gérard Lopez a rappelé quelques propriétés remarquables des nombres premiers, puis dans une seconde partie il a étudié pour les premiers nombres premiers, leur probabilité d’apparition comme $k^{iéme}$ facteur.

 
Première partie
Pour avoir plus de détails sur cette première partie, vous pouvez télécharger l’exposé de Gérard Lopez.

Après avoir rappelé la définition d’un nombre premier et cité le théorème de décomposition (dû à Euclide), il a énuméré quelques curiosités qui pourront intéresser les collègues de collège présentant les nombres premiers à leurs élèves.

• Si on représente les nombres entiers sur un quadrillage par un rectangle, les nombres premiers n’ont que la seule représentation « linéaire ».
• La formule $x^2+x+41$ génère $40$ nombres premiers successifs (Euler).
• Le nombre qui s’écrit en base dix $11\cdots 1$ ($k$ fois le chiffre $1$) est premier pour $k=2, 19, 23, 317, ...$.
• La spirale de Stanislaw Ulam : après avoir disposé la suite des nombres entiers en spirale comme ci-dessous, entourer les nombres premiers ; on constatera alors des alignements diagonaux surprenants.

  

• L’infinitude de l’ensemble des nombres premiers est un résultat puissant dont la démonstration (due à Euclide) est pourtant simple et permet de réfléchir à la notion d’infini en mathématiques.

G. Lopez a ensuite cité quelques résultats moins élémentaires (mais classiques) issus de la théorie analytique des nombres entiers.

 
Seconde partie
Pour le lecteur qui voudrait approfondir ce sujet, vous pouvez télécharger l’exposé détaillé de Gérard Lopez

Le problème qui nous occupe ici apparaît dans un ouvrage du mathématicien québécois Jean-Marie de KONINCK intitulé « Les nombres qui nous fascinent » aux éditions Ellipse.

Prenons un entier $n$ et sa décomposition en facteurs premiers : $n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots$ avec $p_i$ le $i^{iéme}$ nombre premier de la décomposition de $n$.

Notons $\lambda_k(p)$ la probabilité pour que $p$ soit le $k^{ième}$ facteur de la décomposition de $n$.

• $p=2$ : $\lambda_1(2)=\frac{1}{2}$
  puisqu’un entier sur deux est pair ; et pour $k>1$, $\lambda_k(2)=0$.
• $p=3$ : $n$ est divisible par $3$ une fois sur trois ;
  $3$ sera premier facteur si $n$ est impair, second facteur si $n$ est pair :
  $\lambda_1(3)=\frac{1}{3}(1-\frac{1}{2})=\frac{1}{6}$ et
  $\lambda_2(3)=\frac{1}{3}\times\frac{1}{2}=\frac{1}{6}$ et pour $k>2$, $\lambda_k(3)=0$.
• $p=5$ : $n$ est divisible par $5$ une fois sur cinq
  donc on aura :
  $\lambda_1(5)=\frac{1}{5}(1-\frac{1}{2})(1-\frac{1}{3})=\frac{1}{15}$
  (Divisible par $5$ et pas par $2$ ni par $3$)

$\lambda_2(5) = A + B$ avec pour $A$ (resp. pour $B$) le facteur $2$ (resp.$3$) mais pas le facteur $3$ (resp. $2$).

$A=\frac{1}{5}\times\frac{1}{2}(1-\frac{1}{3})=\frac{1}{15}$,
$B=\frac{1}{5}(1-\frac{1}{2})\frac{1}{3}=\frac{1}{30}$
et $\lambda_2(5)=\frac{1}{10}$.

$\lambda_3(5)=\frac{1}{5}\times\frac{1}{2}\times\frac{1}{3}=\frac{1}{30}$

Remarque :
On observe que $\lambda_1(5)+\lambda_2(5)+\lambda_3(5)=\frac{1}{5}$ ;
plus généralement si $p_i$ est le $i^{ième}$ nombre premier on a
$\sum_{k=1}^i \lambda_k(i) = \frac{1}{p_i}$ puisque la somme des probabilités pour que $p_i$ soit $k^{ième}$ facteur, de $k=1$ à $i$ est égal à la probabilité que le nombre soit divisible par $p_i$. Cela nous donne un moyen de vérification pour nos calculs.

Jusqu’ici, les résultats sont conformes à l’intuition : $2$ est le premier facteur le plus probable, $3$ le second facteur le plus probable, et $5$ le troisième facteur le plus probable.

Voyons si $7$ est le quatrième facteur le plus probable.

• $p=7$ : nous donnons les calculs sans explication.
  $\lambda_1(7)=\frac{1}{7}\times\frac{1}{2}\times\frac{2}{3}\times\frac{4}{5}=\frac{8}{210}$
  $\lambda_2(7)=A+B+C=\frac{1}{15}$ avec :
  $A=\frac{1}{7}\times\frac{1}{2}\times\frac{2}{3}\times\frac{4}{5}=\frac{4}{105}$,
  $B=\frac{1}{7}\times\frac{1}{3}\times\frac{1}{2}\times\frac{4}{5}=\frac{2}{105}$,
  $C=\frac{1}{7}\times\frac{1}{5}\times\frac{1}{2}\times\frac{2}{3}=\frac{1}{105}$
  $\lambda_3(7)=D+E+F=\frac{1}{30}$ avec :
  $D=\frac{1}{7}\times\frac{1}{2}\times\frac{1}{2}\times\frac{4}{5}=\frac{2}{105}$,
  $E=\frac{1}{7}\times\frac{1}{2}\times\frac{1}{5}\times\frac{2}{3}=\frac{1}{105}$,
  $F=\frac{1}{7}\times\frac{1}{3}\times\frac{1}{5}\times\frac{1}{2}=\frac{1}{210}$
  $\lambda_4(7)=\frac{1}{7}\times\frac{1}{2}\times\frac{1}{3}\times\frac{1}{5}=\frac{1}{210}$
   
  On constate que $7$ a autant de chances que $5$ d’être troisième facteur.

Si on continue les calculs pour $11$, $13$, $17$ puis $19$ (qui sont naturellement fastidieux), on se rend compte que les plus petits (comme $11$) ne sont pas les mieux placés.

On a par exemple les inégalités :
$\lambda_4(7)<\lambda_4(11)<\lambda_4(13)$ ; $13$ est le $4^{ième}$ facteur le plus fréquent.

De même :
$\lambda_4(17)=\frac{206}{36465}<\lambda_4(19)=\frac{1308}{230945}<\lambda_4(13)=\frac{31}{5005}$

Les calculs des $\lambda_k(23)$ pour arriver au résultat annoncé en début d’exposé ($23$ est le $5^{ième}$ facteur le plus fréquent) sont bien sûr très longs.

Le $6^{ième}$ facteur le plus fréquent est $47$ ($15^{ième}$ nombre premier) et le $7^{ième}$ est $113$ ($30^{ième}$ nombre premier).

Conférence de Kevin PERROT

Ordinateurs, calcul, algorithmes, programmes.
Algorithme : notion abstraite, indépendante de toute machine.
Programme : notion concrète ; ce qui sera traité par l’ordinateur.

Nous allons aborder deux notions : celle de complexité et celle de calculabilité. On va se restreindre à considérer seulement des problèmes de décision (réponse par oui/non) ; en fait on peut toujours se ramener à un problème de décision.

Exemples de problèmes (de décision) :

1. Tests de primalité : en entrée un entier $n$ ; en sortie oui/non ($n$ est-il premier ?)
2. Clique (ensemble des sommets d’un graphe reliés deux à deux) : en entrée un graphe $G$ et un entier $k$ ; en sortie : existe-t-il une clique de taille $k$ ?
3. Independent set (ensemble des sommets d’un graphe sans liens mutuels) : en entrée un graphe $G$ et un entier $k$ ; en sortie : existe-t-il un independent set de taille $k$ ?
4. Satisfiabilité (ou problème SAT) : en entrée une formule de logique propositionnelle $\Phi$ comportant un certain nombres de paramètres $x_1, x_2, \dots, x_k$ ; par exemple : $\Phi = (x_1\vee x_2) \wedge (\neg x_1\vee x_3) \wedge (\neg x_1\vee \neg x_2)$
   en sortie : existe-t-il des valeurs Vrai/Faux pour les $x_i$ qui satisfont la formule $\Phi$ ? On parle de problème 2-SAT, 3-SAT,… selon le nombre maximum de variables par disjonction.
5. Problème de l’arrêt : en entrée un programme $P(E)$ avec un ensemble de paramètres $E$ ; en sortie : le programme $P(E)$ va-t-il s’arrêter ?

Pour formuler ce dernier problème, il faut pouvoir encoder un programme : on se donne un alphabet (un ensemble de symboles comme par exemple des nombres, des parenthèses, des accolades etc.) ; les entrées seront des mots sur cet alphabet et un langage sera un ensemble de mots.

La complexité : Quel est le meilleur algorithme pour résoudre un problème ?

La complexité d’un algorithme est le « temps de calcul » dans le « pire des cas » (compte tenu des paramètres), en fonction de la taille de l’entrée (on entend par « temps de calcul » le nombre d’instructions exécutées par l’ordinateur, la notion devant être indépendante de la machine). Le résultat est exprimé en notation de Landau.

Exemple du test de primalité :

Le programme le plus immédiat prend en entrée un entier $n$ et exécute :

$i \leftarrow 2$

tant que $i \leq \sqrt{n}$ faire :

----- si $i | n$ répondre $non$

----- sinon $i \leftarrow i+1$

fin tant que

répondre $oui$

Ce programme a une complexité en $O(n^\frac{1}{2})$.

Un algorithme est dit efficace si sa complexité est une fonction polynomiale de la taille de l’entrée. La structure algébrique des polynômes fait que si on combine plusieurs algorithmes efficaces on obtient encore un algorithme efficace. En 2002 on a trouvé un test de primalité polynomial en $O(n^{12})$ (Agrawal, Kayal, Saxena).

Les problèmes SAT : 2-SAT est efficace, mais 3-SAT n’est pas efficace.

On note $\mathbf{NP}$ l’ensemble des problèmes pour lesquels il existe un algorithme polynomial pour vérifier une solution, et on note $\mathbf{P}$ l’ensemble des problèmes pour lesquels il existe un algorithme polynomial pour trouver une solution.
On sait que $\mathbf{P}\subset\mathbf{NP}$ , mais on ne sait pas si $\mathbf{P}=\mathbf{NP}$ (l’institut de mathématiques Clay a proposé en 2000 d’offrir un million de dollars à qui démontrerait cette conjecture).

On note aussi $\mathbf{coNP}$ l’ensemble des problèmes pour lesquels il existe un algorithme polynomial pour prouver qu’il n’y a pas de solution. On ne connaît pas les liens d’inclusion entre $\mathbf{coNP}$ et $\mathbf{P}$ ou $\mathbf{NP}$.

La calculabilité : Existe-t-il un algorithme pour résoudre un problème donné ?

Il existe des problèmes pour lesquels il n’existe aucun algorithme pour les résoudre.

D’abord quelques rappels de théorie des ensembles :

Le cardinal de l’ensemble $\mathbb{N}$ des entiers naturels est noté $\aleph_0$ et celui de l’ensemble $\mathbb{R}$ des réels est noté $\aleph_1$.

Rappelons que $\aleph_1$ est aussi le cardinal :

• De l’ensemble $[0,1[$
• De l’ensemble des suites infinies de nombres entiers
• De l’ensemble des applications de $\{0,1\}$ dans $\mathbb{N}$
• De l’ensemble des parties de l’ensemble $\mathbb{N}$

Et que l’on a de ce fait $\aleph_1 = 2^{\aleph_0}$.

Le théorème de Cantor dit que $\aleph_0<\aleph_1$ (inégalité stricte).

La démonstration est classique : par l’absurde, si on suppose qu’il y a une bijection de l’ensemble $\mathbb{N}$ sur $[0,1[$ :
$k \rightarrow 0,a_{k1}a_{k2}a_{k3}\cdots$ avec $a_{kj}\in \{0,1\}$ (écriture binaire d’un élément de $[0,1[$), on construit par le procédé de la diagonale le nombre $0,b_{1}b_2b_3\cdots$ avec $bi=1-aii$ ; ce nombre n’est l’image d’aucun élément de $\mathbb{N}$ par la bijection précédente.

Revenons au codage des programmes : un alphabet étant fini, l’ensemble des mots qu’on peut écrire sur cet alphabet (et donc l’ensemble des algorithmes) est dénombrable (cardinal $\aleph_0$). Par contre l’ensemble des langages sur cet alphabet (ensemble des ensembles de mots) et donc aussi l’ensemble des problèmes a pour cardinal $\aleph_1$. D’après le théorème de Cantor, il existe donc des problèmes (dits problèmes indécidables) pour lesquels il n’existe pas d’algorithme pour les résoudre.

Un exemple de problème indécidable : le problème de l’arrêt.

Rappelons ce qu’est le problème de l’arrêt $P_{arret}$ : il prend en entrée un programme $P$ et une entrée $E$ pour le programme $P$ ; en sortie oui/non selon que, lorsqu’on lance le programme $P$, il s’arrête ou non.
Par l’absurde, supposons que le programme $P_{arret}$ soit décidable. Nous allons alors construire le programme suivant $P_{diagonal}$ prenant en entrée un programme $P$ :

Si $P_{arret}(P)$ retourne oui

---------- $P_{diagonal}(P)$ entre dans une boucle infinie

Sinon

---------- $P_{diagonal}(P)$ retourne « oui »

Passons à ce programme l’entrée $P_{diagonal}$ donc calculons $P_{diagonal}(P_{diagonal})$ : ce programme entre dans une boucle infinie si et seulement si $P_{arret}(P_{diagonal})$ retourne oui donc si et seulement si $P_{diagonal}$ s’arrête ; d’où la contradiction. $P_{arret}$ est indécidable.

L’Assemblée Générale

L’Assemblée Générale de l’association a été présidée par Jean-Baptiste CIVET, président de la Régionale.

Après avoir présenté le bilan financier ainsi que le compte-rendu d’activité pour l’année scolaire en cours (vous trouverez ci-dessous ces documents à télécharger), nous avons abordé quelques sujets qui vont impacter le déroulement de l’année qui suit :

• Nous avons amélioré nos outils de communication au sein de l’association : création d’une liste de discussion pour permettre aux membres du bureau élargi d’échanger facilement, et création d’un outil de diffusion de l’information auprès des adhérents et sympathisants de l’académie.
  Merci à Alain Barnier pour ce travail.

• Nous avons également soulevé le problème de l’hébergement de l’association pour l’année prochaine, le local de la FRUMAM devant âtre libéré pour des travaux.

• Enfin nous allons lancer à la fin du mois de juin la procédure de vote en ligne pour renouveler le bureau pour l’année prochaine ; les adhérents recevront un courrier à cette occasion et ils pourront assister au dépouillement qui aura lieu le 8 juillet en fin d’après-midi.