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

Version interactive avec LaTeX compilé

Télécharger PDF

E3A Option Informatique MP 2007

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

Épreuve d'Informatique MP
durée 3 heures

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 la calculatrice est interdit

Indiquer en tête de copie ou de chaque exercice le langage utilisé

Exercice 1

a) Ecrire la fonction
éàéé
qui prend en entrée le tableau des coefficients d'une matrice carrée de taille et renvoie la valeur 1 si la matrice est symétrique et 0 sinon.
b) Ecrire la fonction
Egalite-listes données L:liste
        L' : liste
    résultat b:booléen
qui prend en entrée deux listes et renvoie la valeur 1 si les deux listes sont égales et 0 sinon. Ces listes contiennent des entiers positifs ou nuls et se terminent par la valeur -1 .
c) Un tableau d'entiers est dit trié par ordre croissant si ses entrées sont triées par ordre croissant : si est la longueur du tableau, . Il est dit trié par ordre décroissant si ses entrées sont triées par ordre décroissant : si est la longueur du tableau, . Dans les deux cas, il est dit trié. Remarquons qu'un tableau peut être à la fois trié dans l'ordre croissant et dans l'ordre décroissant, s'il vérifie : si est la longueur du tableau, . Il alors est dit constant.
Ecrire la fonction
Test-tri données T:tableau d'entiers
    l:entier
    résultat x: entier
qui prend en entrée un tableau de longueur et retourne la valeur 1 si le tableau est trié par ordre croissant et non constant, -1 si est trié par ordre décroissant et non constant, 0 si est constant et 2 si n'est pas trié.
Ecrire la procédure
Fusion données T:tableau d'entiers
    l: entier
    U:tableau d'entiers
    m:entier
    W:tableau d'entiers trié
qui fusionne deux tableaux triés tous deux par ordre croissant (respectivement tous deux triés par ordre décroissant), de longueurs respectives ; le résultat est un tableau trié par ordre croissant (respectivement par ordre décroissant) de longueur . Dans le cas où les deux tableaux ne sont pas tous deux triés dans un même ordre, la procédure Fusion renverra un tableau vide et un message d'avertissement.

Exercice 2

a) Que retourne le programme suivant :
b) Que calculent les procédures suivantes :
à
tableau d'entiers de longueur entier 
si ( $1 \leq l$ ) et ( $l \leq N$ ) faire
    $x \leftarrow T[1]$
    $g \leftarrow 0$
    $d \leftarrow N+1$
    $j \leftarrow 1$
        tant que $(j \leq N)$ faire
            si $(T[j]<x) \quad$ faire $\quad g \leftarrow g+1$
                $U[g] \leftarrow T[j]$
            si $(T[j]>x) \quad$ faire $\quad d \leftarrow d-1$
                $U[d] \leftarrow T[j]$
                    fin si
                $j \leftarrow j+1$
        fin tant que
        si $(g<l<d)$ afficher $x$
        sinon $\quad$ si $(l \leq g) \quad$ faire $\operatorname{Valeur}(g, \operatorname{TR}(N, U, 1, g), l)$
            si $(l \geq d) \quad$ faire $\operatorname{Valeur}(N-d+1, \operatorname{TR}(N, U, d, N), l-d+1)$
        fin si
sinon retourner " $l$ NON VALIDE"
fin si

Exercice 3

Soit un entier naturel. On dit que est un nombre parfait si est la somme des entiers naturels diviseurs de . Par exemple, l'entier 6 est un nombre parfait puisque . Ecrire un programme qui détermine la liste des nombres parfaits tels que .

Exercice 4

Un entier naturel étant donné, on calcule le produit de ses chiffres dans son écriture en base 10, puis le produit des chiffres de prod( ) dans son écriture en base 10, et on recommence ainsi l'application de prod jusqu'à obtenir un chiffre entre 0 et 9 . Le nombre minimal de fois où on applique prod pour transformer en un chiffre entre 0 et 9 est appelé la persistance de . Par exemple, la persistance de 9 est égale à 0 , celle de 97 est égale à 3 , car prod , et celle de 9575 est égale à 5 , car . Ecrire un programme qui calcule le plus petit entier naturel de persistance 5.

Exercice 5

On considère l'alphabet à deux lettres: .
Soit un entier naturel non nul. Un buffer de taille est modélisé par un automate ( ) sur l'alphabet défini par :
  • , l'ensemble des états de est l'ensemble . L'état représente la présence de exactement bits dans le buffer.
  • La lettre a représente l'arrivée d'un bit dans le buffer. La lettre représente la sortie d'un bit du buffer.
  • , est l'ensemble des transitions de :
    ,
    ,
  • 0 est l'état initial de ,
  • est l'ensemble des états finaux.
On note le langage reconnu par l'automate . Dans la suite, désigne le mot vide.
  1. Soient des entiers naturels non nuls. Justifier précisément l'équivalence :
On pourra démontrer que équivaut à .
2. Représenter l'automate ; donner une expression rationnelle de .
3. Représenter l'automate ; démontrer qu'une expression rationnelle de est
  1. Soit un entier naturel non nul. Le but de ces questions est de déterminer une relation de récurrence qui permettrait de calculer une expression rationnelle de . Pour dans , on note le langage reconnu par l'automate , automate dont l'ensemble des états et l'ensemble des transitions sont identiques à ceux de mais ayant le sommet comme unique état final.
    (a) Démontrer la relation de récurrence :
    (b) Soit . Démontrer : .
    (c) Conclure.

Exercice 6

Une compagnie d'avions dessert quatre villes : Angoulême, Bordeaux, Carcassonne, et Dax. Chaque avion ce cette compagnie respecte les règles suivantes :
(1) S'il dessert Dax, il fait escale à Bordeaux,
(2) S'il ne s'arrête pas à Bordeaux, il ne s'arrête pas à Angoulême.
(3) S'il dessert Carcassone, il fait escale à Angoulême.
(4) S'il ne s'arrête pas à Angoulême, il dessert Dax.
On introduit pour chacune de ces villes une variable propositionnelle: Pour Angoulême (respectivement Bordeaux, Carcassonne, Dax) , (respectivement ) dont la valeur est VRAI si l'avion effectue un arrêt à Angoulême (respectivement Bordeaux, Carcassonne, Dax) et FAUX sinon.
  1. Exprimer sous forme de propositions logiques, les quatre assertions (1), (2), (3) et (4). ces propositions seront notées respectivement .
  2. Dresser la table de vérité de chacune des propositions , en fonction de celles de ces variables.
  3. Démontrer :
Que signifie ceci pour les avions de cette compagnie ?
E3A Option Informatique MP 2007 - Version Web LaTeX | WikiPrépa | WikiPrépa