Énoncé
Contents
1. A loga Oo i l Partie b 10 points tant donn deux fonctions Ji et f x on dit que f x cro t moins vite que L si fix est dans O f x mais fx n est pas dans O f x et on dit que f et f x croissent la m me vitesse si f x est dans O x et Pe est dans O f x Classez les fonctions de la partie a selon leur taux de croissance si f x cro t moins vite que x alors crivez f x gauche de f x et si f x et f x croissent la m me vitesse alors crivez l une au dessous de l autre Par exemple si f x tait x f x tait x 1 et f3 x tait x2 alors il faudrait crire fi B h Question 7 sur les s quences de la bioinformatique et les preuves 25 points Soit X1X2 x Et Y 1Y2 Ym deux s quences de lettres de l alphabet 4 C G T Un alignement entre ces deux s quences est donn par deux s quences de la m me longueur aj42 dr bib by de symboles de l alphabet 4 C G T avec b crit au dessous de a pour tout i tel que a pour tout i au moins un des deux symboles a et b doit tre une lettre c est dire Villa _ v b _ b si l on efface les symboles _ de la s quence aja ay on obtient la s quence x x2 x et si l on efface les symboles _ de la s quence b b b on obtient la s quence y1y2 Ym Par exemple voici un alignement des s quences ACGTGA et ACTGGGA Ar E E E OEE 2 C T Ge Le co t de l alignement aj4 d2. b b b est le nombre de paires de symboles a b tels que a b Dans l exemple dessus a b pour i 2 3 4 7 et 8 donc le co t de cet alignement est 5 Partie a 3 points Donnez des alignements de co t 3 4 et 5 entre les s quences AC et CGA Partie b 4 points Trouvez un alignement entre ACGTGA et ACTGGGA de co t minimum Partie c 8 points Quel est le co t maximum d un alignement entre x x2 x et y1 2 y en fonction de n et de m Justifiez votre r ponse Partie d 10 points D montrez qu il existe un alignement de co t 0 entre x1x2 x et y1y2 ym Si et seulement si n m et x1x2 x y1y2 y les s quences sont de la m me longueur et pour tout ionax y Notez qu il faut d montrer deux nonc s a sin m et X1X2 Xy V1 2 Vm alors il existe un alignement de co t 0 entre xjx2 x et YL2 Ym b s il existe un alignement de co t 0 entre x x2 x et Y1Y2 Ym alors n m et X1X2 Xy V1 2 Ve
3. INF1130 SESSION A07 DEVOIR 1 remise vendredi le 19 octobre 2007 avant 16h00 Question 1 sur la logique propositionelle 20 points Le manuel d entretien de votre nouveau gadget est sp cialement mal crit Par exemple on retrouve le texte suivant pour nous aider diagnostiquer les pannes de type 1 Si le voyant est allum alors l indicateur est d fectueux ou la pile est plat Lorsque l indicateur fonctionne et que la pile n est pas plat le voyant est allum Partie a 5 points Traduisez le texte ci dessus l aide de la logique propositionelle en sp cifiant bien quelles sont les propositions l mentaires atomiques Partie b 10 points Trouvez l nonc le plus simple possible qui est quivalent celui que vous avez obtenu en la partie a de cette question pour diagnostiquer une panne de type 1 Partie c 5 points Retraduisez en fran ais votre nouvel nonc Question 2 sur la logique des propositions quantifi es 30 points 5 pour chaque partie Soit U l univers du discours l ensemble des animaux Soit C x le pr dicat que x est un chien canin Soit F y le pr dicat que y est un chat f lin Soit D x y le pr dicat que x d teste y Pour chacune des assertions suivantes exprimez l assertion sous la forme d une proposition quantifi e et exprimez la n gation de cette assertion d abord sous forme d une proposition quantifi e et puis comme une assertion en fran ais Vous tes libre d util
4. iser ou de ne pas utiliser l op rateur tel que barre verticale Seul un pr dicat peut tre ni Tous les chiens d testent tous les chats Certains chiens d testent tous les chats Certains chiens d testent certains chats Il y a un chat que tous les chiens d testent Pour tout chat il y a un chien qui le d teste Pour tout chien il y a un chat qu il d teste TE CE Question 3 sur les ensembles 20 points Dans une certaine cole de musique il y a 64 tudiants dont 34 chantent 30 jouent d un instrument 26 crivent de la musique 12 chantent et jouent 10 chantent et crivent 8 jouent et crivent et 3 chantent et jouent et crivent Partie a 6 points Combien y a t il d tudiants sans aucun talent musical sauf pour critiquer la musique pour un journal local Justifiez Partie b 4 points Combien de triplets ordonn s x y z y a t il tels que x chante et joue mais n crit pas y chante et crit mais ne joue pas et z crit et joue mais ne chante pas Justifiez Partie c 4 points On dit qu un tudiant est un sp cialiste s il crit mais ne joue pas ou s il joue mais n crit pas Combien y a t il d tudiants qui sont soit des sp cialistes mais pas des chanteurs soit des chanteurs mais pas des sp cialistes Justifiez Partie d 6 points Le directeur de l cole cherche former un orchestre de chambre parmi les tudiants qui jouent mais n crivent pas et ne chantent pas Combien y a t i
5. l d orchestres possibles avec au moins 1 joueur Avec au moins 2 Avec au moins 3 Justifiez Question 4 sur les fonctions et l arithm tique modulaire 20 points Soit E 3 2 1 0 1 2 3 et soit S 1 0 1 Soit f la fonction de E vers S d finie par fx 1 si x gt 0 f x 1 si x lt 0 et 0 0 Soit g la fonction de S vers E d finie par g x x mod 3 1 Pour chacune des fonctions f g fog gof o o veut dire la composition de deux fonctions Partie a 4 points Dessinez le diagramme de cette fonction Partie b 8 points Dites si la fonction est injective si elle est surjective si elle est bijective Justifiez Partie c 4 points Si la fonction n est pas surjective donnez son image tendue Partie d 4 points Si la fonction est bijective dessinez le diagramme de son inverse sa r ciproque Question 5 sur les suites 15 points dont 9 pour la partie a nn n n nn Partie a valuez les sommes suivantes D D 3i 2 j D D i j D 5 j i l j 1 i l j 1 i l j 1 Partie b Une suite g om trique a pour premier terme x pour deuxi me terme y et pour dernier terme z En supposant que x y donnez une formule pour la somme de la suite en fonction de x y etz Question 6 sur le comportement asymptotique des fonctions 20 points Partie a 10 points Pour chacune des fonctions suivantes donnez le plus petit nombre r el n tel que la fonction est dans O x AO BAN POE INEA ABA 2x3 x2l08 x
Download Pdf Manuals
Related Search