Examen du cours dapproximation PDF

Exercices avec Solutions

Exercices Corrigés d'Algorithmique – 1ére Année MI 5. EXERCICE 1. Ecrire un algorithme qui demande un nombre à l'utilisateur puis calcule et affiche le

Algorithme exercice corrigé 1ere année mi pdf

sujet ) 4 ou 5 ( sur la Algorithme non corrigé Algorithme PDF[PDF] for i in range ( ): PDF[PDF] Algorithmes - Cours

INF1120 - Programmation I

Introduction aux algorithmes. De l'algorithme au programme ... en ce qui concerne les séances de cours ou d'exercices que les examens.

Examen du cours dapproximation

Jan 7 2004 EXERCICE 1. On considère l'algorithme suivant pour Max-SAT : soit ? une instanciation arbitraire des variables et ? son complémentaire (i.e. ...

INF3105 - Structures de données et algorithmes

Sep 3 2020 Ce cours comporte une séance obligatoire de laboratoire (2 ... en ce qui concerne les séances de cours ou d'exercices que les examens.

Exercices Corrigés Matrices Exercice 1 – Considérons les matrices

Puis calculer A-1. Exercice 8 – Appliquer avec précision aux matrices M et N suivantes l'algorithme du cours qui détermine si une matrice est inversible et

Guide détude pour lexamen de connaissances générales en

Si vous avez suivi le cours IFT-3001 Conception et analyse d'algorithmes http://www2.ift.ulaval.ca/~quimper/Algorithmique/Exercices/AideMemoire.pdf.

Examen de Session de Rattrapage dAlgorithmique 2 Filière : SMI3

Vous pouvez utiliser les fonctions prédéfinies vues au cours. Exercice 1 : Preuve d'algorithme [5 points] [~ 25 minutes]. On considère l'algorithme suivant

Algorithmique — M1 - Examen du 11 janvier 2010

Jan 11 2010 On applique un algorithme de cours ... Choisissez un algorithme (écrivez juste son nom s'il s'agit d'un ... cours. Exercice 2 – 32 cavaliers.

Sciences de gestion - Synthèse de cours exercices corrigés

de cours exercices corrigés. Éric DOR. &. Économétrie. Cours et exercices adaptés aux besoins Les conclusions de l'examen graphique sont les suivantes :.

Examen du cours d"approximation

{Emmanuelle.Lebhar, Nicolas.Schabanel}@ens-lyon.fr

Mercredi 7 janvier 2004 de 9h00 à 12h00

EXERCICE 1

On considère l"algorithme suivant pour Max-SAT : soitτune instanciation arbitraire des variables etτ?son complémentaire (i.e., une variable est vraie dansτ?ssi elle est fausse dansτ); calculer les poids des clauses satisfaites parτetτ?, puis retourner la meilleure de ces deux instanciations. Question 1Démontrez que cet algorithme est une12-approximation pour Max-SAT, puis exhibez une famille d"instance critique.EXERCICE 2 On considère le programme linéaire (primal) suivant :

Maximiser2x1+ 2x2-2x3+x4

sous les contraintes5x1+x2-2x3= 3 x

1+x2+ 2x3-x4≥1

x Question 2Donnez le dual de ce programme linéaire, et les conditions de complémen-

tarité primal-dual associées. Et démontrez, de deux façons différentes, que les solutions

x= (45,0,12,45)ety= (35,15,-45)sont des solutions réalisables optimales du primal et du dual respectivement. On considère le programme linéaire (primal) suivant :

Minimiser2x1+ 3x2-x3

sous les contraintes2x1-3x2+x3≥1 -x1+ 2x2-x3≥1 x

1≥0, x2≥0, x3≥0

Question 3Donnez les conditions de complémentarité primal-dual relâchées de para-

mètres(α,β) = (1,2)associées (c"est-à-dire exact pour les conditions primales, mais à

un facteur 2 pour les conditions duales). Et démontrez, de deux façons différentes, que les solutionsx= (7,4,0)ety= (7,12)sont des solutions réalisables du primal et du dual respectivement, à un facteur2de la valeur objectif optimale. 1

EXERCICE 3

On étudie le problème de la couverture par sommets de poids minimum restreint aux graphesG= (V,E), muni d"une fonction de poidswsur les sommets, et d"unk-coloriage valide des sommets (i.e., muni d"une fonctionc:V→ {1,...,k}telle que pour tout uv?E,c(u)?=c(v)). Lak-coloration est donnée mais n"est pas supposée optimale. Question 4Proposez une(2-2k)-approximation (polynomiale) pour ce problème. Et prouvez-le. Indication.Utilisez un programme linéaire pour la couverture par sommets de poids minimum dont toutes les solutions extrémales du problème relâché sont demi-entières (on ne redémontrera pas cette propriété) et remarquez que les sommets demi-entiers ne sont pas tous nécessaires dans la couverture. Question 5Exhibez une famille d"instances critiques.EXERCICE 4 On étudie le problème suivant : vous décidez de vous mettre au ski, vous devez donc vous équipez, vous avez le choix entre louer le matériel ou bien l"acheter; dans le premier cas, il vous en coûtexeuros par jour, et dans le second, vous payezyeuros une fois pour toute (y > x); l"ennui de ce sport est qu"au bout d"un certain nombre de jours,τ, soit vous vous lasserez, soit vous serez irrémédiablement blessé; vous ne connaissez pas cette date a priori, et det= 1jusqu"à cette date (incluse) vous faîtes du ski tous les jours. Le problème est de minimiser le coût du matériel de ski, i.e., de savoir quand vous vous décidez d"arrêter de louer pour acheter votre matériel (τétant inconnu). Ce problème est typiquement celui de la mise en veille du disque dur d"un ordinateur portable : le système cherche à minimiser la consommation d"énergie et ne sait pas quand l"utilisateur va réutiliser son disque, mais il doit décider quand le mettre en veille, ce qui lui coûtera par la suite un surcoût de consommation constant pour le remettre en route. Question 6Supposez quex= 3ety= 10, quelle est la stratégie optimale pourτ= 1,

τ= 3,τ= 5,τ= 10?

Question 7Posezc=y/x(cest connu), et donnez la stratégie optimale en fonction de τ(qui vous est inconnu, mais que vous supposez connu par l"optimal). On se propose d"étudier la stratégie suivante, de paramètret0: on loue tant que la Question 8Donnez un facteur d"approximation pour cet algorithme (valable quelque soit la valeurτ, qui est inconnue). Question 9Démontrez que pour une valeur det0, cet algorithme est une2-approximation (quelque soit la valeurτ, qui est inconnue). Quelle est cette valeur? Peut-on obtenir un meilleur facteur d"approximation pour une autre valeur det0? 2

EXERCICE 5

Étant donnéntâchesJ1,...,Jnde durée d"exécutionp1,...,pn, unordonnancementde ces tâches est une fonction qui à chaque tâche associe une date pour le début de son exécution. Deux tâches ne peuvent pas s"exécuter en même temps. On noteJi?Jj, si la tâcheJjdépend de la tâcheJi, i.e., si l"exécution de la tâcheJjne peut commencer qu"après la fin de l"exécution de la tâcheJi. On dit qu"un ordonnancement estvalidesi aucune tâche n"est ordonnancée en même temps qu"une autre et si chaqueJjest exécutée après la fin de l"exécution deJi, pour toutJi?Jj. On appelletemps de complétionCide la tâcheJidans un ordonnancement donné, la date de la fin de l"exécution de la tâche dans cet ordonnancement. On étudie le problème d"ordonnancement suivant : Problème 1 (Ordonnancement avec dépendances)Étant donnéntâchesJ1,...,Jn de temps d"exécutionp1,...,pn, munies de poidsw1,...,wnpositifs, et un ensemble (acy- clique) de relations de dépendanceJi?Jj, trouver un ordonnancement valide des tâches sur un processeur, qui minimise la somme pondérée des temps de complétion des tâches :?n i=1wiCi. Question 10Redémontrez rapidement la règle de Smith qui affirme qu"en l"absence de dépendance, un ordonnancement optimal est obtenu en ordonnançant les tâches par ratio w i/pidécroissant. Indication.On pourra étudier l"effet de l"inversion de deux tâches. Nous étudions maintenant le cas général avec dépendance. Question 11Démontrez que dans tout ordonnancement valide des tâches (avec ou sans dépendance), n? i=1p iCi≥n? i=1p ii j=1p j Indication.Appliquez la règle de Smith sur l"instance modifiée suivante : aucune dépen- dance et pour fonction de poidsw?i=pi; et remarquez que dans ce cas, l"ordre des tâches est sans importance. Question 12Démontrez de même que pour tout ordonnancement valide des tâches, ?A? {1,...,n},? i?Ap iCi≥12? i?Ap

2i+12?

i?Ap i? 2

Indication.Remarquez que :n?

i=1p ii j=1p j=12n i=1p

2i+12?

n? i=1p i? 2. On considère donc le programme linéaire suivant (qui admet un nombre exponentiel de contraintes, mais qui, malgré tout, se résout exactement en temps polynomial par la méthode des ellipsoïdes). On noteyila variable associée au temps de complétion de la tâcheJidans le programme linéaire. 3

Minimisern?

i=1w iyi sous les contraintes i?Ap iyi≥12? i?Ap

2i+12?

i?Ap i?

2?A? {1,...,n}

y i≥0?i On peut démontrer que les solutions extrémales de ce problème définissent des or- donnancements valides sans dépendance entre les tâches; cependant ce n"est plus le cas lorsqu"on introduit des dépendances entre les tâches. Question 13Pour tenir compte des dépendances, définissez pour chaque dépendance J i?Jj, une contrainte liant les variablesyietyj. Donnez le nouveau programme linéaire incluant les dépendances. Démontrez que ce programme linéaire est un minorant du temps de complétion pondéré optimal. Étudions l"algorithme suivant : soity?une solution optimale (calculée en temps po- lynomial) du programme linéaire complet (avec les contraintes de dépendance);y?ne définit pas en général un ordonnancement valide, mais on ordonnance les tâches dans l"ordre défini pary?(les tâches ayant le mêmey?isont ordonnancées dans un ordre arbi- traire); notonsSl"ordonnancement obtenu. Question 14Démontrez que les contraintes de dépendance sont satisfaites dansS. j=1pj, le temps de complétion deJidansS.

Question 15Démontrez que, pour touti,

y ?i≥12Ci. Indication.Utilisez les contraintes du programme linéaire. Question 16Démontrez que cet algorithme est une2-approximation. Question 17Exhibez une famille d"instances critiques pour cet algorithme. Indication.Considérezntâches de temps d"exécution unitaireJ1,...,Jntelles que pour touti < n,Ji?Jn. On munit ces tâches des poidsw1=···=wn-1= 1etwn=M. PourMassez grand, on ay?1=···=y?n-1=n+12-1nety?n=n+32-1n. On suppose maintenant que chaque tâche n"est disponible qu"à partir d"une dateri donnée en entrée, i.e.,Jine peut pas être ordonnancée avant la dateri. Question 18Quelles contraintes doit-on ajouter au programme linéaire pour tenir compte de la disponibilité des tâches? Question 19Proposez un algorithme qui construit un ordonnancement pour ce nouveau problème. 4 Question 20(?)Démontrez que cet algorithme est une3-approximation.EXERCICE 6 L"objectif de cet exercice est de démontrer que, pour tout? >0, il n"existe pas de(78+?)- approximation pour Max-3SAT, à moins queP=NP. Nous définissons la classePCPc,s(r(n),q(n))comme suit : un langageLappartient à PCP c,s(r(n),q(n))s"il existe un vérifieur (polynomial)VpourL, utilisantO(r(n))bits et lisantO(q(n))bits de la preuvey, tel que : - six?L, il existe une preuveytel queVaccepte(x,y), avec probabilité≥c, - six??L, alors pour toute preuvey,Vaccepte(x,y)avec probabilité< s, les probabilités étant prises sur la chaîne de bits aléatoiresrde longueurO(r(n)). Nous admettons le résultat suivant (dû à Haståd, 1997) :

Théorème 1Pour tout? >0,

NP=PCP1-?,12+?(logn,1).

De plus, il existe un vérifieur particulièrement simple pour SAT dans cette classe, qui utiliseclognbits aléatoires pour calculer trois positions seulement de la preuvey, disons i,j, etk, et un bitb, et qui accepte(x,y)ssi : y i+yj+yk≡b(mod 2), oùyidésigne lei-ème bit de la preuvey. Nous noteronsVSATce vérifieur. À l"instar de la réduction vu en cours, nous allons utiliser un problème intermédiaire pour construire notre réduction séparatrice de SAT à Max-3SAT. Ce problème est le suivant, notéMax-3EQ: Problème 2 (Systèmes d"équations linéaires à 3 variables dansZ/2Z) Étant donnéesméquations linéaires, utilisant chacune trois variables parmix1,...,xn à valeurs dansZ/2Z, trouvez une instanciation des variables qui maximise le nombre d"équations linéaires satisfaites. Rappel.Une équation à trois variablesx,y, etzdansZ/2Zest nécessairement de la formex+y+z=b, oùb= 0ou1. Question 21Exhibez à partir du vérifieurVSATdonné par le théorème 1, une réduction séparatrice (polynomiale) deSATàMax-3EQ Ψ :??→Σtelle que, sim?désigne le nombre d"équations dans le systèmeΣ = Ψ(?): - si?est satisfiable, alors il existe une instanciation qui satisfait l"ensemble desm?

équations deΣ, i.e.,Max-3EQ(Σ) =m?, et

- si?n"est pas satisfiable, alorsMax-3EQ(Σ)<(12+?)m?. Indication.Inspirez-vous de la réduction séparatrice vu en cours pour Max-SAT : in-

dexez les équations utilisées par le vérifieur par toutes les chaînes aléatoires possibles,

pour construire l"instance réduite. 5 Question 22Déduisez que, pour tout? >0, il n"existe pas de(12+?)-approximation pour

Max-3EQ, à moins queP=NP.

Question 23Exhibez une gap-preserving réduction (polynomiale) deMax-3EQàMax-

3SATqui démontre que, pour tout? >0, il n"existe pas de(78+?)-approximation pour

Max-3SAT, à moins queP=NP.

Indication.Chaque équationx+y+z= 0 (mod 2)peut se réécrire sous la forme de quatre 3-clauses : (x?y?z)?(x?y?z)?(x?y?z)?(x?y?z), oùxdésigne la négation dex. 6quotesdbs_dbs45.pdfusesText_45

[PDF] Examen du cours dapproximation

Examen du cours d"approximation

Mercredi 7 janvier 2004 de 9h00 à 12h00

EXERCICE 1

Maximiser2x1+ 2x2-2x3+x4

1+x2+ 2x3-x4≥1

Minimiser2x1+ 3x2-x3

1≥0, x2≥0, x3≥0

EXERCICE 3

τ= 3,τ= 5,τ= 10?

EXERCICE 5

2i+12?

Indication.Remarquez que :n?

2i+12?

Minimisern?

2i+12?

2?A? {1,...,n}

Question 15Démontrez que, pour touti,

Théorème 1Pour tout? >0,

NP=PCP1-?,12+?(logn,1).

équations deΣ, i.e.,Max-3EQ(Σ) =m?, et

Max-3EQ, à moins queP=NP.

3SATqui démontre que, pour tout? >0, il n"existe pas de(78+?)-approximation pour

Max-3SAT, à moins queP=NP.