Université Paris 13 Partiel du jeudi 25 novembre 2004 ILOG2
Contents
1. 2 Syntaxe DefConcept gt NomConcept DescrConcept Defindividu gt Nomindividu DescrConcept DefR le gt NomR le DescrR le DescrConcept gt NomConcept CombConcept D finition Restriction CombConcept gt AND DescrConcept D finition gt D finitionExtensionnelle D finitionPrimitive D finitionExtensionnelle gt ONE OF Nomindividu D finitionPrimitive gt PRIMITIVE DescrConcept DISJOINT PRIMITIVE DescrConcept Restriction gt RestrictionCardinalit Restriction Valeur RestrictionCardinalit gt AT LEAST EntierPos NomR le AT MOST EntierPos NomR le Restriction Valeur gt ALL NomR le DescrConcept FILLS NomR le NomlIndividu SAME AS CheminAttributs CheminAttributs Descrindividu gt DescrConcept Descrk le gt NomR le INVERSE NomR le DescrAttribut gt ATTRIBUT NomR le DescrR gle gt NomConcept gt DescrConcept CheminAttributs gt NomAttribut NomAfttribut gt 1 nom de r le NomConcept gt 1 symbole de concept Nomlndividu gt 1 symbole d individu NomR le gt 1 symbole de r le EntierPos gt T entier positif EXAMEN D OPTIMISATION COMBINATOIRE 1 Institut Galil e Universit Paris 13 Examen du lundi 24 janvier 2005 ILOG2 MMI1 MI1 Dur e 3 heures notes de cours et TD autoris es 1 EXERCICE 1 max 271 To C 4T T2 lt Soit le programme lin aire P z z lt 1 3T1 2 gt 6 Ti2. Jel Construisez une ontologie en logique de description CLASSIC dont le langage est donn en annexe qui d crive les connaissances ci dessous Conservez autant que possible les termes du texte pour d signer les concepts et les r les Pr cisez bien quels sont les concepts g n riques et les individus concepts individuels Choisissez et respectez une convention de nommage par exemple les noms de concepts en majuscule en concat nant les mots comme ENTITEABSTRAITE les noms d individus avec une majuscule comme JeanDupont et les noms de r les en minuscule comme aPourDate entit et processus sont les concepts de plus haut niveau juste sous topConcept une entit administrative est une entit abstraite un b timent est une entit concr te une personne est une entit concr te une entit administrative se situe dans un b timent un coll gien est une personne un lyc en est une personne un tudiant est une personne un coll gien est l ve dans un coll ge un lyc en est l ve dans un lyc e un tudiant est l ve dans une universit un coll ge un lyc e une universit sont des entit s administratives qui d livrent des dipl mes un lyc e d livre le baccalaur at un dipl me poss de les caract ristiques aPourDate aPourDiscipline et aPourMention toute personne peut avoir un dipl me LU UJ 3 4 Le 20 3 7 Compl tez les connaissances ci dessus pour que votre ontologie soit coh rente
3. Exercice 1 On dispose de 3 urnes La premi re urne contient 3 boules num rot es 1 2 et 3 la deuxi me contient 2 boules num rot es 2 et 3 la troisi me contient 3 boules num rot es 2 3 et 4 On choisit au hasard une urne et on tire une boule dans l urne Soit U l v nement la io urne est choisie pour i 1 2 3 On note Y le num ro de la boule tir e 1 Calculer P U P Y kIU pour i 1 2 3 et 1 lt k lt 4 En d duire la loi de Y et calculer E Calculer les probabilit s conditionnelles P U Y amp PEPR k 3 Les v nements 1 et U sont ils ind pendants Justifier votre r ponse a a Exercice 2 Dans un jeux de d on s int resse la sortie du num ro 6 1 On jette plusieurs fois le d On suppose que les jets sont ind pendants est l v nement exactement un 6 au cours des k 1 premiers jets k gt 1 B l v nement le k i me jet donne un 6 Quelle est la probabilit de Aet de B 2 Soit X la variable al atoire qui est le nombre minimum de jets n cessaires pour obtenir deux 6 Exprimer l v nement X k en fonction de A et de B 3 En d duire la loi de X 4 Calculer E X et Var X Indication si lai lt 1 Jo n 0 Q Yna E S n n a z S n n 1 n 2 a n l Ha a n 2 1 a n 3 d g a Exercice 3 On tire successivement et sans remise 2 boules dans une urne qui contient n boules num rot es de 1 n Y le premier num ro
4. qu il ne manque pas de relations et que toutes les relations soient correctes Rajoutez les connaissances n cessaires concepts et r les g n riques ou individuels pour repr senter le fait que l individu Jean Dupont a obtenu son baccalaur at S avec mention Bien en juillet 2001 Quelles connaissances sur l individu Jean Dupont un classifieur peut il d duire Pr cisez la cardinalit des r les seSitue Dans et aPourDate Comment pourriez vous exprimer qu une personne a un dipl me si et seulement si elle a suivi les tudes correspondantes en particulier elle a t l ve dans un lyc e pour avoir le baccalaur at Proposez une mod lisation plus raffin e qui permette de d tailler les dipl mes d livr s par le d partement d informatique de l Institut Galil e Logique de description ee Langage Classic 1 Vocabulaire Ensemble de symboles non logiques Symboles de concept CONCEPT Symboles d individus Individu Symboles de r les r le AND ALL FILLS AT MOST AT LEAST ONE OF SAME AS PRIMITIVE DISJOINT PRIMITIVE INVERSE ATTRIBUT Ensembles de symboles logiques Vocabulaire auxiliaire DefConcept Defindividu DefR le DescrConcep Descrindividu DescrR le DescrAttribut DescrR gle NomConcept Nomindividu NomR le NomAttribut CombConcept D finition D finitionExtensionnelle D finitionPrimitive Restriction RestrictionCardinalit Restriction Valeur CheminAttributs EntierPos
5. 1 71 1 6 R soudre le programme lin aire en variables continues K associ K D terminer une solution r alisable de K par l heuristique gloutonne et la valeur v K associ e 3 mme Calculer les co ts r duits optimaux de K en d duire que pour esp rer trouver une valeur sup rieure v K les variables z et z2 doivent tre fix es la valeur 1 4 _ Premi re fa on de poursuivre la r solution de K 4 1 Utiliser la relaxation lagrangienne associ e u 2 1 pour fixer la variable z3 la valeur 1 4 2 D duire par implication logique la fixation 0 d une nouvelle variable 4 3 R soudre le probl me ainsi r duit deux variables en d duire la solution optimale ainsi que la valeur de K 5 Autre facon de poursuivre la r solution de K i e autre suite de la question 3 5 1 On note K le probl me K z1 z2 1 D montrer que la variable z4 doit tre fix e la valeur 0 en d terminant la solution vidente en variables 0 1 du probl me K z4 1 5 2 On note K le probl me K z z2 1 4 0 R soudre le programme lin aire en variables continues K associ K 5 3 Calculer les co ts r duits optimaux de K en d duire que pour esp rer trouver une valeur sup rieure v K les variables z3 et xs doivent tre fix es la valeur 1 5 4 Retrouver par implication logique la solution optimale ainsi que la valeur de K Institu
6. Exercice 3 On envisage le programme lin aire en nombres entiers P suivant min 9T1 2T2 s c 4x1 T2 lt 8 1 spi 2 lt 1 2 3x1 2x2 gt 6 3 T1 z2 EN dont on suppose connu le tableau optimal du programme lin aire en variables continues associ o T3 Ta t z5 sont les variables d cart ou de surplus respectives des contraintes 1 2 et 3 1 Rappeler les r solutions graphiques de P et de PL Dessiner galement le domaine Conv Dom P pr ciser les valeurs des probl mes et les solutions optimales z de P et z de PL 2 D terminer et repr senter graphiquement la coupe de Dantzig les coupes de Gomory associ es z1 2 et z3 chaque fois pour A 1 3 Parmi ces quatre coupes laquelle permettrait de r soudre la probl me P par la r solution en continu Expliquer 4 R soudre P par un algorithme de branch and bound en n utilisant que les r solutions gra phiques des programmes lin aires en continu associ s aux sous probl mes de chaque n ud de l arborescence Exercice 4 On consid re le programme lin aire en nombres entiers P suivant MAT T1 T2 s c 9x1 3x2 lt 20 1 3T1 672 lt 14 2 T1 T2 gt Q et entiers 3 et le probl me en variables continues associ not PL 1 D terminer successivement par r solution graphique les valeurs et solutions optimales et r alisables de P et de PL ainsi que les
7. T2 gt 0 1 R soudre graphiquement le probl me P 2 D rouler la premi re phase de l algorithme primal du simplexe en suivant le crit re de Dantzig ehair de dD Indication le dernier tableau du simplexe correspondant la base r alisable optimale de P est le suivant 5 3 11 3 1 3 4 3 1 3 2 EXERCICE 2 max 271 To E AS S C Ati T2 lt 8 Soit le programme lin air Pi Lu z 72 lt 1 Ti Z2 gt 0 1 Que pouvez vous dire a priori sur les valeurs optimales relatives de P et de Q Le dernier tableau du simplexe correspondant la base r alisable optimale de Q est le suivant 4 0 1 1 3 4 3 3 1 0 1 3 178 2 Dans quelle mesure peut on faire varier le param tre sans changer de base r alisable optimale I a Si l on remplace la contrainte 4x 2 lt 8 par la contrainte 4x1 z2 lt 8 b Si l on remplace la contrainte x1 z2 lt 1 par la contrainte 1 2 lt 1 c Si la fonction objectif 2x1 xz devient la fonction 2 x1 2 d Si la fonction objectif 2x z2 devient la fonctiongr 1 xo 1 Pour chacune des quatre questions pr c dentes donner la solution de base x I et sa valeur vo x 1 en fonction de 3 crire de dual Do du prol me Q 4 R soudre Do des quatre mani res suivantes a r solution graphique du probl me dual b d termination de la solution duale partir de la fonction objectif et
8. du tableau optimal c d duction partir du vecteur de co ts marginaux de la base optimale d d duction partir des relations d exclusion 3 EXERCICE 3 min T1 ITa s c t1 T2 lt 8 Soit le programme lin aire R z z lt 1 3x1 2To gt 6 Ti T2 2 0 1 Initialiser l algorithme dual du simplexe 2 Faire une seule it ration de l algorithme dual du simplexe 4 EXERCICE 4 CG lt Soit le programme lin aire S PGE PE a Pa 2T3 P T 2 gt 1 2 3 2 0 1 R soudre par l algorithme primal du simplexe 2 crire le dual Ds de S confirmer le r sultat obtenu la question pr c dente par r solution graphique de Ds C RECANATI Interfaces Graphiques ILOG 2 2004 2005 Examen du 21 octobre 2004 14h 17h On veut crire un programme pr sentant une fen tre dans laquelle on pourra dessiner des lignes Cette fen tre sera dispos e au dessus de trois boutons align s comme sur la figure ci dessous les boutons sont implant s ici par des fen tres dans lesquelles ont dessine une cha ne de texte qui permettront de lancer des commandes Lors d un changement de taille de la fen tre principale la fen tre de dessin de lignes devra s agrandir afin d occuper le maximum d espace en largeur et en hauteur en laissant bien entendu l espace n cessaire en bas aux trois fen tres boutons Les fen tres boutons seront donc attach es comme il convient au bas de la fen tre
9. est ce qu une sp cialisation maximale Donner 2 r gles de g n ralisation Donner 2 r gles de sp cialisation 2 2 Exercice Spts On d crit des pierres par leur forme ronde oblongue irr guli re leur poids en gr le fait qu elles l soient coupantes ou pas Ces pierres sont peut tre des outils pr historiques On veut apprendre reconna tre les outils Ces objets sont donc soit des exemples positifs d outils soit des exemples n gatifs On va construire l espace des versions d finissant l ensemble de tous les concepts coh rents avec les exemples positifs et n gatifs connus c est dire dont les l ments acceptent les outils et rejettent les autres pierres Soient les exemples suivants PAS 222 elr oblongue 300 non coupante e2 irr gulier 700 non coupante Es irr gulier 400 coupante e4 ronde 60 non coupante GoT oblongue 150 coupante D roulez l algorithme pas pas en donnant chaque fois G et S les ensembles des hypoth ses respectivement les plus g n rales et les moins g n rales de H ensemble des hypoth ses Lors de l initialisation G vrai et S Expliquez chaque modification de G ou S quelles sp cialisations maximales ou g n ralisations minimales vous introduisez Donnez un exemple de concept plus g n ral qu un l ment de S et plus sp cifique qu un l ment de G qui sera donc solution 3 Construction d ontologie 8 pts
10. proc dure CRCW ProduitMatrices A B C optimale au sens du 3 2 ii Calculer la complexit Tcrcw n de ProduitMatrices A B C En d duire que la proces dure est bien optimale toujours au sens du 3 2 3 4 Algorithme produit EREW a Sous les hypoth ses du 3 3 peut on calculer le produit A x B avec un algorithme EREW Ses performances sont elles alors les m mes b D crire un algorithme EREW de che en temps TEREw n O log n calculant A x B matrices carr es n x n l aide de n processeurs L algorithme EREW obtenu est il efficace Optimal 4 Recherche des racines d un arbre binaire Consid rons une for t F d arbres binaires et l algorithme qui permet chaque n ud de conna tre la racine de son arbre On se restreint ici au cas particulier o F n est constitu e que d un seul arbre binaire n n uds a crire un algorithme TrouverRacines qui r sout le probl me b Montrer qu avec cette hypoth se on peut faire en sorte qu un algorithme CRCW Trou verRacines s ex cute en O 1 ind pendamment de la profondeur de l arbre c Montrer qu une impl mentation EREW quelconque de TrouverRacines n cessite un temps Q log n d Les algorithmes CRCW et EREW obtenus respectivement en b et c sont il efficaces Optimaux 5 Classement optimal d une liste cha n e Soit une liste cha n e cha n e L contenant n objets L algorithme EREW de classement par sauts de pointeur
11. processus F 1 lt i lt Z est alors calcul e comme le produit id X p 2 1 La d finition de la variable val est elle math matiquement fond e En d autres termes le d montrer i Toutes les variables val des processus initiateurs construites partir de p et id ont elles bien des valeurs distinctes ii En chaque initiateur d identit id la fonction al atoire enti re prem id 2n a t elle un bien sens Autrement dit engendre t elle un nombre premier p tel que id lt p lt 2n gr ce un tirage al atoire uniforme sur un ensemble d entiers d fini correctement et sans ambiguit 2 2 Expliquer en d tail le d roulement de l algorithme distribu A sp cifi ci dessus en prenant 1 lt T Z lt n Pr ciser le comportement des initiateurs et celui des n processus non initiateurs ainsi que le r le jou par la variable val Montrer que l algorithme lit un processus qui n est pas n cessairement celui qui serait lu par l algorithme de Chang Roberts 2 3 Complexit en messages Quelle sont les configurations qui constituent le meilleur cas et le pire cas pour la complexit en messages de l algorithme A En d duire ces deux mesures de complexit Cmin n et Cmaz n 1 pour un initiateur unique 2 lorsque tous les processus sont initiateurs En d duire la complexit moyenne en messages C n de l algorithme A 2 4 Complexit en temps Quelle est la configuration qui c
12. un doublement du nombre de contraintes D montrer qu il suffit d ajouter l unique contrainte TTL mn Aix gt Yai 1 au syst me Aix lt ai Vi 1 m 2 t i l pour obtenir l quivalence avec le syst me de contraintes initial Am o Vie leam 0 Institut Galil e Th orie des graphes Algo3 Ann e 2004 2005 L3 Informatique ILOG2 Devoir rendre pour le 28 02 2005 1 Sujet On consid re le probl me de la recherche des composantes fortement connexes d un graphe orient Pour r soudre ce probl me nous allons utiliser l algorithme de Kosaraju Sharir vu en cours et en TD 2 Travail r aliser Ce devoir est faire en bin me Programmer l algorithme de Kosaraju Sharir ainsi que DFS Faire une analyse de complexit de votre impl mentation En sortie de votre programme vous devrez fournir le graphe r duit sous la forme d un fichier d instance 2 1 Bonus Pour ceux qui d sirent aller plus loin vous pouvez cr er une petite interface graphique permettant de s lectionner le fichier d instance d afficher le d roulement de l algorithme et enfin d afficher le graphe r duit obtenu 3 Instances Vous devrez g n rer les instances vous permettant de tester votre programme Pour cela vous impl menterez un g n rateur de graphes orient s qui en sortie devra fournir l instance dans un fichier ce fichier devant comporter au minimum le nom bre de sommets le nombre d arcs et les
13. ION RESPECTEZ LES NOTATIONS DE L NONC Exercice 1 application de la m thode probabiliste K d signe la clique n sommets c est dire le graphe complet n sommets Soit 2 lt n Montrez qu il existe un 2 coloriage des ar tes de la clique X qui laisse au plus n e oi 2 o Exercice 2 calcul d esp rance et de variance sous cliques K monochromes Soit o une permutation de 1 n Un couple i j 1 lt 4 lt j lt n est une inversion de o si o j lt a i On d signe par Inv ao le nombre d inversions de Dans la suite on consid rera que toutes les permutations de 1 n sont quiprobables n n 1 a Montrez que E Inv o Indication utilisez Ij variable al atoire indica trice de l v nement i j est une inversion n n 1 2n 5 b Montrez que Var Inv o 2 i lt j c On consid re le tri par insertion d une liste de n valeurs deux deux distinctes Par exemple si la liste de d part est Indication utilisez la variable al atoire 6114253 les tats apr s chaque insertion sont on a fait appara tre en gras les valeurs qui sont d plac es au cours de l insertion ki Li NO ND A EE 6 5 6 1 2 3 4 5 6 On d signe par X le nombre total de valeurs d plac es au cours du tri En supposant que tous les ordres initiaux sont quiprobables calculez E X et Var X 1 Exercice 3 analyse d algorithme randoni
14. PARTIEL D OPTIMISATION COMBINATOIRE 1 Institut Galil e Universit Paris 13 Partiel du jeudi 25 novembre 2004 ILOG2 MMI MIT Dur e 2 heures notes de cours et TD non autoris es 1 EXERCICE 1 max T ATo s c 5tit z2 lt 16 PE lt Soit le programme lin aire P a i nee p p o a ER 1 lt To lt 6 T1 22 gt 0 1 R soudre graphiquement le probl me pour a 1 2 puis Q 2 2 Appliquer l algorithme du simplexe pour a 1 et en d duire l ensemble des solutions optimales de P 1 2 EXERCICE 2 max 271 To 8Ta S C T4 1 2r3 Soit le programme lin aire P T5 3 92 4z 6x3 T6 2 71 3x2 dta T1 T2 Z3 La T5 T6 gt 0 1 Donner une solution triviale du probl me 2 Faire une it ration de l algorithme du simplexe que remarquez vous 3 EXERCICE 3 tant donn s R et f f f R tel que Jj 1 n f gt 0 on s int resse au probl me suivant ad se y 17 0 PAT x E0 1 V5 1 n y 0 1 Donner les deux valeurs possibles avec les solutions optimales et r alisables associ es du probl me P A f selon les valeurs relatives du r el et du vecteur f 4 EXERCICE 4 La transformation d un syst me de contraintes d galit en un syst me de contraintes d in galit peut se faire simplement en rempla ant chaque contrainte A x a par la paire de contraintes Aix lt ai Aix gt ai ce qui implique
15. Z LES NOTATIONS DE L NONCE Exercice 1 calcul d esp rances Dans cet exercice g d signe une permutation de l ensemble 1 n On suppose que toutes les permutations de 1 n sont quiprobables a On dit que i 1 n est un point fize de o si ofi i Calculez E F o F est le nombre de points fixes de On rappelle que o i a ix est une sous suite croissante de o si et seulement si i lt ig lt lt ip et ali lt olia lt lt olik b Une sous suite croissante maximale est une sous suite croissante qui n est incluse dans aucune autre sous suite croissante Par exemple la permutation 3 5 1 2 4 6 a exactement deux sous suites croissantes maximales 3 5 6 et 1 2 4 6 Calculez E M o M est le nombre de sous suites croissantes maximales de Indication Consid rez j variable al atoire indicatrice de l v nement Il existe une sous suite croissante maximale qui commence par la valeur 5 c Une suite montante est une sous suite croissante de valeurs cons cutives qui n est incluse dans aucune autre sous suite croissante de valeurs cons cutives Par exemple la permutation 4 3 5 1 2 6 a exactement trois sous suites montantes 4 5 6 3 et 1 2 Calculez E R o R est le nombre de sous suites montantes de d Calculez E X o X est le nombre de sous suites croissantes de Exercice 2 Algorithme Las Vegas pour une grande coupe On cherche une coupe auss
16. ang le toujours plus a c d la place au toujours mieux Quels sont les deux principaux facteurs de l volution en cours Question 6 1 point En quoi consiste l annualisation du temps de travail WQuestion 7 2 points Pour faire face une p riode difficile et sans recourir des licenciements quels sont les autres proc d s la disposition d une entreprise pour r duire ses effectifs Question 8 2 points Quelle diff rence faites vous entre qualification et comp tence Question 9 3 points Apr s avoir d fini le besoin en fonds de roulement vous expliquerez pourquoi l activit d une entreprise engendre un tel besoin Vous pourrez illustrer votre r ponse par un sch ma Question 10 2 points Quels sont les principaux moyens externes dont dispose une entreprise pour financer sont cycle d investissement Partiel d Ing nierie des Connaissances jeudi 9 juin 2005 9h 11ih Amphi Euler Tous documents manuscrits autoris s Bar me indicatif 1 Analyse syntaxique de texte en LN 5 pts Soit le texte suivant Unissons nous contre le projet d implantation d un Centre de R tention Administrative Deuil la Barre Unissons nous afin que notre ville reste toujours UNE VILLE DANS SON JARDIN extrait de la p tition NON au CRA du maire de Deuil la Barre J C Noyer juin 2005 1 1 Consid rez les noms ou expressions suivants implantation Centre R tention Administra
17. arcs sous forme de matrice d adjacence ou de liste par exemple Vous devrez galement fournir des explications d taill es du format des instances dans un fichier s par 4 A rendre Le devoir doit contenir un rapport dans lequel vous devrez d crire le probl me les algorithmes utilis s les analyses de complexit et les r sultats que vous aurez obtenus sur les diff rentes instances Votre devoir et pas le rapport doit galement contenir vos programmes comment s avec makefile et readme si n cessaire les instances et le fichier explicatif du format des instances Le rapport est ren dre sous forme de fichier txt doc tex ou html et sous forme papier d poser d ns le casier ILOG2 ou L3 Informatique Les fichiers rapport et pro grammes sont envoyer par mel letocart lipn univ paris13 fr pour les ILOG2 et toulouse lipn univ paris13 fr pour les L3 Informatique Le tout doit tre mis dans une archive tar gz ou tgz MI1 ILOG2 ann e 2004 2005 Probabilit s et Statistiques Epreuve Partielle Exercice 1 On joue n fois avec une pi ce de monnaie La probabilit d avoir une pile est p les jets sont suppos s ind pendants Soit X la variable al atoire qui vaut 1 si le i i me jet donne une pile et 0 sinon Soient S gt X le nombre des piles obtenues X 2 la i n proportion des piles 1 On fixe le nombre de jets n 100 et p 0 40 a Calculer E X et Var X Quelle loi continue peut on
18. autres processus et qu il est seul conna tre Ces identit s appartiennent l ensemble fini n 1 n C N lt l ordre total des entiers L algorithme A est d clench par un ensemble non vide 7 C n d identit s de processus appel s initiateurs de mani re ind pendante et non simultan e 6 2 Preuve informelle de Sous l hypoth se d un nombre quelconque 7 d initiateurs 1 lt I lt n expliquer le d rou lement global de l algorithme A a Pr ciser le comportement des I initiateurs et celui des n I processus non initiateurs non sp cifi dans l algorithme donn page 5 Que fait un processus passif actif b partir de l algorithme de Franklin vu en cours montrer que utilise le m me principe de comparaison entre identit s sous des hypoth ses plus restrictives Quelle est l identit lue ici par l algorithme A c L algorithme A s ex cute l aide de trois identit s quelconques r q et p prises dans cet ordre sur l anneau unidirectionnel Autrement dit q est l identit du premier pr d cesseur actif de p et r joue le m me r le pour q compte tenu du sens de rotation des messages sur l anneau A est sp cifi ici page 5 pour l identit p Expliquer le r le des variables idcour identit courante ou provisoire et idpredp identit du premier voisin actif de p qui le pr c de sur l anneau utilis es par p Que se passe t il lorsque idco
19. d terminer le plus grand entier k tel que CH1 CT2 CTk Cin k 1 Cin 1 Cin Autrement dit k est la taille du plus long pr fixe de C qui est aussi un suffixe de C Donner un algorithme parall le CRCW de complexit en temps T n O 1 Cet algorithme est il efficace Optimal 2 Calcul parall le de n Le but est de donner un algorithme parall le qui calcule n la factorielle d un entier donn n en temps Oflog n avec O n processeurs 2 1 Algorithme de la factorielle a Sp cifier l algorithme qui calcule n sous ces hypoth ses b Pr ciser la technique ainsi que le type d algorithme parall le de PRAM utilis c L algorithme obtenu est il efficace Optimal 3 Produit de deux matrices Soit un algorithme parall le CRCW calculant le produit d une matrice m x k et d une matrice B x n selon la formule classique du produit de deux matrices quelconques 3 1 Formule du produit de deux matrices Sous quelles conditions le produit x B existe t il Rappeler la formule calculant les coeffi cients de la matrice produit C m x n 3 2 Algorithme produit CRCW optimal Pr ciser comment r soudre les conflits en lecture criture pour obtenir un algorithme fond sur la formule de 3 1 ci dessus et optimal par rapport l algorithme s quentiel correspondant de complexit en temps T n O n 2 n max n k m 3 3 Proc dure ProduitMatrices A B C i crire une
20. e de Calculer la complexit en espace m moire S n de 6 3 4 Comparaisons de performances Comparer les mesures de complexit respectives de A questions 6 3 1 6 3 2 et 6 3 3 ci dessus et celles des algorithmes de Franklin et de Chang Roberts Qu en concluez vous ALGORITHME pour un processus d identit p TAPE 1 lection var tat lu battu actif passif Init nond f idcour Init idp idpred Init nond f vaing Init nond f In d but si p alors tat actif sinon tat passif fsi tantque vaing nond f faire si tat actif alors envoyer 1 idcour recevoir 1 q idpred q si idpred idcour alors idpred est un minimum local envoyer min tdpred vain idpred recevoir min g sinon idpred est l identit courante du pr d cesseur actif de p envoyer 2 idpred recevoir 2 q si idpred lt idcour et idpredp lt q alors idcour idpred sinon tat passif fsi fsi sinon tat passif recevoir 1 q envoyer 1 q recevoir M envoyer M M min q ou bien M 2 q si M min q alors vaing q fsi fsi fintantque si id vaing alors tat lu sinon tat battu fsi fin TAPE 2 Terminaison Le processus lu est l initiateur d identit minimale id Une fois lu il informe tous les processus de son identit et de la fin de l lection par l envoi d un message ci
21. e de deux Aide la d cision et optimisation et Communication homme machine et documents lectroniques Pour le semestre courant certains modules sont obligatoires pour les tudiants d sirant s orien ter vers ces deux options Il s agit des modules de Probabilit s P Algorithme et complexit II AC Ing nierie des connaissances IC et Syst mes distribu s et parall lisme SDP Certains autres sont optionnels Bases de donn es Il BD R seaux R Optimisation combinatoire H OC Interface graphique IG C C Paradigme logique PL et G nie logiciel III GL PTS X EL ele LT il K PR LL goy e ee FRERE HE ne ne ne le AP Ha OS 3 ex FT TE e FL a5 zm az ait HE Di Be CIE un J g lt Mme Eud t doit planifier les examens pr vus la fin du semestre Chaque examen dure deux heures Deux journ es sont r serv es pour planifier ces examens suivant les plages horaires suivantes 8h 10h 10h15 12h15 14h 16h et 16h15 18h15 Pour chaque examen elle conna t l ensemble des examens incompatibles qui ne peuvent avoir lieu en m me temps car devant tre effectu s par des tudiants communs Ces incompatibilit s sont r sum es dans le tableau une croix indiquant une incompatibilit Aidez Mme Eud t construire un emploi du temps de telle sorte qu aucun tudiant n ait plus d un examen en m me te
22. elle est l utilit pour une entreprise de disposer d un mod le de gestion de son portefeuille d activit Citez trois limites des mod les pr sent s en cours 2 points _ EXAMEN DE GESTION GROUPE 1 Mercredi 9 mars 2005 Question 1 3 points Si la strat gie d termine la structure la structure conditionne galement la strat gie Exposez bri vement trois raisons justifiant que les dirigeants tiennent comptent de la structure dans l laboration d une strat gie globale Question 2 2 points D finissez et sch matisez une structure divisionnelle simple x Question 3 3 points L volution de l conomie capitaliste depuis le march de p nurie du d but du XIXT si cle jusqu au march de concurrence internationale de la fin du XX si cle a fortement influenc l organisation interne de l entreprise La fonction commerciale y a pris une place de plus en plus importante G n ralement on distingue trois phases dans cette volution Pouvez vous nommez et d finir ces trois phases Question 4 2 points Quelles sont les principales m thodes de fixation des prix auxquelles recourent les entreprises Question 5 2 points En d pit de l informatisation et de l automatisation de la production le travail garde un r le essentiel dans la cr ation de biens et de services par les entreprises Mais le travail a volu dans son contenu et les objectifs qui sont assign s aux travailleurs ont ch
23. et de plus petit num ro En d duire le graphe r duit GR associ G Appliquer l algorithme de Dijkstra pour d terminer le chemin de valeur min imale issu de la source vers le puits de GR connaissant les valeurs des arcs suivants 21 27 6 27 Valeurs 4 6 le 7 da da dln Pour la valuation de GR lorsqu il y a le choix s lectionner le meilleur arc de liaison entre deux composantes fortement connexes D tailler dans un tableau les diff rentes tapes de l algorithme de Dijkstra 11 15 12 15 13 15 14 15 TET 500 700 900 1000 Universit PARIS NORD 2004 2005 Institut Galil e Ing nierie Logicielle seconde ann e Examen d Analyse Num rique Jeudi 3 F vrier 2005 9h 11h On consid re la matrice carr e A d ordre n dont tous les coefficients sont donn s par les relations suivantes dj i 1 lt i lt n i dj j 1 Oi 2 lt i lt n nn Xn 1 ai 0 dans les autres cas De plus 0 Vi i 1 2 3 n 1 1 crire les n quations du syst me lin aire Ax b o b b b Dh est un vecteur de RP On explicitera les 3 premi res quations les 3 derni res et l quation g n rale d indice i 2 Donner la solution explicite du syst me si n est pair puis si n est impair On remplacera dans les formules n par 2k puis par 2k 1 3 Trouver une formulation identique dans le cas pair et impair 4 Comment peut on minimiser l enc
24. et parall lisme SDP Certains autres sont optionnels Bases de donn es II BD R seaux R Optimisation combinatoire IT OC Interface graphique IG C C Paradigme logique PL et G nie logiciel ITI GL E ES aL JIC ic ACPE OC P SDE pen LL 1 a pi QU heeh 4 k K K H t L FL BOES k a Mme Eud t doit planifier les examens pr vus la fin du semestre Chaque examen dure deux heures Deux journ es sont r serv es pour planifier ces examens suivant les plages horaires suivantes 8h 10h 10h15 12h15 14h 16h et 16h15 18h15 Pour chaque examen elle conna t l ensemble des examens incompatibles qui ne peuvent avoir lieu en m me temps car devant tre effectu s par des tudiants communs Ces incompatibilit s sont r sum es dans le tableau une croix indiquant une incompatibilit Aidez Mme Eud t construire un emploi du temps de telle sorte qu aucun tudiant n ait plus d un examen en m me temps Ey Institut Galil e Universit Paris 13 OC2 ILOG2 Semaine du 31 mai 2005 T P Examen Dur e 2 heures Notes de cours de TD et de TP autoris es Planification d examens Dans une cole d ing nieurs de la r gion parisienne chaque semestre chaque tudiant de deuxi me ann e choisit un ensemble de huit modules parmi onze propos s en fonction de l op tion qu il d sire suivre en troisi me ann e Ces options sont au nombr
25. i grande que possible dans un graphe non orient sans boucle a Soit G X U un graphe non orient sans boucle ayant n sommets et m ar tes Montrez en utilisant la m thode probabiliste qu il existe une partition de X AU B qui d finit une coupe de taille m 2 b En utilisant la question pr c dente montrez qu il existe un algorithme Las Vegas de complexit polynomiale en le nombre de sommets qui calcule dans un graphe non orient sans boucle une coupe de taille au moins gale la moiti du nombre d ar tes Exercice 3 Marche al atoire la ruine du joueur On consid re deux joueurs et B qui chaque tour identifi un instant du processus misent chacun 1 euro Le joueur qui remporte le tour rafle la mise et on suppose que les tours sont ind pendants et qu chaque tour les deux joueurs ont chacun une chance sur deux de gagner Ce jeu est repr sent par un syst me dont l tat l instant t est le nombre d euros gagn s par le joueur depuis le d but du jeu l instant t 0 l tat du syst me du syst me vaut donc 0 Il est raisonnable de supposer que le joueur ne peut pas perdre plus de 4 euros et que le joueur B ne peut pas perdre plus de g euros le jeu cesse donc quand il atteint l tat 4 ou l tat 8 qui correspondent l un et l autre la ruine d un des joueurs a Montrez comment mod liser ce jeu l aide d une cha ne de Markov Identifiez le
26. iant 2 1 Traduisez les contraintes d h ritage sp cifi es ci dessus en utilisant SQL2 2 2 Traduisez les contraintes d h ritage sp cifi es ci dessus en utilisant SQL3 EXERCICE 3 Questions 1 2 3 points gt L Objet en SQL3 F Boufar s UP13 IG ILO2 BD 13 06 05 3 1 Cr ez un type objet cours 3 2 cr ez ensuite une table d objets cours Question 2 points gt Les entrep ts de donn es 4 1 Donnez la d finition des entrep ts de donn es et citez leurs sp cificit s par rapport aux bases de donn es transactionnelles Bonne chance Pr F Boufar s UP13 IG ILO2 BD 13 06 05 Institut Galil e Universit Paris 13 OC2 ILOG2 Semaine du 31 mai 2005 T P Examen Dur e 2 heures Notes de cours de TD et de TP autoris es Planification d examens Dans une cole d ing nieurs de la r gion parisienne chaque semestre chaque tudiant de deuxi me ann e choisit un ensemble de huit modules parmi onze propos s en fonction de l op tion qu il d sire suivre en troisi me ann e Ces options sont au nombre de deux Aide la d cision et optimisation et Communication homme machine et documents lectroniques Pour le semestre courant certains modules sont obligatoires pour les tudiants d sirant s orien ter vers ces deux options Il s agit des modules de Probabilit s P Algorithme et complexit II AC Ing nierie des connaissances IC et Syst mes distribu s
27. me un trigger la ou les tables n cessaires qui p fmet de garder un historique des prix de ventes PVArt et des prix d achat PAArt Lors des mises jour de la table ARTICLES on veut garder une trace des prix 1 3 D veloppez une proc dure PL SQL qui permet de v rifier la coh rence de la base de donn es V rifier si toutes les commandes portent au moins sur un article et afficher celles qui sont donc vides F Boufar s UP13 IG ILO2 BD 13 06 05 l Le dictionnaire de donn es de la BD GESCOM est le suivant AdnCli Adresse du client um ro Caract res Texte 5 Caract res Texte 10 jj mmm aaaa Nom d signation de l article Caract res Texte 50 Caract res Texte 20 Caract res Textes 10 __ R el 10 dont 2 d cimales Caract res Texte 30 en MAJUSCLUE PrenCli Caract res Texte 20 PVArt Prix de vente de l article Prix catalogue R el 10 dont 2 d cimales PUArt R el 10 dont 2 d cimales QsArt Entier 3 lt 1000 Q Entier 3 lt 1000 R f rence de l article Caract res Texte 10 Taux de remise appliqu l article R el 4 dont 2 d cimales VilCli Ville o habite le client Caract res Texte 20 en MAJUSCLUE i EXERCICE 2 Questions 2 3 5 points gt SQL2 et SQL3 Consid rons le sch ma suivant pr sentant des liens d h ritage PERSONNE Num ro Nom Pr nom DateNaissance Sexe fonctionnaire Echelon Indice Sp cialit Etud
28. mps Institut Galil e Syst mes Distribu s Ann e 2004 2005 ILOG2 Devoir de Syst mes Distribu s Lundi 11 04 2005 RMI Le but du devoir est la mise en oeuvre d un syst me bas sur l architecture RMI pour invoquer les m thodes fonctions distance l anc tre tant le RPC Vous proc derez ainsi l Parmi tous les algorithmes qui vous ont t pr sent s en cours TD TP vous en choisissez deux ou trois en mode centralis que vous programmerez en JAVA en tant que m thodes invocables distance 9 Vous mettez les machines en anneau sous RMI au moins 3 machines 3 Vous implantez la m thode de Chang amp Roberts pour l lection d un serveur qui se fera connaitre sur l anneau Les machines battues sont clientes et peuvent invoquer les m thodes mises en service sur le serveur Bien entendu les utilisateurs sur ces machines clientes ont droit un affichage graphique soign Challenge Les machines clientes peuvent galement aller d poser leurs m thodes chez le serveur et faire profiter tous de leur g nie cr ateur Ces m thodes deviennent invocables pour tous Le logiciel complet professionnel quoi en html ou pdf ou doit m tre envoy par e mail jc lipn univ paris13 fr Je dois y trouver entre autres une analyse en complexit de la solution Chang amp Roberts dans le cas g n ral o il y a plus d un initiateur un manuel d installation de votre logiciel e
29. ombrement m moire 1 V rifier que la m thode de Gauss Seidel est consistante 2 Expliciter les formules qui permettent de calculer les composantes de x m 1 connaissant celles de x n 3 crire en Matlab la r solution du syst me lin aire Ax b A r guli re de dimension n par la m thode de Gauss Seidel sous la forme d une fonction de param tres A betn Examen de G nie Logiciel GLIH CC Janvier 2005 L preuve dure 2 heures Les notes de cours et de TD manuscrites ainsi que les nonc s et supports de cours distribu s cette ann e sont les seuls documents autoris s Les t l phones portables doivent tre teints Soignez l criture et la pr sentation cela peut rapporter 1 2 points crivez avec un stylo d encre suffisamment sombre wO O tie ma sen E X CR P2 P3 1 a Donner pour le r seau ci dessus les matrices Pre Post ainsi que la matrice d incidence b Partant du marquage initial donn donner le marquage obtenu apr s la s quence de transitions lt t2 tl t3 t3 gt 3 P1 P2 P3 E 2 D crire le fonctionnement du r seau ci dessus et EA en d taillant les premi res tapes de calcul a le graphe des marquages accessibles b l arborescence de couverture c le graphe de couverture d Quelles sont les propri t s de ce r seau 3 Mod lisez l aide d un r seau de Petri le fonctionnement d un cabinet de consultation d un m decin qui ne perme
30. onstituent le pire cas pour la complexit en temps T n de A Calculer T n 2 5 Complexit en espace m moire Calculer la complexit en m moire S n de A dans le pire des cas lorsque tous les processus sont initiateurs Quelle est la valeur de cette complexit lorsque 1 lt Z lt n 2 6 Comparer les mesures de complexit respectives en messages en temps et en espace m moire de l algorithme d lection A et de celui de Chang Roberts Qu en concluez vous OO LL Algorithme A pour un processus P quelconque TAPE 1 lection var tat lu battu candidat passif initialis e passif io val entier Liste sous ensemble de N initialis e val d but si P est initiateur alors p prem id 2n val id x p tat candidat envoyer val recevoir val tantque val val faire Liste Liste U val envoyer val recevoir val fintantque si val max Liste alors tat lu sinon tat battu fsi sinon r p ter recevoir val envoyer val si tat passif alors tat battu fsi jusqu faux fsi fin TAPE 2 Inauguration Terminaison Le processus initiateur lu est celui de valeur maximale Vabnar lisible dans sa liste Liste Une fois lu il informe tous les processus de son identit et de la fin de l lection par l envoi d un message circulant fin Valinax qui termine l algorithme A SSSR RL RRQ
31. principale pour qu il n y ait pas besoin de les repositionner On pourra tout moment dessiner des lignes dans la fen tre graphique de la fa on suivante on clique en un point et en maintenant le bouton de souris enfonc on tire la souris jusqu un autre point o l on rel che le bouton Pendant tout le temps du tirer de la souris la ligne joignant le point initial et le point courant est affich e interactivement la pr c dente tant effac e chaque fois La derni re ligne trac e i e celle trac e au moment du rel cher sera galement dessin e dans un Pixmap qui sauvegardera ainsi le dessin des lignes Ce Pixmap sera utilis pour r afficher les droites avec la commande du bouton Show et pour traiter les v nements de type Expose pouvant survenir sur la fen tre de dessin Programmer le sujet dans l ordre suivant 1 Cr ez et affichez les diff rentes fen tres Veillez calculer la taille des boutons en fonction de la fonte pour bien les disposer dans la fen tre m re Modifiez leur attribut de gravit pour qu ils soient replac s automatiquement en cas de changement de taille 2 Programmez le tracer des lignes dans la fen tre graphique pour obtenir le comportement d crit plus haut On pourra s inspirer fortement de l exercice de tracer d un rectangle avec la souris vu dans le TP 3 3 En utilisant le Pixmap de sauvegarde du contenu de la fen tre graphique traitez les v nements de type Expose su
32. r cette fen tre cf la copie de la racine de l exercice 5 TP1 4 Programmez la r action suivante au cliquer rel cher de la souris sur les boutons dans un premier temps sans vous pr occuper de modifier l apparence des boutons a Le bouton Hide efface le contenu de la fen tre graphique mais pas celui du Pixmap de sauvegarde b Le bouton Show r tablit le contenu de la fen tre graphique sauvegard dans le Pixmap c Le bouton Clear efface le contenu de la fen tre graphique et celui du Pixmap On repart z ro 5 Saisir les entr es au clavier pour que l enfoncement des touches Control C dans la fen tre principale permette de quitter le programme 6 Traitez le changement de taille de la fen tre principale on doit modifier la taille de la sous fen tre graphique 7 Faites en sorte que le clic de souris sur une fen tre bouton soit soulign par un affichage en inverse video du bouton et que le rel cher r tablisse ensuite l affichage normal 8 Veillez ensuite ce que la commande associ e au bouton ne soit ex cut e que si l on rel che le bouton de souris au dessus de la fen tre bouton et non l ext rieur Institut Galil e Th orie des graphes Algo3 Ann e 2004 2005 L3 Informatique ILOG2 Examen Vendredi 04 f vrier 2005 Cours et TD autoris s Dur e 3 heures Exercice 1 Trac d une autoroute Quinze villes num rot es de 1 15 sont reli es par des routes La figure ci des
33. rculant fin id qui termine l algorithme A Institut Galil e Ing nierie logicielle ILOG 2 ann e 2004 2005 Masters MI1 amp MMII Algorithmique parall le et distribu e Devoir rendre pour la semaine du 24 janvier 2005 1 Algorithme CRCW de calcul d un maximum On consid re une liste L s1 82 s de n nombres non n cessairement distincts 1 1 Expliquer en d tail comment l algorithme Maxrapide L du cours permet de d terminer le maximum de L en temps O 1 sur une PRAM CRCW commune de surface H n Q n 1 2 On souhaite maintenant trouver un algorithme MAX calculant le maximum de L sur une PRAM CROW de surface H n n a Soit une PRAM CRCW p processeurs Montrer que le probl me consistant trouver le maximum parmi m lt p 2 nombres peut se ramener au probl me du calcul du maximum parmi au plus m p nombres en O 1 sur une PRAM CRCW p Processeurs b Si on commence avec m p 2 nombres combien en reste t il apr s k it rations de Max c Montrer que MAX peut d terminer le maximum de L en temps fglg n sur une PRAM CRCW p n processeurs d Quelle type de PRAM CRCW doit utiliser MAX Peut on obtenir les m mes performances avec un autre type de PRAM e L algorithme MAX est il efficace optimal 1 3 On suppose maintenant que les n nombres s toujours non n cessairement dis tincts de la liste L sont compris entre 1 et n a Donner un algorithme MAX2 de complexit en temp
34. retour n est pas pris en charge dans cette version du syst me m me si cette caract ristique est pr vue pour une future version Il s agit d une caract ristique important devant tre support e via le web Voici les diff rentes r gles d emprunt Chaque utilisateur peut emprunter un nombre limit de livres en m me temps en fonction de la cat gorie de l utilisateur Par exemple les directeurs de d partement peuvent emprunter jusqu 100 ouvrages simultan ment alors que les assistant sont limit s 15 Pour chaque cat gorie de livre la cat gorie d utilisateur d finit aussi la p riode d emprunt d un ouvrage Par exemple un directeur de d partement peut emprunter un livre standard durant 6 mois tandis qu un assistant est limit 3 mois La p riode durant laquelle un utilisateur peut emprunter un ouvrage d pend de la cat gorie de ce livre Par exemple un assistant peut emprunter un livre standard durant 3 mois alors que l emprunt d un p riodique sera limit 1 mois De plus certains livres ne peuvent pas tre emprunt s par cer taines cat gories d utilisateur E g les assistants et les tudiants ne peuvent pas emprunter les livres de r f rence Universit Paris Nord ILOG2 Institut Galil e Ann e 20042005 Partiel 1 d algorithmique randonis e Algo III 2 Jeudi 7 avril 2005 de 10 heures midi Avertissement Les documents et les calculatrices sont interdits SOIGNEZ LA R DACT
35. riables enti res P suivant min 5T1 3T2 S C T T2 lt 8 2 2 lt 1 3x1 2x2 gt 6 T gt 0 z2 gt 0 et entiers et le probl me en variables continues associ not PL 1 Faire les r solutions graphiques de P et de PL Pr ciser les valeurs des probl mes et les solutions optimales x de P et rP de PL Dessiner galement le domaine Conv Dom P 2 Quelle est la valeur atteinte au point xheuT tel que p gt fr L7 j 1 27 Quel est l cart entre u PL l et cette valeur 3 Quel aurait t cet cart si l objectif de P avait t f 1 0 Exercice 3 R diger une version non r cursive de l algorithme de complexit lin aire recherchant les k plus grands l ments d un ensemble de n r els distincts t J 1 n avec k lt n Il est demand d utiliser le principe et les notations 1 h E2 de l algorithme de complexit lin aire du cours r solvant le programme lin aire K associ un sac dos 0 1 K Exercice 4 Appliquer l algorithme de complexit lin aire r solvant le programme lin aire K associ au sac dos 0 1 K suivant mar 5x1 8z 1973 14r4 9x5 3x6 20t7 s c 4x1 4z 2073 1574 1875 276 20x7 lt 23 tj 0 1 lise t Exercice 5 Etant donn le probl me du sac dos K six variables bivalentes maxr 30r 2579 2273 A0ra 2825 20T6 s c T1 4r Trs 16t4 1375 1076 lt 26 pi 0
36. s On consid re l algorithme randonis r cursif suivant Select S k qui s lectionne le k l ment d un ensemble S d au moins k entiers deux deux distincts Select S k 1 Tirer au hasard un l ment x S 2 En comparant x chaque l ment de S x constituer les ensembles S y ES y lt z et Srieyes vx 3 Si S k 1 retourner x Si S_ gt k 1 retourner Select S_ k Si SL lt k 1 retourner Select S4 k S_ 1 a En supposant qu l tape 1 tous les l ments de S sont quiprobables calculez le nombre moyen de comparaisons lorsque l algorithme Select S k est ex cut sur un ensemble S contenant n l ments deux deux distincts Indication utilisez X variable al atoire indicatrice de l v nement le 1 et le 7 l ments sont compar s au cours de l ex cution et distinguez trois cas selon les positions respectives de et j par rapport k b Donnez une estimation de la valeur calcul e en 3 a quand n k avec k an o TL 1 0 lt a lt 1 Rappel lim D F0 mn y o y est la constante d Euler y amp 0 57721 1 1 Universit Paris Nord ILOG2 Institut Galil e Ann e 20042005 Partiel 2 d algorithmique randonis e Algo I 2 Vendredi 10 juin 2005 de 10 heures midi Er Avertissement Les notes de cours et de TD sont autoris es Les calculatrices sont interdites SOIGNEZ LA R DACTION RESPECTE
37. s tats r currents et transitoires b Soit j un entier satisfaisant 44 lt j lt g On d signe par q la probabilit d aboutir la ruine du joueur B partir de l tat j Ecrivez une relation de r currence liant qj q 1 et qj 1 pour 4a lt 7 lt g c R solvez l quation de r currence de la question b D duisez en la probabilit que le joueur B soit ruin par le jeu NO Institut Galil e Universit Paris 13 OC2 ILOG2 08 avril 2005 Partiel Dur e 3 heures Notes de cours et de TD autoris s Exercice 1 On envisage le probl me d affectation P suivant min J i1 jet CijTij sc Dj Tij 1 vi Llech 1 J Tij 1 Vre dosh 2 zij 0 1 vea e bhasan 3 qui consiste affecter n t ches J 1 n n machines i 1 n au moindre co t de r alisation des t ches tous les ci sont suppos s positifs 1 D montrer pourquoi les contraintes 3 peuvent tre remplac es par Tij 2 0 Vi 1 reipi 3 2 En d duire que le probl me P est un cas particulier du probl me de transport 3 R soudre par l algorithme primal dual le probl me P dont les donn es sont les suivantes 4 machines et 4 t ches Pr ciser sa valeur et la solution optimale et r alisable associ e Utiliser l heuristique initiale des chemins am liorants i re usine non satisfaite vers ler client non satisfait Exercice 2 On consid re le programme lin aire en va
38. s T n O 1 qui d termine le maximum de L sur une PRAM CRCW de surface H n n b Expliquer en quoi la restriction de la taille des nombres permet de trouver un maximum de L en temps constant c Quelle PRAM CROW doit on utiliser pour MAX Peut on obtenir les m mes performances avec un autre type de PRAM d L algorithme MAX est il efficace optimal 2 Algorithme distribu d lection sur un anneau Dans la suite un syst me distribu S est mod lis par un graphe G P L tel que IP net L m cf cours Les hypoth ses sont identique celles de l algorithme d lection de Chang Roberts vu en cours n L algorithmes distribu d lection permet d lire un processus par comparaisons et choix d un extremum sur un anneau de taille n unidirectionnel asynchrone et avec identit s E Chaque processus F P i 1 2 n poss de une identit unique id qu il est seul conna tre Toute identit appartient l ordre total n 1 n CN L anneau est asynchrone d lais born s ADB L algorithmes A peut tre enclench par tout sous ensemble non vide T P des processus initiateurs L algorithme choisit l lu partir de la variable locale val d finie comme suit 1 Un processus initiateur d identit id engendre uniform ment et ind pendemment un nombre premier id lt p lt 2n gr ce la fonction al atoire enti re prem id 2n 2 La variable locale val d un
39. s vu en cours est efficace mais non optimal Donner un algorithme ClassementListe L optimal de complexit en temps T n O log n et utilisant O n log n processeurs comme suit i R duire la liste L une liste L de taille O n log n it Utiliser l algorithme habituel de classement sur la liste r duite L puis r cup rer les objets t s lors de l initialisation et calculer leur rang Quel est le travail obtenu En d duire que ClassementListe L est bien optimal iti Quelles hypoth ses faut il formuler sur les entr es de ClassementListe L pour op rer ainsi 6 Algorithme distribu d lection sur un anneau Soit un syst me distribu S repr sent par un graphe fini connexe simple et sym trique X U o X constitue l ensemble des processus de S et U X l ensemble de ses lignes de communication on note X n et U L algorithme distribu sp cifi ici page 5 r sout le probl me de l lection par comparaisons et calcul d une identit extr male sur un anneau unidirectionnel et asynchrone 6 1 Hypoth ses sur Un certain nombre d hypoth ses simplificatrices sont faites ici sur sans perte de g n ralit La communication entre les n processus s effectue par messages et sans d s quencement communication FIFO Le r seau en anneau est asynchrone d lais born s Chacun des n processus de poss de une identit unique distincte de delie des
40. sous porte la longueur kilom trique de chaque tron on 5 40 OS 2 o Yh a 50 50 s0 o V70 79 30 O 7 Ne RS Distances kilom triques Pour chaque r ponse aux questions suivantes vous donnerez l algorithme que vous utiliserez et vous d taillerez les diff rentes tapes de l algorithme Donner un arbre couvrant de longueur minimale pour ce graphe Que repr sente un tel arbre pour le r seau routier consid r Quel est le chemin le plus court permettant de joindre la ville 1 la ville 15 Ah oO IN e On a valu pour chaque route le nombre horaire maximal de v hicules qu elle peut couler compte tenu des ralentissements aux travers es des villes et villages des arr ts aux passages niveau etc Ces valuations ont t les suivantes 1 2 750 2 5 600 5 10 650 9 11 500 1 3 650 2 6 400 6 9 700 9 12 150 1 4 800 3 5 200 6 10 200 9 14 150 3 6 gt 350 7 9 250 10 12 350 3 8 150 7 10 150 10 13 700 4 6 300 8 9 300 10 14 250 4 7 250 4 8 200 11 15 12 15 13 15 14 15 A 600 250 790 400 Quel est le d bit horaire total maximal de v hicules susceptible de s couler entre les villes 1 et 15 Afin d accro tre les possibilit s de trafic routier entre les extr mit s du r seau un projet de construction d une autorou
41. st me envoie un e mail d avertissement chaque personne ayant em prunt un ouvrage et ayant d pass la p riode de pr t autoris Le serveur central de l universit centralise toutes les informations concernant les utilisateurs du syst me cat gorie adresse e mail etc Un utilisateur s identifie aupr s du syst me l aide d une carte et d un mot de passe comme avec les distributeurs automatiques de billets Pour des raisons de s curit le serveur central de l universit se charge de r aliser toutes les v rifications de mot de passe Pour cela le syst me b n ficie d une connexion Ethernet ce serveur Des codes barres sont appos s aux livres pour pouvoir les identifier lors d un emprunt un lecteur de codes barres est la disposition des utilisateurs Dans le cas o un code barre est endommag rendant sa lecture impossible il est possible de rentrer manuellement sa valeur Chaque biblioth que de d partement poss de son propre syst me de recherche de livres que LBBS doit utiliser lors de toutes les recherches d ouvrage Ces syst mes ne peuvent pas tre modifi s car il s agit de logiciels propri taires dont le code n est pas disponible Lorsqu un seul de ces syst mes est en cours de recherche la recherche d ouvrage n est plus disponible aupr s des autres utilisateurs Toutes les recherches doivent s effectuer via LBBS Le renouvellement d emprunt i e l extention de la date de
42. t un readme pour le lancement du programme Une d mo de votre logiciel sera demand e EXAMEN DE GESTION GROUPE 1 Mercredi 15 d cembre 2004 Question 1 En plus d une activit technique l ing nieur a de plus en plus une activit manag riale Apr s avoir d fini l expression activit manag riale exposez une raison expliquant le sens de cette phrase 2 points Question 2 Pourquoi les restructurations dans les grandes entreprises au cours des ann es 1980 et 1990 se sont elles accompagn es d un mouvement de d concentration Avant de r pondre cette question vous pr ciserez la signification du terme d concentration 4 points Question 3 Quelles sont les diff rentes formes que peut prendre un investissement socialement responsable Citez et d finissez en deux 2 points Question 4 Selon la grille d analyse propos e par M PORTER cinq forces commandent la concurrence et d terminent conjointement la rivalit et la rentabilit d un secteur d activit Citez et d finissez en quatre 2 points Question 5 Pourquoi est il quivalent de parler de strat gie de co t et de strat gie de volume 1 point Question 6 D finissez et commentez les diff rentes phases du graphique ci dessous 4 points Co t et pri Volume cumul Question 7 En quoi consiste une strat gie de diff renciation D finissez et donnez deux exemples de strat gie de diff renciation 3 points Question 8 Qu
43. t Galil e Universit Paris 13 OC2 ILOG2 17 juin 2005 Examen Dur e 3 heures Notes de cours et de TD autoris es Exercice 1 Etant donn le probl me du sac dos K quatre variables bivalentes maxz l4z 4x2 373 8xa s c 1571 4x2 273 4xa lt 23 x E 0 1 j 1 4 T R soudre K par programmation dynamique en g rant des ensembles de triplets a jeJ j Pajeg Cj J non domin s pour d terminer la valeur de K et sa solution optimale et r alisable 2 Quelle aurait t la valeur de K si le second membre avait t gal 207 i gt j R C 5 amp Appliquer l algorithme glouton dans l ordre d croissant des a j 1 4 pour d terminer une solution r alisable x de K 4 Appliquer une recherche de type Tabou avec z pour solution initiale jusqu obtenir la valeur v K trouv e la question 1 Exercice 2 On envisage le probl me du sac dos K sept variables bivalentes mar 30x1 20x2 60x3 1074 875 2X6 T7 s c 5x1 579 2073 574 4T5 276 2x7 lt 37 Tj 0 1 EA T Appliquer l algorithme glouton pour d terminer une solution r alisable z de K et le mino rant v K associ de v K PA Ecrire la relaxation lagrangienne de K pour le multiplicateur u l Utiliser cette relaxation lagrangienne pour fixer 5 variables de K la valeur 1 En d duire la valeur et la solution optimale et r alisable de K Expliquer
44. t l attente que d un patient la fois i 4 Pour le syst me d crit ci apr s a Identifier quels sont les l ments pertinents de ce syst me et d veloppez les cas d utilisation pour ce probl me b Donner une description d taill e de l emprunt d un livre c Indiquez ensuite de quel type de syst me il s agit et d veloppez les l ments de sp cification corres pondants Donnez les diagrammes correspondant la m thode vue en cours Le but de cet exercice est de concevoir un syst me automatis d emprunt de livres de biblioth que LBBS Library Book Borrowing System pouvant tre utilis dans les biblioth ques de d partement des universit s LBBS permettrait d abaisser la charge de travail des biblioth caires en automatisant le traitement des emprunts de livre Le syst me ne n cessite pas que les utilisateurs s identifient avant de rechercher des ouvrages selon certains crit res ou de v rifier la disponibilit d un livre en particulier Cependant pour emprunter des livres pour v rifier l tat de ses emprunts ou pour r server des se d j emprunt s les utilisateurs doivent au pr alable s identifier aupr s du syst me Lors de chaque session un re u est imprim d taillant pour chaque livre emprunt le titre du livre l identifiant unique correspondant au livre la date d emprunt du livre et la date laquelle le ve doit tre rendu Au d but de chaque semaine le sy
45. te est tudi Connaissant le co t des travaux pour chaque tron on d autoroute quel sera le trac le plus conomique Co ts des tron ons en millions d euros Exercice 2 1 2 1000 2 5 1100 5 10 gt 900 9 11 1100 1 3 600 2 6 700 6 9 1400 9 12 1200 1 4 800 3 5 1300 6 10 1400 9 14 900 3 6 800 7 9 1000 10 12 600 3 8 1600 7 10 800 10 13 1100 4 6 700 8 9 800 10 14 800 4 7 1300 4 8 700 _ Parmi les cina troncons de l autoroute d termin es la question pr c dente F dans quel ordre a t on int r t construire les deux premiers tron ons si l on d sire am liorer le trafic d ensemble le plus vite possible L autoroute en question permettra l coulement de 1500 v hicules l heure Composantes fortement connexes et plus courts chemins j 73 Del PS woo N D terminer les composantes fortement connexes du 1 graphe orient G X T d ordre 10 d fini ci dessous CX a Jef m e sw me a r s so Ts 7 6 T7 T8 Tr 10 Ta T8 To T10 TA T7 D tailler les diff rentes tapes de l algorithme de Kosaraju Sharir ainsi que les diff rents types d arcs obtenus par chaque application de DFS Rappel par convention la construction de chaque arborescence des deux for ts couvrantes se fera en cherchant atteindre prioritairement le somm
46. tir et Y le second num ro 1 D terminer la loi jointe de Y Y ainsi que les lois marginales de Y et de K 2 Soit Z max Y calculer P Z lt k pour 1 lt k lt n 3 En d duire la loi de Z Calculer Z 4 Soit U min Y D terminer la loi de U et calculer E U Indication Xk n n 1 X 2n 1 k 1 O2 Bases de Domes EE Bois RS NNEENRRR PIRE EXERCICE 1 La gestion commerciale GESCOM Le syst me d information de l entreprise BB BOBO est articul autour de la base de donn es GESCOM d crite par le sch ma relationnel ci dessous CLIENT Passer COMMANDE Porter_sur ARTICLE Porter_sur Sch ma conceptuel de donn es Pour la gestion de ses commandes les articles sont identifi s de mani re unique par la r f rence RefArt Les clients sont identifi s par le code CodCli Les commandes sont retrouv es gr ce au num ro NumCom Une ligne de comande est identifi e par la combinaison NumCom et RefArt CLIENTS CodCli CivCli NomCli PrenCli CatCli AdnCli AdrCli CPCIi VilCli PaysCli COMMANDES NumCom CodCli DatCom ARTICLES RefArt NomArt PVArt QsArt PAArt DETAILCOM NumCom RefArt QtCom PUArt Remise Sch ma relationnel de la BD GESCOM Questions 2 4 4 10 points gt SQL amp PL SQL 1 1 Formulez en SQL la requ te qui permet de d terminer le chiffre d affaires par pays F2 D veloppez le m canis
47. tive Deuil la Barre jardin Indiquez quels mots ils se rattachent pour permettre une analyse s mantique correcte Par exemple Administrative se rattache R tention pas implantation par contre Deuil la Barre se rattache implantation 1 2 On propose le lexique suivant remarque d de Noms projet implantation Centre R tention Deuil la Barre ville jardin Adjectifs Administrative Verbes Unissons nous reste Conjonction de subordination afin que Adverbe toujours D terminants articles le un notre une son Pr positions contre d dans et la grammaire suivante GN groupe nominal GP groupe pr positionnel Phrase gt Verbe GP Verbe ConjSub Phrase GN Verbe Adv GN GN gt GN GP GN GP GP D terminant Nom Adij GP gt Pr position GN Pr position Nom Montrez comment cette grammaire permet d analyser les phrases donn es de mani re retrouver le d coupage pr c dent Donnez pour chaque phrase l arbre syntaxique r sultant de cette analyse 1 3 Montrez que la grammaire propos e permet d analyser la premi re phrase d autres mani res Expliquez quels probl mes va rencontrer un analyseur syntaxique pour automatiser le d coupage 1 4 Comment pourrait on am liorer la grammaire pour emp cher ces mauvaises analyses 2 Apprentissage de concepts construction de l espace des versions 7 pts 2 1 Questions de cours 2 pts Qu est ce qu une g n ralisation minimale Qu
48. urp idpredp Montrer qu une identit qui suit un minimum local n est pas minimale En d duire que si une phase commence avec k gt 1 processus actifs d identit s idcour distinctes alors le nombre de candidats restant en fin de phase est compris entre 1 et k 2 En d duire que termine bien avec un unique lu 6 3 Analyse de complexit de A Dans les calculs de complexit de l algorithme qui suivent on fait l hypoth se que tous les processus sont initiateurs Z n sans perte de g n ralit 6 3 1 Complexit en temps de cas extr mes i Donner une configuration initiale de A qui requiert un nombre maximal de phases vir tuelles complexit en temps dans le pire des cas ii Montrer que le nombre maximal de phases Tan de A est alors au pire Tmaz n g n 1 flg n 1 1 tit Donner une configuration initiale de qui requiert seulement deux phases quel que soit le nombre d initiateurs L algorithme A peut il se terminer en une seule phase 6 3 2 Complexit en communication de A cas extr mes i Calculer la complexit en messages au pire de A Montrer que le nombre de messages de tous types re us par chaque processus est exactement de deux chaque phase En conclure que Cmos n 2nlg n O n n oo ti M me question pour la complexit en messages de Cmin n dans le meilleur cas s il existe 6 3 3 Complexit en espace m moir
49. utiliser pour approcher la loi de X b Calculer alors la probabilit que 30 lt S lt 70 2 On d cide de choisir le nombre de jets n al atoirement suivant la loi de Poisson de param tre a Calculer P S m n k et P S m n k pourm lt k b D terminer la loi de S En d duire P n k S m c Calculer E Exercice 2 Soit 4 4 un chantillon d une loi admettant la densit su 0 1 4 f 4 ax gt l o le param tre 4 gt 0 0 sinon D terminer la constante c en fonction de 8 Calculer E In X et Var ln X Calculer l estimateur du maximum de vraisemblance 8 de 8 Calculer E et Var 0 Calculer l information de Fisher port e par l chantillon sur DS HE be _ L estimateur est il sans biais Si oui tudier son efficacit Exercice 3 On dispose d un chantillon x x x de n 18 observations d une v a de loi normale N u o u inconnu Les donn es suivantes sont extraites de l chantillon D LUI A est i l i l Supposons o 2 D terminer un intervalle de confiance pour u de niveau 95 2 Etablir un test de hypoth se H 4 6 contre H 4 5 au risque de 5 Quelle est votre d cision Calculer alors le risque de deuxi me esp ce 2 du test 3 Supposons d sormais inconnu Donner une estimation de o D terminer un intervalle de confiance pour u de niveau 95 MI1 ILOG2 ann e 2004 2005 Probabilit s et Statistiques Epreuve Partielle
50. valeurs du dual lagrangien DRL obtenu en dualisant la contrainte 1 du dual lagrangien D RL obtenu en dualisant la contrainte 2 du dual DDL de la d composition lagrangienne du dual de la relaxation agr g e DRA combinant les contraintes 1 et 2 Quelles sont les coupes de Chvatal associ es respectivement aux contraintes 1 et 2 Quel domaine de la question 1 retrouve t on lorsque ces deux coupes remplacent les contraintes 1 et 2 Agr ger ces deux coupes avec les poids 1 D terminer la coupe de Chvatal de cette nouvelle contrainte avec u 1 3 Quel domaine de la question 1 retrouve t on ainsi Exercice 5 Soit le probl me en nombres entiers P suivant MAX Li T2 s c 2741 5x2 lt 10 AT s 3T9 lt 6 T1 2 EN trait en cours par l algorithme de Gomory V rifier que les deux premi res it rations de l algorithme primal du simplexe en nombres entiers permettent de d tecter sans le prouver la valeur de P et sa solution optimale et r alisable repr senter graphiquement les deux coupes de Gomory engendr es Il est demand de d marrer l algorithme en choisissant s 1 Universit Paris 13 ILOG 2 amp MII Institut Galil e 2004 2005 Algorithmique parall le et distribu e Examen du mardi 25 janvier 2005 Documents autoris s notes de cours et de T D 1 Plus long pr fixe Soit une cha ne de caract res C comportant n lettres Le probl me consiste
Download Pdf Manuals
Related Search