J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

E3A Option Informatique MP 2015

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo e3a
🔗 Explorer
Banque
E3A
Année
2015
Filière
MP
Matière
Info
E3A MPE3A 2015MP InfoInfo 2015
2025_08_29_ab6e6bb8a71f5ba26132g
e3a 2015

CONCOURS ARTS ET MÉTIERS ParisTech -ESTP -POLYTECH
Épreuve d'Informatique MP
Durée 3 h

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

AVERTISSEMENT

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies. En particulier, les résultats non justifiés ne seront pas pris en compte. Les candidats sont invités à encadrer les résultats de leurs calculs.
Les différents exercices sont indépendants.
Lorsqu'on demande d'évaluer une complexité, on attend un ordre de grandeur, par exemple .
Pour un nombre réel , on note sa partie entière.
Il est interdit aux candidats de signer leur composition ou d'y mettre un signe quelconque pouvant indiquer sa provenance.

Exercice 1

On admettra que la multiplication de deux entiers naturels se fait en temps constant.
  1. On s'intéresse dans cette partie au calcul de la puissance -ième d'un entier naturel , pour un entier naturel .
    (a) Dans un premier temps, on utilise un algorithme naïf :
let rec puissance n k =
    if k= 1 then n
    else n * (puissance n (k-1));;
val puissance : int -> int -> int
Quelle est la complexité de cet algorithme ? Le justifier précisément.
(b) On utilise ensuite l'algorithme suivant :
let rec puissance2 n k =
    if k >1 then
        let x = puissance2 n (k/2) in
        if k mod2 =0 then
            x * x
        else
            else x * x * n;;
val puissance2 : int -> int -> int
i. Décrire l'exécution du programme puissance2 sur l'entrée ( 2,7 ).
ii. Décrire l'exécution du programme puissance2 sur l'entrée .
iii. Démontrer que le nombre d'appels récursifs à l'intérieur du programme puissance2 sur l'entrée ( ) est au plus de . En déduire que le programme termine.
iv. Justifier que ce programme est correct.
v. Évaluer la complexité de ce programme.
2. On s'intéresse ici au problème de déterminer si un entier naturel est une puissance non triviale d'un nombre entier ou non : on dit qu'un nombre entier naturel n est une puissance entière s'il existe deux entiers naturels et tous deux tels que .
(a) Écrire la fonction :
test_puissance : int -> int -> bool
qui prend en entrée les entiers naturels et et renvoie le booléen true s'il existe un entier naturel tel que et false sinon.
Note : l'énoncé original mentionne un qui n'est pas défini.
(b) i. Soit un entier naturel. On suppose que est une puissance entière : Soient et deux entiers naturels tels que . Justifier que .
ii. Écrire la fonction :
test_puissance_entiere : int -> bool
qui prend en entrée l'entier naturel et renvoie le booléen true s'il existe deux entiers naturels et tous deux tels que et false sinon.
iii. Démontrer que la complexité de ce programme est au plus .
iv. En déduire la fonction :
liste1_puissances_entieres : int -> int list
qui prend en entrée l'entier naturel et renvoie la liste des entiers naturels compris entre 2 et qui sont des puissances entières.
(c) En vous inspirant du crible d'Erathosthène, écrire la fonction :
liste2_puissances_entieres : int -> int list
qui prend en entrée l'entier naturel et renvoie la liste des entiers naturels compris entre 2 et qui sont des puissances entières.

Exercice 2

Soit l'alphabet des chiffres : .
Un nombre entier naturel non nul est considéré à l'aide de son écriture en base 10 comme un mot sur l'alphabet :
é
Un mot sur sera considéré comme un tableau de type int vect dont les éléments sont compris entre 0 et 9 . Par exemple le nombre 2015 sera représenté par .
On dit qu'un entier naturel non nul a la propriété si son écriture en base 10 comprend le motif 2015. On cherche à reconnaître les entiers naturels non nuls ayant cette propriété.
  1. Dessiner un automate déterministe complet qui reconnait exactement les entiers naturels non nuls ayant la propriété .
  2. On considère la fonction qui envoie un mot dans sur l'entier naturel .
    (a) Combien de valeurs distinctes la fonction peut-elle prendre?
    (b) Étant donné un mot dans , expliciter comment calculer en fonction de et .
    (c) Écrire la fonction :
decalG : int -> int -> int
qui prend en entrée l'entier naturel et le chiffre dans et renvoie la valeur , pour abcde un mot dans .
(d) On utilise la fonction pour résoudre le problème. Étant donné un entier naturel non nul s'écrivant en base 10 , on calcule la valeur prise par sur chaque facteur . Écrire la fonction :
testG_motif : int vect -> bool
qui prend en entrée le tableau défini par l'écriture en base 10 d'un entier naturel non nul et renvoie le booléen true si l'entier naturel a la propriété et false sinon. Cette fonction ne lira qu'une fois au plus chacun des caractères de l'écriture en base 10 de .
(e) Évaluer la complexité de votre algorithme.
(f) Écrire la fonction :
nbG_motif : int vect -> int
qui prend en entrée le tableau défini par l'écriture en base 10 d'un entier naturel non nul et renvoie le nombre d'occurrences du motif 2015 dans l'écriture en base 10 de .
3. On considère la fonction qui envoie un mot dans sur l'entier naturel compris entre 0 et 10 égal à modulo 11 .
(a) Combien de valeurs distinctes la fonction peut-elle prendre?
(b) Écrire la fonction :
calculH : int vect -> int
qui prend en entrée un mot dans et renvoie la valeur de prise sur ce mot.
(c) Étant donné un mot dans , expliciter comment calculer en fonction de , et .
(d) En utilisant la fonction , écrire la fonction :
testH_motif : int vect -> int
qui prend en entrée le tableau défini par l'écriture en base 10 d'un entier naturel non nul et renvoie renvoie le booléen true si l'entier naturel a la propriété et 0 (ou false) sinon. Cette fonction ne lira que trois fois au plus chacun des caractères de l'écriture en base 10 de .
(e) Évaluer la complexité de votre algorithme.

