MANUEL D’ENTRETIEN
Contents
1. 3 1 2 1 1 1 0 1 1 0 2 0 3 0 Partie b 8 points Dites si la fonction est injective si elle est surjective si elle est bijective Justifiez Solution f n est pas injective puisque par exemple 1 2 1 donc n est pas bijective est surjective puisque f 1 1 0 0 et A1 1 donc tout le codomaine est couvert g est injective puisque les images de 1 O et 1 sont toutes distinctes 0 1 et 1 respectivement n est pas surjective puisque par exemple x Z2 pour tout x dans le domaine donc n est pas bijective Jog est injective puisque les images de 1 0 et 1 sont toutes distinctes 0 1 et 1 respectivement est surjective puisque tous les membres 1 0 et 1 du codomaine sont touch s donc est bijective noter fog est bijective m me si f n est pas injective et g n est pas surjective Pouvez vous trouver une condition n cessaire et suffisante sur f et g pour que fog soit injective surjective bijective La solution est sur le site web la solution du Devoir 1 de la session A03 gof n est pas injective puisque par exemple gof 1 gof 2 1 donc n est pas bijective n est pas surjective puisque par exemple gof x 2 pour tout x dans le domaine Partie c 4 points Si la fonction n est pas surjective donnez son image tendue Solution L tendue des deux fonctions non surjectives g et gof est 1 0 1 Partie d 4 points Si la fonction est bijective dessinez le diagramme de son invers2. 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 Solution AC GC AC Z _ CGA CG_ A CGA Partie b 4 points Trouvez un alignement entre ACGTGA et ACTGGGA de co t minimum Solution AC GTGA ACTGGGA Cet alignement est de co t 2 Pour un co t lt 2 il faut au plus un _ et puisque les longueurs des s quences sont 6 et 7 le nombre des _ doit tre impair donc exactement un Parmi les 7 alignements avec un seul le co t minimum est 2 et l alignement dessus est le seul de co t 2 11 Dans la suite le symbole _ sera appel espace Partie c 8 points Quel est le co t maximum d un alignement entre x1x2 X et Y1Y2 Ym en fonction de n et de m Justifiez votre r ponse Solution n m Le co t d un alignement ne peut pas tre plus grand que sa longueur k et puisqu on ne peut pas aligner un espace avec un autre espace k lt n m d o aucun alignement ne peut avoir un co t gt ntm Par contre on peut toujours trouver un alignement de co t ntm en mettant m espaces avant x1x x et n espaces apr s y1y2 Ym donc n m est le co t maximum Partie d 10 points D montrez qu il existe un alignement de co t 0 entre x1x2 x et y1y2 y Si et seulement si n m et x1x2 x y1y2 y les s quences sont de la m me longueur et
3. est dans O x fh amp x3 2x 2x 1 ha 2 1 x 1 130 2x3 x2log x Jax log x 2 x OY i l Solution Pour fi x et f x on simplifie le num rateur et le d nominateur en ne gardant que le terme avec l exposant le plus grand sans coefficient et puis on fait la division Ainsi 10 se simplifie x3 x x2 n 2 et fa x se simplifie x2 x x n 1 Pour f x et f4 x on utilise le fait que log x cro t moins vite que toute puissance positive de x Ainsi x2log x sera domin par 2x et peut tre limin f x se simplifie x3 n 3 De la m me fa on log x 2 sera domin par Vx puisque log x cro t moins vite que x 4 donc J se simplifie Vx n 0 5 Pour f5 x on remplace chaque terme par le plus grand terme x2 ce qui augmente la valeur de la somme Donc fs x lt x x2 x n 3 En fait on a d montr que n lt 3 mais pas que n23 Pour compl ter la preuve on peut soit utiliser le calcul int gral soit proc der ainsi On divise la somme en 2 parties xX plancher x 2 xX 2 2 2 i A Ji i Xi La premi re somme est non n gative Pour la i l i l i 1 plancher x 2 deuxi me on constate que chaque terme gt x 2 et il y a au moins x 2 termes donc la deuxi me somme gt x3 8 La somme originale gt x3 8 d o n gt 3 Puisque la preuve n a pas t demand e il suffit de donner la bonne r ponse n 3 Partie b 10 points tant donn deux fonctions f et H
4. pour tout ionax y Notez qu il faut d montrer deux nonc s a sin m et x1X2 Xy Y1Y2 Ym alors il existe un alignement de co t 0 entre x x x et Y1Y2 Ym b s il existe un alignement de co t 0 entre x x2 x et y1y2 y alors n m et x1X2 X Y1Y2 Vme Solution Preuve de l nonc a Supposons que n m et x1x2 x y1 2 y C est dire les s quences sont de la m me longueur et pour tout i on a x y Alors on met chaque y directement au dessous de x ce qui donne un alignement de co t 0 Preuve de l nonc b Supposons qu il existe un alignement de co t 0 entre x1x2 x et y1 2 ym Alors un tel alignement ne peut pas avoir des espaces puisqu un espace ne peut pas tre au dessous d un autre espace ce qui implique que k n m L alignement do t tre X1X2 Xm Y1V2 Ym avec y directement au dessous de x pour tout i Puisque le co t est 0 on a x y pour tout i CQFD
5. 1 INF1130 SESSION A07 DEVOIR 1 SOLUTIONS Vendredi le 19 octobre 2007 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 Solution Soit la proposition que le voyant est allum D la proposition que l indicateur est d fectueux et P la proposition que la pile est plat Alors le texte se traduit A D v P A D n P gt A Partie b 10 points Trouvez l nonc le plus simple possible qui est quivalent celui que vous avez obtenu la partie a de cette question pour diagnostiquer une panne de type 1 Solution Par de Morgan D v P D P donc on peut traiter D v Pcomme une proposition atomique q et la proposition de la partie a se simplifie A q A q A Voici sa table de v rit A q A gt q 4 _ q A g A q 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 En comparant la table de v rit de A q A q A avec celle de q on voit que ces deux propositi
6. F gt D x y ou val C x FO A D x y Pour tout chien il y a un chat qu il ne d teste pas c Certains chiens d testent certains chats Solution xl C IF P D x y ou Ihc A FO A D x y N gation VxlC GX VylF y D x y ou val C x WCF D x Aucun chien ne d teste aucun chat d Il y a un chat que tous les chiens d testent Solution 11F VxlC x D x y o IFO YC gt D x N gation Vy1F AxlC x D x y o Y FO gt IAC 4 D x 7 Pour tout chat il y a un chien qui ne le d teste pas e Pour tout chat il y a un chien qui le d teste Solution YYIFO IxC D y ou Yy FO 2x C0 D x N gation 3 1F VxiC x D x y o IFO Va C x gt D x Il y a un chat qui n est d test par aucun chien f Pour tout chien il y a un chat qu il d teste Solution VxlC GX IF y D x y ou val C x FO A D x y N gation axlC YyIF y D x y ou ETCE a WFO D x Il y a un chien qui ne d teste aucun chat 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 Solution D abord on dessine un diagramme de Venn dont voici la table d appartenance avec cardinalit o C est l en
7. e sa r ciproque Solution Pour l inverse de la seule fonction bijective fog il y a les fl ches 1 0 0 1 1 1 Puisque l inverse de fog est identique fog son diagramme est le m me sauf que fog devrait tre remplac par fog lt DIAGRAMME REMPLIR gt 8 Question 5 sur les suites 15 points dont 9 pour la partie a Partie a valuez les sommes suivantes 5 Gi 2 j 5 a j 5 5 j i 1j 1 i 1j 1 i 1j 1 Solution n n n n n n Do 3i 2j 5935 52 X 3in n 2j 3n i 2nT j Sn n n 1 2 i l j l i j 1 i j 1 i l j 1 i l j 1 5n n 1 dans la premi re somme on c SA l Se ommation et dans la deuxi me on change les r les de i et j gt 2 je nn 41 2 r2 n 102 l j 1 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 et z Solution La formule pour la somme d une suite g om trique est a r Lt Q Ar QT OP si rl r _ Ici a x et y ar d o r y x Puisque xy r 1 Enfin z ar d o ar l zr zy x En substituant GES ce qui se simplifie 2 ces valeurs dans le c t droit de la formule on obtient y x 1 y x 9 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
8. on dit que f x cro t moins vite que L si fix est dans O f x mais x n est pas dans O f x et on dit que f x et f x croissent la m me vitesse si fix est dans O x et fix est dans O x Classez les fonctions de la partie a selon leur taux de croissance si f x cro t moins vite que H alors crivez f x gauche de h 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 h x tait x 1 et f3 x tait x2 alors il faudrait crire IE a h Solution Il suffit de comparer les estim s des fonctions A h fA B s 10 Question 7 sur les s quences de la bioinformatique et les preuves 25 points Soit X1X2 x Et Y 1Y2 y 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 aj4 d bb5 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 vb b si l on efface les symboles _ de la s quence aa ay on obtient la s quence x x2 x et si l on efface les symboles _ de la s quence b b2 b on obtient la s quence y 72 7 Par exemple voici un alignement des s quences ACGTGA et ACTGGGA A GT ___ A LC Er p e G GUA Le co t de l alignement 4142 Ak b b5 b est le nombre
9. ons sont logiquement quivalentes d o A DvP A DAa P A Dv P Puisque D v Pne peut pas tre simplifi c est l nonc le plus simple possible qui est quivalent celui obtenu en la partie a de la question Partie c 5 points Retraduisez en fran ais votre nouvel nonc Solution L indicateur est d fectueux ou la pile est plat 2 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 utiliser ou de ne pas utiliser l op rateur tel que barre verticale Seul un pr dicat peut tre ni a Tous les chiens d testent tous les chats Solution VxlC GX VF DG y o Va C YF gt D x y N gation axl C x 1F D x y ou Ihc A FO A D x y Il y a un chien et un chat qu il ne d teste pas ou Il y a un chien qui ne d teste pas tous les chats b Certains chiens d testent tous les chats Solution xl C x VyiF D a y ou 3x C x A Vy F gt gt D x y N gation VxlC GX I
10. semble de chanteurs J l ensemble de joueurs et E l ensemble de compositeurs musiciens qui crivent de la musique C J E 1 3 1 5 8 3 1 7 10 3 0 9 12 3 1 11 26 3 5 7 0 13 30 3 5 9 0 15 34 3 7 9 0 1 64 3 5 7 9 11 13 15 O nt O m DOrODda O e eO e C 34 15 ii 9 1 la 13 5 11 1 E 26 U Classe de 64 tudiants 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 Solution Il y en a 1 selon la table d appartenance 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 Solution Ily en a CNJ E x CNE J x ENJ C CN D E x UCN E J xX EN D 0 9 7 5 315 selon la table d appartenance 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 Solution L ensemble des sp cialistes est E J et donc l ensemble requis par la question est E J C En faisant la table d appartenance de cet ensemble on trouve qu il est compos des musiciens avec un nombre impair de talents sa cardinalit est 3 11 13 15 42 J 30 Que
11. stion C 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 il d orchestres possibles avec au moins 1 joueur Avec au moins 2 Avec au moins 3 Justifiez Solution L ensemble des musiciens qui jouent mais ne font rien d autre est J CU E de cardinalit 13 Un orchestre est un sous ensemble de J CU E donc il y a 213 8192 orchestres dont 1 vide et donc il y en a 8191 avec au moins 1 musicien Parmi ceux ci 13 consistent d un seul musicien donc il y en a 8178 avec au moins 2 musiciens Parmi ceux ci 13 12 2 78 sont compos s de 2 musiciens comptez les paires non ordonn s de 13 musiciens donc il y en a 8100 avec au moins 3 musiciens 5 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 Solution Pour f il y a les fl ches 3 1 2 1 1 1 0 0 1 1 2 1 3 D Pour g il y les fl ches 1 0 0 1 1 1 Pour fog il y a les fl ches 1 0 0 1 1 1 lt DIAGRAMME REMPLIR gt Pour gof il y a les fl ches
Download Pdf Manuals
Related Search