Rappels de langage C
Pointeurs typés Présentation
A une variable correspond un emplacement mémoire caractérisé par une adresse et une longueur (par exemple 4 octets consécutifs pour un long int). C’est, bien sur, le compilateur qui assure la gestion de la mémoire et affecte à chaque variable un emplacement déterminé. On peut accéder à la valeur de cette adresse grâce à l’opérateur unaire &, dit opérateur d’adressage.
Un pointeur est une variable d’un type spécial qui pourra contenir l’adresse d’une autre variable. On dit qu’il pointe vers cette variable. Celui-ci devra aussi connaître le type de la variable vers laquelle il pointe puisque la taille d’une variable (en octets) dépend de son type. La déclaration d’un pointeur devra donc indiquer le type d’objet vers lequel il pointe (on dit d’un pointeur qu’il est typé). La syntaxe est la suivante: type *identificateur;
La déclaration d’un tableau réserve de la place en mémoire pour les éléments du tableau et fournit une constante de type pointeur qui contient l’adresse du premier élément du tableau. Cette constante est identifiée par l’identificateur donné au tableau (sans crochets). C’est cette constante de type pointeur qui va permettre de manipuler facilement un tableau en particulier pour le passer en paramètre d’une fonction puisqu’on ne passera à la fonction que l’adresse du tableau et non tous ses éléments.
Allocation dynamique
La déclaration de variables dans la fonction main ou globalement réserve de l’espace en mémoire pour ces variables pour toute la durée de vie du programme. Elle impose par ailleurs de connaître avant le début de l’exécution l’espace nécessaire aux stockages de ces variables et en particulier la dimension des tableaux. Or dans de nombreuses applications le nombre d’éléments d’un tableau peut varier d’une exécution du programme à l’autre.
La bibliothéque stdlib fournit des fonctions qui permettent de réserver et de libérer de manière dynamique (à l’exécution) la mémoire. La fonction qui permet de réserver de la mémoire est malloc(). Sa syntaxe est : void* malloc(unsigned int taille)
Algorithmes
Notion d’algorithme
Un algorithme est une suite de traitements élémentaires effectués sur des données en vue d’obtenir un résultat en un nombre finis d’opérations.
Traitement élémentaire: traitement pouvant être effectué par un ordinateur. Notion relative. Exemple: le calcul de la racine carrée d’un nombre peut être considéré comme élémentaire en C en utilisant la bibliothèque mathématique. Il ne l’est pas pour un microcontrôleur programmé en assembleur.
Exemple: l’algorithme d’Euclide calculant le PGCD de deux entiers:
Soit la division euclidienne de a par b, a = bq+r. L’algorithme d’Euclide est basé sur le principe que les diviseurs communs de a et b sont les mêmes que ceux de b et r. En remplaçant a par b et b par r et en divisant à nouveau, on obtient deux entiers ayant les mêmes diviseurs que les entiers a et b d’origine.
Finalement, on obtient deux entiers divisibles entre eux (r= 0) dont le plus petit est le PGCD de a et de b.
Représentation des algorithmes
Un programme est la réalisation d’un algorithme. Pour s’affranchir d’un langage de programmation particulier, différentes techniques de représentation sont utilisées.
Pseudo langage Permet de représenter formellement un algorithme indépendamment de l’implémentation (langage). Basé sur les instructions disponibles dans la plupart des langages.
Analyse et complexité d’un algorithme
Il existe souvent plusieurs algorithmes permettant de résoudre un même problème. Exemple: les algorithmes de tri. Le choix du meilleur algorithme implique une analyse de ses performances. En général, le critère le plus important est celui du temps nécessaire à son exécution. Celui ci dépend le plus souvent de la quantité de données à traiter. Par exemple, le temps nécessaire pour trier un ensemble d’objets dépend du nombre d’objets.
L’étude de la complexité d’un algorithme consiste essentiellement à évaluer la dépendance entre le temps d’exécution et le volume de données. Les résultats s’expriment de manière qualitative: On cherche par exemple à savoir si la complexité croit de manière linéaire ou polynomiale avec le volume n de données.
…..
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Analyse et complexité d’un algorithme (Cours PDF)
