INSA Toulouse 1A Algorithme ADA TD 2

8/9/2019 INSA Toulouse 1A Algorithme ADA TD 2

1/10

Ada

Sujets des Travaux Dirigs

UV Algorithmique 2

INSA premire anne

Campagne 20092010 Didier LE BOTLANc o n t a c t . l e b o t l a n @ i n s a - t o u l o u s e . f r


2/102

Mode demploi

Droulement des sances

Vous travaillez par quipes de quatre tudiants.

Sur le travail demand

Pour rsoudre le problme pos, vous pouvez avoir besoin dutiliser des concepts qui nont pasencore t vus en cours. Cest un choix pdagogique : feuilletez le polycopi de cours.

Pendant la sance, vous pouvez poser des questions de comprhension lenseignant, mais il nersoudra pas le problme votre place.

Aucun corrig officiel ne sera fourni concernant les sujets de TD. Par contre, votre encadrant se feraune joie dexaminer et de commenter ce que vous aurez produit. Nhsitez pas le solliciter lorsquevous ne comprenez pas un point prcis.


3/103

TD Problme 1

Contexte

Lors dune discussion la cantine de votre entreprise, vous avez voqu avec votre quipe de travail

le paradoxe des anniversaires1, puis le paradoxe du paradoxe des anniversaires2. Malheureusementpour vous, le Directeur du dpartement Recherche et Dveloppement vous a entendu, et comme ila toujours de bonnes ides, il a dcid, malgr vos protestations, que votre quipe serait dsormaisresponsable du calcul probabiliste, suscitant aussitt ladmiration de vos collgues.

Le paradoxe des anniversaires

Dans une assemble suffisamment grande (>40 personnes), il y a

presque toujours deux personnes nes le mme jour de lanne.

On note p(n) la probabilit que deux personnes soient nes le mmejour de lanne dans une assemble de n personnes.

p(1) = 0 p(2) = 1365

p(25) 57% p(30) 70%

p(35) 81% p(40) 89% p(50) 97% p(100) 99, 99997%

(Vous trouverez la formule tout seuls plus tard)Mission

La premire tche ne tarde pas venir : afin de mettre au point une simulation de percolation, vousdevez calculer des probabilits de prsence lies au mouvement brownien une dimension :

Considrons 2n + 1 cases, en ligne, numrotes de 1 2n + 1.

1 2 3. . .

n n+1 n+2. . .

2n+1

Au dpart ( t = 0), la case n + 1 contient une particule. Les autres cases sont vides. Si la particule se trouve dans la case i linstant t, elle a une probabilit 1

3de se retrouver dans la

case i 1, i, ou i + 1 linstant t + 1, sauf aux bords (i = 1 et i = 2n + 1) o elle ne peut pas sortir(sur le bord, la particule a une probabilit 2

3de rester en place).

Ainsi la particule avance gauche ou droite, ou reste en place, de manire alatoire. Ce mouvement alatoire sur une ligne est appel mouvement brownien une dimension.

Vous devez crire une procdure Proba qui reoit deux arguments : n (la ligne contient 2n +1 cases)et t temps de mesure, et affiche la probabilit de prsence de la particule dans chaque case linstant t.

Un cabinet daudit externe, grassement rmunr, vous propose la ligne de conduite suivante :

1. Calculer la main p(i, t) pour t = 1, 2, 3, 4 et une valeur de n suffisamment grande.2. Trouver la formule de rcurrence permettant de calculer p(i, t + 1) en fonction des p(_, t). Le

cabinet vous fournit les conditions initiales : p(i, 0) = 0 pour i = n + 1 et p(n + 1, 0) = 1.

3. crire le programme demand

Le paradoxe du paradoxe des anniversaires

Si on exprimente trop souvent le paradoxe des anniversaires, on tombe sur un cas

incroyable o il ne marche pas (sauf en amphi ou il marche tout le temps).

1qui nen est pas un, comme tous les paradoxes.2qui nen est pas un non plus.


4/104

Pour ceux qui veulent tester

Si vous essayez en salle de TP, multipliez la valeur finale par 3t pour obtenir des valeurs entires. Avecn = 2 et t = 4, les valeurs sont :

14 17 19 17 14

Suite de lhistoire

