Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Polytechnique X 2004 epreuve d algorithmique classe prepa mp

4 pages
´ECOLE POLYTECHNIQUE´ ´ECOLE SUPERIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLESCONCOURS 2004` `´FILIEREMP - OPTION PHYSIQUE ET SCIENCES DE L’INGENIEUR FILIEREPCCOMPOSITION D’INFORMATIQUE(Dur´ee : 2 heures)L’utilisation des calculatrices n’est pas autoris´ee pour cette ´epreuve.Le langage de programmation choisi par le candidat doit ˆetre sp´ecifi´eentˆete de la copie.Compression ternaireOn attachera une grande importance `a la concision, `alaclart´e, et `alapr´ecision de la r´edaction.On supposera que le langage de programmation utilis´eposs`ede deux op´erations x div y et x mod ydonnant le quotient et le reste de la division euclidienne de x par y.Le temps d’ex´ecution T(f) d’une fonction f est le nombre d’op´erations ´el´ementaires (addi-tion, soustraction, multiplication, division, affectation, etc.) n´ecessaire au calcul de f.Lorsquece temps d’ex´ecution d´epend d’un param`etre n,ilseranot´e T (f). On dit que la fonction fns’ex´ecute :• en temps lin´eraire en n, s’il existe K>0 tel que pour tout n, T (f)≤ Kn ;n2• en temps quadratique en n, s’il existe K>0 tel que pour tout n, T (f)≤ Kn .nNombres ternairesEn base 3, les entiers 0, 1, 2, 3, 4, 5, 6, 7, 8 sont repr´esent´es par 00, 01, 02, 10, 11, 12, 20,21, 22.Lechiffredepoidsfortdebc est b ;lechiffredepoidsfaibleestc.´Question 1. Ecrire la fonction entier(b,c) retournant l’entier compris entre 0 et 8 qui s’´ecritbc en base 3.1´Question 2. Soit x un entier v´erifiant 0≤ x≤ 8. Ecrire une fonction ...
Voir plus Voir moins
´ ECOLE POLYTECHNIQUE ´ ´ ECOLE SUPERIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES
CONCOURS 2004
`´ MP FILIERE-OPTION PHYSIQUE ET SCIENCES DE L’INGENIEUR
COMPOSITION D’INFORMATIQUE (Dure´e:2heures)
FILIEREPC `
L’utilisation des calculatricesee´orissautstpanerpe´ettecruop.veeu Lelangagedeprogrammationchoisiparlecandidatdoitˆetresp´ecie´entˆetedelacopie.  
Compressionternaire
Onattacheraunegrandeimportance`alaconcision,a`laclarte´,et`alapre´cisiondelare´daction. Onsupposeraquelelangagedeprogrammationutilis´eposse`dedeuxope´rationsxdivyetxmody donnant le quotient et le reste de la division euclidienne dexpary.
Letempsdex´ecutionT(f) d’une fonctionflestmbnodre´eopitar´snoe´letnemid-(sdaiaere tion,soustraction,multiplication,division,aectation,etc.)ne´cessaireaucalculdef. Lorsque cetempsdexe´cutionde´penddunparam`etrene´tonarels,iTn(f). Ondit que la fonctionf sex´ecute:
etnpsemn´liaierenren, s’il existeK >0 tel que pour toutn,Tn(f)Kn; 2 en temps quadratique enn, s’il existeK >0 tel que pour toutn,Tn(f)Kn.
Nombres ternaires
Enbase3,lesentiers0,1,2,3,4,5,6,7,8sontrepr´esente´spar00,01,02,10,11,12,20, 21,22. Lechiffre de poids fort debcestb; le chiffre de poids faible estc.
Question 1. bcen base 3.
´ Ecrire la fonctionentier(b,cneitreocpmirestnre0et8quis´ecritltnanruoter)
1
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin