Mines-Ponts 2019 MP Informatique commune : sujet en PDF
Sujet de l'épreuve de Informatique commune du Concours commun Mines-Ponts, France, session 2019, filière MP, en 1 heure 30 minutes. Thème : Autour des nombres premiers : crible, tests probabilistes, fonction de comptage et logarithme intégral.
Ce que traite le sujet, partie par partie
- Partie I : préliminaires. Import de fonctions du module math, test de proximité de deux flottants avec tolérances absolue et relative, fonction récursive qui renvoie la partie entière d'un logarithme et accumulation d'erreurs d'arrondi sur les flottants.
- Partie II : génération de nombres premiers. Crible d'Ératosthène : taille mémoire maximale, écriture et complexité en fonction de N puis du nombre de chiffres, générateur pseudo-aléatoire de Blum Blum Shub, test de primalité de Fermat et estimation du taux d'erreur.
- Partie III : compter les nombres premiers. Fonction de comptage des nombres premiers calculée en temps linéaire à partir du crible et vérification d'une minoration, puis logarithme intégral : complexité des méthodes de quadrature, rectangles à droite autour de la singularité, analyse des écarts avec une référence et calcul par le développement en série de l'exponentielle intégrale avec critère d'arrêt.
- Partie IV : analyse de performance de code. Clé primaire d'une table de tests, puis requêtes SQL : comptage et moyenne, ordinateurs sur lesquels un algorithme n'a pas été testé et tri des temps d'exécution avec jointure.
Chapitres à revoir avant de traiter ce sujet
- Architecture de l'ordinateur et représentation des nombres
- Récursivité
- Bases de Python : expressions, types, instructions, fonctions
- Complexité des algorithmes itératifs et récursifs
- Listes et algorithmes de recherche (séquentielle, dichotomique)
Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.