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.
Indiquer en tête de copie le langage de programmation, Caml ou Pascal, choisi pour l'ensemble du sujet.
L'épreuve est composée de 5 exercices, totalement indépendants.
Dans toute la suite, on supposera que les éléments d'un tableau de longueur sont indexés de 0 à et ce, quel que soit le langage choisi en début de sujet. De plus, on supposera disposer d'une fonction longueur qui donne le nombre d'éléments d'un tableau.
On rappelle que pour chaque entier naturel se décompose de manière unique en base sous la forme :
est appelé chiffre de en base . On dit que a au plus chiffres en base si pour tout .
Ainsi, , son premier chiffre en base 2 est 0 , le second est 1 et le troisième est 1 .
Exercice 1
Un échiquier est un plateau avec 8 lignes et 8 colonnes. Ces lignes et ces colonnes seront, dans cet exercice, numérotées de 0 à 7 . Une position sur l'échiquier est un couple ( ) d'entiers compris entre 0 et 7 inclus, avec le numéro de ligne et le numéro de colonne.
Un cavalier placé sur l'échiquier se déplace en bougeant de 2 cases dans une direction (verticale ou horizontale) et de 1 case perpendiculairement. Le dessin ci-dessous à gauche illustre les 8 possibilités de déplacement d'un cavalier situé loin des bords de l'échiquier. Comme le cavalier ne peut pas sortir du plateau, lorsqu'il est près des bords, il a moins de possibilités de se déplacer, comme l'illustre le dessin ci-dessous à droite.
Écrire une fonction Valide prenant en argument deux entiers relatifs et et vérifiant que le couple ( ) est bien une position de l'échiquier. Valide renvoie un booléen.
Écrire une fonction CoupSuivant prenant en argument une position et renvoyant la liste des positions que peut atteindre un cavalier placé en en un seul coup.
Écrire une fonction Cavalier prenant en argument une position et renvoyant une matrice de taille telle que est le nombre minimum de coups nécessaires à un cavalier situé en ( ) pour arriver à la position ( ).
Exercice 2
Dans cet exercice, on considère l'alphabet . On note le mot vide, la longueur du mot . Étant donnés un automate , et deux états et de , on note le fait qu'il existe un chemin dans , qui part de l'état et arrive dans l'état , étiqueté par le mot . De plus, étant donné un mot sur l'alphabet , on définit le langage par . On remarque que .
Enfin, on dit qu'un langage satisfait la propriété de l'étoile si et seulement si il existe tel que pour tout mot tel que , il existe trois mots et tels que , et , et , et .
On considère l'automate suivant, et on appelle le langage qu'il reconnaît :
Soit .
(a) Justifier que l'automate est déterministe complet.
(b) Indiquer le chemin parcouru dans l'automate pour reconnaître .
(c) Démontrer qu'il existe 3 mots et tels que et et . Vous donnerez une valeur de ( ) qui convient.
2. On considère dans cette question un langage reconnu par un automate fini déterministe complet ayant états et d'état initial . Soit un mot dans tel que ; démontrez qu'il existe un état et 3 mots et tels que et et et .
3. Démontrer que tout langage rationnel satisfait la propriété de l'étoile.
4. Le langage est-il rationnel ?
5. Citer un langage qui n'est pas rationnel, mais tel que le langage et est rationnel.
6. On considère le langage .
(a) Démontrer que satisfait la propriété de l'étoile.
(b) est-il rationnel ? Si oui, dessiner un automate qui le reconnaît.
Exercice 3
On considère un ensemble de variables , et on note .
Dans cet exercice, on considère les formules logiques exprimées avec les variables de et les connecteurs logiques OR, AND et NOT qui sont notés, respectivement, et . Une formule peut être représentée par un arbre, par exemple la formule est représentée par l'arbre suivant.
Enfin, une interprétation des variables de sera représentée par un tableau de booléens de longueur . Le élément du tableau étant la valeur de vérité de .
En Caml, les formules seront représentées par un type formule défini comme suit: type formule OR of formule formule AND of formule formule NOT of formule | Var of int;;
En Pascal, on supposera défini un type FORMULE, ainsi que les 3 fonctions suivantes:
FUNCTION symbole(f:FORMULE): INTEGER qui étant donné une formule renvoie respectivement ou -3 si est de la forme OR OU AND OU NOT . Si est de la forme , alors symbole renvoie l'entier .
FUNCTION fils_gauche(f:FORMULE) :FORMULE qui étant donné une formule renvoie la formule si est de la forme OR ou AND ou NOT .
FUNCTION fils_droit(f:FORMULE): FORMULE qui étant donné une formule renvoie la formule si est de la forme OR oug AND OU NOT .
Dessinez l'arbre correspondant à la formule .
Écrire une fonction récursive eval prenant comme argument un entier naturel , une formule ne faisant intervenir que les variables de , et une interprétation des variables de et renvoyant la valeur de vérité de .
Écrire une fonction maxVar qui, étant donné une formule , renvoie le plus grand tel que apparaît dans .
Écrire une fonction satisfiable prenant en argument une formule et renvoyant un booléen valant vrai si et seulement si la formule est satisfiable.
Vous pouvez introduire une fonction intermédiaire qui servira pour cette question et la suivante.
Écrire une fonction tautologie prenant en argument une formule et renvoyant un booléen valant vrai si et seulement si la formule est une tautologie.
Exercice 4
On rappelle les représentations des portes AND, OR, XOR et NOT.
Dans cet exercice, nous n'utiliserons que ces 4 portes et aucune autre.
Implémentez avec le minimum de portes, les fonctions booléennes suivantes:
.
Exercice 5
Dans les trois algorithmes suivants, et sont des tableaux, est un entier naturel, et clef est une fonction qui à chaque élément de associe un entier compris entre 0 et inclus. Enfin, on appelle clef d'un élément du tableau l'entier clef( ).
Exécuter Algo1 avec et et clef valant la fonction identique.
Démontrez, à l'aide d'un invariant de boucle, qu'à l'issue de l'exécution de Algo1, pour tout est le nombre d'éléments du tableau ayant pour clef .
8 \text { Algo2(T)}
9 Pour i allant de 1 à (longueur(T) -1) faire
10 T[i] prend la valeur T[i]+T[i-1]
11 fin faire
12 Fin : Ne renvoie rien.
Que fait l'algorithme Algo2?
Algo3(A,k,clef)
Crée un tableau B de même longueur que A
T prend la valeur Algo2(Algo1(A,k,clef))
Pour i allant de 1 à longueur(A) faire
j prend la valeur longueur(A)-i
p prend la valeur clef(A[j])
T[p] prend la valeur T[p]-1
B[T[p]] prend la valeur A[j]
fin faire
Fin : Renvoie B.
Démontrer que trie les éléments du tableau par clef croissante.
Démontrez que si et sont deux éléments du tableau ayant la même clef, alors et sont placés dans le même ordre dans le tableau et le tableau .
Déterminer la complexité d'Algo3 en fonction de la longueur de et de .
On considère à présent l'algorithme suivant, qui prend en entrée un tableau d'entiers naturels ayant chacun au plus chiffres en base . Ici chiffre est la fonction qui a associe son chiffre en base .
23 Algo4(A,k,d)
24}B\mathrm{ prend la valeur }
25 Pour i allant de 1 à d faire
26 B prend la valeur Algo3(B,k-1,chiffre }\mp@subsup{}{k,i}{}\mathrm{ )
27 fin faire
28 Fin : Renvoie B
Que fait l'algorithme Algo4 ? Justifier votre réponse avec un invariant de boucle.
Démontrer que la complexité de Algo4 est où est la longueur de .
On suppose dans cette question que contient entiers naturels d'au plus chiffres en base 2.
(a) Soit un entier naturel inférieur ou égal à . Comment choisir et en fonction de pour que Algo4 termine en temps ?
(b) En supposant de plus que avec . Comment choisir et en fonction de pour qu'Algo 4 termine en temps .
Citer d'autres algorithmes pouvant faire la même chose qu'Algo4. Comparer la complexité d'Algo4 avec ces algorithmes.
E3A Option Informatique MP 2014 - Version Web LaTeX | WikiPrépa | WikiPrépa
