\documentclass[12pt]{article} \usepackage{fullpage,amsmath,amssymb,graphicx} \usepackage[utf8]{inputenc} % \usepackage[boxed,french]{algorithm2e} \usepackage[usenames]{xcolor} \usepackage{harmony} \newcommand{\tower}[2]{$#1~\|~#2$} \newenvironment{proof} {\noindent\textbf{Proof\ }} {\hspace*{\fill}$\Box$\medskip} \newtheorem{lemma}{Lemma} \newtheorem{question}{Question} % \renewcommand{\thesubsection}{\Alph{section}.subsection} \begin{document} \begin{center} Master 1 STL 4I505 CPA -- Examen 31 Mai 2018 \end{center} Les documents distribués dans le cadre du cours et les notes personnelles sont autorisés. \section*{Partie B} \subsection{Un mauvais algorithme pour $k$-\emph{means} (1 point)} % % http://www.spoj.com/problems/ROCK/ Le problème de $k$-\emph{means} consiste en un ensemble donné $X$ de $n$ points dans l'espace $\mathbb R^2$ et un entier $k\geq 1$. On veut partitionner $X$ en $k$ ensembles $X_1,\ldots,X_k$ et trouver $k$ centres $c_1,\ldots,c_k \in \mathbb R^2$ tel que la valeur objectif suivante \[ \sum_{i=1}^k \sum_{x\ in X_i} ||x-c_i||^2 \] soit minimale. Ici $||x-c_i||$ dénote la distance Euclidienne entre les points $x$ et $c_i$. Pour approcher ce problème NP-dur, généralement on commence par générer une première solution, qu'on améliore ensuite par une recherche locale. Comme on ne sait pas évaluer les améliorations obtenues par la recherche locale, on se contente d'analyser la génération de la solution initiale. Voici deux algorithmes de génération possibles. \subsubsection*{$k$-means++} \begin{enumerate} \item Choisir $c_1$ uniform{\'e}ment au hasard parmi $X$. \item Pour tout $i = 2, \ldots, k$, choisir $c_i = x \in X$ avec probabilité proportionnelle {\`a} $D^2 (x)$, o{\`u} $D (x)$ d{\'e}note la distance entre $x$ et le centre le plus proche parmi ceux d{\'e}j{\`a} sélectionnés, donc $D (x) := \min_{\{ j = 1, \ldots, i - 1 \}} \| x - c_j \|$ dans ce cas. \end{enumerate} \subsubsection*{$k$-means-stupide} \begin{enumerate} \item Choisir $c_1$ uniform{\'e}ment au hasard parmi $X$. \item Pour tout $i = 2, \ldots, k$, choisir $c_i = x \in X$ tel qu'il maximise $D(x)$. \end{enumerate} Pour le premier algorithme $k$-means++ il a été montré qu'il produit une solution dont la valeur objectif est en espérance au plus $8(\ln k + 2)$ fois plus grande que la solution optimale. Montrez à l'aide d'un exemple que le deuxième algorithme $k$-means-stupide peut produire une solution avec une valeur objectif arbitrairement grande par rapport à la solution optimale. % \begin{figure}[ht] % \includegraphics[width=8cm]{rock.pdf} % \caption{Le problème Sucré-Acide illustré sur l'exemple $x=1001100010100011$. Les segments sucrés sont montrés en gris. La réponse optimale est $11$, ce qui correspond au total des morceaux de longueur $5,3$ et $3$.} % \end{figure} % Donnez le cas de base, la récursion et expliquez votre solution. % \begin{tabular}{lll} % entrée & sortie & explication\\ \hline % 10011 0 0 0 101 000 1 & 9 & \underline{10011} {000} \underline{101} 000 \underline{1} % \\ \hline % 0010111101100000 & 13 & \underline{0010111101100} 000 % \\ \hline % \end{tabular} \subsection{Déplacement droite-bas dans une grille (1 points)} \label{sec:droite-bas} Soit une grille composée de $n$ colonnes et $m$ lignes, voir Figure~\ref{fig:droite-bas}. Chaque case est identifiée par une coordonnée $(i,j)$ où $i$ est l'indice de ligne et $j$ l'indice de colonne. La case $(1,1)$ se trouve en haut à gauche et la case $(m,n)$ en bas à droite. Un fromage se trouve dans la case $(m,n)$, et seulement dans cette case. Il existe une souris qui initialement se trouve dans la case $(1,1)$. Elle veut atteindre la case avec le fromage en effectuant des déplacements successifs très simples, soit vers la case adjacente droite soit vers la case adjacente en dessous. Formellement si la souris est dans la case $(i,j)$, alors elle peut atteindre en un pas la case $(i+1,j)$ pourvu que $i <---- n -----> (distances) \end{verbatim} Une solution optimale consiste à choisir un centre dans l'amas du centre et un centre sur le point tout à gauche. Son coût est de $\Theta(n + \epsilon n)$. Mais si l'algorithme choisit le premier centre tout à gauche et l'autre du coup tout à droite, le coût sera $\Theta(n^2)$. Le rapport entre les coût est de l'ordre de $n$ qui peut être arbitrairement grand, quand $n$ tend vers l'infini. Le problème avec cet exemple est que l'algorithme k-means-stupide choisira un point extrême pour le premier centre seulement avec une probabilité $2/(n+2)$, donc très petite. Un meilleur exemple force l'algorithme à faire un mauvais choix avec grande probabilité. Ici avec probabilité $1/2$ il choisir un centre dans l'amas tout à gauche et le deuxième centre tout à droite, pour un coût espéré de $\Omega(n^2)$, ce qui donne de nouveau un rapport $\Omega(n)$. \begin{verbatim} [n] [n-1] [1] <----- n ----> <---- n -----> (distances) \end{verbatim} \subsection{Déplacement droite-bas dans une grille} Ceci est un classique de la programmation dynamique. La souris peut atteindre une case $(i,j)$ si elle y est déjà (donc $(i,j)=(1,1)$) où si elle peut venir de la gauche ou du haut. Formellement notons $A[i,j]$ l'accessibilité de la case $(i,j)$. Le but est de calculer $A[m,n]$. La clé est de remplir la matrice dans l'ordre des ligne, puis colonnes de telle sorte à ce que les entrées nécessaires au calcul de $A[i,j]$ aient déjà été calculés. \begin{verbatim} pour toutes les lignes i de 1 à m pour toute les colonnes j de 1 à n Si pas de chat en (i,j) et ( (i,j)=(1,1) ou (i > 1 et A[i - 1, j]) ou (j > 1 et A[i, j - 1]) alors A[i,j] := Vrai sinon A[i,j] := Faux retourner A[m,n] \end{verbatim} Il y a $mn$ variables, chacune se calcule en temps constant, la complexité du programme dynamique est $O(mn)$. \subsection{Déplacement gauche-droite-bas dans une grille} Si on garde le même principe, on rencontre une difficulté. Le calcul de $A[i,j]$ dépendra de $A[i,j + 1]$ qui à son tour dépendra de $A[i,j]$. Pour casser cette dépendance circulaire, on peut calculer plusieurs variables par case. Notons $D[i,j]$ la propriété que la case $(i,j)$ peut être atteinte avec une série de pas dont le dernier est un pas vers la droite. Similairement on note $B[i,j]$ et $G[i,j]$ pour un dernier pas vers le bas ou la gauche. Alors on a $A[i,j]=G[i,j]\vee B[i,j]\vee D[i,j]$. La clé est que $D[i,j]$ ne dépend que de $D$ et $B$ pour des entrées de la même ligne, mais des colonnes précédentes. Similairement $G[i,j]$ ne dépend que de $G$ et $B$ pour des entrées de la même ligne, mais des colonnes suivantes. Et finalement $B[i,j]$ ne dépend que de $B,G,D$ de la case $(i-1,j)$. Il faut donc procéder ligne par ligne, en calculant $B$, $G$, $D$ dans des boucles indépendantes. \begin{verbatim} Dans ce qui suit A[i,j] est un raccourci pour G[i,j] ou B[i,j] ou D[i,j] ou (i,j)=(1,1) pour toutes les lignes i de 1 à m pour toute les colonnes j de 1 à n B[i,j] = non Chat[i,j] et i > 1 et A[i-1,j] D[i,1] = faux pour toute les colonnes j de 2 à n D[i,j] = non Chat[i,j] et (D[i,j-1] ou B[i,j-1]) // plusieurs ou un seul dernier pas à droite G[i,n] = faux pour toute les colonnes j de n-1 à 1 en sens descendant G[i,j] = non Chat[i,j] et (G[i,j+1] ou B[i,j+1]) // plusieurs ou un seul dernier pas à gauche retourner A[m,n] \end{verbatim} L'analyse de la complexité est identique à la question précédente. \subsection{Pavage par des dominos (2 points)} Pour faciliter les notations on tourne la grille, qui a donc 4 colonnes et $n$ lignes. Notons par $O,E$ les cases d'un domino horizontal et $N,S$ ceux d'un domino vertical, pour Ouest, Est, Nord, Sud. Alors une ligne d'un pavage valide correspond à un mot de 4 lettres sur l'alphabet $\{O,E,N,S\}$ avec la restriction que chaque $O$ est suivi d'un $E$ et vice-versa. Soit $\cal C$ l'ensemble de ces mots. On peut définir une matrice $M$ de dimension $|\cal C|\times |\cal C|$ tel que $M[a,b]$ est $1$ si la configuration $a$ peut être suivi de la configuration $b$ et $M[a,b]=0$ sinon. Formellement $M[a,b]=1$ si pour tout $k\in\{1,2,3,4\}$, $a[k]=N \Leftrightarrow b[k]=S$. Maintenant calculons $A[n,a]$ le nombre de pavages étendues d'une grille $4\times n$ où chaque case est couverte par exactement un domino et les dominos peuvent dépasser la dernière ligne, et la dernière ligne a la configuration $a$. Pour le cas de base: $A[1,a]$ est $1$ si $a$ est sans la lettre $S$ et $0$ sinon. Pour la récursion et $n>1$ on a: $A[n,a]=\sum_{b} A[n-1,b]$ où la somme est prise sur tous les $b\in \cal C$ tel que $M[a,b]=1$. Le but est de calculer $\sum_a A[n,a]$ où la somme est prise sur $a\in \cal C$ sans la lettre $N$. Comme $\cal C$ a une taille constante, chacune des $O(n)$ variables peut être calculée en temps constant. \paragraph{Bonus:} Pour une solution en $O(\log n)$ il suffit d'observer que le nombre de pavages de la grille $4\times n$ est égal au nombre de pavages de la grille $4\times (n+2)$ avec la configuration $a=OEOE$ dans la première et dernière ligne. Et ce nombre est précisément $M^{n+1}_{a,a}$. La matrice $M^{n+1}$ peut-être calculée par exponentiation rapide en temps $O(\log n)$. Il suffit de calculer successivement les matrices $M, M^2,M^4,M^8,\ldots$ et de multiplier ceux dont l'exposant apparaît dans la décomposition binaire de $n+1$. \subsection{Arbre de segments} Attention les intervalles $[0,2)$ et $[1,6)$ sont demi-ouverts. \centerline{\includegraphics[width=5cm]{arbre_segment_2a}} Pour l'analyse de la complexité, on considère le sous-arbre $A$ composé des nœuds traités lors des appels récursifs de la mise à jour. Comme tout arbre les nœuds de $A$ de décomposent en feuilles et en nœuds internes. Pour l'analyse il suffit de borner le nombre de nœuds internes de $A$, le nombre de feuilles étant juste un nœud de plus. Soit $p$ un nœud responsable de l'intervalle $A$ appelé pour une mise à jour sur un intervalle $I$. Si $A \subseteq I$ ou $A\cap I=\emptyset$ alors le parcours d'arbre termine ici, dans les autres cas, deux appels récursifs sont effectués à partir du nœud $p$ sur les descendants de $p$. Pour un niveau donnée dans l'arbre soit $p$ le nœud responsable de l'intervalle contenant $\min I$ et $q$ le nœud responsable de l'intervalle contenant $\max I$. Il est possible que $p=q$. Alors par l'observation précédente ce sont les seuls nœuds de l'arbre où le parcours de l'arbre ne termine pas nécessairement. Donc il y a au plus $2\log n$ nœuds internes dans $A$, ce qui termine la preuve. \end{document}