Exercice 3

On souhaite analyser les résultats de sondages concernant une élection. Les candidats à l'élection sont numérotés de 0 à . Les résultats de chaque sondage sont stockés dans un tableau : si le sondage a recueilli réponses, le tableau comporte cases, une pour chaque réponse : la -ème case du tableau contient le numéro du candidat proposé par la -ème personne sondée. On a ainsi un tableau de longueur qui contient des entiers naturels entre 0 et .
Le sondage donne le candidat numéroté élu si le nombre est dans strictement plus de cases de . Par exemple, un sondage correspondant au tableau donne le candidat 4 élu. Mais un tableau ne donne pas toujours un élu, par exemple le tableau .
On suppose qu'un entier est défini.
  1. (a) Écrire une fonction nb de type int vect int int telle que si a est un entier naturel et tab un tableau de taille issu d'un tel sondage, nb tab a est le nombre de cases du tableau tab qui contiennent a.
    (b) Évaluer la complexité de l'appel de nb en fonction de et de .
    (c) En déduire une fonction elu1 de type int vect int telle que elu1 tab est l'entier donné élu par le tableau tab si celui-ci existe et -1 sinon.
    (d) Évaluer la complexité de votre algorithme en fonction de et de .
  2. On se propose d'utiliser la stratégie diviser pour régner pour déterminer l'éventuel élu donné par un tableau. On dispose de deux fonctions, qu'on ne cherchera pas à décrire :
  • miGauche : int vect int vect qui prend en argument un tableau tab de longueur et retourne le tableau de longueur formé par les premières cases de tab,
  • miDroite : int vect -> int vect qui prend en argument un tableau tab de longueur et retourne le tableau de longueur formé par les dernières cases de tab.
    (a) Soit tab un tableau de longueur . Démontrer que si tab donne comme élu alors celui-ci est aussi donné élu par le tableau miGauche tab ou par le tableau miDroite tab.
    (b) Proposer une fonction elu2, utilisant la stratégie diviser pour régner, de type int vect int * int ; si tab est un tableau, elu2 tab est le couple ( ) si l'entier a est donné élu par tab et apparait dans cases exactement de tab, et si tab ne donne pas d'élu. On pourra utiliser la fonction nb définie en l(a).
    (c) Évaluer la complexité de cette fonction en fonction de .
  1. Soit un tableau de longueur . On dit que le nombre entier est un postulant pour la valeur du tableau si : est un entier strictement supérieur à tel que apparait au plus (au sens large) fois dans et tout entier distinct de , apparait au plus (au sens large) fois dans . Par exemple, 3 est un postulant pour du tableau [ ].
    On dit que le nombre entier est un postulant du tableau s'il existe un nombre entier tel que est un postulant pour la valeur du tableau
    (a) Démontrer que si le tableau donne élu alors est un postulant de .
    (b) Démontrer que si est un postulant de , alors aucun autre élément de ne pourrait être donné comme élu.
    (c) Donner un exemple de tableau qui contient un postulant mais ne donne aucun élu et un exemple de tableau n'ayant aucun postulant.
    (d) Soit un tableau de longueur un entier pair . On note le tableau de longueur formé par les premières cases de et le tableau de longueur formé par les dernières cases de .
    i. On suppose que le tableau ne donne pas d'élu. Soit un postulant pour la valeur du tableau . Démontrer que est un postulant de . On exprimera la valeur d'un entier tel que et est un postulant pour la valeur du tableau en fonction de et .
    ii. Soient un postulant pour la valeur du tableau et un postulant pour la valeur du tableau .
    A. On suppose que . Démontrer que est un postulant de . On exprimera la valeur d'un entier tel que et est un postulant pour la valeur du tableau en fonction de et .
    B. On suppose que et . Démontrer que est un postulant pour la valeur de .
    . On suppose que et . Démontrer que ne donne pas d'élu.
  2. Écrire une fonction postulant : int vect int int telle que, si tab est un tableau d'entiers naturels de longueur , postulant tab est un couple ( ) tel que
  • lorsque postulant tab renvoie le couple , le tableau tab n'a pas d'élu,
  • lorsque postulant tab renvoie le couple ( ) avec , a est un postulant pour la valeur n du tableau tab. On supposera pour simplifier que la taille du tableau est une puissance de 2 , La procédure utilisera la stratégie diviser pour régner et aura une complexité linéaire, ce qu'on justifiera précisément.
  1. En déduire une fonction elu3, de type int vect int qui prend en argument un tableau tab et retourne l'entier élu de tab si celui-ci existe et -1 sinon, de complexité linéaire.
E3A Option Informatique MP 2015 - Version Web LaTeX | WikiPrépa | WikiPrépa