Lors de la dmonstration de votre programme avec n = 5 000 et t = 20000, votre chef a trouv que letemps de rponse tait un peu long et il sinquite de savoir si votre algorithme tiendra la route pourles applications ayant besoin de valeurs de t au del du million.

Il vous demande donc dvaluer deux grandeurs de votre programme en fonction de n et t, supposs

assez grands (les approximations raisonnables sont les bienvenues) :1. la taille mmoire ncessaire

2. le temps de calcul

Quelques pistes sommaires :

Calcul de la taille mmoire

Un entier occupe 4 octets en mmoire, un nombre rel 8 octets. Un tableau de n rels occupe n fois 8 octets.

Calcul du temps dexcution

Lordinateur du chef tourne 1GHz, il ne peut donc pas aller plus vite que 1 milliarddoprations par seconde. En ralit cest plutt 10 fois moins.

Une opration est, par exemple, un calcul simple (une addition, une multiplication, etc.) ou uneaffectation de variable.

Thorme des crpes (1)

Si on mlange une quantit arbitraire doeufs, farine, et lait (en proportions raisonnables),avec un peu de beurre, on obtient une pte crpes tout fait honorable.

Thorme des crpes (2)

La premire crpe est presque toujours rate.


5/105

TD Problme 2

28 juillet 2012, LondresCe matin a eu lieu la premire preuve de natation des jeux olympiques de Londres.

cause dun dysfonctionnement logiciel, le chronomtrage officiel sest arrt en pleine course, aumoment o le nageur en tte a effectu son premier demi-tour (lincident nest pas pass inaperu).De plus, il a fallu attendre 25 minutes pour russir dpartager trois nageurs arrivs en mme temps,en procdant au visionnage de lpreuve au ralenti.

Ds midi, les organisateurs des J.O. ont lanc un appel doffre pour rcrire intgralement le logiciel de

chronomtrage des preuves de natation. Le dlai est de 18 heures, car il faut tre prt pour lpreuvedu 400 mtres nage libre ayant lieu demain.En vacances avec quelques collgues de lINSA, vous dcidez de rpondre cet appel doffre pouroccuper constructivement votre aprs-midi et encaisser au passage les 15 000 .

Cahier des charges

Objectifs crire un programme qui demande le nom des nageurs, chronomtre chaque nageur, d-tecte les faux dparts, compte les aller-retours jusqu 400 mtres, et affiche les noms des nageursdans lordre darrive, avec leur numro darrive.

Une piscine olympique fait 50 mtres de long. Elle peut avoir un nombre quelconque de couloirsutiliss (en gnral 8). Pour spcifier le nombre de couloirs, il suffira de modifier une seule ligne de

votre programme.

Capteurs Les capteurs envoient des signaux qui sont immdiatement enregistrs puis peuvent trercuprs par la fonction Attend_Signal (voir dans lacteur Capteurs ci-dessous). Lorsque le nageur de la ligne numro i quitte son plot de dpart, le capteur situ dans le plot envoie

un signal de type Un_Evenement, dans lequel Emetteur = Capteur_Depart, Num = i, et Date = la datede lvnement en secondes.

De mme, lorsque le nageur de la ligne numro i touche lun des bords du bassin, les capteurs

optiques envoient un signal. Les plots de dpart sont sur le ct Nord. Le capteur tant trs sensible,plusieurs signaux peuvent tre envoys daffile pour un seul toucher du nageur.

Le signal de dpart est signal par le capteur Capteur_Feu.

Conseils techniques

Commencez par faire un algorigramme sur papier ! Un type record ne peut contenir que des chanes (String) de taille fixe, ce qui scrit String (1..12)

pour une chane de 12 caractres.Vous pourrez utiliser la fonction Normalise (X, N) de GAda.Text_IO, qui prend une chane X et renvoieune chane de taille N en la tronquant ou en la compltant avec des espaces.


6/106

Pour arrter le programme au milieu dun bloc, vous pouvez utiliser linstruction raise Program_Error ;

Mission complmentairePour chaque nageur, reprer son meilleur temps de parcours de 50m (sur une longueur de piscine).

la fin de lpreuve, lorsque tous sont arrivs, afficher un classement des nageurs les plus rapides sur50m.

