Introduction à l’algorithmique et à la programmation


Introduction à l’algorithmique et à la programmation

 

Introduction à l?algorithmique et à la programmation Antoine FRABOULET antoine.fraboulet@insa-lyon.fr INSA de Lyon, D´ epartement T´ el´ ecommunications, Services et Usages Introduction ` a l?algorithmique et ` a la programmation ? p. 1 Algorithmique ? Algorithmique : Science qui étudie l?application des algorithmes à l?informatique ? Algorithme : Suite finie, séquentielle de règles que l?on applique à un nombre fini de données, permettant de résoudre des classes de problèmes semblables. L?algorithme d?Euclide permet de trouver le P.G.C.D de deux nombre ? Calcul, enchaînement des actions nécessaires à l?accomplissement d?une tâche. Le Petit Robert Introduction ` a l?algorithmique et ` a la programmation ? p. 2 Pr´ esentation ? Introduction ? Bases de l?algotithmique ? Structure des données ? Structure des opérations ? Quelques méthodes de tri ? Gestion des listes Introduction ` a l?algorithmique et ` a la programmation ? p. 3 Introduction ? Un algorithme est motivé par la résolution d?une tâche ? méthode indépendante de la machine ? méthode indépendante du langage de programmation ? résolution structurée ? algorithme = description des étapes de la méthode utilisée Introduction ` a l?algorithmique et ` a la programmation ? p. 4 Algorithmique et programmation 1. Analyse du problème 2. Conception d?une solution : algorithmique choix de la représentation des données choix de la méthode utilisée 3. Développement : programmation choix du langage de programmation choix de la machine utilisée 4. Tests On ne s?intéressera donc ici qu?à la partie algorithmique, ou plutôt aux structures de données ainsi qu?aux opérations de calcul utilsées en algorithmique. Introduction ` a l?algorithmique et ` a la programmation ? p. 5 Quelques th` emes ? Tri : permet de réarranger et de classer des données. De nombreuses méthodes existent pour trier un ensemble, elles se différencient par la suite des étapes effectuées. ? Recherche : localiser des données dans un fichier. Les méthodes sont très variées et dépendent de l?organisation des données dans la mémoire. ? Traitement de chaines : manipulation de (longues) chaines de caractères. recherche de motifs dans des chaines (pattern matching), compression de fichiers, cryptographie. Introduction ` a l?algorithmique et ` a la programmation ? p. 6 Quelques th` emes (2) ? Algorithmes sur graphes : résolution de problèmes complexes pouvant être représentés par une structure de données particulière (par exemple le problème du voyageur de commerce). ? Algorithmes mathématiques : méthodes provenant de l?analyse numérique et de l?arithmétique. Problèmes traitant de l?arithmétique des entiers, des polynômes, des matrices. ? . . . Introduction ` a l?algorithmique et ` a la programmation ? p. 7 Bases de l?algorithmique Données ? variables ? structures ? tableaux ? pointeurs ? modèles dynamiques Calcul ? instructions ? conditions ? boucles ? fonctions ? récursion l?algorithmique c?est : le choix d?un algorithme le choix d?une structure de données les deux sont indissociables Introduction ` a l?algorithmique et ` a la programmation ? p. 8 Structures de donn´ ees Un algorithme manipule des données : ? Constante : nombres, chaînes de caractères ? 1, 2, 3, 4 . . . ? 3,1415 ? ?bonjour? ? Variable : nom d?une valeur en mémoire ? caractère ? entier ? nombre à virgule ? . . . Introduction ` a l?algorithmique et ` a la programmation ? p. 9 Structures de donn´ ees ? Variable = nom d?un espace en mémoire 1 octet caractère "C" entier "X" Introduction ` a l?algorithmique et ` a la programmation ? p. 10 Structures de donn´ ees : types de base Les donneés sont finies : elles ont donc une taille maximale. Par exemple, les tailles usuelles des variables en C sont les suivantes: nom taille (octets) min max "unsigned" caractère 1 (8 bits) ?128 127 255 short 2 (16 bits) ?32768 32767 65535 int 4 (32 bits) ?231 231 ? 1 232 ? 1 long 4 (32 bits) idem idem idem float 4 (32 bits) 1.17 ? 10?38 3.40 ? 10+38 double 8 (64 bits) 2.22 ? 10?308 1.79 ? 10+308 Introduction ` a l?algorithmique et ` a la programmation ? p. 11 Structures de donn´ ees ? Type construit : structure regroupant plusieurs variables. structure date = ( entier jour entier mois entier annee ) ... structure rendez vous = ( structure date date structure personne nom structure adresse lieu ) Introduction ` a l?algorithmique et ` a la programmation ? p. 12 Structures de donn´ ees ? Type structuré = création d?un nouveau type de variable = nom d?un espace en mémoire 1 octet caractère "C" entier "X" jour mois année date "t" Introduction ` a l?algorithmique et ` a la programmation ? p. 13 Types de base ? La contrusction de types peut être faite en combinant tous les types de base et les types déjà définis. ? L?utilisation se fait en utilisant le point ?.? structure date ( entier jour entier mois entier annee ) structure date t1,t2 t1.jour = 10 t1.mois = 5 t1.annee = 2008 ... t2 = t1 (copie de toute la structure = 3 variables) Introduction ` a l?algorithmique et ` a la programmation ? p. 14 Structures de donn´ ees : tableaux Collections de variables : ? Tableaux : structure permettant d?accéder de façon indépendante à un ensemble de variables de même type. entier t[12] tableau t contenant 12 entiers entier x x = t[5] copie du 6` eme élément de t dans la variable x t[6] = 42 modification du 7` eme élément ? Un tableau est de taille fixe et ses données son contiguës en mémoire. ? Attention : le premier élément d?un tableau est souvent numéroté 0 en informatique. Introduction ` a l?algorithmique et ` a la programmation ? p. 15 Structures de donn´ ees : tableaux (2) 4 octets tableau t[0] t[1] t[5] t[6] t[11] t Introduction ` a l?algorithmique et ` a la programmation ? p. 16 Bases de l?algorithmique ? Structures de données ? variables ? structures ? tableaux ? Structures de contrôle ? . . . Introduction ` a l?algorithmique et ` a la programmation ? p. 17 Structures de contr? ole Organisation des opérations : ? Opérations : + - * / = != . . . ? + ? ? / : opérations usuelles ? comparaisons sur les types simples ? opérateurs logiques (et, ou, négation) ? la priorité, l?associativité et la commutativité des opérations sont respectées ? Instructions simples et expressions ? x = 123 ? y = x+w*3 Introduction ` a l?algorithmique et ` a la programmation ? p. 18 Ex´ ecution conditionnelle ? Exécution conditionnelle : si [test est vrai] alors instructions sinon instructions fin si instruction ? Exemple : si a < b alors a = b sinon b = a finsi Introduction ` a l?algorithmique et ` a la programmation ? p. 19 ´ Ex´ ecution r´ ep´ etitive ? Boucle de répétition fixe: pour [ensemble de valeurs] faire instructions fin pour instruction ? Exemple : pour i=0 jusqu?` a i<12 faire afficher t[i] fin pour Introduction ` a l?algorithmique et ` a la programmation ? p. 20 ´ Ex´ ecution r´ ep´ etitive ? Boucle de répétition ?tant que?: tant que [test vrai] faire instructions fin tant que instruction ? Exemple : i = 0 tant que i < 12 faire afficher t[i] i = i + 1 fin tant que Introduction ` a l?algorithmique et ` a la programmation ? p. 21 Structure de contr? ole : fonctions Découpage d?un programme en blocs ou fonctions. ? Permet de regrouper et nommer un ensemble d?instructions. ? Permet d?utiliser des paramètres. ? Permet de réutiliser une même portion de programme depuis plusieurs endroits. ? Interface = paramètres et valeur renvoyée. ? La valeur renvoyée peut être ignorée si on ne l?utilise pas. ? passage des paramètres ? passage par valeur : seule la valeur de la variable est importante ? passage par adresse : la variable peut être modifiée par la fonction Introduction ` a l?algorithmique et ` a la programmation ? p. 22 Exemple de fonction entier TrouveMaximum(entier a, entier b) { entier m ( variable locale m ) si a < b alors m = b sinon m = a fin si renvoyer m } ... i = TrouveMaximum(1,100) j = TrouveMaximum(i,120) ... Introduction ` a l?algorithmique et ` a la programmation ? p. 23 Structure d?une fonction entier TrouverMaximum( entier a , entier b ) { entier m si a < b alors m = b sinon m = a fin si renvoyer m } Introduction ` a l?algorithmique et ` a la programmation ? p. 24 Fonctions r´ ecursives ? itérative : exécution répétitive sur des ensembles de données ? récursive : une fonction s?appelle elle même avec un ensemble de données à traiter plus petit entier f(entier n) { entier r si n = 0 alors r = 1 sinon r = n * f(n-1) fin si renvoyer r } Introduction ` a l?algorithmique et ` a la programmation ? p. 25 Structure d?un programme ? On peut utiliser une variable ou une fonction uniquement si elle est déjà définie dans le programme ? Visibilité des variables ? variables locales : internes à un bloc ? variables globales : visibles dans tout le programme ? Le déroulement d?un programme commence ? à la première instruction isolée ? en appelant une fonction dont le nom est fixé à l?avance Introduction ` a l?algorithmique et ` a la programmation ? p. 26 Bases de l?algorithmique ? Structures de données ? variables ? structures ? tableaux ? . . . ? Structures de contrôle ? instructions ? conditions ? boucles ? fonctions ? récursion ? Quelques méthodes de tri Introduction ` a l?algorithmique et ` a la programmation ? p. 27 Tri par s´ election ? on cherche l?élément de plus petite valeur dans le tableau ? le placer en tête du tableau ? recommencer avec le tableau moins la première case 14 3 2 9 5 3 2 5 9 14 3 2 14 9 5 3 2 14 9 5 3 2 14 5 9 Introduction ` a l?algorithmique et ` a la programmation ? p. 28 Tri par s´ election TriSelection(entier t[], entier taille) { entier i,j,min,tmp pour i=0 jusqu?` a j < taille-2 faire min = i pour j = i+1 jusqu?` a j < taille faire si t[j] < t[min] alors min = j fin si fin pour tmp = t[min] t[min] = t[i] t[i] = tmp fin pour } Introduction ` a l?algorithmique et ` a la programmation ? p. 29 Autres tris ? insertion : méthode utilisée pour trier une main de jeu de carte. On prend les cartes une par une de la gauche vers la droite. Pour chaque carte on la place au bon ordre parmi les précédentes. ? bulle : les éléments les plus petits se «déplacent» vers le début du tableau. Les éléments contiguës sont échangés 2 à 2. ? par segmentation (ou tris rapide) : faire 2 ensembles séparés par une valeur pivot. Tous les éléments inférieurs au pivot sont rangés à gauche, tous les éléments supérieurs à droite, puis trier les deux nouveaux tableaux de la même manière (on s?arrête lorsque les tableaux ont un seul élément). Introduction ` a l?algorithmique et ` a la programmation ? p. 30 Tri par insertion TriInsertion(entier t[], entier taille) { entier i,j,tmp pour i=0 jusqu?` a i<taille faire tmp = t[i] j = i tant que j>0 et t[j-1] > tmp faire t[j] = t[j-1] j = j-1 fin tant que t[j] = tmp fin pour } Introduction ` a l?algorithmique et ` a la programmation ? p. 31 Tri bulle TriBulle(entier t[], entier taille) { entier i,j,tmp pour i = taille jusqu?` a i>1 avec i = i-1 faire pour j = 1 jusqu?` a j<i faire si t[j-1] > t[j] alors tmp = t[j-1] t[j-1] = t[j] t[j] = tmp fin si fin pour fin pour } Introduction ` a l?algorithmique et ` a la programmation ? p. 32 Co? ut des algorithmes Plusieurs algorithmes peuvent faire la même chose mais en effectuant un nombre d?opérations différent. ? Différencier leurs coûts : ? coût en temps d?exécution ? coût en place mémoire ? nombre de transferts mémoire Le nombre d?étapes et la place mémoire dépendent le plus souvent de la taille des entrées de l?algorithme (la taille des tableaux par exemple). Introduction ` a l?algorithmique et ` a la programmation ? p. 33 Complexit´ e des algorithmes Tris par sélection : il y a 2 boucles imbriquées et le nombre d?opérations effectuées est proportionnel à n2 . On peut différencier l?analyse pour ? meilleur cas ? cas moyen ? pire cas Le tri par insertion a la même complexité dans les 3 cas mais pas le tris bulle dont la complexité peut varier. Introduction ` a l?algorithmique et ` a la programmation ? p. 34 Diff´ erentes complexit´ e 0 50 100 150 200 250 300 350 400 0 5 10 15 20 x log(x) x*log(x) x*x x*x*x exp(x) Introduction ` a l?algorithmique et ` a la programmation ? p. 35 Comparaison des ordres de grandeur ? taille du problème / temps d?exécution taille du problème : n 2 24 26 28 ln ln n 0 2 2.58 3 ln n 1 4 6 8 n 2 16 64 256 n ln n 2 64 384 2 048 n2 4 256 4096 65 536 2n 4 65 536 1.84e+19 1.15e+77 n! 2 2.09e+13 1.26e+89 8.57e+506 Introduction ` a l?algorithmique et ` a la programmation ? p. 36 Algorithmique pratique ? L?algorithme reste le même quel que soit la nature des données à traiter. ? Les modifications sont à faire dans des points très précis : ceux où l?on regarde le contenu des données. ? Pour changer le type des tableaux que nous savons pour l?instant trier et avoir, par exemple, des tableaux de carte de visite il suffit de changer les endroits où l?on compare les éléments des tableaux. Introduction ` a l?algorithmique et ` a la programmation ? p. 37 Les tris externes ? On peut vouloir avoir simultanément plusieurs classements sur un même ensemble de données (par nom, par ville, par date pour des rendez vous par exemple) ? On peut également vouloir avoir l?ordre des éléments d?un ensemble sans les changer de place ? Utilisation d?index pour avoir des classements sans modifier les données. Introduction ` a l?algorithmique et ` a la programmation ? p. 38 Bases de l?algorithmique ? Structures de données ? variables ? structures ? tableaux ? pointeurs Introduction ` a l?algorithmique et ` a la programmation ? p. 39 Pointeurs ? Un pointeur est une variable contenant une adresse ? Les pointeurs permettent de manipuler des objets sans avoir à les nommer (comme les tableaux !). Mais on peut allouer dynamiquement les de nouvelles variables. ? Les pointeurs peuvent être construits à partir de n?importe quel type entier *pi : pi contient l?adresse d?un entier structure date *t : t contient l?adresse d?une date ? On peut obtenir l?addresse d?un objet avec l?opérateur & entier i entier *pi = &i i = 3 (*pi) = 4 : i est ´ egal ` a 4 Introduction ` a l?algorithmique et ` a la programmation ? p. 40 Mod` eles de donn´ ees dynamiques ? Structures dynamiques : Arbres, listes chaînées, piles, files . . . structures dynamiques dont la taille peut varier au cours de l?exécution du programme. L?accès aux informations stockées dépend de la structure. Ce type de structure utilise des pointeurs structure elmt liste { int valeur; structure elmt liste* suivant; } Introduction ` a l?algorithmique et ` a la programmation ? p. 41 Structures de donn´ ees : liste (2) 4 octets Liste chaînée L L Introduction ` a l?algorithmique et ` a la programmation ? p. 42 Structures de donn´ ees: liste (3) 4 octets Liste chaînée L L ajout d?un élément Introduction ` a l?algorithmique et ` a la programmation ? p. 43 Structures de donn´ ees ? Choix de manipulation des structures ? Listes ? Piles (Last In First Out) ? Files (First In First Out) Introduction ` a l?algorithmique et ` a la programmation ? p. 44 Structures de donn´ ees : Piles Pile ? ajouter toujours au sommet ? seul le sommet est visible ? retirer toujours au sommet Introduction ` a l?algorithmique et ` a la programmation ? p. 45 Structures de donn´ ees : Files Pile ? ajouter toujours au sommet ? seul le dernier est visible ? retirer toujours à la fin ? on peut garder un pointeur sur la fin pour être plus efficace Introduction ` a l?algorithmique et ` a la programmation ? p. 46 Structures de donn´ ees Pile Arbre Introduction ` a l?algorithmique et ` a la programmation ? p. 47 Conclusion ? données ? variables ? structures ? tableaux ? pointeurs ? modèles dynamiques ? calcul ? instructions ? conditions ? boucles ? fonctions ? récursion l?algorithmique c?est : le choix d?un algorithme le choix d?une structure de données les deux sont indissociables Introduction ` a l?algorithmique et ` a la programmation ? p. 48 Conclusion ? Dans un programme de grande taille le temps d?exécution est dominé par un poignée d?algorithmes ? Beaucoup de programmes sont sur-optimisés. Il n?est pas indispensable de trouver tout le temps le «meilleur» algorithme partout, sauf si ces derniers sont des tâches conséquentes ou très répétitives. ? Un mauvais choix d?algorithme pour une partie critique peut rendre le programme entier inutilisable. Introduction ` a l?algorithmique et ` a la programmation ? p. 49 Quelques livres ? Initiation à l?algorithmique et aux structures de données, Courtin & Kowarski, Dunod, 1989 ? Introduction à l?algorithmique, Cormen, Leiserson & Rivest, Dunod, 1994 ? Algorithmes en langage C, Sedgewick, InterEditions, 1991 Introduction ` a l?algorithmique et ` a la programmation ? p. 50

PARTAGER SUR

Envoyer le lien par email
1721
READS
4
DOWN
7
FOLLOW
4
EMBED
DOCUMENT # TAGS
#algorithme  #maths 

licence non indiquée


DOCUMENT # INDEX
Mathematiques, Sciences 
img

Partagé par  macuche

 Suivre

Auteur:fraboulet
Source:INSA de Lyon