2016-exam.md

title	scripts	addons
Examen première session	https://d3js.org/d3.v3.min.js	style_goodies true

{{ page.title }} – 4 mai 2016

Durée 2h, documents autorisés

Notation asymptotique

Soit $$f(n)$$ et $$g(n)$$ des fonctions asymptotiquement positives. Prouver ou démentir chacune des affirmations suivantes:

• $$f(n) = \mathcal{O}(g(n))$$ implique $$g(n) = \mathcal{O}(f(n))$$;

• $$f(n) + g(n) = \Theta(\min (f(n),g(n)))$$;

La notation $$\Omega$$. Pour une fonction $$g(n)$$ donnée, on note $$\Omega(g(n))$$ l'ensemble des fonctions :

$$\Omega(g(n)) = {f(n): \text{ il existe des constantes positives } c \text{ et } n_0 \text{ telles que } \ 0 \leq cg(n) \leq f(n) \text{ pour tout } n \ge n_0. } $$

La notation $$\Omega$$ fournit une borne inférieure asymptotique.

• $$f(n) = \mathcal{O}(g(n))$$ implique $$g(n) = \Omega(f(n))$$.

Programmation dynamique

On s'intéresse au problème des multiplications matricielles enchaînées. Étant donné une chaîne de $$n$$ matrices $$M_1, M_2, \dots, M_n$$ on cherche à trouver le parenthèsage optimal, c'est-à-dire celui qui minimise le nombre de multiplications scalaires pour l'opération $$M_1M_2\cdots M_n.$$

:{:.exercise} Donner le nombre de parenthésages possibles pour la multiplication de $$n=5$$ matrices.

:{:.exercise} Soit cinq matrices $$M_1, M_2, \dots, M_5$$, où chaque matrice $$M_i$$ pour $$i = 1 \dots n$$ est de dimension $$p_{i-1} \times p_i$$. (La première matrice est de dimension $$p_0 \times p_1$$, la deuxième de dimension $$p_1 \times p_2$$ etc.) On notera $$c_{i,j}$$, pour $$1 \leq i \leq j \leq n$$, le nombre minimal de multiplications scalaires nécessaires pour le calcul de la matrice $$M_iM_{i+1}\cdots M_{j}$$. Exprimer $$c_{1,4}$$ en fonction des coûts $$c_{1,1}, c_{2,4}, c_{1,2}, c_{3,4}, c_{1,3}, c_{4,4}$$ et des entiers $$p_i$$ pour $$i = 0\dots 5.$$

:{:.exercise} On suppose maintenant que les dimensions des matrices $$M_1, M_2, \dots, M_5$$ sont données par $$(p_0, p_1, p_2, p_3, p_4, p_5) = (2,3,5,1,4,3)$$. Calculer le coût optimal $$c_{1,5}$$ pour la multiplication $$M_1M_2\cdots M_5$$ en calculant et sauvegardant les coûts pour la multiplication des chaînes plus petites. (Evidemment, $$c_{i,i}=0$$, pour $$i = 1, 2, \dots n$$. Calculer les coûts $$c_{i,i+1}$$ pour $$i=1,2, \dots n-1,$$ ensuite les coûts $$c_{i,i+2}$$ pour $$i = 1, 2, \dots, n-2$$ et ainsi de suite). À la fin, montrer le parenthésage associé au coût $$c_{1,5}$$.

Algèbre linéaire

On rappelle que $$ω$$ représente l'exposant de l'algèbre linéaire, c'est à dire un nombre réel tel que deux matrices de taille $$n×n$$ à coefficients dans un corps quelconque peuvent être multipliées en $$n^ω$$ opérations du corps.

Dans cette partie nous allons prouver que la multiplication et le carré des matrices carrées ont la même difficulté algorithmique.

:{:.exercise} Prouver que le carré d'une matrice $$n×n$$ peut être calculé en $$O(n^ω)$$ opérations.

:{:.exercise} Soit $$S(n)$$ la complexité de calculer le carré d'une matrice $$n×n$$, prouver que $$n^ω = O(S(N))$$. (Suggestion : si $$A$$ et $$B$$ sont les matrices à multiplier, construisez une matrice dont le carré contient le produit $$AB$$).

Graphes

La clôture transitive d'un graphe $$G$$ est le graphe obtenu en ajoutant à $$G$$, pour toute paire $$(u,v)$$ de nœuds tels qu'il existe un chemin de $$u$$ à $$v$$, une arrête $$u→v$$.

:{:.exercise} Dessiner la clôture transitive du graphe ci-dessous.

<script> var nodes = [{x:10,y:150},{x:40,y:50},{x:200,y:50},{x:100,y:150},{x:100,y:50},{x:200,y:150},{x:150,y:100}]; var edges = [{f:0,t:1}, {f:1,t:4}, {f:2,t:5},{f:2,t:6}, {f:3,t:4}]; document.on("DOMContentLoaded", function() { var g = d3.select("#graph"); g.selectAll("line") .data(edges) .enter() .append("line") .attr("x1", function(d) { return nodes[d.f].x }) .attr("y1", function(d) { return nodes[d.f].y }) .attr("x2", function(d) { return nodes[d.t].x }) .attr("y2", function(d) { return nodes[d.t].y }) .style("stroke", "#11e"); g.selectAll("circle .nodes") .data(nodes) .enter() .append("svg:circle") .attr("class", "nodes") .attr("cx", function(d) { return d.x; }) .attr("cy", function(d) { return d.y; }) .attr("r", "10px") .attr("fill", "black"); g.selectAll(".n") .data(nodes) .enter() .append("text") .attr("class","n") .attr("x", function(d) { return d.x; }) .attr("y", function(d) { return d.y; }) .text(function(d,i) { return String.fromCharCode(97+i); }) .style({"font-size":"60%","fill":"white","text-anchor": "middle", "dominant-baseline": "middle" }); }); </script>

:{:.exercise} Écrire les matrices d'adjacence du graphe et de sa clôture.

Les matrices booléennes sont les matrices à coefficients $$0$$ ou $$1$$, avec la règle de multiplication usuelle, mais où l'on remplace l'opération $$+$$ par le ou logique $$∨$$, et l'opération $$×$$ par le et logique $$∧$$.

:{:.exercise} En voyant la matrice d'adjacence du graphe précédent comme une matrice booléenne, en calculer le carré. Dessiner le graphe correspondant.

:{:.exercise} Prouver que le carré de la matrice d'adjacence d'un graphe $$G$$ correspond à la matrice d'adjacence du graphe $$G'$$ contenant une arrête $$u→v$$ pour tout chemin entre $$u$$ et $$v$$ dans $$G$$ de longueur au plus 2.

:{:.exercise} Généraliser par induction à la $$n$$-ième puissance de la matrice d'adjacence.

:{:.exercise} Donner un algorithme de complexité $$O(n^3\log n)$$ pour le calcul de la clôture transitive d'un graphe.

Programmation linéaire

On considère le programme linéaire suivant :

Minimiser $$-x - 2y$$
Sous
$$\begin{array}{c r r r} x& & ≤& 3,\ 2x& + y& ≤& 7,\ -x& + 2y& ≤& 4, \end{array}$$

$$x,y≥0$$.

:{:.exercise} Mettre le programme linéaire sous forme relaxée en ajoutant des variables de relaxation.

:{:.exercise} Trouver la solution du programme linéaire en détaillant les étapes de l'algorithme du simplexe.