1 Informations générales Références 2 Quelques rappels

Publié par

TP, Supérieur, TP
  • cours - matière potentielle : utilisation comment
  • cours - matière potentielle : utilisation
“Algorithmique et approche fonctionnelle” S3 IFIPS - Cycle Preparatoire Cours : Jerome Aze 1 Informations generales Organisation du module Algorithmique et approche fonctionnelle – Volume horaire : 48h CM=14h TD=14h TP=21h – Responsable du cours : Jerome Aze – Charges de TD/TP : Jerome Aze, Cedric Bentz et Thomas Larguillier – Contenu : – la notion d'abstraction dans la modelisation de problemes – la recursivite – l'analyse de la complexite des algorithmes – Certains algorithmes classiques peuvent servir de support – Algorithmes de tri ou de recherche (recherche sequentielle, dichotomique, hachage, etc.) – Problemes classiques : les tours de
  • structure de donnees associee
  • int main
  • chaıne
  • buffer
  • buffer dans la nouvelle chaıne
  • pile
  • piles
  • taille
  • allocation memoire
  • tailles
  • pointeur
  • pointeurs
  • tableaux
  • tableau
Publié le : mercredi 28 mars 2012
Lecture(s) : 34
Source : lri.fr
Nombre de pages : 33
Voir plus Voir moins

