\documentstyle[12pt, fullpage]{article} \parskip=2.5pt plus 0.5 pt minus 0.5pt \parindent=0pt \def\ds{\displaystyle} \newcommand{\Frac}[2]{\frac{\ds{#1}}{\ds{#2}}} \def\deg{\hbox{deg}} \def\hat {\widehat} \def \pn {\par \noindent} \def\bar{overline} \begin{document} \begin{center} {\Large \bf\sf DEA d'ALGORITHMIQUE 1998-1999} \\ {\large\bf\sf Analyse d'algorithmes: Mod\`eles combinatoires}\\ {\tt Philippe.Flajolet@inria.fr}\\ {\tt http://algo.inria.fr/flajolet/Teach/} \end{center} \begin{center} \sc Partie I. S\'eries de Dirichlet \end{center} {\em On explore ici quelques propri\'et\'es des s\'eries de Dirichlet, lesquelles sont \`a la base de la th\'eorie analytique des nombres. Seule l'inversion de Moebius, \'equation~(\ref{moebius}), est n\'ecessaire \`a la Partie~II du probl\`eme. } {\bf Q1.} La fonction {\em zeta\/} de Riemann est d\'efinie par \[ \zeta(s):=\sum_{n=1}^\infty \frac{1}{n^s}. \] D\'eterminer le meilleur $s_0$ tel que la somme converge pour tout $s$ complexe tel que $\Re(s)>s_0$. ($\Re$ = partie r\'eelle.) Que vaut $\lim_{s\to s_0^+}\zeta(s)$? \'Etablir (sans lourd d\'etail analytique) la formule dite du produit Eul\'erien, \begin{equation}\label{euler} \zeta(s)=\prod_p \frac{1}{1-1/p^s}, \end{equation} valable pour $s>s_0$. (Ici, $\prod_p$ signifie un produit \'etendu aux valeurs de $p$ premiers, $p=2,3,5,7,\ldots$\,.) {\bf Q2.} Utiliser la question pr\'ec\'edente pour \'etablir par un argument tres simple d'analyse qu'il existe une infinit\'e de nombres premiers. (Cette preuve ing\'enieuse du th\'eor\`eme d'Euclide est due \`a Euler.) {\bf Note,} Les propri\'et\'es fines de $\zeta(s)$ sont \`a la base du th\'eor\`eme des nombres premiers (Riemann, puis Hadamard et de la Vall\'ee-Poussin) d'apr\`es lequel le nombre de nombres premiers inf\'erieurs \`a~$x$, soit $\varpi(x)$, est estim\'e par: \begin{equation}\label{pnt} \varpi(x)=\frac{x}{\log x}(1+o(1)), \end{equation} En admettant~(\ref{pnt}), montrer que le nombre de premiers dont la repr\'esentation binaire comporte exactement $n$~bits est asymptotique \`a \[ c_1\frac{2^n}{n}, \] et d\'eterminer $c_1$. {\bf Q3.} Montrer que \[ \frac{1}{\zeta(s)}=\sum_{n=1}^\infty \frac{\mu(n)}{n^s}, \] o\`u ne prend que les valeurs $0,\pm1$; pr\'ecis\'ement: $\mu(n)=0$ d\`es que $n$ est divisible par un carr\'e ($>1$), et \[ \mu(p_1p_2\cdots p_r)=(-1)^r,\] les $p_j$ \'etant des premiers distincts. La suite des valeurs $\{1,-1,-1,0,-1,1,-1,\ldots\}$ est appel\'ee suite de Moebius. {\bf Q4.} Soit $\{a_n\}$ une suite de complexes. On appelle {\em s\'erie g\'en\'eratrice de Dirichlet\/} associ\'ee \`a cette suite la somme \[ \alpha(s):=\sum_{n\ge1} a_n n^{-s}. \] \'Etant donn\'e trois suites $a_b,b_n,c_n$ de s\'eries de Dirichlet associ\'ees $\alpha(s),\beta(s),\gamma(s)$. Montrer l'\'equivalence \[ \alpha(s)=\beta(s)\cdot\gamma(s) ~~\Longleftrightarrow~~ a_n=\sum_{d\;|\;n} b_d c_{n/d}, \] o\`u la somme est \'etendue \`a tous les diviseurs $d$ de $n$, ce qui est not\'e $d~|~n$. En d\'eduire la {\em formule d'inversion de Moebius\/}: pour deux suite $f_n,g_n$ quelconques, on a l'\'equivalence \begin{equation}\label{moebius} f_n=\sum_{d\;|\;n}g_d ~~\Longleftrightarrow~~ g_n=\sum_{d\;|\;n} \mu(d)g_{n/d}. \end{equation} Inverser la relation entre s\'eries g\'en\'eratrices ordinaires: \[ f(z)=\sum_{k\ge1} g(z^k), \] en exprimant $g(z)$ en fonction de $f(z)$. On suppose $g$ sans terme constant: $g(0)=0$. {\bf Q5.} [Facultatif] Soit $\Omega=\{\omega_n(z)\}$ un syst\`eme de fonctions. Les cas \[ \Omega_{OGF}=\{z^n\}_{n=0}^\infty,~~ \Omega_{EGF}=\{\frac{z^n}{n!}\}_{n=0}^\infty,~~ \Omega_{DGF}=\{n^{-z}\}_{n=1}^\infty \] donnent lieu aux s\'eries ordinaires, exponentielles, et de Dirichlet. On definit la fonction $\zeta$ et les coefficients de Moebius par \[\zeta_\Omega(z):=\sum_n 1\cdot \omega_n(z),~~ \frac{1}{\zeta_\Omega(z)}:=\sum_n \mu_\Omega(n)\omega_n(z). \] Remplir une matrice $4\times 3$ dont les colonnes correspondent \`a OGF, EGF, DGF, et les lignes donnent: (i) la fonction zeta, (ii) les coefficients de Moebius, (iii) la relation entre coefficients qui exprime le produit de s\'eries, (iv) la relation d'inversion de type Moebius. Pouvez-vous interpr\'eter \[ [z^n]\frac{1}{2-\frac{1}{1-z}}, ~~~ [z^n]\frac{1}{2-e^z},~~~ [n^{-z}] \frac{1}{2-\zeta(z)}, \] o\`u l'on utilise la g\'en\'eralisation naturelle de la fonction coefficient $[\,\cdot\,]$? (Une telle th\'eorie transverse a \'et\'e d\'evelopp\'ee par Rota.) \begin{center} \sc Partie II. Polyn{\^o}mes \end{center} {\em Cette partie du probl\`eme montre que des objets alg\'ebriques peuvent se traitent par les m\'ethodes de la combinatoire \'enum\'erative. Les d\'eveloppements qui suivent sont \`a la base de l'analyse d'algorithmes probabilistes en calcul formel et en th\'eorie des codes.} {\bf Rappel.} Pour un nombre premier $p$, on consid\`ere le corps $F=F_p$ form\'e par les entiers pris modulo~$p$. On travaille dans l'anneau $F[x]$ des polyn\^omes \`a coefficients dans $F$. On rappelle que, dans cet anneau, il existe une division euclidienne et une propri\'et\'e de factorisation unique. Les \'elements de $F[x]$ qui sont ind\'ecomposables (l'\'equivalent des nombres premiers) sont appel\'es polyn{\^o}mes irreductibles: $f$ est irr\'eductible si $f=g\cdot h$ implique $g=1$ ou $h=1$. Fixons $p$. On d\'esigne par ${\cal P}$ la classe des polyn\^omes unitaires (dont le coefficient de t\^ete vaut 1) et par ${\cal I}$ la sous-classe des polyn\^omes unitaires et irr\'eductibles. Par convention, la taille (au sens combinatoire) d'un polyn{\^o}me est son degr\'e (au sens alg\'ebrique). La sous-classe ${\cal Q}\subset {\cal P}$ repr\'esente les polyn\^omes unitaires ``sans carr\'es'', c-\`a-d, non divisibles par un carr\'e: $f$ est sans carr\'e si $f=g\cdot h^2$ implique $h=1$. {\bf Q1.} Montrer que la s\'erie g\'en\'eratrice de $\cal P$ vaut \[ P(z)=\frac{1}{1-pz}. \] Observer que tout $f(x)\in F[x]$ s'\'ecrit $f(x)=g(x)\cdot h(x)^2$ o\`u $g$ est sans carr\'e et $h$ quelconque. D'autre part, sii ${\cal H}$ est une classe de polyn\^omes de s\'erie g\'en\'eratrice $H(z)$, la s\'erie g\'en\'eratrice de l'ensemble $\{h(x)^2~/~h(x)\in{\cal H}\}$ vaut $H(z^2)$. En d\'eduire la s\'erie g\'en\'eratrice de $\cal Q$. Calculer la probabilit\'e qu'un polyn\^ome pris uniform\'ement dans ${\cal P}_n$ soit sans carr\'e. {\bf Q2.} Montrer que \[ \begin{array}{lll} P(z)&=&\ds \prod_{n=1}^\infty (1-z^n)^{-I_n}\\ &=&\ds \exp\left(\sum_{k=1}^\infty \frac1k I(z^k)\right). \end{array} \] Exprimer la relation correspondante entre $zP'(z)/P(z)$ et $J(z)=zI'(z)$. En d\'eduire la relation \[ I_n =\frac{1}{n}\sum_{d~|~n}\mu(d)p^{n/d}, \] o\`u $\mu$ est le coefficient de Moebius. {\bf Q3.} Montrer bri\`evement que \[ I_n =\frac{p^n}{n}(1+o(1)). \] Comment se compare la situation des polyn\^omes sur un corps fini \`a celle des entiers? On suppose qu'on dispose de deux proc\'edures: {\tt draw(n)} tire au hasard un \'el\'ement de ${\cal P}_n$ et {\tt irred(f)} r\'epond vrai ou faux selon que $f$ est irr\'eductible ou non. Combien d'essais en moyenne effectue l'algorithme de tirage d'un polyn\^ome irr\'eductible suivant? \begin{verbatim} repeat f := draw(n); until irred(f); \end{verbatim} Quelle est la variance du nombre de tirages? {\bf Q4.} Soit $\omega(f)$ le nombre de facteurs irr\'eductibles de $f$ compt\'es avec multiplicit\'e, par exemple, \[ \omega\left((1+x)(3+x+x^3)^5(4+x^7)^2(2+2x+x^9)\right)=1+5+2+1=9. \] Soit $P_{n,k}$ le nombre de $f\in{\cal P}_n$ tels que $\omega(f)=k$ et $P(z,u):=\sum_{n,k}P_{n,k}u^kz^n$. Montrer que \[ \begin{array}{lll} P(z,u)&=&\ds \prod_{n=1}^\infty (1-uz^n)^{-I_n}\\ &=&\ds \exp\left(\sum_{k=1}^\infty \frac{u^k}{k} I( z^k)\right). \end{array} \] Montrer que l'esp\'erance de $\omega$ prise sur l'ensemble des polyn\^omes ${\cal P}_n$ vaut exactement \[ M_n=\hbox{coeff} [z^n]\, \left(\frac{\partial}{\partial u}P\left(\frac zp ,u\right)\right)_{u=1}. \] D\'eterminer un \'equivalent asymptotique de \[ [z^n] \left(I(\frac{z}{p})+I(\frac{z^2}{p^2})+I(\frac{z^3}{p^3})+\cdots\right) \] et en d\'eduire que \[ M_n=\log n (1+o(1)). \] (Se limiter aux grandes \'etapes de la d\'emonstration.) [Facultatif] Qu'est-ce que ce r\'esultat sugg\`ere quant au nombre moyen de facteurs premiers d'un entier $\le x$? {\bf Q5.} [Facultatif] Montrer que le nombre d'\'el\'ements de ${\cal P}_n$ qui ont $n_1$ facteurs irr\'eductibles de degr\'e $1$, $n_2$ de degr\'e~2, etc, vaut (en marquant la d\'ependance en~$p$): \[ G(n_1,n_2,\ldots;p)=\prod_{j=1}^n {I_{n_j}+n_j-1\choose n_j}. \] Les $I_n$ sont bien s\^ur ceux qui sont relatifs \`a la caract\'eristique $p$ du corps: $I_n=I_n(p)$. Calculer pour $n$ {\em fix\'e\/} et $p\to+\infty$ la limite \[ g(n_1,n_2,\ldots)=\lim_{p\to+\infty} \frac{G(n_1,n_2,\ldots;p)}{p^n}. \] Montrer que $g(n_1,n_2,\ldots)$ est aussi le nombre de permutations de $n$ qui ont $n_1$ cycles de taille 1, $n_2$ cycles de taille 2, etc. En r\'esum\'e la d\'ecomposition en facteurs irr\'eductibles d'un polyn\^ome de degre fix\'e~$n$ sur un corps de grande cardinalit\'e ressemble \`a la d\'ecomposition en cycles d'une permutation de la m\^eme taille~$n$. \clearpage \begin{center} \sc Partie III. Explorations de calcul formel \end{center} Il s'agit l\`a d'un exercice \`a pr\'eparer en binome. Le r\'esultat peut fort bien \^etre une feuille de travail {\sc Maple}, mais \'edit\'ee convenablement et bri\`evement comment\'ee, ou bien un ``compte-rendu'' d'exp\'erience manuscrit. {\em Le probl\`eme trait\'e ici est une simplification d'une situation qui s'est pr\'esent\'ee r\'eellement il y a quelques ann\'ees. Les statisticiens construisent des arbres de classification appel\'es {\em hi\'erarchies\/}. Le probl\`eme consiste \`a analyser les propri\'et\'es des hi\'erarchies al\'eatoires sur la base du principe qu'une classification produite dans le monde r\'eel (par ex. par un programme d'analyse statistique) a d'autant plus de ``chances'' d'\^etre significative qu'elle s'\'ecarte des lois du hasard. D'o\`u l'int\'er\^et de quantifier l'al\'ea!} Les hi\'erarchies sont des arbres dont les sommets externes sont les $n$ objets \`a classifier (la taille vaut alors $n$) et dont les sommets internes (repr\'esentant les ``classes'') ont degr\'e tous $\ge2$, car il faut que la classification soit non triviale. Par exemple: \begin{small} \begin{verbatim} C=chat, H=homme, L=lion, O=orang-outang, T=tigre, V=vache . n = 5 (nombre de sommets externes) /|\ / | \ 3 sommets internes (classes) . V . /|\ /\ T C L H O \end{verbatim} \end{small} Les hi\'erarchies sont donc ``non-planaires'' (pas de distinction gauche/droite) et enracin\'ees, de par l'origine du probl\`eme. Les objets \`a classifier sont assimil\'es aux \'etiquettes $1,\ldots,n$. En d'autres termes: \begin{quote}\sl La classe ${\cal H}$ des hi\'erarchies est la classe des arbres enracin\'es non-planaires, \'etiquet\'es aux sommets externes seulement (qui d\'eterminent la taille) et dont les sommets internes ont tous degr\'es $\ge2$. \end{quote} Symboliquement: \[ {\cal H}={\cal Z}+{\tt Set}({\cal H}, \hbox{card}\ge2).\] \bigskip {\bf III.1 D\'enombrement asymptotique des hi\'erarchies} {\bf Q1.} On commence par se convaincre que la s\'erie g\'en\'eratrice exponentielle des hierarchies v\'erifie l'\'equation \[ H(z)=z+\left(e^{H(z)}-1-H(z)\right). \] Maple sait trouver pour nous une solution au moyen de la fonction ``sp\'eciale'' {\tt LambertW} $(W$) qui est la solution de \[ z=We^W. \] d\'efinie et positive pour $z\in[0,e^{-1}]$. (En terme de la fonction d'arbre du cours, $T(z)$ , on a $W(z)=-T(-z)$; essayer {\tt series(LambertW(z),z=0,10);}) \begin{verbatim} eqH:=H=z+exp(H)-1-H; Hz:=solve(eqH,H); \end{verbatim} Calculer les 30 premiers coefficients \begin{verbatim} Hs:=series(Hz,z=0,31); for i from 0 to 30 do c[i]:=coeff(Hs,z,i)*1.0 od; \end{verbatim} et deviner une loi tr\`es approximative de croissance de \[ c_i=[z^i]\, H(z). \] On pourra s'aider de \begin{verbatim} plot([seq([i,c[i+1]/c[i]],i=5..30)],0..30,0..3); \end{verbatim} Le nombre de hi\'erarchies de taille $n$ vaut $H_n=n!c_n$. {\bf Q2.} On sait que le rayon de convergence d'une s\'erie enti\`ere \`a coefficients positifs est \'egal \`a la distance entre l'origine et la singularit\'e positive la plus proche. Ici, la singularit\'e correspond \`a une pente verticale (de d\'eriv\'ee infinie), comme on peut s'en convaincre par un {\tt plot}. \begin{verbatim} plot(Hz,z=0..0.5); plot(diff(Hz,z),z=0..0.5); H1z:=normal(diff(Hz,z)); \end{verbatim} Par une suite de trac\'es de ce type, on devra obtenir une approximation \`a 0.001 pr\`es de la singularit\'e positive, \[\rho=???\pm0.001.\] Combien de chiffres environ comporte la repr\'esentation d\'ecimale de $H_{1000}$? {\bf Q3.} On se propose de d\'eterminer maintenant exactement la singularit\'e positive $\rho$. En supposant qu'elle provient de l'annulation du denominateur de $\frac{d}{dz}H(z)$, on d\'eterminera alors sa valeur exacte (utliser {\tt solve}): \[ \rho=??? \] On peut alors tenter de comprendre de quelle mani\`ere $H(z)$ devient singuli\`ere lorsque $z$ tend vers $\rho$ par valeurs inf\'erieures. Il est commode de poser $z=\rho-h$ et faire $h\to0^+$, ce qui s'obtient par un d\'eveloppement en s\'erie. \begin{verbatim} map(simplify,series(subs(z=rho-h,Hz),h=0)); \end{verbatim} On suppose que $c_n$ est asymptotiquement equivalent a ce que l'on obtient en ne retenant que les deux premiers termes, soit \[ c_n \sim [z^n]\left(c_0-c_1\sqrt{\rho-z}\right). \] En d'autres termes, on suppose, et cela est justifi\'e par l'analyse de singularit\'e que:{\em une bonne approximation de la fonction donne une bonne approximation des coefficients}. En d\'eduire une formule asymptotique pour $c_n$ de la forme \[ c_n \sim K_1 K_2^n n^{K_3},~~~ K_1,K_2,K_3=???. \] V\'erifier comme suit: \begin{verbatim} for i from 2 to 30 do evalf(coeff(Hs,z,i)/rho^(-i+1/2)*i^(3/2)*sqrt(Pi)) od; \end{verbatim} Avec quelle pr\'ecision estimez-vous pouvoir pr\'evoir la valeur de $H_{1000}$? {\bf III.2 Nombre d'\'etapes de classification.} On s'int\'eresse au nombre de sommets internes de l'arbre (le nombre de classes). Soient $H_{n,k}$ le nombre de hi\'erarchies de taille $n$ ayant $k$ sommets internes et $n$ sommets externes. On se convaincra (ou bien, on admettra) que la s\'erie double \[ H(z,u)=\sum_{n,k}H_{n,k}u^k\frac{z^n}{n!} \] v\'erifie l'equation \[ H(z,u)=z+u\left(e^{H(z,u)}-1-H(z,u)\right). \] {\bf Q4.} R\'esoudre cette \'equation en termes de la fonction $W$ de Lambert. On pose \[ G(z):=\left(\frac{\partial}{\partial u}F(z,u)\right)_{u=1} \] Exprimer de m\^eme $G(z)$ (la d\'erivation s'obtient par {\tt diff}). Soit $d_n:=[z^n]G(z)$, de sorte que le nombre moyen de sommets internes dans une hi\'erarchie de taille $n$ vaut \[ \mu_n=\frac{d_n}{c_n}. \] On tabulera $\mu_n$ pour $n=2\,.\,.\,30$. Deviner une formule approximative d\'ecrivant la croissance asymptotique de $\mu_n$. Chercher a am\'eliorer l'estimation, empiriquement (en devinant simultan\'ement une valeur approch\'ee du terme d'erreur), et/ou en \'evaluant \[ \gamma:=\lim_{z\to\rho^-} \frac{G(z)}{z\frac{d}{dz}H(z)}. \] Estimer au mieux $\mu_{1000}$. Un programme de classification produit sur $n=1000$ donn\'ees une hierarchie qui comprend 273 classes (sommets internes). La hi\'erarchie ainsi constitu\'ee ressemble-t-elle \`a une hi\'erarchie al\'eatoire? \begin{quote} [\ ] OUI~~~~~[\ ] NON~~~~~[\ ] INCERTAIN \end{quote} \end{document}