1. Récursivités simples Dans cette partie nous allons donc traiter le cas des algorithmes récursifs, et voir comment le calcul de leur complexité se déduit d'une étude de suite.  Position du problème Dans un algorithme itératif, le décompte du nombre d'opérations élémentaires se fait en additionnant le nombre d'opérations de chaque itération. C'est pourquoi dans le chapitre précédent nous avons souvent utilisé des calculs de sommes pour arriver à nos fins. La complexité d’un algorithme récursif traitant des données d'une certaine taille va quand à elle naturellement dépendre de la complexité du même algorithme avec des données de taille inférieure. Cette complexité va donc être une suite définie par récurrence. Définition Soit $k$ élément de $N^{\ast }$, et ${\left({}_n\right)}_{n\in N}$ une suite réelle. On dit que la suite ${\left({}_n\right)}_{n\in N}$ est une suite définie par une récurrence d'ordre $k$ s'il existe une fonction $f$ définie sur $R^k$ et à valeur dans $R$ telle que $u_n=f\left(u_{n-1},u_{n-2},...,u_{n-k}\right)$ Dans la suite de cette partie on se limitera au cas des suites arithmético-géométriques et des suites récurrentes linéaires d’ordre $2$. Cela sera déjà bien suffisant pour calculer la complexité de nombreux algorithmes récursifs.  Suites arithmético-géométriques Commençons par une définition, sans doute déjà connue du lecteur. Définition Une suite réelle ${\left({}_n\right)}_{n\in N}$ est dite arithmético-géométrique s'il existe deux réels $a$ et $b$ tels que $\forall n\in N^{\ast },u_n=a{u}_{n-1}+b$ On prend l'habitude de distinguer deux cas particuliers, celui des suites arithmétiques et celui des suites géométriques. Définition Avec les notations de la définition précédente : Si $a=1$, on dit que la suite ${\left({}_n\right)}_{n\in N}$ est une suite arithmétique de raison $b$. Si $b=0$, on dit que la suite ${\left({}_n\right)}_{n\in N}$ est une suite géométrique de raison $a$. Le résultat suivant nous donne l'expression explicite du terme général d'une suite arithmético-géométrique. Propriété Soit ${\left({}_n\right)}_{n\in N}$ une suite arithmético-géométrique associée aux réels $a$ et $b$. Si $a=1$, alors $\forall n\in N,u_n=u_0+nb$ Si $a\ne 1$, et si l'on pose $l=\frac{b}{1-a}$, alors $\forall n\in N,u_n=\left(u_0-l\right)a^n+l$ On admettra ce résultat, ce n’est pas l’objet de ce cours. Ce n’est ceci-dit pas bien méchant à démontrer. Nous utiliserons peu cette expression exacte, mais plutôt l'approximation suivante qui nous renseigne sur l'ordre de grandeur du terme général d'une suite arithmético-géométrique. Propriété Soit ${\left({}_n\right)}_{n\in N}$ une suite arithmético-géométrique associée aux réels $a$ et $b$. On suppose que $a$, $b$ et $u_0$ sont positifs. Si $a=1$, $u_n=\Theta \left(n\right)$. Si $a>1$, $u_n=\Theta \left(a^n\right)$. La restriction que $a$, $b$ et $u_0$ soient positifs n'est absolument pas génante car ça sera toujours le cas dans notre contexte de calculs de complexité. Voyons maintenant sur des exemples comment appliquer ce qui précède. Le premier concerne la très fameuse fonction factorielle. Example 1.1. Complexité de la fonction factorielle récursive Rappelons tout d'abord que $n!=1\times 2\times 3\times \mathrm{...}\times n$ et que cette fonction vérifie la relation de récurrence $n!=n\times \left(n-1\right)!$. L'implémentation en Python de cette fonction est : def factorielleRecursive(n): if n == 0: return 1 else: return n*factorielleRecursive(n-1) Cette fonction n'est composée que d'une structure conditionelle. Si $n>0$, une opération élémentaire (une comparaison) est effectuée lors du test, et une autre (un produit) lors de l'appel récursif. On a donc dans ce cas $T\left(n\right)=T\left(n-1\right)+2$. Si $n=0$, seule la comparaison a lieu donc $T\left(0\right)=1$. La complexité $T$ est donc une suite arithmético-géométrique associée aux constantes $a=1$ et $b=2$. D'après les résultats précédents, on a alors $T\left(n\right)=1+2n$ et surtout $T\left(n\right)=\Theta \left(n\right)$. Cet algorithme est donc de complexité linéaire. A noter que l'algorithme itératif calculant cette factorielle a la même complexité. Le voici en effet en Python : def factorielleIterative(n): resultat = 1 for i in range(2,n+1): resultat *= i return resultat On a une structure for qui réalise $n-1$ itérations, chacune comportant le même nombre fixe d'opérations élémentaires. C'est pourquoi là aussi $T\left(n\right)=\Theta \left(n\right)$. L'exemple suivant est le fameux problème des tours de Hanoï, imaginé par le mathématicien français Edouard Lucas (1842-1891). Ce problème a été recontré dans les séances d'exercices du cours 1ADS mais nous allons le redétailler. Example 1.2. Problème des tours de Hanoï Le but est de déplacer $n$ disques de diamètres différents, d’une tour initiale (celle de gauche) à une tour finale (celle de droite) en passant par une tour intermédiaire (celle du milieu). Initialement, tous les disques sont empilés sur la tour initiale, du plus grand au plus petit. Les règles de déplacement sont les suivantes : On ne peut bouger qu’un seul disque à la fois. On ne peut déplacer un disque que vers une tour vide, ou sur un disque plus grand. Etudions "à la main" le cas $n=3$. Voici la position initiale : Effectuons ces trois premiers mouvements : On a donc réussi à bouger les deux plus petits disques vers la tour intermédiaire en passant par la tour finale. Bougeons maintenant le plus grand : Il ne reste plus qu'à effectuer ces trois derniers mouvements qui ressemblent évidemment fortement aux trois premiers : Et le problème est résolu pour trois disques. Essayons maintenant de reproduire dans le cas général ce que l'on vient de faire dans ce cas très particulier. On arrive vite à la conclusion que la résolution du problème pour toute valeur de $n$ est récursive : On déplace $n-1$ disques de la tour initiale à la tour intermédiaire en passant par la tour finale. On déplace le plus grand disque de la tour initiale vers la tour finale. On déplace $n-1$ disques de la tour intermédiaire à la tour finale en passant par la tour initiale. Le cas de base étant le déplacement d'un seul disque. En Python cela donne cette implémentation : def hanoi(de,vers,via,n): if n==1: print(de," vers ",vers) else: hanoi(de,via,vers,n-1) print(de," vers ",vers) hanoi(via,vers,de,n-1) hanoi("1","3","2",3) Sans surprises, pour trois disques on retrouve bien les mouvements précédemment mis en images : 1 vers 3 1 vers 2 3 vers 2 1 vers 3 2 vers 1 2 vers 3 1 vers 3 Venons-en maintenant au calcul de la complexité de cette procédure qui n'est composée que d'une structure conditionnelle. Si $n>1$, une opération élémentaire (une comparaison) est effectuée lors du test, une autre lors de l'affichage, et on a deux appels récursifs. On a ainsi $T\left(n\right)=2T\left(n-1\right)+2$. Si $n=1$, seule la comparaison a lieu donc $T\left(1\right)=1$. La complexité $T$ est donc une suite arithmético-géométrique associée aux constantes $a=2$ et $b=2$. D’après le résultat précédent, on a alors $T\left(n\right)=\Theta \left(2^n\right)$. Cet algorithme est donc de complexité exponentielle.  Suites récurrentes linéaires Cette sous-partie n'est pas conceptuellement très difficile, mais elle demande de la vigilance car certains résultats sont assez techniques. On distinguera le cas des suites homogènes des suites non homogènes, et l'on verra qu'en pratique ce sont ces dernières qui nous intéresserons le plus.  Suites homogènes Commençons naturellement par une définition du concept. Définition Une suite réelle ${\left({}_n\right)}_{n\in N}$ est une suite récurrente linéaire homogène d'ordre deux s'il existe deux réels $a$ et $b$ tels que $\forall n\ge 2,u_n=a{u}_{n-1}+b{u}_{n-2}$ Pour étudier une telle suite, on doit tout d'abord lui associer un polynôme dit caractéristique. Définition Soit ${\left({}_n\right)}_{n\in N}$ une suite récurrente linéaire homogène d'ordre deux associée aux réels $a$ et $b$. Le polynôme caractéristique de la suite ${\left({}_n\right)}_{n\in N}$ est par définition le polynôme $x^2-ax-b$. L'équation caractéristique de la suite ${\left({}_n\right)}_{n\in N}$ est alors l'équation $x^2-ax-b=0$. Le terme général d'une suite récurrente linéaire homogène d'ordre deux va alors s'exprimer en fonction des racines de son polynôme caractéristique. On ne fera pas l'insulte au lecteur de lui rappeler comment l'on calcule les racines d'un polynôme du second degré. Propriété Soit ${\left({}_n\right)}_{n\in N}$ une suite récurrente linéaire homogène d'ordre deux et soit $\Delta$ le discriminant de son équation caractéristique. Si $\Delta >0$, en notant $x_1$ et $x_2$ les deux racines réelles distinctes du polynôme caractéristique, on a $\exists \lambda ,\mu \in R,\forall n\in N,u_n=\lambda x_1^n+\mu x_2^n$ Si $\Delta =0$, en notant $x$ la racine réelle double du polynôme caractéristique, on a $\exists \lambda ,\mu \in R,\forall n\in N,u_n=\left(\lambda n+\mu \right)x^n$ Dans les deux cas, les constantes $\lambda$ et $\mu$ se déterminent à l’aide de la valeur des deux premiers termes de la suite. On a alors un système linéaire de deux équations à deux inconnues à résoudre. On ne traitera pas le cas où $\Delta <0$ car on ne le rencontrera pas lors de nos calculs de complexités. En un mot, on peut alors montrer que les suites sont alors exprimables à l’aide des fonctions cosinus et sinus. Ou au choix de l’exponentielle complexe. Appliquons ce resultat sur un exemple célèbre, la suite due au mathématicien italien Leonardo Fibonacci (1175-1250). Example 1.3. Suite de Fibonacci La suite de Fibonnaci est la suite récurrente linéaire homogène d'ordre deux définie par $u_n=\{\begin{array}{cc}0& \text{si}n=0\\ 1& \text{si}n=1\\ u_{n-1}+u_{n-2}& \text{si}n\ge 2\end{array}$ L'équation caractéristique de cette suite est $x^2-x-1=0$. Son discriminant $\Delta$ est égal à $5$. Le polynôme caractéristique possède donc deux racines distinctes $x_1=\frac{1+\sqrt{5}}{2}$ et $x_2=\frac{1-\sqrt{5}}{2}$. D'après le résultat précédent $\exists \lambda ,\mu \in R,\forall n\in N,u_n=\lambda {\left(\frac{1+\sqrt{5}}{2}\right)}^n+\mu {\left(\frac{1-\sqrt{5}}{2}\right)}^n$ On détermine alors $\lambda$ et $\mu$ en se servant de la valeur des deux premiers termes $u_0$ et $u_1$. On a en effet d'une part $u_0=0$ et $u_1=1$ d'après la définition de la suite, et d'autre part d'après l'expression du terme général $\{\begin{array}{c}{u}_0=\lambda +\mu \\ u_1=\lambda \left(\frac{1+\sqrt{5}}{2}\right)+\mu \left(\frac{1-\sqrt{5}}{2}\right)\end{array}$ On doit donc résoudre le système $\{\begin{array}{c}0=\lambda +\mu \\ 1=\lambda \left(\frac{1+\sqrt{5}}{2}\right)+\mu \left(\frac{1-\sqrt{5}}{2}\right)\end{array}$ On trouve $\lambda =\frac{1}{\sqrt{5}}$ et $\mu =-\frac{1}{\sqrt{5}}$. Finalement, on obtient $\forall n\in N,u_n=\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^n$ Rappelons maintenant un résultat classique sur les limites, qui nous permettra ensuite d'obtenir l'ordre de grandeur d'une suite récurrente linéaire. Propriété Soit $x$ élément de $R$. On a Si $x>1$, $\underset{n\to \infty }{lim}{x}^n=+\infty$. Si $-1<x<1$, $\underset{n\to \infty }{lim}{x}^n=0$. Si $x\le -1$, $x^n$ n'a pas de limite quand $n\to +\infty$. Le prochain résultat sera celui qui in fine nous servira lors de nos calculs de complexité. Propriété Soit ${\left({}_n\right)}_{n\in N}$ une suite récurrente linéaire homogène d'ordre deux et soit $\Delta$ le discriminant de son équation caractéristique. On suppose que $\Delta >0$ et l'on note $x_1$ et $x_2$ les deux racines réelles distinctes du polynôme caractéristique. Si $x_1>1$, et si $\left|x_1\right|>\left|x_2\right|$, alors $u_n=\Theta \left(x_1^n\right)$. Cette propriété signifie moralement que sous certaines conditions $x_1^n$ impose le comportement asymptotique de la suite. Appliquons la à la suite de Fibonacci. Example 1.4. Ordre de grandeur de la suite de Fibonacci Pour la suite de Fibonacci, on a montré que $\Delta =5$, $x_1=\frac{1+\sqrt{5}}{2}$ et $x_2=\frac{1-\sqrt{5}}{2}$. Les hypothèses de la propriété précédente sont donc vérifiées. Ainsi $u_n=\Theta \left({\left(\frac{1+\sqrt{5}}{2}\right)}^n\right)$.  Suites non homogènes La différence avec une suite homogène réside dans la présence d'un terme supplémentaire dans l'équation de récurrence. Définition Une suite réelle ${\left({}_n\right)}_{n\in N}$ est une suite récurrente linéaire non homogène d'ordre deux s'il existe deux réels $a$ et $b$ et une fonction $f$ de $N$ dans $R$, tels que $\forall n\ge 2,v_n=a{v}_{n-1}+b{v}_{n-2}+f\left(n\right)$ On pourrait donner des résultats très précis sur le terme général d'une telle suite, mais nous nous contenterons de la propriété suivante qui en donne son ordre de grandeur. En un mot, pour étudier une suite non homogène il convient d'étudier la suite homogène associée, i.e. la suite obtenue en "supprimant" la fonction $f$ dans l'équation de récurrence. Propriété Soit ${\left({}_n\right)}_{n\in N}$ une suite récurrente linéaire non homogène d'ordre deux associée aux réels $a$ et $b$ et à la fonction $f$. On considère ${\left({}_n\right)}_{n\in N}$ la suite récurrente linéaire homogène d'ordre deux associée aux réels $a$ et $b$. Soit $\Delta$ le discriminant de son équation caractéristique. On suppose que $\Delta >0$ et l'on note $x_1$ et $x_2$ les deux racines réelles distinctes du polynôme. caractéristique. Si $x_1>1$, si $\left|x_1\right|>\left|x_2\right|$, et si $f$ est une fonction polynomiale alors $v_n=\Theta \left(x_1^n\right)$. Moralement cela signifie que si elle est polynomiale, la fonction $f$ n’influe pas sur le comportement de la suite, et que l'ordre de grandeur de la suite non homogène est alors celui de la suite homogène. Terminons cette partie par un exemple, avec l'implémentation de la suite de Fibonacci et le calcul de sa complexité. Example 1.5. Complexité de la fonction récursive calculant le terme général de la suite de Fibonacci Voici une fonction récursive calculant le nième terme de la suite de Finonacci : def fibonacci(n): if n<2: return n else: return fibonacci(n-1) + fibonacci(n-2) Si $n>2$, une opération élémentaire (une comparaison) est effectuée lors du test et une autre (une addition) entre les deux appels récursifs. On a ainsi $T\left(n\right)=T\left(n-1\right)+T\left(n-2\right)+2$. Si $n=0$ ou $n=1$, seule la comparaison a lieu donc $T\left(0\right)=T\left(1\right)=1$. Dans cet exemple la complexité est donc une suite récurrente linéaire non homogène d'ordre deux. La suite homogène associée est $u_n=\{\begin{array}{cc}1& \text{si}n=0\\ 1& \text{si}n=1\\ u_{n-1}+u_{n-2}& \text{si}n\ge 2\end{array}$ Cette dernière suite est quasiment celle de Fibonacci, seul le premier terme diffère. La relation de récurrence est en tout cas la même que pour la suite de Fibonacci donc (avec les notations précédentes) $\Delta =5$, $x_1=\frac{1+\sqrt{5}}{2}$ et $x_2=\frac{1-\sqrt{5}}{2}$. D'autre part, la fonction $f$ de la relation de récurrence non linéaire est constante égale à $2$ donc en particulier polynomiale. Toute les hypothèses de la propriété précédente sont vérifiées, ainsi $T\left(n\right)=\Theta \left({\left(\frac{1+\sqrt{5}}{2}\right)}^n\right)$. La complexité de cet algorithme est donc exponentielle.  Algorithmes de type "diviser pour régner" Après les récursivités relativement simples de la partie précédente, nous allons maintenant nous confronter à celles inhérentes à l'utilisation d'une technique de type "diviser pour régner". Soyons honnête, ce qui va suivre est délicat et demandera de gros efforts au lecteur.  Position du problème Commençons par rappeler les trois étapes du paradigme "diviser pour régner" : Diviser : on divise les données initiales en plusieurs sous-parties. Régner : on résout récursivement chacun des sous-problèmes associés (ou on les résout directement si leur taille est assez petite). Combiner : on combine les différents résultats obtenus pour obtenir une solution au problème initial. Avec ce paradigme, la complexité d’un algorithme traitant des données de taille $n$ va naturellement dépendre de la complexité du même algorithme avec des données de taille $n/b$, où $b$ est le facteur avec lequel on divise le problème en sous-problèmes. Il va falloir de plus tenir compte de la complexité de l’étape de combinaison des résultats des sous-problèmes. Avant le cas général, nous allons commencer par étudier un exemple, celui du tri fusion.  L’exemple du tri fusion Le tri fusion consiste à trier récursivement les deux moitiés de la liste, puis à fusionner ces deux sous-listes triées en une seule. La condition d’arrêt à la récursivité sera l’obtention d'une liste à un seul élément, car une telle liste est évidemment déjà triée. Nous renvoyons le lecteur à ce chapitre du cours 1ADS pour la description des principaux algorithmes de tri, y compris celui-ci. Voici donc les trois étapes (diviser, régner et combiner) de cet algorithme : Diviser la liste en deux sous-listes de même taille (à un élément près) en la "coupant" par la moitié. Trier récursivement chacune de ces deux sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément. Fusionner les deux sous-listes triées en une seule. Example 1.6. Déroulement du tri fusion sur un exemple On considère la liste suivante de sept entiers : On la scinde en deux sous-listes en la coupant par la moitié : Sous-listes que l’on scinde à leur tour : Sous-listes que l’on scinde à leur tour : Ces sous-listes sont triées car elles n’ont qu’un élément. On va maintenant les fusionner deux par deux en de nouvelles sous-listes triées : De nouveau une étape de fusionnnement : Une dernière fusion : On a fusionné toutes les sous-listes obtenues lors des appels récursifs, le tri est terminé : En voici son implémentation en Python : def fusion(l,first,middle,last): i,j = first,middle+1 pro = [] while (i<=middle) and (j<=last): if l[i]<=l[j]: pro.append(l[i]) i+=1 else: pro.append(l[j]) j+=1 while i<=middle: pro.append(l[i]) i+=1 while j<=last: pro.append(l[j]) j+=1 for k in range(last-first+1): l[first+k] = pro[k] def triFusionRec(l,first,last): if first<last: triFusionRec(l,first,(first+last)//2) triFusionRec(l,((first+last)//2)+1,last) fusion(l,first,(first+last)//2,last) def triFusion(l): triFusionRec(l,0,len(l)-1) Bien prendre le temps d'appréhender le fonctionnement de cet algorithme. Voici maintenant le résultat établissant la complexité du tri fusion. Vu la nature même de celui-ci, le lecteur comprendra facilement qu'il n'y a pas de meilleur ou pire des cas. Théorème La complexité du tri fusion est $T\left(n\right)=\Theta \left(n\mathrm{l}\mathrm{o}{\mathrm{g}}_2\left(n\right)\right)$. Il s'agit de la meilleure complexité que puisse avoir un algorithme de tri. L'idée pour démontrer ce résultat est de construire l'arbre des appels récursifs, d'évaluer le coût de chaque sommet, puis d'en faire la somme. Démonstration Commençons par remarquer que la procédure de fusion est de complexité linéaire. Plus précisément, pour fusionner deux tableaux de taille $n/2$, on a une complexité en $\Theta \left(n\right)$. Dans l’algorithme précédent $n$ étant la différence entre "last" et "first" et donc $n/2$ la différence entre "middle" et "first" ou "last" et "middle". Cela provient du fait que l'on traite une et une seule fois chaque élément des deux listes à fusionner, et que ce traitement est de complexité constante. Dans la suite de cette preuve on va supposer que $n$ est une puissance de $2$, cela nous permettra d'avoir des subdivisions qui "tombent juste". A chaque appel récursif, on subdivise un problème de taille $n$ en $2$ sous-problèmes de taille $n/2$, les $2$ sous-listes que l'on va trier récursivement. A un niveau $j$ on aura donc $2^j$ sous-problèmes. Chacun de ces sous-problèmes sera de taille $n/2^j$, et aura ainsi un coût de l'ordre de $n/2^j$ (rappelons que la procédure de fusion est de complexité linéaire). Le coût d'un niveau $j$ est donc $2^j\times \left(\frac{n}{2^j}\right)=n$. C'est en effet le nombre de sous-problèmes du niveau $j$ multiplié par le coût de chacun d'eux. Pour mieux visualiser tout cela, voici l'arbre des appels récursifs, sur chaque sommet étant indiqué la taille du paramètre lors de l'appel en question : On a supposé que $n$ était une puissance de $2$, donc $n$ est de la forme $n=2^h$ où $h$ est la hauteur de l'arbre. C'est pourquoi $h=\mathrm{l}\mathrm{o}{\mathrm{g}}_2\left(n\right)$. Egalité que l'on a utilisée dans la figure précédente. Le nombre de niveaux est alors égal à $h+1$ (ne pas oublier le niveau initial), i.e. $\mathrm{l}\mathrm{o}{\mathrm{g}}_2\left(n\right)+1$. On a de plus déjà constaté que le coût de chaque niveau était égal à $n$. Le coût total est alors égal à la somme des coûts de tous les niveaux, i.e. $\mathrm{n}\times \left(\mathrm{l}\mathrm{o}{\mathrm{g}}_2\left(n\right)+1\right)$. Q.E.D. Dans la preuve précédente, on a supposé que $n$ était une puissance de $2$, ce qui a facilité notre étude de l'arbre. Si ce n'est pas le cas, il faut alors l'encadrer entre deux puissances de $2$, puis effectuer le raisonnement précédent sur ces deux puissances. On arrive alors relativement facilement au résultat. Nous ne rentrerons pas dans ces détails car ils n'apportent rien en terme de compréhension profonde.  Le Master Theorem (version simplifiée) Dans cette sous-partie nous n'allons plus nous limiter au cas du tri fusion, mais nous allons présenter et démontrer un résultat applicable à la majorité des algorithmes de type diviser pour régner. Nous allons donc nous intéresser à des algorithmes de la forme : def divideAndConquer(n): if n ==1: end of processing else: divideAndConquer(n//b) divideAndConquer(n//b) ... a times divideAndConquer(n//b) work of cost f(n) for dividing the problem and merging the solutions to the subproblems Un problème de taille $n$ est ainsi divisé en $a$ sous-problèmes de taille $n/b$, avec un coût $f\left(n\right)$ pour combiner les résultats de ces sous-problèmes. Il est donc implicitement supposé que chaque sous-problème a la même taille. Dans le cas contraire le Master Theorem ne peut s'appliquer. Master Theorem Soient $a\ge 1$, $b>1$, et $T$ une fonction vérifiant $T\left(n\right)=aT\left(\frac{n}{b}\right)+f\left(n\right)$ Les différents paramètres s'interprètent comme suit : $n$ est la taille du problème. $a$ est le nombre de sous-problèmes. $n/b$ est le taille de chaque sous-problèmes. $f\left(n\right)$ est le coût de la subdivision et de la combinaison des solutions des sous-problèmes. On suppose de plus que $f\left(n\right)=\Theta \left(n^d\right)$. Alors $T\left(n\right)=\{\begin{array}{cc}\Theta \left(n^d\right)& \text{si}\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)<d\\ \Theta \left(n^d\mathrm{l}\mathrm{o}\mathrm{g}\left(n\right)\right)& \text{si}\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)=d\\ \Theta \left(n^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)}\right)& \text{si}\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)>d\end{array}$ On a également la formulation équivalente suivante $T\left(n\right)=\{\begin{array}{cc}\Theta \left(n^d\right)& \text{si}a<b^d\\ \Theta \left(n^d\mathrm{l}\mathrm{o}\mathrm{g}\left(n\right)\right)& \text{si a}=b^d\\ \Theta \left(n^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)}\right)& \text{si}a>b^d\end{array}$ Il n’est pas nécessaire de préciser la base du logarithme dans le deuxième cas, puisque rappelons le toutes les fonctions logarithmes diffèrent juste d’une constante multiplicative. Comme lors de la démonstration de la complexité du tri fusion, nous allons étudier l'arbre des appels récursifs en faisant la somme des coûts de chaque sommet. Certains arguments seront donc similaires à ceux utilisés dans la sous-partie précédente. Nous aurons également besoin du petit lemme suivant : Lemme Soit $q\in R$. Si $q<1$, on a $\sum _{j=0}^r{q}^j\le \frac{1}{1-q}$ Si $q>1$, on a $\sum _{j=0}^r{q}^j\le q^r\left(1+\frac{1}{q-1}\right)$ Démonstration du lemme On sait (voir paragraphe 1.4 du chapitre, 1) que si $q\ne 1$, on a $\sum _{j=0}^r{q}^j=\frac{1-q^{r+1}}{1-q}=\frac{q^{r+1}-1}{q-1}$ Si $q<1$, on se sert de la première égalité et du fait que $1-q^{r+1}<1$. Le résultat en découle immédiatement. Si $q>1$, on utilise cette fois la seconde égalité et le fait que $q^{r+1}-1<q^{r+1}$. On obtient alors $\sum _{j=0}^r{q}^j\le \frac{q^{r+1}}{q-1}$ Il ne reste plus qu'à factoriser par $q^r$ et à changer la forme de la fraction. Démonstration du Master Theorem Dans la suite de cette preuve on va supposer que $n$ est une puissance de $b$, cela nous permettra d'avoir des subdivisions qui "tombent juste". A chaque appel récursif, on subdivise un problème de taille $n$ en $a$ sous-problèmes de taille $n/b$. A un niveau $j$ on aura donc $a^j$ sous-problèmes. Chacun de ces sous-problèmes sera de taille $n/b^j$, et aura ainsi un coût de l'ordre de ${(n/{}^{})}^d$ (rappelons que la complexité de la procédure de combinaison est en $\Theta \left(n^d\right)$). Le coût d'un niveau $j$ est donc $a^j\times {\left(\frac{n}{{}^{}}\right)}^d$. C'est en effet le nombre de sous-problèmes du niveau $j$ multiplié par le coût de chacun d'eux. Pour mieux visualiser tout cela, voici l'arbre des appels récursifs, sur chaque sommet étant indiqué la taille du paramètre lors de l'appel en question : On a supposé que $n$ était une puissance de $b$, donc $n$ est de la forme $n=b^h$ où $h$ est la hauteur de l'arbre. C'est pourquoi $h=\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)$. Egalité que l'on a utilisée dans la figure précédente. Contrairement au tri fusion, chaque niveau n'a pas le même coût, et l'on ne peut donc avoir le coût total en multipliant le nombre de niveaux par le coût de chacun d'eux. Pour estimer $T\left(n\right)$ on doit ainsi calculer la somme $\sum _{j=0}^{lo{g}_b\left(n\right)}{a}^j\times {\left(\frac{n}{{}^{}}\right)}^d$ On peut factoriser par $n^d$ dans cette somme puisque ce terme ne dépend pas de l'indice $j$ de sommation. On obtient alors l'égalité $\sum _{j=0}^{lo{g}_b\left(n\right)}{a}^j\times {\left(\frac{n}{{}^{}}\right)}^d=n^d\sum _{j=0}^{lo{g}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j$ On reconnaît la somme des premiers termes d'une suite géométrique de raison $q=\frac{a}{b^d}$. La valeur de cette quantité va donc déterminer celle de la complexité totale. Plus précisément, on devra distinguer les cas où $\frac{a}{b^d}$ est plus petit, plus grand ou égal à $1$. Cas où $a=b^d$ : On a alors $\frac{a}{b^d}=1$, et l'on est ramené à une somme de termes constants $\begin{array}{ccc}{n}^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j& =& n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}1\\ & =& n^d\times \left(\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)+1\right)\end{array}$ D'où $T\left(n\right)=\Theta \left(n^d\mathrm{l}\mathrm{o}\mathrm{g}\left(n\right)\right)$ Cas où $a<b^d$ : On utilise la première inégalité du lemme pour obtenir $n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j\le n^d\frac{1}{1-\frac{a}{b^d}}$ D'où $T\left(n\right)=\Theta \left(n^d\right)$ Cas où $a>b^d$ : On utilise cette fois la seconde inégalité du lemme. Il vient $n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j\le n^d{\left(\frac{a}{{}^{}}\right)}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}\left(1+\frac{1}{\frac{a}{b^d}-1}\right)$ Quelques changements d'expressions dues aux règles opératoires usuelles sur les puissances conduisent à $\frac{n^d}{b^{d\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}}=n^d{b}^{-d\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}=n^d{\left({}^{}\right)}^{-d}$ Or l'on sait que les fonctions logarithmes et exponentielles de base $b$ sont réciproques l'une de l'autre. Cela implique en particulier que $b^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}=n$ On a alors $n^d{\left({}^{}\right)}^{-d}=n^d{n}^{-d}=1$ Cela prouve que $n^d\sum _{j=0}^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}{\left(\frac{a}{{}^{}}\right)}^j\le a^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}\left(1+\frac{1}{\frac{a}{b^d}-1}\right)$ Et donc $T\left(n\right)=\Theta \left(a^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}\right)$ Il ne reste plus qu'à constater que $a^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)}=n^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)}$. Cela est vrai car les logarithmes dans la base $b$ de chacun de ces deux termes sont égaux à $\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)\times \mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)$. Si $n$ n'est pas une puissance de $b$ il faut procéder par encadrement. Comme pour le tri fusion nous ne rentrerons pas dans ces détails. Example 1.7. Retour sur le tri fusion Le tri fusion rentre bien sûr dans le cadre du Master Theorem. A chaque appel récursif, on y subdivise un problème de taille $n$ en $2$ sous-problèmes de taille $n/2$. On a donc $a=2$ et $b=2$. De plus la procédure de fusion est de complexité linéaire donc $d=1$. On est ainsi dans le cas où $a=b^d$. La complexité est alors $T\left(n\right)=\Theta \left(n^d\mathrm{l}\mathrm{o}\mathrm{g}\left(n\right)\right)$, i.e. $T\left(n\right)=\Theta \left(n\mathrm{l}\mathrm{o}\mathrm{g}\left(n\right)\right)$. On retrouve bien le résultat démontré sur ce cas particulier au début de cette partie. Pour terminer cette sous-partie, on propose au lecteur un petit exercice corrigé afin qu'il s'interroge sur les conditions d'application du Master Theorem. Exercice corrigé   Expliquer dans chacun des cas suivants pourquoi le Master Theorem ne s'applique pas : $T\left(n\right)=2^{n}T\left(\frac{n}{2}\right)+n^3$. $T\left(n\right)=T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+n^2$. $T\left(n\right)=\frac{1}{2}T\left(\frac{n}{2}\right)+n$. Display answer Si l'on se retrouve dans une situation où le Master Theorem ne s'applique pas, il faut considérer l'arbre des appels récursifs et l'analyser en détail. Un peu comme dans la preuve du théorème, mais en prenant bien sûr en compte les facteurs qui ont fait qu'il ne s'appliquait pas.  Interprétation des trois cas du Master Theorem Livrons nous maintenant à une petite interprétation de chacun des cas du Master Theorem afin de mieux en comprendre leur essence. Rappelons que le coût d'un niveau $j$ est proportionnel à $a^j\times {\left(\frac{n}{{}^{}}\right)}^d$, quantité que l'on peut mettre sous la forme $n^d\times {\left(\frac{a}{{}^{}}\right)}^j$. La constante $a$ peut être vue comme la vitesse de prolifération des sous-problèmes, et le terme $b^d$ comme la vitesse de diminition du coût de traitement par sous-problème. Le fait que l'une de ces vitesses prenne le pas sur l'autre ou au contraire qu'elles se compensent expliquera la complexité finale. Voici les trois situations possibles : Cas où $a<b^d$ : le coût d’un niveau est une fonction décroissante de $j$. Moralement la complexité sera essentiellement celle de l’appel initial donc en $n^d$. Cas où $a=b^d$ : le coût d’un niveau est une fonction constante de $j$ et vaut $n^d$. La complexité sera alors égale à $n^d$ multiplié par le nombre de niveau qui est $\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(n\right)$. Cas où $a>b^d$ : le coût d’un niveau est une fonction croissante de $j$. Moralement la complexité sera essentiellement celle due aux appels finaux. Elle sera donc de l’ordre du nombre de feuilles de l’arbre des appels récursifs, i.e. $n^{\mathrm{l}\mathrm{o}{\mathrm{g}}_b\left(a\right)}$.  Le Master Theorem (cas général) Les notations et leur signification seront les mêmes que dans la version dite simple, mais les hypothèses seront moins restrictives, en particulier celles portant sur la complexité de la procédure de subdivision et combinaison. Nous présentons cette version du théorème par soucis de complétude, mais en général la précédente suffit. D'ailleurs nous n'en ferons pas de démonstration, les "nouveaux" arguments étant essentiellement mathématiques. Master Theorem Soient $a\ge 1$, $b>1$, et $T$ une fonction vérifiant $T\left(n\right)=aT\left(\frac{n}{b}\right)+f\left(n\right)$ Les différents paramètres s'interprètent comme suit : $n$ est la taille du problème. $a$ est le nombre de sous-problèmes. $n/b$ est le taille de chaque sous-problèmes. $f\left(n\right)$ est le coût de la subdivision et de la combinaison des solutions des sous-problèmes. Alors $T\left(n\right)=\{\begin{array}{cc}\Theta \left(f\left(n\right)\right)& \text{si}f\left(n\right)=\Omega \left(n^d\right)\text{avec}lo{g}_b\left(a\right)<d\text{et si}a\times f\left(\frac{n}{b}\right)\le c\times f\left(n\right)\text{avec}c<1\\ \Theta \left(n^{lo{g}_b\left(a\right)}log\left(n\right)\right)& \text{si}f\left(n\right)=\Theta \left(n^d\right)\text{avec}lo{g}_b\left(a\right)=d\\ \Theta \left(n^{lo{g}_b\left(a\right)}\right)& \text{si}f\left(n\right)=O\left(n^d\right)\text{avec}lo{g}_b\left(a\right)>d\end{array}$ On trouve ce théorème sous cette forme générale dans l'excellent livre de Thomas H. Cormen (1956-), Charles E. Leiserson (1953-), Ronald L. Rivest (1947-) et Clifford Stein (1965-), "Introduction to algorithms". Ne pas se fier au titre, ce livre est bien plus qu'une introduction, c'est une référence.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir

SUPINFO International University Ecole d'Informatique - IT School École Supérieure d'Informatique de Paris, leader en France La Grande Ecole de l'informatique, du numérique et du management Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I. SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels

• @SUPINFO
• Contact

• ACCUEIL
• CURSUS
• COURS
• ADMISSIONS
• CAMPUS
• DOCUMENTATION
• ANCIENS
• ENTREPRISES
• OPEN CAMPUS
• PUBLICATIONS

• Naviguer sur la page
• Récursivités simples
• Algorithmes de type "diviser pour régner"

Détails

Écrit par : Richard GAUTHIER

Création : 10 Juin 2020

Mis à jour : 10 Juin 2020

Clics : 2372

Détails

Écrit par : Richard GAUTHIER

Création : 7 Juin 2020

Mis à jour : 7 Juin 2020

Clics : 2297

En pratique

Étape 1 : mettez votre système à jour

Sur une distribution Debian ou Ubuntu récente, nous vous conseillons de réinstaller totalement votre serveur si cela est possible sur votre machine. Attention, cette action effacera totalement vos données.

Connectez-vous en SSH en tant qu’administrateur « root ». N’hésitez pas à vous reporter au guide SSH.

Une fois le système installé, il convient de le mettre à jour :

apt-get update && apt-get upgrade -y

Vous partez ainsi sur une base saine et totalement à jour.

Étape 2 : créez un nouvel utilisateur avec les privilèges « sudo »

Pour des raisons de sécurité et pour suivre les bonnes pratiques, il est préférable d’installer et gérer un serveur LAMP avec un utilisateur séparé, ne possédant pas les privilèges « root ». Si vous disposez déjà d’un utilisateur avec les privilèges « sudo », sans pour autant être « root », vous pouvez vous rendre directement à la deuxième étape. Ce type de fonctionnement est déjà en vigueur pour les dernières versions d’Ubuntu.

Dans le cas où vous ne possédez que l’utilisateur « root », il convient de créer un nouvel utilisateur :

adduser mynewuser

Diverses informations seront obligatoires, comme un mot de passe. D’autres seront optionnelles : le nom ou le numéro de téléphone, par exemple.

Il faut ensuite rajouter cet utilisateur au groupe « sudo » :

usermod -aG sudo mynewuser

Et enfin, connectez-vous sur ce nouveau compte utilisateur :

su - mynewuser

Étape 3 : installation du serveur web Apache 2

La première brique du stack LAMP, le système d’exploitation Linux, a été installée lors des étapes précédentes.

Nous allons installer ici la deuxième brique, le serveur web Apache 2, ainsi que sa documentation :

sudo apt-get install apache2 apache2-doc

Si l’installation s’est effectuée correctement, vous devriez pouvoir accéder à la page par défaut d’Apache en joignant l’adresse IP (ou le nom du service) de votre serveur dans le navigateur, comme suit : http://IP_du_serveur. N’essayez pas de vous connecter en HTTPS, car à ce stade aucun certificat SSL n’est encore installé.

Cette page est très instructive, et vous donnera un aperçu des fichiers de configuration d’Apache 2 et leur spécificités. N’hésitez pas à la parcourir.

Il est possible de vérifier que le service Apache fonctionne correctement en utilisant la commande suivante :

sudo service apache2 status

La mention active (running) doit apparaître.

La procédure Apache peut se gérer comme suit :

service apache2 start => permet de démarrer le service
service apache2 stop => permet d’arrêter le service
service apache2 restart => permet de relancer ou recharger le service

Étape 4 : installez PHP

Nous passons ensuite à l’installation de la troisième brique, le langage de programmation PHP.

Pour installer le paquet PHP, tapez cette commande :

sudo apt-get install php5-common libapache2-mod-php5 php5-cli

Pour tester l’installation, dans le répertoire /var/www/html, créez le fichier info.php avec le contenu suivant :

cd /var/www/html
sudo nano info.php

Insérez dedans :

<?php
phpinfo();
?>

Accédez ensuite au fichier via le navigateur : http://IP_du_serveur/info.php.

Vous devriez pouvoir visualiser une page détaillant toutes les spécificités de votre environnement PHP (version 7.0.30 dans notre cas) :

Une fois visualisé, nous vous recommandons vivement de supprimer le fichier index.php. En effet, il n’est jamais conseillé de donner publiquement des informations sur votre configuration.

Étape 5 : installez le système de base de données MySQL/MariaDB

Nous arrivons à la quatrième et dernière brique du stack LAMP, le système de bases de données.

Voici la commande à utiliser (votre mot de passe de compte utilisateur Linux vous sera demandé) :

sudo apt-get install mysql-server

Par défaut, le mot de passe administrateur MySQL/MariaDB sera le même que celui de votre utilisateur système. Pour personnaliser la sécurisation de votre base de données, voici la commande à effectuer :

mysql_secure_installation

Entrez votre mot de passe « root », puis changez le mot de passe :

Change the root password? [Y/n] => y
New password:

Désactivez ensuite les connexions anonymes :

Remove anonymous users? [Y/n] => y

Désactivez la connexion en « root » depuis une connexion distante :

Disallow root login remotely? [Y/n] => y

Il faut maintenant effacer la base de données de test créée par défaut :

Remove test database and access to it? [Y/n] => y

Il reste à charger les nouveaux paramètres :

Reload privilege tables now? [Y/n] => y

Pour tester l’accès à votre base de données, voici la commande à utiliser dans votre terminal :

mysql -u root -p

MariaDB [(none)]> show databases;
MariaDB [(none)]> exit

Nous vous conseillons de créer un utilisateur spécifique et dédié à votre applicatif web. Si besoin, référez-vous à la documentation officielle MySQL ou MariaDB.

Étape 6 : installez phpMyAdmin (optionnel)

L’installation du serveur LAMP est terminée ! Cette étape est optionnelle. L’interface open source phpMyAdmin va vous permettre de gérer plus facilement vos bases de données via une interface web.

Pour l’installer voici la commande à entrer :

sudo apt-get install phpmyadmin

Dans les choix proposés, sélectionnez un serveur web à reconfigurer automatiquement pour exécuter phpMyAdmin :

• cochez ()apache2, puis Entrée ;
• acceptez l’aide à la configuration, puis rentrez un mot de passe administrateur MySQL.

Afin d’accéder à l’interface de gestion de phpMyAdmin, vous devrez finaliser la configuration votre serveur Apache. Pour cela, éditez le fichier de configuration Apache :

sudo nano /etc/apache2/apache2.conf

À la fin du fichier, rajoutez :

# Include phpMyAdmin
Include /etc/phpmyadmin/apache.conf

Le service Apache doit ensuite être relancé grâce à cette commande :

sudo service apache2 restart

Afin de vous connecter, vous devrez au préalable créer un utilisateur possédant les droits administrateur pour phpMyAdmin :

mysql -u root -p
[mot de passe]
MariaDB [(none)]> CREATE USER 'my_user'@'localhost' IDENTIFIED BY 'my_password';
MariaDB [(none)]> GRANT ALL PRIVILEGES ON * . * TO 'my_user'@'localhost';
MariaDB [(none)]> FLUSH PRIVILEGES;

Accédez ensuite à l’interface via http://IP_du_serveur/phpmyadmin/ :

Étape 7 : installez WordPress (optionnel)

Cette partie est elle aussi optionnelle. Voici brièvement les étapes pour installer ce CMS :

Téléchargez, décompressez et copiez le contenu dans un nouveau dossier appelé mywebsite:

wget https://wordpress.org/latest.tar.gz
tar xpf latest.tar.gz
sudo cp -r wordpress /var/www/html/mywebsite

Ce dossier contenant WordPress est maintenant accessible sur http://IP_du_serveur/mywebsite/.

Créez une base nommée wordpress en ligne de commande ou via phpMyAdmin.

Votre écran de configuration doit ressembler à celui ci-dessous :

Si vous avez un avertissement au niveau de la création du fichier wp-config.php, éditez les droits en exécution, lecture, écriture en fonction de vos besoins (communément appelés CHMOD).

Conclusion

Voilà, le CMS WordPress est installé et est propulsé par votre stack LAMP installé dans ce tutoriel !

Nous venons d’installer un serveur LAMP en partant de zéro, vous permettant ainsi d’héberger vous-même vos sites et applications web. En réalisant cette installation par vos propres moyens, vous gardez une liberté de configuration totale. N’hésitez pas à lire la documentation officielle d’Apache pour en découvrir toutes les possibilités.

Si vous désirez aller plus loin ou que vous êtes curieux, sachez qu’il existe des alternatives à Apache : la plus connue au succès grandissant étant NGNIX (prononcez « engine-x »). Un stack incluant NGINX est appelé LEMP, et est souvent réputé pour être plus léger. Nous vous conseillons enfin de sécuriser votre site avec un certificat SSL.

Step 1: Connect to your server via SSH and update your server OS packages

Before we begin, let’s connect to your VPS via SSH as user root and update your Ubuntu OS packages to the latest available version.

To connect to your server via SSH as user root, use the following command:

ssh root@IP_ADDRESS -p PORT_NUMBER

Replace “IP_ADDRESS” and “PORT_NUMBER” with your actual server IP address and SSH port number.

Once logged in, make sure that your server OS packages are up-to-date by running the following commands:

apt-get update
apt-get upgrade

If this is your first time logging into your brand new Ubuntu VPS, you can also check our First Steps After Getting An Ubuntu VPS tutorial for some additional basic initial server setup and security tips.

Step 2: Install a Web Server

In this section, we will show you how to install a web server on your VPS. We can install Apache, or nginx as a web server. For the purpose of this tutorial, we will install the Apache web server. Apache is a fast and secure web server and one of the most popular and widely used web server in the world.

To install the Apache web server, run the following command on your server:

apt-get install apache2

After the installation is complete, you should start Apache:

systemctl start apache2

Also, you can enable Apache to start automatically on server boot:

systemctl enable apache2

To check the status of the Apache web server and make sure it is up and running, you can use the following command:

systemctl status apache2

To verify that Apache is running, you can also open your web browser and enter your server IP address, (e.g. http://your_server_ip_address). If Apache is successfully installed, you should see the Apache default welcome page.

Step 3: Install Ondřej Surý’s PPA

PHP 7.2 can be installed using Ondřej Surý’s PPA, so install the software-properties-common and python-software-properties packages:

sudo apt-get install software-properties-common python-software-properties

Then, add the ondrej PPA and update your sources:

sudo add-apt-repository -y ppa:ondrej/php
sudo apt-get update

Step 4: Install PHP 7.2

Install PHP 7.2 using the following command:

sudo apt-get install php7.2 php7.2-cli php7.2-common

Step 5: Search and install specific PHP 7.2 extensions

If you want to install a specific PHP 7.2 extension, you can search if it is available using the following command:

sudo apt search php7.2

Step 7: Install most commonly used PHP extensions

To install the most commonly used PHP extensions you can use the following command:

sudo apt-get install php7.2-curl php7.2-gd php7.2-json php7.2-mbstring php7.2-intl php7.2-mysql php7.2-xml php7.2-zip

Step 8: Check the PHP installation

Use the following command to check the PHP version installed on your server:

php -v

You should receive the following output:

PHP 7.2.9-1+ubuntu16.04.1+deb.sury.org+1 (cli) (built: Aug 19 2018 07:16:12) ( NTS )
Copyright (c) 1997-2018 The PHP Group
Zend Engine v3.2.0, Copyright (c) 1998-2018 Zend Technologies
    with Zend OPcache v7.2.9-1+ubuntu16.04.1+deb.sury.org+1, Copyright (c) 1999-2018, by Zend Technologies

Now, PHP 7.2 has been installed on your Ubuntu server, and if we want to change the default PHP version to PHP 7.2 that is used by the web server, we need to disable the old PHP 7.0 version and enable the newly installed one.

Disable PHP 7.0

a2dismod php7.0

Enable PHP 7.2

a2enmod php7.2

Restart the Apache web server for the changes to take effect:

systemctl restart apache2

To test your installation and check that Apache, PHP and PHP extensions are working properly, create a new php info file:

vi /var/www/html/phpinfo.php

Add the following content to it:

<?php phpinfo(); ?>

Open the ‘phpinfo.php’ file using a web browser:

http://<ip-address>/phpinfo.php or http://<your-domain.com>/phpinfo.php

and view the current information about PHP on your server.
That’s it. You have successfully installed PHP 7.2 on an Ubuntu 16.04 server. For more information about PHP 7, please refer to the official PHP documentation.

Sources :

https://docs.ovh.com/fr/dedicated/installer-lamp-debian-ubuntu/

https://www.rosehosting.com/blog/how-to-install-php-7-2-on-ubuntu-16-04/

Détails

Écrit par : Richard GAUTHIER

Création : 5 Juin 2020

Mis à jour : 5 Juin 2020

Clics : 1804

Write a Python program to check that a string contains only a certain set of characters (in this case a-z, A-Z and 0-9). Go to the editor

Click me to see the solution

Write a Python program that matches a string that has an a followed by one or more b's. Go to the editor

Click me to see the solution

Write a Python program that matches a string that has an a followed by three 'b'. Go to the editor

Click me to see the solution

Write a Python program to find sequences of lowercase letters joined with a underscore. Go to the editor

Click me to see the solution

Write a Python program that matches a word at the end of string, with optional punctuation. Go to the editor

Click me to see the solution

Write a Python program where a string will start with a specific number. Go to the editor

Click me to see the solution

Write a Python program to search a literals string in a string and also find the location within the original string where the pattern occurs. Go to the editor

Sample text : 'The quick brown fox jumps over the lazy dog.'
Searched words : 'fox'

Click me to see the solution

Write a Python program to remove all whitespaces from a string. Go to the editor

Click me to see the solutio

Write a Python program to remove the parenthesis area in a string. Go to the editor
Sample data : [\"example (.com)\", \"w3resource\", \"github (.com)\", \"stackoverflow (.com)\"]
Expected Output:
example
w3resource
github
stackoverflow
Click me to see the solution

Détails

Écrit par : Richard GAUTHIER

Création : 25 Mai 2020

Mis à jour : 25 Mai 2020

Clics : 1535