Examen première session – 4 mai 2016

Durée 2h, documents autorisés

Notation asymptotique

Soit et des fonctions asymptotiquement positives. Prouver ou démentir chacune des affirmations suivantes:

La notation . Pour une fonction donnée, on note l’ensemble des fonctions :

La notation 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 matrices on cherche à trouver le parenthèsage optimal, c’est-à-dire celui qui minimise le nombre de multiplications scalaires pour l’opération

: Donner le nombre de parenthésages possibles pour la multiplication de matrices.

: Soit cinq matrices , où chaque matrice pour est de dimension . (La première matrice est de dimension , la deuxième de dimension etc.) On notera , pour , le nombre minimal de multiplications scalaires nécessaires pour le calcul de la matrice . Exprimer en fonction des coûts et des entiers pour

: On suppose maintenant que les dimensions des matrices sont données par . Calculer le coût optimal pour la multiplication en calculant et sauvegardant les coûts pour la multiplication des chaînes plus petites. (Evidemment, , pour . Calculer les coûts pour ensuite les coûts pour et ainsi de suite). À la fin, montrer le parenthésage associé au coût .

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 à coefficients dans un corps quelconque peuvent être multipliées en 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 peut être calculé en opérations.

: Soit la complexité de calculer le carré d’une matrice , prouver que . (Suggestion : si et sont les matrices à multiplier, construisez une matrice dont le carré contient le produit ).

Graphes

La clôture transitive d’un graphe est le graphe obtenu en ajoutant à , pour toute paire de nœuds tels qu’il existe un chemin de à , une arrête .

: 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 ou , 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 correspond à la matrice d’adjacence du graphe contenant une arrête pour tout chemin entre et dans de longueur au plus 2.

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

: Donner un algorithme de complexité pour le calcul de la clôture transitive d’un graphe.

Programmation linéaire

On considère le programme linéaire suivant :

Minimiser
Sous

.

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