[[{"quiz":976}]]

Détails

Écrit par : Richard GAUTHIER

Création : 17 Juin 2020

Mis à jour : 24 Juin 2020

Clics : 1206

[[{"text":"Afin de vérifier vos acquis, répondez aux questions suivantes.","posi":0}],[{"text":" En hexadécimal (base 16), quelle est la valeur de la différence CBD - BAC ? ","theme":"A","nume":"1","sujet":1,"annee":2020,"posi":3},{"radio":[{"label":" AB "},{"label":" TB "},{"label":" FF "},{"label":" 111 ","sol":true}]}],[{"text":" Deux entiers positifs ont pour écriture en base 16 : A7 et 84. Quelle est l'écriture en base 16 de leur somme ? ","theme":"A","nume":"2","sujet":1,"annee":2020},{"radio":[{"label":" 1811 "},{"label":" 12B ","sol":true},{"label":" 13A "},{"label":" A784 "}]}],[{"text":" Quelle est l'écriture binaire, en complément à deux sur 8 bits, de l'entier négatif 7 ? ","theme":"A","nume":"3","sujet":1,"annee":2020},{"radio":[{"label":" - 0000 0111 "},{"label":" 1000 0111 "},{"label":" 1111 1000 "},{"label":" 1111 1001 ","sol":true}]}],[{"text":"","theme":"A","nume":"4","sujet":1,"annee":2020},{"radio":[{"label":"2¹⁵−1"},{"label":"2¹⁵"},{"label":"2¹⁶−1","sol":true},{"label":"2¹⁶","sol":false}]}],[{"text":"","theme":"A","nume":"5","sujet":1,"annee":2020},{"radio":[{"label":"8"},{"label":"16","sol":true},{"label":"32","sol":false},{"label":"64","sol":false}]}],[{"text":"","theme":"A","nume":"6","sujet":1,"annee":2020},{"radio":[{"label":"6×𝑁"},{"label":"8×𝑁","sol":true},{"label":"1000×𝑁","sol":false},{"label":"aucune des réponses précédentes","sol":false}]}],[{"text":"On veut affecter à t la valeur [[0,1,2], [3,4,5], [6,7,8], [9,10,11], [12,13,14]].","theme":"B","nume":"1","sujet":1,"annee":2020},{"radio":[{"label":" i*j + j "},{"label":" p*i + j "},{"label":" p*j + i ","sol":true},{"label":" i*(j+1) "}]}],[{"text":"","theme":"B","nume":"2","sujet":1,"annee":2020},{"radio":[{"label":" [2, 13, 9, 2] "},{"label":" [2, 8, 14, 2] ","sol":true},{"label":" [7, 13, 14, 7] "},{"label":" [7, 13, 9, 2] "}]}],[{"text":"","theme":"B","nume":"3","sujet":1,"annee":2020},{"radio":[{"label":"le mois le plus froid"},{"label":"le mois le plus chaud"},{"label":"la température moyenne la plus basse"},{"label":"la température moyenne la plus haute","sol":true}]}],[{"text":" Quelle est la valeur de la variable r à la fin de l'exécution du script suivant ? ","theme":"B","nume":"4","sujet":1,"annee":2020},{"radio":[{"label":" -9 "},{"label":" 2 "},{"label":" 3 "},{"label":" 6 ","sol":true}]}],[{"text":" On définit un dictionnaire : d = { 'couleur': 'vert', 'taille': 42, 'marque': 'le coq sportif' } Quelle est la valeur de l'expression d.keys() ? ","theme":"B","nume":"5","sujet":1,"annee":2020},{"radio":[{"label":" ['couleur', 'taille', 'marque'] ","sol":true},{"label":" [('couleur', 'vert'), ('taille', 42), ('marque', 'le coq sportif')] "},{"label":" ['vert', 42, 'le coq sportif'] "},{"label":" ['couleur': 'vert', 'taille': 42, 'marque': 'le coq sportif'] "}]}],[{"text":"","theme":"B","nume":"6","sujet":1,"annee":2020},{"radio":[{"label":"4","sol":false},{"label":"25"},{"label":"10","sol":true},{"label":"9"}]}],[{"text":"","theme":"C","nume":"1","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":""},{"label":"","sol":true}]}],[{"text":"","theme":"C","nume":"2","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":"","sol":true},{"label":""},{"label":"","sol":false}]}],[{"text":"","theme":"C","nume":"3","sujet":1,"annee":2020},{"radio":[{"label":"[‘Grace’, ‘Ada’]
"},{"label":""},{"label":"","sol":true},{"label":"","sol":false}]}],[{"text":"","theme":"C","nume":"4","sujet":1,"annee":2020},{"radio":[{"label":" tableau[4][1] "},{"label":" tableau[1][4] "},{"label":" tableau[3][0] ","sol":true},{"label":" tableau[0][3] "}]}],[{"text":" Quelle est la valeur de la variable table à la fin de l'exécution du script suivant :","theme":"C","nume":"5","sujet":1,"annee":2020},{"radio":[{"label":" [[1, 5, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]] "},{"label":" [[1, 2, 3], [5, 2, 3], [1, 2, 3], [1, 2, 3]] "},{"label":" [[1, 2, 3], [1, 2, 5], [1, 2, 3], [1, 2, 3]] ","sol":true},{"label":" [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 5, 3]] "}]}],[{"text":"","theme":"C","nume":"6","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":"","sol":true},{"label":""}]}],[{"text":" Dans une page HTML, lequel de ces codes permet la présence d'un bouton qui appelle la fonction javascript afficher_reponse() lorsque l'utilisateur clique dessus ? ","theme":"D","nume":"1","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":""},{"label":"","sol":true}]}],[{"text":"","theme":"D","nume":"2","sujet":1,"annee":2020},{"radio":[{"label":" JavaScript "},{"label":" HTML "},{"label":" CSS "},{"label":" PHP ","sol":true}]}],[{"text":" En HTML, un formulaire commence par quelle balise ? ","theme":"D","nume":"3","sujet":1,"annee":2020},{"radio":[{"label":"","sol":true},{"label":""},{"label":""},{"label":" "}]}],[{"text":"","theme":"D","nume":"4","sujet":1,"annee":2020},{"radio":[{"label":" des bornes "},{"label":" des balises ","sol":true},{"label":" des paragraphes "},{"label":" des liens "}]}],[{"text":"","theme":"D","nume":"5","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":"","sol":false},{"label":""},{"label":"","sol":true}]}],[{"text":"","theme":"D","nume":"6","sujet":1,"annee":2020},{"radio":[{"label":"","sol":true},{"label":"","sol":false},{"label":"","sol":false},{"label":""}]}],[{"text":"","theme":"E","nume":"1","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":""},{"label":"","sol":true}]}],[{"text":"","theme":"E","nume":"2","sujet":1,"annee":2020},{"radio":[{"label":"","sol":true},{"label":""},{"label":""},{"label":""}]}],[{"text":" À partir du dossier ~/Doc/QCM, quelle commande permet de rejoindre le dossier ~/Hack/Reponses ? ","theme":"E","nume":"3","sujet":1,"annee":2020},{"radio":[{"label":" cd Hack/Reponses "},{"label":" cd /Hack/Reponses "},{"label":" cd /~/Hack/Reponses ","sol":false},{"label":" cd ../../Hack/Reponses ","sol":true}]}],[{"text":"","theme":"E","nume":"4","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":"","sol":true},{"label":""},{"label":""}]}],[{"text":"","theme":"E","nume":"5","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":"","sol":true},{"label":""},{"label":""}]}],[{"text":"","theme":"E","nume":"6","sujet":1,"annee":2020},{"radio":[{"label":"","sol":false},{"label":""},{"label":"","sol":true},{"label":""}]}],[{"text":" Quel est le seul langage de programmation parmi les propositions suivantes ? ","theme":"F","nume":"1","sujet":1,"annee":2020},{"radio":[{"label":" HTML "},{"label":" CSS "},{"label":" C++ ","sol":true},{"label":" WEB "}]}],[{"text":"","theme":"F","nume":"2","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":""},{"label":"","sol":true}]}],[{"text":"","theme":"F","nume":"3","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":""},{"label":"","sol":true}]}],[{"text":"","theme":"F","nume":"4","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":""},{"label":"","sol":true}]}],[{"text":"","theme":"F","nume":"5","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":"","sol":true},{"label":""}]}],[{"text":"","theme":"F","nume":"6","sujet":1,"annee":2020},{"radio":[{"label":""},{"label":""},{"label":""},{"label":"","sol":true}]}],[{"text":" Pour pouvoir utiliser un algorithme de recherche par dichotomie dans une liste, quelle précondition doit être vraie ? ","theme":"G","nume":"1","sujet":1,"annee":2020},{"radio":[{"label":" la liste doit être triée ","sol":true},{"label":" la liste ne doit pas comporter de doublons "},{"label":" la liste doit comporter uniquement des entiers positifs "},{"label":" la liste doit être de longueur inférieure à 1024 "}]}],[{"text":" On exécute le script suivant : ","theme":"G","nume":"2","sujet":1,"annee":2020},{"radio":[{"label":" "},{"label":" "},{"label":" ","sol":true},{"label":" "}]}],[{"text":"","theme":"G","nume":"3","sujet":1,"annee":2020},{"radio":[{"label":" "},{"label":" "},{"label":" ","sol":true},{"label":" "}]}],[{"text":"","theme":"G","nume":"4","sujet":1,"annee":2020},{"radio":[{"label":" for i in range(n//2): "},{"label":" for i in range(n): ","sol":true},{"label":" L = [ i+j for i in range(n) for j in range(n) ]  "},{"label":" for i in range(n//2): "}]}],[{"text":"","theme":"G","nume":"5","sujet":1,"annee":2020},{"radio":[{"label":" 10 "},{"label":" 45 ","sol":true},{"label":" 55 "},{"label":" 100 ","sol":false}]}],[{"text":" Pour rendre la monnaie, il est possible d'utiliser un algorithme glouton. Une seule des affirmations suivantes est vraie : ","theme":"G","nume":"6","sujet":1,"annee":2020},{"radio":[{"label":" Avec un algorithme glouton, on rend la monnaie en commençant toujours par la pièce ayant la plus grande valeur possible et en procédant ensuite par valeurs décroissantes. ","sol":true},{"label":" Avec un algorithme glouton, on rend la monnaie en commençant toujours par la pièce de plus petite valeur afin de maximiser le nombre de pièces rendues. "},{"label":" Quel que soit le type de pièces dans un pays donné, un algorithme glouton donne toujours la monnaie de manière optimale. "},{"label":" Un algorithme glouton procède en testant toutes les combinaisons possibles de pièces afin de trouver le rendu optimal. "}]}]]

Détails

Écrit par : Richard GAUTHIER

Création : 16 Juin 2020

Mis à jour : 19 Juin 2020

Clics : 2205

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

Détails

Écrit par : Richard GAUTHIER

Création : 10 Juin 2020

Mis à jour : 10 Juin 2020

Clics : 2142

 

 

INTRODUCTION AUX INTERFACES « HOMME – MACHINE »

Détails

Écrit par : Richard GAUTHIER

Création : 7 Juin 2020

Mis à jour : 7 Juin 2020

Clics : 2152