capteurs.ads

Cet acteur permet dattendre un signal provenant des capteurs.

package Capteurs is

numration des diffrentes sortes de capteurs| Capteur_Depart : capteur situ sur le plot de dpart

| Capteur_Nord : capteur situ lextrmit Nord du bassin| Capteur_Sud : capteur situ lextrmit Sud du bassin| Capteur_Feu : signal mis au moment du dpart

type Un_Capteur is (Capteur_Depart, Capteur_Nord, Capteur_Sud, Capteur_Feu) ;

Un vnement est un signal mis par un capteurNumero est le numro de couloir du capteur (pour les capteurs Depart, Nord, Sud)Date est la date de lvnement, en secondes depuis minuit.

type Un_Evenement is record

Emetteur : Un_Capteur ;

Num : Integer ;

Date : Float ;

end record ;

Attend jusqu ce quun vnement se dclencheet renvoie lvnement qui sest produit.Les vnements arrivent forcment dans lordre chronologique.

function Attend_Signal return Un_Evenement ;

end Capteurs ;


7/107

TD Problme 3

Contexte : BioinformatiqueVoici un extrait dun gnome humain (chromosome 18, position 53 464 656) :

. ..A T G A G T A C A G A A A G A G A C T C A G A A A C G A C A T T T G A C G A G G A T T C T C A G C C T A A T G A C G A A G T G G T T C C C T A C A G T G A T G A T G A A A C AG A A G A T G A A C T T G A T G A C C A G G G G T C T G C T G T T G A A C C A G A A C A A A A C C G A G T C A A C A G G G A A G C A G A G G A G A A C C G G G A G C C A T T CA G A A A A G G T A A C C A C A T G A A G T C C C G G T G A C T A G G T C G C T T A T A A A T C C T C A T G T G G G T C A T G G C C A C A C G T G C C A A A G A T G A T C G G TC T A T T T T G C G T G G T C T A G G A G A G A A T C T T C T C T G A T C T C T T C T T A G G A T G C G A C T G A C A G A A T G G T G G A T G G G C T T G G A C A A G T A C C CA T T G T C C T T A G T A A G A A G G G C T G G G A G A G C A T A T C T G A C A A G T T C T G C A G A G A A A A T A C A T T A A G G T C T T T G T T A G T G T G T G T A T A T A TA T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A T A . ..

Pour information, le gne ci-dessus (dont vous ne voyez quun court extrait) est l ATPase, Class I, type8B, member 1. Il code une enzyme li au cycle de lATP.

chaque triplet de bases (p. ex. ATT) est associ un acide amin (ici Ile, c.--d. Isoleucine).

Ala GCT, GCC, GCA, GCG Lys AAA, AAG

Arg CGT, CGC, CGA, CGG, AGA, AGG Met ATG

Asn AAT, AAC Phe TTT, TTC

Asp GAT, GAC Pro CCT, CCC, CCA, CCG

Cys TGT, TGC Sec TGA

Gln CAA, CAG Ser TCT, TCC, TCA, TCG, AGT, AGC

Glu GAA, GAG Thr ACT, ACC, ACA, ACG

Gly GGT, GGC, GGA, GGG Trp TGG

His CAT, CAC Tyr TAT, TAC

Ile ATT, ATC, ATA Val GTT, GTC, GTA, GTG

Leu TTA, TTG, CTT, CTC, CTA, CTG

Note : ce tableau nest pas totalement universel : il existe des petites variantes de codage dans les mitochondrieset chez certaines espces de bactries, algues, etc. .

MissionEn utilisant lacteur Genome (ci-aprs), crire un programme qui remplit le cahier des charges suivant : Votre programme lit deux fichiers "chromosome" et "proteine". Le premier contient la squence ADN

dun chromosome, le second contient une squence dacides amins. Votre programme cherche dans le chromosome une squence qui code la protine indique. Sil la trouve, il affiche sa position, sinon un message indique quil ne la pas trouve. Quand vous avez termin, valuez le temps dexcution de votre programme en considrant le pire

cas et le cas moyen ( vous de faire les estimations raisonnables). La taille du chromosome 18 est de

