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

“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&