“Algorithmique et approche fonctionnelle”
S3 IFIPS - Cycle Pre´paratoire
Cours : Je´roˆme Aze´
1 Informations ge´ne´rales
Organisation du module
Algorithmique et approche fonctionnelle
– Volume horaire : 48h CM=14h TD=14h TP=21h
– Responsable du cours : Je´roˆme Aze´
– Charge´s de TD/TP : Je´roˆme Aze´, Ce´dric Bentz et Thomas Larguillier
– Contenu :
– la notion d’abstraction dans la mode´lisation de proble`mes
– la re´cursivite´
– l’analyse de la complexite´ des algorithmes
– Certains algorithmes classiques peuvent servir de support
– Algorithmes de tri ou de recherche (recherche se´quentielle, dichotomique, hachage, etc.)
– Proble`mes classiques : les tours de Hano¨ı, etc.
´Evaluation
Controˆle des connaissances
– Controˆle continu (CC)
– rendu des TPs (CC-TP)
– controˆle e´crit (CC-TD) : de´but octobre
– Examen : controˆle e´crit avec documents autorise´s mi-novembre
NoteFinale = 0.5×(0.6×CC−TD +0.4×CC−TP)
+ 0.5×Examen
Re´fe´rences
Ouvrage de re´fe´rence
– Types de donne´es et algorithmes, Christine Froidevaux, Marie-Claude Gaudel et Miche`le Soria McGraw-
Hill, Collection Informatique,1990, 575 pages.
2 Quelques rappels
2.1 Rappels de compilation
IDE / Editeur de texte+Console+compilateur
IDE (Anjuta) : avantages/inconve´nients
1– Avantages
– Facilite´ d’utilisation
– Coloration syntaxique
– Compilateur et debugger inte´gre´s
– Supporte plusieurs langages : C, C++, Java, Perl, ...
– Inconve´nients
– Anjuta non installe´ = catastrophe :(
– Utilisation d’un autre IDE ?
– Tout faire a` la main ?
Que faire sans IDE ?
Les bases de la survie sans IDE
– Utilisation d’un e´diteur de textes quelconque : kate, kedit, emacs, ...
– Inte´gration de la coloration syntaxique pour la plupart
– Utilisation d’une console (Terminal, xterm) pour compiler le code source et exe´cuter le programme
– Compilation manuelle du programme avec gcc
Les bases de la compilation
Les trois e´tapes
– La pre´compilation : gcc -E test.c
– Les #include et les #define sont re´solus.
– La compilation : gcc -c test.c
– Le fichier test.o est cre´e´.
– La ve´rification des fonctions et de leur parame`tres est re´alise´e lors de cette e´tape.
– L’e´dition de liens et la cre´ation de l’exe´cutable :
gcc -o test test.o tris.o
– Ve´rification que les fonctions de´finies dans les .h sont bien de´finies dans les .o correspondants et cre´ation
du programme exe´cutable.
Les options de compilation
Les options de gcc
– -E : pre´compilation
– -c : compilation
– -g : mode de´boggage
– -ansi : impose la ve´rification du format ANSI
– -Wall : active la de´tection de tous les warnings
Aide sur le langage C
Utilisation des pages de man de C
En cas de doute sur les parame`tres d’une fonction, ...
– Utiliser les pages de man du C
– Dans une console : man printf (ou toute autre fonction)
– Sur google : man scanf
Trouver les erreurs simples de vos programmes
#include<stdio.h>
int main()
{
printf(”Hello world\n”) ;
return (0)
}
2Anjuta
main.c :5 : erreur : expected ’ ;’ before ’}’ token
Console + gcc
helloWorld.c : In function ’main’ :
helloWorld.c :5 : erreur : expected ’ ;’ before ’}’ token
3 Rappels sur la gestion de la me´moire
´3.1 Gestion statique de la memoire
Me´moriser les re´sultats
Utilisation d’un tableau
– Inte´reˆt : stocker des re´sultats pour les re´utiliser
– Permet de ne pas refaire inutilement des calculs complexes
– Plusieurs structures de donne´es utilisables
– Si le nombre de re´sultats a` me´moriser est connu : tableau
– Si l’acce`s aux re´sultats doit eˆtre rapide : tableau
– Si le nombre de re´sultats est inconnu : liste, file, pile, ...
– Syntaxe : int tab[10] de´finit un tableau permettant de stocker 10 entiers
– Les tableaux sont indice´s de 0 a` taille - 1
– Acce`s :x =tab[9] permet d’affecter a` x la 10e`me valeur du tableau.
3.2 Gestion dynamique de la me´moire
Comment ge´rer un nombre quelconque d’e´le´ments a` me´moriser ?
Aller au dela` d’une taille pre´de´finie
– Les tableaux de la forme int tab[100] sont de taille pre´de´finie.
– Impossible de de´passer cette taille sans provoquer d’erreur
– Utilisation d’autres tableaux de la forme int * tab ;
– Cette syntaxe permet de de´clarer une variable tab de type pointeur sur un entier.
– tab contiendra l’adresse du de´but de la zone me´moire correspondant au tableau.
– Ensuite, il faudra allouer dynamiquement la me´moire en cours d’utilisation
Comment ge´rer un nombre quelconque d’e´le´ments a` me´moriser ?
Allocation dynamique de la me´moire
– Librairie : #include<stdlib.h> (standard library)
– Instruction : malloc permet d’allouer de la me´moire memory allocation
– Usage : tab = (int *) malloc (sizeof(int) * taille) ;
– sizeof(TYPE) permet de connaˆıtre le nombre d’octets qu’occupe TYPE en me´moire
– taille : correspond au nombre de cases me´moires a` allouer
Boucle et allocation me´moire
3#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main (){
float rayon, perimetre ;
float * les perimetres ;
int i, nb perimetres = 0 ;
printf (”Entrer le nombre de calcul souhaites\n”) ; scanf (”%i”, &nb perimetres) ;
les perimetres = (float *) malloc (sizeof(float) * nb perimetres) ;
for (i = 1 ; i<= nb perimetres ; i++){
printf (”Veuillez indiquer le rayon du cercle !\n”) ; scanf (”%f”, &rayon) ;
perimetre = 2 * M PI * rayon ; les perimetres[i-1] = perimetre ;
printf (”Le cercle numero %i de rayon %f a un perimetre de %f\n”, i, rayon, perimetre) ;
}
free (les perimetres) ;
return (0) ;
}
´ ´ `Calcul et memorisation d’un nombre quelconque de perimetres
`Pas a pas
– float * les perimetres : de´claration du tableau destine´ a` stocker les pe´rime`tres
– les perimetres = (float *) malloc (sizeof(float) * nb perimetres) : Allocation me´moire du tableau. Re´servation
de nb perimetres cases de float
eme– les perimetres[i] = perimetre : Permet de me´moriser le i pe´rime`tre calcule´
– free (les perimetres) : Ope´ration indispensable qui permet de libe´rer la me´moire pour une nouvelle utili-
sation.
Calcul et me´morisation d’un nombre quelconque de pe´rime`tres
Le nombre d’e´le´ments a` me´moriser inconnu
– Possibilite´ d’allouer de nouveau de la me´moire en cours d’utilisation
– Inte´reˆt : e´tendre un tableau devenu trop petit
tab = (int *) realloc (tab, sizeof(int) * nouvelle taille) ;– Syntaxe :
Utilisation de Realloc
#include<stdio.h> #include<math.h> #include<stdlib.h>
int main (){
float rayon, perimetre ; float * les perimetres ;
int i = 0, nb perimetres = 10 ;
printf (”Entrer un rayon = 0 pour arreˆter la boucle !\n”) ;
les perimetres = (float *) malloc (sizeof(float) * nb perimetres) ;
do{
printf (”Veuillez indiquer le rayon du cercle !\n”) ; scanf (”%f”, &rayon) ;
if (rayon != 0){
perimetre = 2 * M PI * rayon ; les perimetres[i] = perimetre ;
printf (”Le cercle de rayon %f a un perimetre de %f\n”, rayon, perimetre) ;
i++ ;
if (i>= nb perimetres){
nb perimetres+=10 ;
les perimetres = (float *) realloc (les perimetres, sizeof(float) * nb perimetres) ;
}
} while (rayon != 0) ;
free (les perimetres) ;
return (0) ;
}
Calcul et me´morisation d’un nombre quelconque de pe´rime`tres
Pas a` pas
– 1e`re e´tape : allouer un tableau de taille raisonnable
– En cours d’utilisation :
– Ve´rifier si l’indice courant i n’a pas atteint la taille du tableau
– Si oui, alors augmenter la taille et re´allouer le tableau
– Le tableau s’utilise normalement
43.3 Manipulation de pointeurs
Manipulation de pointeurs
Quel affichage produit le code suivant :
float f1 = 3.0 ; float f2 = 8.7 ;
float * ptr1 = &f1 ;
float * ptr2 = &f2 ;
ptr1 = ptr2 ;
*ptr1 = *ptr2 + f1 ;
printf (”f1 = %f, f2 = %f\n”,f1,f2) ;
Re´ponses
f1 = 3.0000, f2 = 11.7000
f1 = 6.0000, f2 = 8.7000
f1 = 3.0000, f2 = 8.7000
f1 = 11.7000, f2 = 8.7000
Manipulation de pointeurs
Acce`s au contenu d’un tableau
int * tab ;
tab = (int *) malloc (sizeof(int) * 100) ;
– tab : correspond a` l’emplacement me´moire ou` se trouve le tableau
– tab[0] ou (*tab) : correspond a` la premie`re valeur du tableau
– tab[i] ou (* (tab + i)) : correspond a` lai−1e`me valeur du tableau
4 Fonctions
´Creation de fonctions
Syntaxe
TypeDeRetour nomDeLaFonction (parametres){
corps de la fonction ;
}
Exemple
float puiss (float i, int j){
float puiss = 1.0 ;
int k ;
for (k=0 ; k< j ; k++){ puiss *= i ;}
return puiss ;
}
Appel de fonction float i = puiss (2., 10) ;
5 Enregistrement d’informations structure´es
Comment enregistrer en meˆme temps plusieurs informations ?
Structuration des informations
– Besoin : pouvoir enregistrer des informations lie´es
– Exemple : pe´rime`tre, rayon et nume´ro du calcul
– Utilisation de type structure´
5typedef struct{
int numero ;
– De´claration : float rayon ;
float perimetre ;
} t cercle ;
– Utilisation : t cercle un cercle ;
– Acce`s : un cercle.rayon = rayon ;
Enregistrement de plusieurs informations ?
#include<stdio.h> #include<math.h> #include<stdlib.h>
typedef struct{ int numero ; float rayon, perimetre ; } t cercle ;
int main (){
float rayon, perimetre ; t cercle * les perimetres ;
int i = 0, nb perimetres = 10 ;
printf (”Entrer un rayon = 0 pour arreˆter la boucle !\n”) ;
les perimetres = (t cercle *) malloc (sizeof(t cercle) * nb perimetres) ;
do{
printf (”Veuillez indiquer le rayon du cercle !\n”) ; scanf (”%f”, &rayon) ;
if (rayon != 0){
perimetre = 2 * M PI * rayon ;
les perimetres[i].numero = i ;
les perimetres[i].rayon = rayon ;
les perimetres[i].perimetre = perimetre ;
printf (”Le cercle de rayon %f a un perimetre de %f\n”, rayon, perimetre) ;
i++ ;
if (i>= nb perimetres){
nb perimetres+=10 ;
les perimetres = (t cercle *) realloc (les perimetres, sizeof(t cercle) * nb perimetres) ;
}
} while (rayon != 0) ;
free (les perimetres) ;
}
5.1 Gestion des chaines de caracte`res
Cas particulier : les chaˆınes de caracte`res
Pas de type pre´de´fini
– Une chaˆıne de caracte`res est une succesions de caracte`res
– Une chaˆıne est un simple tableau de caracte`res
– De´claration : char * chaine ;
– Utilisation : la librairie string.h contient de nombreuses fonctions permettant de manipuler les chaˆınes de
caracte`res
– Interaction avec un utilisateur :
– Cre´ation d’une chaˆıne “buffer” de taille suffisante pour contenir le texte a` saisir : char buffer[256];
– Calcul de la taille exacte : int taille = strlen (buffer) ;
– De´finir une chaˆıne de la bonne taille
– Recopier le buffer dans la nouvelle chaˆıne
– Une chaˆıne de caracte`re est toujours termine´e par le caracte`re non imprimable ’\0’
Les chaˆınes de caracte`res
Quelques fonctions utiles de<string.h>
– La fonction int strlen (const char * string) : renvoie la longueur de la chaˆıne pointe´e par string sans compter
le caracte`re ’\0’
– La fonction char * strcpy (char * dest, const char * src) : copie la chaˆıne pointe´e par src (y compris le
caracte`re ’\0’ final) dans la chaˆıne pointe´e par dest.
– La fonction int strcmp (const char * s1, const char * s2) : compare les deux chaˆınes s1 et s2. Elle renvoie
un entier :
– ne´gatif si s1<s2
– nul si s1=s2
– ou positif si s1> s2
6`Les chaˆınes de caracteres
Quelques fonctions utiles de<string.h>
– La fonction char * strcat (char * dest, const char * src) ajoute la chaˆıne src a` la fin de la chaˆıne dest en
e´crasant le caracte`re ’\0’ a` la fin de dest, puis en ajoutant un nouveau caracte`re ’\0’ final.
– pour plus de de´tails : man string
6 Piles, files et listes
6.1 Les piles
Piles
– Cette structure de donne´es est tre`s utilise´e et est utile lorsque plusieurs e´le´ments doivent eˆtre me´morise´s et
que seul le dernier e´le´ment me´morise´ doit eˆtre accessible.
– Les piles respectent le principe dit LIFO (Last In First Out) : le dernier e´le´ment empile´ est le premier qui
sera traite´. Par exemple : pile de livres, pile d’assiettes,...
Cette structure est utilise´e pour traiter les fonctions (ou proce´dures) re´cursives (gestion des appels en attente).
Principe
– Chaque e´le´ment empile´ connait l’e´le´ment situe´ derrie`re lui mais pas celui qui est devant lui.
– Il existe un e´le´ment particulier : le sommet de la pile.
– La pile est repre´sente´e uniquement par son sommet.
sommet→ 10
9
Example 1. 45
12
9
Manipulations
– Les piles sont manipule´es a` l’aide de trois fonctions :
– empiler : permet d’ajouter un e´le´ment en sommet de pile.
– de´piler : retire l’e´le´ment situe´ au sommet de la pile.
– pile vide : indique si la pile est vide.
– Ces trois fonctions sont suffisantes pour pouvoir manipuler une pile.
NPI ou Notation post-fixe´e
– Introduite en 1920
– Permet de ne plus utiliser de parenthe`se dans les calculs
– Ainsi 3×(4+7) s’e´crira : 3 4 7 +×
– Le calcul utilise une pile
7
Example 2. – empiler (3), empiler (4), empiler (7) 4
3
11
– empiler (de´piler()+de´piler()) 7+4
3
33– empiler (de´piler()× de´piler()) 11× 3
Structures de donne´es
– Les piles sont de simples enregistrements contenant deux informations :
– Le contenu de l’e´le´ment empile´
– L’e´le´ment suivant (c’est-a`-dire l’e´le´ment qui a e´te´ empile´ pre´ce´demment)
– Les e´le´ments empile´s doivent tous eˆtre du meˆme type.
– L’e´le´ment suivant est de´signe´ par un pointeur sur la pile dont il repre´sente le sommet.
Type t pile = Enreg (element : t element, suivant : pointeur (t pile);
7sommet
pile d’entiers
10element
10 sommet
suivant
89
5
89element
suivant
5element
suivant null
Example 3.
Ope´rations de base
Voici l’ensemble des ope´rations de base ne´cessaire pour manipuler des piles :
– pile vide :∅→ pile
– est vide : pile→ booleen
– empiler : pile× element→ pile
– de´piler : pile→ pile (contrairement a` l’exemple des expressions arithme´tiques, de´piler ne renvoie pas la
valeur du sommet mais juste la pile)
– sommet : pile→ element
Cette fonction renvoie une pile vide.
Fonction pile vide() : pointeur(t pile);
de´but
retourner null;
fin
Cette fonction renvoie vrai si la pile est vide et faux sinon.
Fonction est vide(sommet : pointeur(t pile)) : Booleen;
de´but
retourner (sommet = null);
fin
Fonction empiler(sommet : pointeur(t pile), element : t element) : pointeur(t pile);
Variables : nouveau sommet : pointeur(t pile);
de´but
nouveau sommet←allouer (t pile);
nouveau sommetˆ.element←element;
nouveau sommetˆ.suivant←sommet;
retourner nouveau sommet;
fin
6.2 Les files
Files
– Cette structure de donne´es est elle-aussi tre`s utilise´e et est tre`s proche de la pile.
– Les files respectent le principe dit FIFO (First In First Out) : le premier e´le´ment enfile´ est le premier qui
sera traite´.
8Fonction de´piler(sommet : pointeur(t pile)) : pointeur(t pile);
Variables : sommet precedent : pointeur(t pile);
de´but
si (non est vide (sommet)) alors
sommet precedent←sommet;
sommet←sommetˆ.suivant;
desallouer (sommet precedent);
fin Si
retourner sommet;
fin
Fonction sommet(sommet : pointeur(t pile)) : t element;
de´but
si (non est vide (sommet)) alors
retourner sommetˆ.element;
sinon
exception(“pile vide”);
fin Si
fin
– Cette structure est utilise´e pour traiter les acce`s multiples a` une meˆme ressource (imprimante par exemple).
Example 4. – file d’attente au cine´ma,...
Principe
– Chaque e´le´ment de la file connait l’e´le´ment qui le suit mais pas celui qui le pre´ce`de.
ˆ– Il existe deux e´le´ments particuliers : le premier (tete) et le dernier (queue) de la file.
– La file est donc repre´sente´e par ces deux e´le´ments.
tete 10 9 45 3 17 queue
Example 5.
´Structures de donnees
– Les files sont de simples enregistrements contenant deux informations :
– Le contenu de l’e´le´ment enfile´
– L’e´le´ment suivant
– Les e´le´ments enfile´s doivent donc tous eˆtre du meˆme type.
– L’e´le´ment suivant est de´signe´ par un pointeur sur la file dont il repre´sente la teˆte.
Type t element file = Enreg (
element : t element,
suivant : pointeur (t element file)
);
Type t file = Enreg (
premier, dernier : pointeur (t element file)
);
queuetete
10 89 5
file d’entiers
10 element 5element element 89
tete
suivant suivant suivant null
queue
Example 6.
9´Operations de base
Voici l’ensemble des ope´rations de base ne´cessaire pour manipuler des files :
– file vide :∅→ file
– est vide : file→ booleen
– enfiler : file× element→ file
– de´filer : file→ file
– premier : file→ element
6.3 Les listes chaˆıne´es
Listes chaˆıne´es
– Les listes chaˆıne´es sont des structures proches des piles et des listes.
– Elles peuvent eˆtre repre´sente´es dans des tableaux ou a` l’aide de structures re´cursives (avec des pointeurs).
– Nous de´velopperons dans ce cours les structures avec pointeurs. Cette repre´sentation est fortement recom-
mande´e lorsque le nombre d’e´le´ments a` stocker n’est pas connu a` l’avance.
Principe
Il existe plusieurs formes de listes chaˆıne´es :
– Chaˆınage simple : avant ou arrie`re
– Chaˆınage double : avant et arrie`re
– Gestion circulaire de la liste
Ces trois formes peuvent eˆtre combine´es et fournir par exemple, des listes circulaires doublement chaˆıne´es.
tete
7elem 48 elem elem 63 elem12
precedent precedent precedent precedent
suivant suivant suivant suivant
Structure de donne´es
La structure de donne´es associe´e a` cette repre´sentation est la suivante :
Type t maillon = Enreg (
element : t element,
suivant, precedent : pointeur (t maillon)
);
Type t liste = pointeur (t maillon);
La liste est alors repre´sente´e par un unique e´le´ment appele´ la teˆte.
Ope´rations
Toutes les ope´rations suivantes doivent pouvoir eˆtre effectue´es sur des listes chaˆıne´es. Cet ensemble d’ope´rations
n’est pas exhaustif.
– liste vide :∅→ liste
– est vide : liste→ booleen
– est present : liste× element→ booleen
– supprimer : liste× element→ liste (supprime le premier e´le´ment e´gal a` element de la liste)
– ajouter tete : liste× element→ liste (ajouteelement en teˆte de liste)
10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.