Cours d'algorithmique

Résumé du document

Cours d'introduction à la programmation portant sur l'algorithmique. Une présentation très détaillée, de 98 diapositives, traitant en profondeur tous les aspects des algorithmes avec de bons exemples.

Extraits

[...] Il n'est pas difficile de voir que va représenter la complexité de Fibonacci(n-1) et celle de Fibonacci(n-2). Par ailleurs, la relation entre et est comme suit: = + si n > 1 = 1 (un seul test) = 2 tests) Pour résoudre cette équation (aux différences), on va procéder comme suit: Soit = Sum_{n=0}^{infini} t(n)x^n Il est facile de voir: Sum_{n>1} t(n)x^n = sum_{n>1} t(n-1)x^n + sum_{n>1}t(n-2)x^n Pour faire ressortir on fait comme suit: Sum_{n>1} t(n)x^n = sum_{n=0}^{infini} t(n)x^n - t(0)x^0 t(1)x^1 = Sum_{n>1} t(n-1)x^n = x sum_{n>1}^{infini} = x sum_{n>0}^{infini} = x sum_{n=0}^{infini} t(n)x^n = Sum_{n>1} t(n-2)x^n = x^2 sum_{n>1}^{infini} = x^2 sum_{n=0}^{infini} = x^2G(x) Par conséquent, on obtient: = xG(x) x x^2G(x) x = x 3 = x = Où a = (1+racine(5))/2 b = (1-racine(5))/2 On peut aussi mettre = + On obtient a = (1/(racine(5)) b = -(1/(racine(5)) = 1/(racine(5)(1/(x-a) Rappels de mathématiques: = sum_{n=0}^{infini} et = sum_{n=0}^{infini} Par conséquent: - = sum_{n=0}^{infini} Par conséquent, on obtient: 1/(racine(5))(sum_{n=0}^{infini} (rel1) Et nous avons aussi: = Sum_{n=0}^{infini} t(n)x^n (rel2) Par identification entre (rel1) et (rel2), on obtient: = 1/(racine(5)(a^n = = Cours d'Algorithmique :Introduction La question abordée dans ce chapitre est la suivante: Comment choisir parmi les différentes approches pour résoudre un problème? [...]

[...] Pour atteindre cet objectif, un algorithme utilise deux ressources d'une machine: le temps et l'espace mémoire. Définition la complexité temporelle d'un algorithme est le temps mis par ce dernier pour transformer les données du problème considéré en un ensemble de résultats. Définition la complexité spatiale d'un algorithme est l'espace utilisé par ce dernier pour transformer les données du problème considéré en un ensemble de résultats. Comparaison de solutions Pour comparer des solutions entre-elles, deux méthodes peuvent être utilisées: Méthode empirique Méthode mathématique Cette comparaison se fera, en ce qui nous concerne, relativement à deux ressources critiques: temps, espace mémoire Dans ce qui suit, nous allons nous concentrer beaucoup plus sur le temps d'exécution Facteurs affectant le temps d'exécution: 1. [...]

[...] algorithme de tri par insertion de tri rapide? , etc Pour comparer des solutions, plusieurs points peuvent être pris en considération Exactitude des programmes (démontrer que le résultat de l'implantation est celui escompté) Simplicité des programmes Convergence et stabilité des programmes (il est souhaitable que nos solutions convergent vers la solution exacte; la perturbation des données ne chamboule pas d'une manière drastique la solution obtenue) Efficacité des programmes (il est souhaitable que nos solutions ne soient pas lentes, ne prennent pas de l'espace mémoire considérable) Le point que nous allons développer dans ce chapitre est celui de l'efficacité des algorithmes. [...]

[...] Définition la complexité spatiale d'un algorithme est l'espace utilisé par ce dernier pour transformer les données du problème considéré en un ensemble de résultats. Comparaison de solutions Pour comparer des solutions entre-elles, deux méthodes peuvent être utilisées: Méthode empirique Méthode mathématique Cette comparaison se fera, en ce qui nous concerne, relativement à deux ressources critiques: temps, espace mémoire Dans ce qui suit, nous allons nous concentrer beaucoup plus sur le temps d'exécution Facteurs affectant le temps d'exécution: 1. machine langage programmeur compilateur algorithme et structure de données. [...]

[...] Il n'est pas difficile de voir que va représenter la complexité de Fibonacci(n-1) et celle de Fibonacci(n-2). Par ailleurs, la relation entre et est comme suit: = + si n > 1 = 1 (un seul test) = 2 tests) Pour résoudre cette équation (aux différences), on va procéder comme suit: Soit = Sum_{n=0}^{infini} t(n)x^n Il est facile de voir: Sum_{n>1} t(n)x^n = sum_{n>1} t(n-1)x^n + sum_{n>1}t(n-2)x^n Pour faire ressortir on fait comme suit: Sum_{n>1} t(n)x^n = sum_{n=0}^{infini} t(n)x^n - t(0)x^0 t(1)x^1 = Sum_{n>1} t(n-1)x^n = x sum_{n>1}^{infini} = x sum_{n>0}^{infini} = x sum_{n=0}^{infini} t(n)x^n = Sum_{n>1} t(n-2)x^n = x^2 sum_{n>1}^{infini} = x^2 sum_{n=0}^{infini} = x^2G(x) Par conséquent, on obtient: = xG(x) x x^2G(x) x = x 3 = x = Où a = (1+racine(5))/2 b = (1-racine(5))/2 On peut aussi mettre = + On obtient a = (1/(racine(5)) b = -(1/(racine(5)) = 1/(racine(5)(1/(x-a) Rappels de mathématiques: = sum_{n=0}^{infini} et = sum_{n=0}^{infini} Par conséquent: - = sum_{n=0}^{infini} Par conséquent, on obtient: 1/(racine(5))(sum_{n=0}^{infini} (rel1) Et nous avons aussi: = Sum_{n=0}^{infini} t(n)x^n (rel2) Par identification entre (rel1) et (rel2), on obtient: = 1/(racine(5)(a^n = = Cours d'Algorithmique :Introduction La question abordée dans ce chapitre est la suivante: Comment choisir parmi les différentes approches pour résoudre un problème? [...]