Mines Informatique Commune MP PC PSI 2019Sujet, corrigé et rapport du jury

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique, ENSAE PARISTECH, CHIMIE PARISTECH.

CONCOURS 2019

ÉPREUVE D'INFORMATIQUE COMMUNE

INFORMATIQUE COMMUNE

L'énoncé de cette épreuve comporte 9 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.

Autour des nombres premiers

Préambule

Définitions, rappels et notations

• Un nombre premier est un entier naturel qui admet exactement deux diviseurs : 1 et lui-même. Ainsi 1 n'est pas considéré comme premier.
• Un flottant est la représentation d'un nombre réel en mémoire.
• Quand une fonction Python est définie comme prenant un « nombre » en paramètre cela signifie que ce paramètre pourra être indifféremment un flottant ou un entier.
• On note ⌊x⌋ la partie entière de x.
• abs(x) renvoie la valeur absolue de x . La valeur renvoyée est du même type de données que celle en argument.
• int(x) convertit vers un entier. Lorsque x est un flottant positif ou nul, elle renvoie la partie entière de x , c'est-à-dire l'entier n tel que n ⩽ x < n + 1.
• round(x) renvoie la valeur de l'entier le plus proche de x . Si deux entiers sont équidistants, l'arrondi se fait vers la valeur paire.
• floor(x) renvoie la valeur du plus grand entier inférieur ou égal à x.
• ceil(x) renvoie la valeur du plus petit entier supérieur ou égal à x.
• log(x) renvoie sous forme de flottant la valeur du logarithme népérien de x (supposé strictement positif).
• log(x, n) renvoie sous forme de flottant la valeur du logarithme de x en base n .
• La fonction time() du module time renvoie un flottant représentant le nombre de secondes depuis le 01/01/1970 avec une résolution de 10^(− 7) seconde (horloge de l'ordinateur).
• L'opérateur usuel de division / renvoie toujours un flottant, même si les deux opérandes sont des multiples l'un de l'autre.
• L'infini + ∞ en Python s'écrit float("inf").
• En Python 3, on peut utiliser des entiers illimités de plus de 32 bits avec le type long.

Partie I. Préliminaires

• Q1 - Dans un programme Python on souhaite pouvoir faire appel aux fonctions log, sqrt, floor et ceil du module math (round est disponible par défaut). Écrire des instructions permettant d'avoir accès à ces fonctions et d'afficher le logarithme népérien de 0.5.
• Q2 - Écrire une fonction sont_proches (x, y) qui renvoie True si la condition suivante est remplie et False sinon

def mystere(x,b):
    if x < b:
        return 0
    else:
        return 1 + mystere(x / b, b)

• Q4 - Exprimer ce que renvoie mystere en fonction de la partie entière d'une fonction usuelle.
• Q5 - On donne le code suivant :

pas = 1e-5
x2 = 0
for i in range(100000):
    x1 = (i + 1) * pas
    x2 = x2 + pas
print("x1:", x1)
print("x2:", x2)

x1: 1.0
x2: 0.9999999999980838

Partie II. Génération de nombres premiers

II.a Approche systématique

Algorithme 1 : Crible d'Ératosthène

• Q6 - Sachant que le langage Python traite les listes de booléens comme une liste d'éléments de 32 bits, quel est (approximativement) la valeur maximale de N pour laquelle liste_bool est stockable dans une mémoire vive de 4 Go?
• Q7 - Quel facteur peut-on gagner sur la valeur maximale de N en utilisant une bibliothèque permettant de coder les booléens non pas sur 32 bits mais dans le plus petit espace mémoire possible pour ce type de données (on demande de le préciser) ?
• Q8 - Écrire la fonction erato_iter(N) qui implémente l'algorithme 1 pour un paramètre N qui est un entier supérieur ou égal à 1 .
• Q9 - Quelle est la complexité algorithmique du crible d'Ératosthène en fonction de N? On admettra que :

• Q10 - Quand on traite des nombres entiers il est intéressant d'exprimer la complexité d'un algorithme non pas en fonction de la valeur N du nombre traité mais de son nombre de chiffres n. Donner une approximation du résultat de la question précédente en fonction de n en précisant la base choisie.

II.b Génération rapide de nombres premiers

1. générer un entier pseudo-aléatoire (voir ci-dessous)
2. vérifier si cet entier a de fortes chances d'être premier
3. recommencer tant que le résultat n'est pas satisfaisant.

• Q12 - Compléter (avec le nombre de lignes que vous jugerez nécessaire) la fonction bbs (N) donnée ci-dessous qui réalise ces itérations. La graine est un entier représentant la fraction de secondes du temps courant, par exemple 1528287738.7931523 donne la graine 7931523 . Le paramètre N est un entier non nul.

...
def bbs(N):
    p1 = 24375763
    p2 = 28972763
    M = p1 * p2
    # calculer la graine
        (à compléter)
    A = 0
    for i in range(N):
        if ... (à compléter) # si xi est impair
            A = A + 2** i
        # calculer le nouvel xi
        xi = ... (à compléter)
    return (A)

Partie III. Compter les nombres premiers

III.a Calcul de π(n) via un crible

• Q16 - Écrire une fonction verif_Pi(N) qui renvoie True si l'inégalité est vérifiée jusqu'à N inclus, False sinon. Le paramètre N est un entier supposé supérieur ou égal à 5393 .

III.b Calcul d'une valeur approchée de π(n)

Figure 1 - Allure de li sur [0,2.5]

Estimation de li par quadrature numérique

• Q18 - Dans les mêmes conditions d'évaluation, quelle est la complexité en temps de la méthode des rectangles centrés? Donner aussi celle de la méthode des trapèzes.
• Q19 - Écrire une fonction inv_ln_rect_d(a, b, pas) qui calcule par la méthode des rectangles à droite une valeur approchée de ∫_a^b(dt)/(ln(t)) avec un incrément valant pas. On suppose dans cette question que a < b et que 1 n'appartient pas à l'intervalle [a, b] de sorte que la fonction intégrée est définie et continue sur [a, b].
  On considère que le réel b − a est un multiple du réel pas.
  Les paramètres a, b et pas sont des flottants.
• Q20 - Écrire une fonction li_d(x, pas) qui calcule une valeur approchée de li( x ) avec la méthode des rectangles à droite en se basant sur inv_ln_rect_d. Si x = 1 la fonction renvoie − ∞. On rappelle qu'on suppose que pas est choisi de manière à ce que 1 et x soient multiples de pas et qu'on utilise ε = pas dans l'équation (4). Les paramètres x et pas sont des flottants.

Analyse des résultats de li_d

Figure 2 - Écart relatif entre li_d (pas = 10^(− 4) ) et l'implémentation de référence ref_li.

Figure 3 - Écart absolu entre li_d (pas = 10^(− 4) ) et l'implémentation de référence ref_li.

• Q21 - Expliquer le comportement de l'écart relatif entre li_d et ref_li, illustré figure 2 au voisinage de x ≃ 1.4.
• Q22 - On constate un écart absolu important entre li_d et ref_li au delà de x = 1, illustré figure 3. Expliquer succinctement d'où vient ce phénomène. On ne demande pas une démonstration mathématique rigoureuse.
  Pour répondre à cette question on pourra remarquer qu'au premier ordre 1/(ln(1 + ε)) ≃ − 1/(ln(1 − ε)) quand ε → 0 et s'interroger sur la valeur que devrait avoir l'intégrale impropre de 1/(ln(x)) sur un intervalle [1 − ε, 1 + ε] avec ε≪1. Une analyse géométrique de la figure 4 peut aussi s'avérer utile.
• Q23 - Proposer, en justifiant votre choix, une ou des modifications de l'algorithme utilisé afin d'éliminer le problème constaté sur l'écart absolu. Il n'est pas demandé d'écrire le code mettant en œuvre ces propositions.

Figure 4 - Rectangles utilisés par la méthode des rectangles à droite au voisinage de 1 afin de calculer la valeur principale de Cauchy introduite dans l'équation (4). Les paramètres sont pas = ε = 10^(− 2)

Estimation de li via Ei

• Q24 - Écrire une fonction li_dev(x) qui calcule l(x) en se basant sur Ei_n et la fonction sont_proches de la question 2 (on pourra utiliser la fonction associée même si la question n'a pas été traitée). li_dev doit renvoyer False si :
• Ei_(n − 1) et Ei_n ne peuvent pas être considérés comme proches au bout de MAXIT itérations.
• la valeur de x ne permet pas d'aboutir à un résultat.

Partie IV. Analyse de performance de code

• nom TEXT, clé primaire, le nom de l'ordinateur.
• gflops INTEGER la puissance de l'ordinateur en milliards d'opérations flottantes par seconde.
• ram INTEGER la quantité de mémoire vive de l'ordinateur en Go.

• id INTEGER l'identifiant du test effectué.
• nom TEXT le nom de la fonction testée (par exemple li, Ei, etc).
• algorithme TEXT le nom de l'algorithme qui permet le calcul de la fonction testée (par exemple BBS si on teste une fonction de génération de nombres aléatoires).
• teste_sur TEXT le nom du PC sur lequel le test a été effectué.
• temps_exec INTEGER le temps d'exécution du test en millisecondes.

• Q25 - Expliquer pourquoi il n'est pas possible d'utiliser l'attribut nom comme clé primaire de la table fonctions.
• Q26 - Écrire des requêtes SQL permettant de :

1. Connaître le nombre d'ordinateurs disponibles et leur quantité moyenne de mémoire vive.
2. Extraire les noms des PC sur lesquels l'algorithme rectangles n'a pas été testé pour la fonction nommée li.
3. Pour la fonction nommée Ei, trier les résultats des tests du plus lent au plus rapide. Pour chaque test retenir le nom de l'algorithme utilisé, le nom du pc sur lequel il a été effectué et la puissance du PC.

Fin de l'épreuve.