\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 rattrapage Juin 2017 \end{center} Les documents distribués dans le cadre du cours et les notes personnelles sont autorisés. \appendix \section{Programmation dynamique et structures de données} \subsection{Piano (3 points)} Jean-Claude vient d'apprendre à jouer au piano. Pour l'instant il ne sait jouer qu'une seule note, la plus à gauche du piano. Il active un métronome et à chaque tic il joue ou ne joue pas la note. Pour que la musique produite soit plus intéressante il ne joue jamais la note pendant deux tics consécutifs. Maintenant son côté informaticien reprend le dessus, et il se demande, étant donné $n$ tics, de combien de différentes manières peut-on jouer avec la contrainte mentionnée. Appelons $f(n)$ cette valeur. Par exemple si on note $o$ l'absence d'une note et $p$ une note jouée on a les valeurs suivantes~: \begin{tabular}{lll} $n$ & $f(n)$ & explication \\ \hline 0 & 1 & par convention \\ 1 & 2 & o, p \\ 2 & 3 & oo, op, po mais pas pp \\ 3 & 5 & ooo, opo, poo, oop, pop \end{tabular} Donnez un programme dynamique de complexité $O(n)$ pour calculer $f(n)$. \subsection{Sucré-Acide (5 points)} % % http://www.spoj.com/problems/ROCK/ Un fabriquant de bonbons dispose d'un bâton comestible composé de segments d'un centimètre chacun. Un segment peut être sucré ou acide. Les segments sont numérotés de 0 à $n-1$. Le bâton est décrit par un tableau $x\in\{0,1\}^n$, où $x[j]=1$ si et seulement si le j-ème segment est sucré. Le fabriquant peut découper le bâton en plusieurs morceaux, chacun étant constitué d'un nombre entier de segments. Les enfants achètent un morceau seulement s'il contient strictement plus de segments sucrés que de segments acides. On veut calculer la longueur totale des morceaux vendables que le fabriquant peut produire à partir d'un bâton décrit par $x$~? Donnez un programme dynamique qui résout ce problème en temps $O(n^2)$. Des points partiels seront données pour un algorithme correct de plus grande complexité. \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} % \section{Pavage par des dominos (4 points)} % % http://www.spoj.com/problems/GNY07H/ % On vous donne une grille de composée de 4 lignes et de $n$ colonnes avec $n\geq 2$. % On veut \emph{paver} cette grille avec des \emph{dominos}, chaque domino couvre exactement 2 cases adjacentes verticalement ou horizontalement. Paver veut dire que chaque case de la grille est couverte par exactement un domino. % Étant donné $n$, calculez par programmation dynamique le nombre de pavages possibles, modulo 1000007. Votre algorithme devrait avoir une complexité $O(n)$. Notez: une solution en temps $O(\log n)$ est possible, mais c'est hors sujet. Notez: le résultat est attendu modulo 1000007 juste pour s'assurer qu'il tient dans un entier 32 bits. % Donnez le cas de base, la récursion et expliquez votre solution. % \begin{figure}[bht] % \centerline{\includegraphics[width=10cm]{tiling}} % \caption{Les 5 pavages pour $n=2$ et les 11 pavages pour $n=3$.} % \label{fig:tiling} % \end{figure} % \section{Tétris avec des rectangles (8 points)} % On considère un problème similaire à celui étudié en TME6. Considérons une grille verticale sous forme d'une bande de largeur $W$ et de hauteur infini. Des rectangles alignés sur la grille tombent du haut jusqu'à ce que leur bord bas touche un autre rectangle déjà en place ou touche le bord bas de la grille. Et alors il ne bougeront plus. Notez que dans l'exemple de la figure~\ref{fig:tetris} quand le deuxième rectangle est tombé --- il s'agit du rectangle bleu de dimensions $(x_2,w_2,h_2)=(4,5,1)$ --- il est resté figé en ligne 3, bien que dans la vie réelle la gravitation lui aurait ensuite fait subir une rotation pour faire tomber d'avantage la partie droite du rectangle. % À tout moment, l'empilement des rectangles forme une sorte de histogramme --- illustré par une ligne rouge --- indiquant pour chaque colonne la hauteur de l'empilement. Notons $T[j]$ la hauteur de l'empilement en colonne $j$, avec $0\leq j < W$. % Écrivez une structure de données qui permet de maintenir $T$ en proposant les opérations suivantes, toutes de complexité en temps $O(\log W)$: % \begin{itemize} % \item \textsl{T.set(j, k, v)} pose les entrées $T[j],T[j+1],\ldots,T[k-1]$ à $v$. % \item \textsl{T.max{j, k}} retourne la valeur de $\max\{T[j],T[j+1],\ldots,T[k-1]\}$. % \end{itemize} % \begin{figure} % \centerline{\includegraphics[width=8cm]{tetris}} % \caption{Le jeu de Tétris avec des rectangles sans intervention: le joueur ne peut pas décaler les rectangles qui tombent, ni appliquer des rotations. Il ne peut que regarder les rectangles s’empiler.} % \label{fig:tetris} % \end{figure} \newpage \section{Éléments de correction} \subsection{Piano} Soit $F_n$ l'ensemble des chaînes $x\in\{0,1\}^2$ ne contenant pas deux 1 consécutifs. $F_0$ est composé seul du mot vide $\varepsilon$ et $F_1=\{o,p\}$. Pour $n\geq 2$, soit $x\in F_n$ une chaîne arbitraire. La chaîne $x$ termine par o ou par p. Dans le premier cas $x$ est de la forme $x=yo$ pour une chaîne arbitraire $y\in F_{n-1}$. Dans le deuxième cas, l'avant dernier symbole est forcément $o$, et dans ce cas $x=yop$ pour une chaîne arbitraire $y\in F_{n-2}$. Nous avons donc la récursion suivante. Cas de base $f(0)=1, f(1)=2$ et pour tout $n\geq 2$ $f(n)=f(n-1)+f(n-2)$. Pour information, il s'agit du nombre de Fibonacci. Pour calculer $f(n)$, il suffit de remplir un tableau avec les valeurs $f(0),f(1),\ldots,f(n)$ dans l'ordre des indices croissant, chaque valeur se calculant en temps constant. Ceci montre une complexité $O(n)$ pour calculer $f(n)$. \subsection{Sucré-Acide} % (fold) \label{sub:rock} Pour les indices $0\leq i\leq j\leq n-1$ appelons $A[i,j]$ le \emph{score} du morceau composé des segments $i$ à $j$. Donc $A[i,j]=j+1-i$ s'il y a plus de segments sucrés dans le morceaux qu'acide et $A[i,j]=0$ sinon. Pour calculer $A$ nous utilisons un tableau $C[i,j]$ qui contient le nombre de segments sucrés entre les segments $i$ et $j$. Pour $0\leq i\leq n-1$ nous avons $C[i,i]=x_i$ et pour $i (j+1-i)/2, \\ 0 & \mbox{sinon.} \end{array}\right. \] Les matrices $A$ et $C$ se calculent en temps $O(n^2)$, car il y a $O(n^2)$ valeurs et chacune se calcule en temps constant. Appelons $B[j]$ le score maximum qu'on peut obtenir à partir de segments $0$ à $j$ avec un découpage optimal. Pour un découpage optimal fixé soit $0\leq k\leq j$ le début du dernier morceau. Par additivité des scores, si $k>0$, alors le découpage du reste composé des segments de $0$ à $k-1$ doit à son tour être optimal. Donc $B[0]=A[0,0]$ et pour $j>0$ on a \[ B[j] = \max\left\{ A[0,j], \max_{1\leq k \leq j} (B[k-1] + A[k,j]) \right\}. \] Pour le calcul de $B$ il faut évaluer $n$ valeurs, chacun étant la minimisation sur $O(n)$ expressions, ce qui donne une complexité en $O(n^2)$. % subsection rock (end) \end{document}