Chapitre 1: Introduction à l'algorithmique

1 Chapitre 1: Introduction a l'algorithmique Brice Mayag M1 SIEE. Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 1 / 59. Sommaire 1 Pre sentation du cours 2 Introduction et de finitions Pourquoi l'e tude des algorithmes ? De finitions 3 Paradigmes et langages de programmation 4 Fondements des langages : la re cursivite . Algorithmes re cursifs 5 Le langage python Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 2 / 59. Pre sentation du cours Sommaire 1 Pre sentation du cours 2 Introduction et de finitions Pourquoi l'e tude des algorithmes ? De finitions 3 Paradigmes et langages de programmation 4 Fondements des langages : la re cursivite . Algorithmes re cursifs 5 Le langage python Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 3 / 59.

2 Pre sentation du cours Programme du cours Les grandes notions Les bases de l'algorithmique La re cursivite et le paradigme Diviser pour Re gner Structures de donne es basiques et avance es : listes, files, piles, tas, arbres de recherche Application au filtrage collaboratif E valuation Examen Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 4 / 59. Introduction et de finitions Sommaire 1 Pre sentation du cours 2 Introduction et de finitions Pourquoi l'e tude des algorithmes ? De finitions 3 Paradigmes et langages de programmation 4 Fondements des langages : la re cursivite . Algorithmes re cursifs 5 Le langage python Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 5 / 59.

3 Introduction et de finitions Pourquoi l'e tude des algorithmes ? l'algorithmique ? De finition (informelle). Un algorithme est la composition d'un ensemble fini d'e tapes, chaque e tape e tant forme e d'un nombre fini d'ope rations dont chacune est : de finie de fac on rigoureuse et non ambigue ;. effective ( pouvant e tre re alise e en un temps fini). La notion d'algorithme est plus ge ne rale que celle de programme (inde pendant du langage de programmation utilise ). Un peu d'histoire Le mot algorithme vient du nom du mathe maticien Al Khwarizmi (820) : Introduction de la nume rotation de cimale et des calculs s'y rapportant. Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 6 / 59.

