E3A Option Informatique MP 2009

CONCOURS ENSAM - ESTP - ARCHIMEDE

Durée 3 h

L'usage de calculatrices est interdit.

1 Sommes d'entiers

1. On se place dans le cas où et et . Étudier le problème pour entre 10 et 14 .
2. Écrire un programme prenant en argument et les éléments et renvoyant le booléen «vrai» si une telle décomposition existe et «faux» sinon.
3. On ajoute la contrainte suivante : on se donne des entiers naturels non nuls et on impose d'avoir les inégalités suivantes : pour tout .
   (a) Écrire un programme prenant en argument et les couples et renvoyant le booléen «vrai» si une telle décomposition existe et «faux» sinon.
   (b) Écrire un programme prenant en argument et les couples et renvoyant le nombre de telles décompositions.

2 Autour de la racine carrée entière

1. On ne travaillera qu'avec des entiers relatifs;
2. Les opérations arithmétiques autorisées sur les entiers sont :
   (a) l'addition de deux entiers et ;
   (b) la soustraction de deux entiers et ;
   (c) la multiplication de deux entiers et ;
   (d) la division euclidienne d'un entier positif par un entier strictement positif le reste de la division étant obtenu par et le quotient par en Caml et par a div en Pascal.
   Dans la suite, si et sont deux entiers avec , l'écriture désigne le quotient rationnel de par ; si est un réel, désigne la partie entière de et désigne le plafond de le plus petit entier supérieur ou égal à .

2.1 Algorithme naïf

1. Écrire une fonction isqrt_naif prenant en argument et renvoyant la valeur de en utilisant le principe décrit ci-dessus.
2. Déterminer la complexité de votre programme.

2.2 Une méthode dichotomique

let isqrt n=
    let x=ref 1 in
        let y=ref n in
            while((!y)-(!x)>1) do
                let z=((!x)+(!y))/2 in
                    if }z*z>n then
                        y:=z
                    else
                        x:=z
            done;
    !x;;

Function isqrt(n: longint) : longint;
Var x,y,z : longint;
Begin
    x:=1;y:=n;
    While (y-x>1) Do
    begin
        z:=(x+y) div 2;
        if }\textrm{z}*\textrm{z}>\textrm{n}\mathrm{ then
            y:=z
        else
            x:=z
    end;
    isqrt:=x;
LEnd;

1. Expliciter les exécutions du programme ci-dessus sur l'entier 15. (On donnera en particulier les valeurs successives des variables et .)
2. Démontrer la terminaison du programme.
3. Justifier la correction du programme.
4. (a) Prouver l'inégalité suivante :

2.3 Circuit logique

1. Pour les deux questions suivantes, on veillera à donner un résultat le plus simple possible.
   (a) Donner une formule booléenne exprimant en fonction de et .
   (b) Donner une formule booléenne exprimant en fonction de et .
2. On souhaite construire des circuits logiques implémentant ces deux fonctions. On dispose seulement de porte de type «ou» et de type «non» représentées dans la figure 1.
   (a) Proposer un circuit implémentant la fonction .
   (b) Proposer un circuit implémentant la fonction n'utilisant au plus que quatre portes de type «ou» et quatre portes de type «non».

Figure 1 - Portes «ou» et «non»

2.4 Une méthode Babylonienne

1. Écrire une fonction prenant supposé supérieur ou égal à 1 et calculant l'entier le plus proche de . On détaillera la manière dont est effectué le calcul des parties entières et des plafonds.
2. Déterminer les valeurs de la suite ( ) lorsque vaut 13 et donner la valeur de l'unique entier le plus proche de .

3 Coefficients binomiaux

1. Dans cette question, on n'utilisera ni liste, ni tableau et la seule opération arithmétique autorisée est l'addition; on n'effectuera donc aucune multiplication. Écrire une fonction récursive simple calculant le coefficient .
2. On pose et on souhaite construire un tableau de longueur tel que si contient la valeur du coefficient .
   (a) Expliquer brièvement pourquoi il n'est pas possible d'utiliser la fonction de la question précédente.
   (b) Écrire un programme renvoyant le tableau convenablement rempli.
3. Cette question est indépendante des questions précédentes. Il est demandé de ne pas utiliser de tableau et de ne pas calculer . Un théorème de Lucas assure que si et sont des entiers naturels, alors, en écrivant et en base 2 :

4 Minimisation d'automates

• un automate déterministe sur l'alphabet est un quadruplet où :
• est un ensemble fini d'états
• est une application appelée fonction de transition
• est l'état initial et
• est l'ensemble des états finals.
• un automate sur l'alphabet est un quadruplet où :
• est un ensemble fini d'états
• est l'ensemble des transitions
• est l'ensemble des états initiaux et
• est l'ensemble des états finals.

• ;
• est défini par : ;
• et
• .

Dans la suite désigne l'automate suivant:

1. Donner une expression rationnelle du langage reconnu par l'automate .
2. (a) Représenter graphiquement l'automate .
   (b) Représenter graphiquement l'automate . (Indication : l'automate a quatre états.)
3. Si est un langage, on définit le langage miroir de par :