Examen première session – 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:

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.

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.\)

: Donner le nombre de parenthésages possibles pour la multiplication de \(n=5\) matrices.

: 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.\)

: 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.

: Prouver que le carré d’une matrice \(n×n\) peut être calculé en \(O(n^ω)\) opérations.

: 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\).

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

: É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 \(∧\).

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

: 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.

: Généraliser par induction à la \(n\)-ième puissance de la matrice d’adjacence.

: 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\).

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

: Trouver la solution du programme linéaire en détaillant les étapes de l’algorithme du simplexe.