4 Introduction et de finitions Pourquoi l'e tude des algorithmes ? Des besoins contradictoires Un algorithme doit : e tre simple a comprendre, a mettre en oeuvre et a mettre au point ;. mettre intelligement a contribution les ressources de l'ordinateur, et plus pre cise ment, il doit s'exe cuter rapidement. Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 7 / 59. Introduction et de finitions De finitions Un algorithme : c'est quoi ? Classiquement assimilable a une recette de cuisine Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 8 / 59. Introduction et de finitions De finitions Algorithme : de finitions Un algorithme =. Description pre cise des ope rations a faire pour re soudre un proble me (suite d'instructions).

5 Proce dure de calcul bien de finie qui prend en entre e une valeur, ou un ensemble de valeurs et qui donne en sortie une valeur, ou un ensemble de valeurs. Un bon algorithme =. Un algorithme correct : pour chaque instance en entre e, l'algorithme se termine en produisant la bonne sortie Savoir prouver un algorithme Un algorithme efficace : mesure de la dure e que met un algorithme pour produire un re sultat Savoir analyser la complexite d'un algorithme : de termination de l'espace me moire et du temps d'exe cution ne ce ssaire a la re solution du proble me. Pour un proble me donne , plusieurs algorithmes ou aucun sont possibles. Un algorithme se termine en un temps fini. Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 9 / 59.

6 Introduction et de finitions De finitions Un exemple simple Proble me de tri Donne es : une suite de n nombres, (e0 , e1 , .., en 1 ). 0 0 0. Re sultat : permutation de la suite donne e en entre e (e0 , e1 , .., en 1 ). 0 0 0. de telle sorte que e0 e1 .. en 1. Principe du tri par insertion On parcourt entie rement la liste en appliquant a chaque ite ration la strate gie suivante : Recherche de la place du ie me e le ment Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 10 / 59. Introduction et de finitions De finitions Tri par insertion Principe On veut trier la liste : 3 2 7 1 5. 1 On part du constat que liste[ ] est trie e 3 2 7 1 5. 2 On met l'e le ment d'indice 1 a sa place dans la liste[ ].

7 2 3 7 1 5. 3 liste[ ] est maintenant trie e. On recommence a l'e tape 2 avec l'e le ment suivant. Exemple : Trier la liste de nombres [65; 15; 34; 3; 25; 22; 63; 3; 66; 17].. Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 11 / 59. Introduction et de finitions De finitions Un algorithme simple Conside rons un tableau A contenant une se quence a trier de longueur n Algorithm 1 TRI-INSERTION (A). 1: for j 2 to n do 2: key A[j]. 3: i j 1. 4: while i > 0 and A[i] > key do 5: A[i + 1] A[i]. 6: i i 1. 7: end while 8: A[i + 1] key 9: end for On verra comment implanter cet algorithme en python Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 12 / 59. Introduction et de finitions De finitions Analyse d'un algorithme Simplicite et intelligibilite de l'algorithme Efficacite de l'algorithme : Temps d'exe cution Occupation de la me moire Quantite de trafic ge ne re sur un re seau Quantite de donne es de place es sur le disque.

8 Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 13 / 59. Introduction et de finitions De finitions Complexite d'un algorithme Permet de quantifier les algorithmes Deux types de comple xite : En espace : Quelle quantite de place en me moire va t-on utiliser ? En temps : Combien d'ope rations va t-on effectuer ? Inte re t : comparer deux algorithmes Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 14 / 59. Introduction et de finitions De finitions Mesurer le temps d'exe cution Le temps d'exe cution de pend de l'entre e : par exemple dans le cas d'un algorithme de tri, si le tableau est de ja trie . On cherche une fonction T (n) repre sentant le temps d'exe cution d'un algorithme en fonction de la taille de l'entre e n (nombre d'e lements constituant l'entre e, nombre de bits ne ce ssaire a la repre sentation de l'entre e.)

9 Le calcul exact e tant souvent impossible a appre hender exactement, on s'inte resse aux : Meilleur des cas Pire de cas Cas moyen : ne ce ssite d'avoir des connaissances sur la distribution statistique des entre es Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 15 / 59. Introduction et de finitions De finitions Mesurer le temps d'exe cution Cas du tri par insertion Algorithm 2 TRI-INSERTION (A). 1: for j 2 to n do 2: key A[j]. 3: i j 1. 4: while i > 0 and A[i] > key do 5: A[i + 1] A[i]. 6: i i 1. 7: end while 8: A[i + 1] key 9: end for Soit ci , le cou t temporel de chaque instruction. On P a alors : T (n) = c1 n+c2 (n 1)+c3 (n 1)+c4 nj=2 tj +c5 nj=2 (tj 1)+c6 nj=2 (tj 1)+c7 (n 1).

10 P P. tj nombre de fois que le test de la boucle While est exe cute e pour cette valeur de j Brice Mayag Chapitre 1: Introduction a l'algorithmique M1 SIEE 16 / 59. Introduction et de finitions De finitions Mesurer le temps d'exe cution Cas du tri par insertion Cas le plus favorable : le tableau est de ja trie et donc pour tout j = on a tj = 1. Temps d'exe cution : T (n) = (c1 + c2 + c3 + c4 + c7 )n (c2 + c3 + c4 + c7 ). Temps sous la forme an + b : fonction line aire de n. Cas le plus de favorable : la tableau est trie dans l'ordre de croissant donc tj = j pour tout j = Temps d'exe cution : T (n) = c1 n + c2 (n 1) + c3 (n 1) +. c4 ( n(n+1). 2 1) + c5 ( n(n 1). 2 ) + c6 ( n(n 1). 2 ) + c7 (n 1).