77 millions de paire de bases. La protine que lon cherche est l Amiloride-sensitive cation channel1, neuronal ; elle contient 512 acides amins (cette protine est un canal ions sodium prsentdans les neurones qui permet de crer un courant lectrique).

Marche suivreLa difficult principale est de dterminer comment dcomposer ce problme en tches simples. Unefois la dcomposition faite, les algorithmes crire sont petits.

Premire tape : crire une fonction qui prend en argument trois bases et qui renvoie un acideamin. (crivez seulement le code pour deux acides amins, la suite sera semblable). Pour vous aider dmarrer, cherchez la main la squence GluThr dans lextrait de gnomeci-dessus.


8/108

genome.ads

Cet acteur permet de lire des fichiers contenant un gnomeou contenant une squence dacides amins.

package Genome is

Une base ADN et une squence ADNtype Une_Base is (A, C, G, T) ;

type Une_Sequence_ADN is array (Integer range ) of Une_Base ;

Un acide amin et une squence dAAtype Un_AA is (Ala, Lys, Arg, Met, Asn, Phe, Asp, Pro, Cys, Sec,

Gln, Ser, Glu, Thr, Gly, Trp, His, Tyr, Ile , Val, Leu) ;

type Une_Sequence_AA is array (Integer range ) of Un_AA ;

Lit un fichier dADN et renvoie son contenu (le tableau commence 1)function Lire_ADN (Nom_Fichier : String ) return Une_Sequence_ADN ;

Lit un fichier dacide amins et renvoie son contenu (le tableau commence 1)function Lire_AA (Nom_Fichier : Stri ng ) return Une_Sequence_AA ;

end Genome ;

Remarque techniqueDans un sous-programme, il est possible dajouter use Genome ; avant le begin pour ne pas avoir

ajouter le nom de lacteur devant les valeurs numres. Il est alors possible dcrire A au lieu de

Genome.A (de type Une_Base).


9/109


10/10

G A T C T C T G A T C A A A G C T A A A G G T A A T C A T G A A G G C T A C A A T T C T G T G C A T C G C T T T C C T T A T T G C T G T T G T C G C C T C C G A G A G G T G T A CA T T C T T C C A C C A C G A G T G T T C C G G T A C C A C C T G C T C T G A T G G A G C C C C T C A C T G T G T G T T G G G A A C C T G C A G A T G C A C G C A A A A C A C CG G A A A A G C T T G T A C C A C C G C C T C T G A T T G C A C A G A G C A C T G C G C C C T C T T C G G A G A T C A G C A C T G T G T T G A C G G T T T C T G T C A T T G C CC A T T T G A C A G C G T C C T T C C T G G C G T A G G A A A A T A A A T A T C T T A A T A A A C A A T G A C A C A A C G T T G T C A T A A T A T G G G A A A C T C G G T G C C AT G T A T C A T T G T G G A A C C G T T T C A G A T A G A C G A G A A G A C C C C T G T T C C C T C A T C T T C G A T G C C A T T T T T T A T G G G A A C A A G A A C G A G G T TC A G C A G T T G A T T T C T G G C G G A G T G G A C A A G A A T G T C G T C A C G C A T C G T C A T G T G C G C T G G G A T A G C G C G A G T G C G C T T G G C G C T G C CG C C T A C G A A G G T C A C A T G G A C A T A G T G C G T T A T C T G A T T G A C A T C G G G A C A T C A G T G A A T T T C T C C G A C C C C T G T C A A A G A C G G A C G CC T C T A C A C T G G G C C T G C C T T G G C A A C C A G T A T C A G G C G G C C G C T T A C C T C A T C A A A C A C G G T G C T G A C G T C A A C C A C A G G G A T T T G GA G C A G A C G A C A C C C A T A C T T C G C G C T G C C T T A G G A A G A A A T A T A G A C T T A G T G A A A T G T T T G A T T G A A A A C G G T G C T G A T G T T C G A C A TA T T G A T A T T C T T G G T T G C T C T G T T C T C C A T T A C G C T T G T G T T C A T G G C G A C A A G A A A C T G A T A A A T A C T G T C A T C C G A G C A G G G T G T A TT T C T A A C A A T G T C G C T G T G A T A G G G A A A G C C A C G C C T T T A C A A A C G C T A T C C A A A A A G A A C G A C C G C G A A A A C G T G T C A C A G C T A C T GG C A G C C G G G T A C A A C C T A G A A A A C G A C C A G A A C T G G G T C A A C T C T T T A T C T C C T C C A A T C A C G T G C T C T A A C C C T A C G C T G G A A T A T GT G G T T C G A T T T G C C A A A A C T C G A C C C T T A A G C T T G A A A G G A C T C T G C A G G A A A A C G A T A A G G A A C G A A A T G A G A G G A G T G A A A G T G G AA C A G A T G T T A A A C A A C T T T C C T T G T C C A G C A T T A A T T C G G C A G T A T C T A A T A C T G G A T C A T C T G T G A T A T T G T T C A G A C A C A A C G T T G T CA T A A T A T G G G A A A C T C G G T G C C A T G T A T C A T T G T G G A A C C G T T T C A G A T A G A C G A G A A G A C C C C T G T T C C C T C A T C T T C G A T G C C A T T TT T T A T G G G A A C A A G A A C G A G G T T C A G C A G T T G A T T T C T G G C G G A G T G G A C A A G A A T G T C G T C A C G C A T C G T C A T G T G C G C T G G G A T A GC G C G A G T G C G C T T G G C G C T G C C G C C T A C G A A G G T C A C A T G G A C A T A G T G C G T T A T C T G A T T G A C A T C G G G A C A T C A G T G A A T T T C T C CG A C C C C T G T C A A A G A C G G A C G C C T C T A C A C T G G G C C T G C C T T G G C A A C C A G T A T C A G G C G G C C G C T T A C C T C A T C A A A C A C G G T G C T

G A C G T C A A C C A C A G G G A T T T G G A G C A G A C G A C A C C C A T A C T T C G C G C T G C C T T A G G A A G A A A T A T A G A C T T A G T G A A A T G T T T G A T T GA A A A C G G T G C T G A T G T T C G A C A T A T T G A T A T T C T T G G T T G C T C T G T T C T C C A T T A C G C T T G T G T T C A T G G C G A C A A G A A A C T G A T A A A TA C T G T C A T C C G A G C A G G G T G T A T T T C T A A C A A T G T C G C T G T G A T A G G G A A A G C C A C G C C T T T A C A A A C G C T A T C C A A A A A G A A C G A C CG C G A A A A C G T G T C A C A G C T A C T G G C A G C C G G G T A C A A C C T A G A A A A C G A C C A G A A C T G G G T C A A C T C T T T A T C T C C T C C A A T C A C G T GC T C T A A C C C T A C G C T G G A A T A T G T G G T T C G A T T T G C C A A A A C T C G A C C C T T A A G C T T G A A A G G A C T C T G C A G G A A A A C G A T A A G G A A CG A A A T G A G A G G A G T G A A A G T G G A A C A G A T G T T A A A C A A C T T T C C T T G T C C A G C A T T A A T T C G G C A G T A T C T A A T A C T G G A T C A T C T G T GA T A T T G T T C A G A G T G A C A G G A A A A G G A G C A A T A T A A A A G A T G A A G C A T G C T G G A T T A T T T G C C G T T T C C A T C T C T G T A T T G G T G A T G T TC A C C C T T G T C C A C G A A G G A C T T T C A G C C A C T A C C A C A A C A A C A A C A C C A A G T G G A G G T G G T G G A G G T G G T G G A G G T G G T G G G A T A C GG A A A A A T G A A A A A G A A T G A C G G A T A A A C G T A C G C G T A G C A T T A C C T A C C T G G G A C T T C T A T T T A T T T T C T T A A C G A A G C T T C C T G T G T TG G C G T C T T C T A C A G C A T G T A T C A C T T C A A G A G A A A C C G C A G A A A T A G T G A C A G A A T G T C C C C A A A C A C A A T T G G C A T G G G A A G A A G C AG C G G T A A A G A A A A A T T G T G A A A G G A C G C A A A A C C C C T G T T C T T C T T T T G T T T A T C A C T G T G T A A T G A A T A C A T G G A A A A A T C A G A C T A TT G A A G T G T G T G C C C C G A A A C A G A T G A T T C T C G G A A A A A A C T G T G C A G A A T A T A A T T T T C T T G G A G C C A A A G T C C A A C G C A A T T C T A A A GT G A A A T G C A G C A A A T G T C C T A T T G T G T A T A A T T C A A C T G A C G C T T T T A A A T A T C A A G A A T G C T A C A G A A G T G T T A T C C C T A C A G C T A A T CC T G A T A A C A C A A C T T A T C A A T T A C G T A T T T C A T T T G T T G A G A C A A C A A G C A G A A C G A C A A A T T C A T C T A C A C C T C A T G A T A A A C C C G A A TA T T T A G T T C A A A A T C A A G T T T T G G A C G A C A A G A A A A A C A A A T C T T A T A A A C A T A T A T A T T T T G G A G G A T T T T G T G T G G T A T G A T G G T C A CC C T A T T A A T G G C C G C C T C C A T G A T A T T G T A A A C A T T T A A A A A A T G C C A G C A G A A A A T A T G A C T G A T A A A A A A G A C A A G A A G A A A G A A G AG G T G C C C C C G C C C C C C A C T A A A G G G G T C T A C A T C T T C C C G A A T G G A G A C A A A T A T G A C G G A G A A T A C C A G C A T G G C A G T G A C G G A T CA C T G G A G C G G A A C G G T T A T G G T G T C C A T A C C A C G A C G G A A G G G G C C G T G T A T G A A G G C G A G T G G A A G G G G G A C A A A A T G A A C G G C AG G G G A A A A T T A G C C C A C C C C T C A G G C G C C C T G T A C G A G G G A G A G T T T G T C A A T A A T C A G T T C C A C G G C C A G G G A A A A T A C A C A T G G AA G A A C A A C T C T T T T T A C G A A G G A C A G T T C A A A G A A A A T A A G A T G G A G G G T A C G G G C C A G T T C A C C G A C A C G G A G G G A C A G A T G T G G A CG G G G A C A T T C C G A T A C A A G G C G G C G C C A G G A C T G A G A T T T G A A C T C A A G A T G A A T T A A T G C T A A G C T G C T T A C G T T C T G T A T G A A A A GT T T C A T C A A T C G G A C C C A T C C A C G T C A T C T G C A C A T C G C T C T G G T G G T G T G A T T C A T T G T G T T A G C A A A T G T T G A A T G A A T G T G T G T G TA A T T G T T A A A C A T A A T A A A A A T A C A C T G T A C A T T T T A C T G A A C A A A A A A A G A G A A A G A G C A A G T A A G T A G G C A T T A T A G G A G C A C C T A G TT A G G A A A C A G A A G G A G G G G A G C A T C A T G A C T T G G G C T A G G A T C T C G C T G T T G G T T T T G T G T G T G G T G G T G G C T G T T A A T G C A T C C C C AG T G T C T A A C C A G T G C C C G G A T G A G G A C G A C T T C A T G T G T A T G T C C G A C G G T C A G T C T G C C T G C T T C C C G A A C A A C T G G A A A T G T G A C GG T G A A C C C G A C T G T G A C G G C A A C G T C G A T G A G C A T G G C T G T C C C C C A G T T A C C T G T G A A G C C G A C G A G T T C T C A T G C G A C A A T A C C TG T A T C C C T G C A A C A T T C G T C T G T G A T G G T G A T T A C G A T T G C T A T G A C A A C A A A G A T G A G G C C A T G T G T C C T G C T G T G T G G G T G A A G C CA G A T T C C A A A G A A A A C A C G C G A G A G C G C C G C C T A G T G C C T G G C A T A A T G T C T C C G C C C C T T C C T G T G T T C C T T C A T C A T C T G A T A T C TC A T T T C G T C A T T A A G A A C T T C C A T T C A C T C T G T G A T A T G T T T T G A G A T T G T A A T A T T T T T T T G T T G T T T A G T A A A A A A G G G T G T T C T A T T GT A A T G T T A C A T A T A G A C T G A T T T A T C T G C A G T C T A T A C A A A T A A A T A A C A A A A T G A T G A C A A A

(Extrait authentique du gnome dune hutre, GenBank)

Version du 26 janvier 2010.

Documents

INSA Toulouse 1A Algorithme ADA TD 2