Lundi 25 septembre 2006 : tri fusion itératif
Mercredi 27 septembre 2006 : allocation dynamique de mémoire, matrices
Vendredi 6 octobre 2006 : parcours de listes chaînées
Mercredi 11 octobre 2006 : insertion dans les listes chaînées
Mercredi 18 octobre 2006 : insertion à la fin d'une liste chaînée
Jeudi 26 octobre 2006 : lecture d'un graphe
Jeudi 2 novembre 2006 : recherche des composantes connexes et détection d'un circuit
Mercredi 8 novembre 2006 : recherche des composantes fortement connexes
Mercredi 15 novembre 2006 : parcours itératifs en profondeur et en largeur
Jeudi 23 novembre 2006 : tas

Écrire et exécuter un programme en C : exceed, KDE, Konsole, vim et gcc

Sous windows, il faut d'abord lancer exceed, pour avoir une fenêtre graphique contenant KDE associé à un autre ordinateur tournant sous linux.
Dans KDE le troisième bouton en bas à gauche de la fenêtre, représente un écran d'ordinateur et permet de lancer konsole, qui ouvre un terminal X, c'est-à-dire une fenêtre dans laquelle on peut taper des commandes unix qui sont interprétées par un shell (a priori bash).
Dans Konsole, on va ouvrir deux terminaux X. Pour ouvrir un deuxième terminal, il suffit de cliquer sur le bouton en bas de la fenêtre de Konsole. Pour passer d'un terminal à l'autre on peut cliquer sur un des deux onglets se trouvant en bas de la fenêtre de Konsole, ou bien appuyer sur <shift>← ou <shift>→ .
Dans un des terminaux, on mettra le programme en cours d'écriture. On y tapera donc :
mkdir algo
cd algo
vi bonjour.c
Dans l'autre terminal, on compilera et on exécutera le programme. On y tapera
cd algo
gcc -Wall bonjour.c
./a.out

vi ou vim

Vi est l'éditeur de texte traditionnel d'unix. Il existe depuis plusieurs dizaines d'années. Vim est une version améliorée de vi, que l'on utilise maintenant avec linux. Il reconnaît toutes les commandes de vi, plus beaucoup de nouvelles. Dans beaucoup d'éditeurs de texte, les lettres que l'on tape sont insérées dans le texte et il faut taper <ctrl>+une lettre pour exécuter une commande. C'est différent sous vi : les lettres servent à exécuter des commandes et il faut d'abord passer en mode insertion avant de pouvoir taper du texte.

insertion

Beaucoup de commandes permettent de passer en mode insertion : <ins> permet de passer du mode insertion au mode remplacement et réciproquement.
<échap> permet de sortir du mode insertion ou remplacement et revenir au mode de commande.

déplacement du curseur

Les quatre touches de déplacement du curseur et les quatre touches page vers le haut, page vers le bas, début et fin marchent normalement avec vim, mais certaines de ces commandes peuvent aussi se faire autrement : h=ctrl-H=<backspace>=← , k=↑ , l=<espace;>=→ , j=↓ , ^=<début>=0 , $=<fin> .
on peut aussi utiliser les commandes :

sauvegarder et quitter

divers

remplacement

Pour remplacer toutes les occurences de truc par machin on peut
ou bien d'abord taper /truc puis cwmachin<échap> ou 4clmachin<échap> puis n.n.n.n. autant de fois que nécessaire. n se place sur le prochain truc et . le remplace par machin.
Ou bien on tape une commande comme :%s/truc/machin/g
% est équivalent à 1,$ qui veut dire : sur toutes les lignes. On aurait pu le remplacer par exemple par 21,45 qui veut dire sur lignes 21 à 45.
Le g signifie que l'on fait plusieurs remplacement par ligne

copier (y yank), couper (d delete) et coller (p put)

Il y a plusieurs façons de copier du texte : Il y a autant façons de couper du texte : Dans ce qui précède il faut remplacer y par d. On a donc les commandes dd, 5dd, dl, 2dl, dw, 7dw, d$, d^, v...d, V...d, ctrl-V...d.
La commande p (resp. P) colle le dernier bout de texte copié ou coupé, derrière (resp. devant) le caractère ou la ligne courante.
Exemples :
Pour dupliquer la ligne courante, il suffit de taper yyp .
Pour échanger la ligne courante et la suivante, il suffit de taper ddp .
Pour échanger le caractère sous le curseur et le suivant, il suffit de taper dlp ou xp .
Pour échanger le mot courant et le précédent, il suffit de taper bdwbP .

sélection

Les commandes de sélection (v, V et ctrl-V) sont suivies de déplacements du curseur et se terminent par, au choix : gv resélectionne la même zone.

premier programme

En utilisant vi on va d'abord mettre dans algo/bonjour.c le programme :#include<stdio.h> int main() { printf("Bonjour\n"); return 0; } Puis on va On peut alors compiler le programme par la commande cc -Wall bonjour.c puis l'exécuter par ./a.out
On peut supprimer la ligne #include<stdio.h> du programme, le sauver, par :w le recompiler et l'exécuter, puis le restaurer, par u.
On peut de même supprimer le \n ou la ligne return 0; ou le int devant main ou enfin le point-virgule après le 0.

autre programme : 3+4=7

On peut sortir de vi par :q et le relancer par vi somme.c.
On peut aussi rester dans vi et taper la commande :w somme.c et modifier le programme pour qu'il devienne : #include<stdio.h> int main() { int a,b; printf("Donnez deux nombres entiers : "); scanf("%d%d",&a,&b); printf("%d+%d=%d\n",a,b,a+b); return 0; } On peut modifier le programme pour qu'il calcule aussi le produit, le quotient et le reste de la division : #include<stdio.h> int main() { int a,b; printf("Donnez deux nombres entiers : "); scanf("%d%d",&a,&b); printf("%d+%d=%d\n",a,b,a+b); printf("%d*%d=%d\n",a,b,a*b); printf("%d/%d=%d\n",a,b,a/b); printf("%d%%%d=%d\n",a,b,a%b); return 0; } Si on exécute se programme en lui donnant les deux nombres 3 et 0, il se termine par une erreur.
Pour savoir où cette erreur se produit on peut recompiler en ajoutant l'option -g puis lancer le debugger :cc somme.c -Wall -g gdb a.out On peut alors taper :run 3 0 print a print b quit

maximum des éléments d'un tableau, récursivement et itérativement

#include<stdio.h> void afft(int t[], int n) { int i; for(i=0;i<n;i++) printf("%d ",t[i]); printf("\n"); } int maxite(int t[], int n) { int i, m=t[0]; for(i=1;i<n;i++) if(m<t[i]) m=t[i]; return m; } int maxrec(int t[], int n) { int m; if(n==1) return t[0]; m=maxrec(t,n-1); if(m<t[n-1]) m=t[n-1]; return m; } int main() { int t[]={4,5,2,8,1,9,3,7,4,6,3}; const int n=11; printf("Le plus grand des nombres : "); afft(t,n); printf("est %d = %d\n",maxite(t,n),maxrec(t,n)); return 0; } Le programme précédent écrit : Le plus grand des nombres : 4 5 2 8 1 9 3 7 4 6 3 est 9 = 9

valeur d'un polynôme en un point en O(n) et O(n²)

#include<stdio.h> #include<math.h> void affpol(double P[], int degre) { int i, nul=1; double x; for(i=0;i<=degre;i++) if(P[i]) { x=P[i]; if(x<0) x=-x, printf("-"); else if(!nul) printf("+"); if(x!=1 || !i) { if(x==rint(x)) printf("%.0lf",x); else printf("%.5lf",x); } switch(i) { default:printf("X^%d",i); break; case 3: printf("X³"); break; case 2: printf("X²"); break; case 1: printf("X"); case 0: ; } nul=0; } if(nul) printf("0"); printf("\n"); } double valpolite(double P[], int degre,double x) { int i; double v=0; for(i=degre;i>=0;i--) v=v*x+P[i]; return v; } double puissn(double x,int n) { int i=0; double p=1; for(i=1;i<=n;i++) p*=x; return p; } double valpolrecn2(double P[], int degre,double x) { if(degre<0) return 0; else return valpolrecn2(P,degre-1,x)+P[degre]*puissn(x,degre); } int main() { double P[]={1,3,2,4,0,-1,0,1}, Q[100001], x; const int degP=7; int degQ,i; printf("P(X)="); affpol(P,degP); for(x=-1;x<=1.01;x+=0.2) printf("P(%lf)=%lf=%lf\n",x,valpolite(P,degP,x),valpolrecn2(P,degP,x)); for(degQ=1;degQ<=100000;degQ*=10) { for(i=0;i<=degQ;i++) Q[i]=degQ+1-i; x=1+1.0/degQ; printf("Q=");affpol(Q,degQ<10?degQ:10); printf("Q(%lf)=%lf\n",x,valpolite(Q,degQ,x)); printf("Q(%lf)=%lf\n",x,valpolrecn2(Q,degQ,x)); } return 0; } Pour compiler ce programme il faut rajouter l'option -lm.
Quand on l'exécute, il affiche : P(X)=1+3X+2X²+4X³-X^5+X^7 P(-1.000000)=-4.000000=-4.000000 P(-0.800000)=-2.050035=-2.050035 P(-0.600000)=-0.894234=-0.894234 P(-0.400000)=-0.127398=-0.127398 P(-0.200000)=0.448307=0.448307 P(-0.000000)=1.000000=1.000000 P(0.200000)=1.711693=1.711693 P(0.400000)=2.767398=2.767398 P(0.600000)=4.334234=4.334234 P(0.800000)=6.610035=6.610035 P(1.000000)=10.000000=10.000000 Q=2+X Q(2.000000)=4.000000 Q(2.000000)=4.000000 Q=11+10X+9X²+8X³+7X^4+6X^5+5X^6+4X^7+3X^8+2X^9+X^10 Q(1.100000)=93.842838 Q(1.100000)=93.842838 Q=101+100X+99X²+98X³+97X^4+96X^5+95X^6+94X^7+93X^8+92X^9+91X^10 Q(1.010000)=7391.805874 Q(1.010000)=7391.805874 Q=1001+1000X+999X²+998X³+997X^4+996X^5+995X^6+994X^7+993X^8+992X^9+991X^10 Q(1.001000)=720360.497024 Q(1.001000)=720360.497024 Q=10001+10000X+9999X²+9998X³+9997X^4+9996X^5+9995X^6+9994X^7+9993X^8+9992X^9+9991X^10 Q(1.000100)=71848958.319202 Q(1.000100)=71848958.319201 Q=100001+100000X+99999X²+99998X³+99997X^4+99996X^5+99995X^6+99994X^7+99993X^8+99992X^9+99991X^10 Q(1.000010)=7183026028.129010 Q(1.000010)=7183026028.129013 Dans le programme précédent, réécrire la fonction puissance récursivement : fonction puiss(x,n) si n est impair alors retourner x*puiss(x,n-1) sinon si n=0 alors retourner 1 sinon retourner puiss(x²,n/2) finsi fin fonction Quel est le nouveau temps de calcul de puiss ?
On peut compter combien de fois on calcule xn comme (x²)(n/2) et combien de fois comme x*(xn-1).
10=2*5 1
5=1+4 1
4=2*2 2
2=2*1 3
1=1+0 1
   
100=2*50 1
50=2*25 2
25=1+24 1
24=2*12 3
12=2*6 4
6=2*3 5
3=1+2 2
2=2*1 6
1=1+0 3
   
1000=2*500 1
500=2*250 2
250=2*125 3
125=1+124 1
124=2*62 4
62=2*31 5
31=1+30 2
30=2*15 6
15=1+14 3
14=2*7 7
7=1+6 4
6=2*3 8
3=1+2 5
2=2*1 9
1=1+0 6

110=2*55 1
55=1+54 1
54=2*27 2
27=1+26 2
26=2*13 3
13=1+12 3
12=2*6 4
6=2*3 5
3=1+2 4
2=2*1 6
1=1+0 5
   
113=1+112 1
112=2*56 1
56=2*28 2
28=2*14 3
14=2*7 4
7=1+6 2
6=2*3 5
3=1+2 3
2=2*1 6
1=1+0 4
   
117=1+116 1
116=2*58 1
58=2*29 2
29=1+28 2
28=2*14 3
14=2*7 4
7=1+6 3
6=2*3 5
3=1+2 4
2=2*1 6
1=1+0 5

32=2*16 1
16=2*6 2
8=2*4 3
4=2*2 4
2=2*1 5
1=1+0 1
   
64=2*32 1
32=2*16 2
16=2*6 3
8=2*4 4
4=2*2 5
2=2*1 6
1=1+0 1
   
128=2*64 1
64=2*32 2
32=2*16 3
16=2*6 4
8=2*4 5
4=2*2 6
2=2*1 7
1=1+0 1

On voit que le nombre de division par 2 est 4 pour n=24=16, 5 pour n=25=32, 6 pour n=26=64, 7 pour n=27=128, et plus généralement k pour n=2k. C'est aussi 6 pour tous les n de 64 à 127, et 5 pour tous les n de 32 à 63, et plus généralement k pour tous les n de 2k à 2k-1. Autrement dit c'est ⌊log2⌋ la partie entière inférieure du logarithme en base 2 de n.
De plus on voit qu'entre deux diminutions d'un de n, il y au moins une division par 2. Cela prouve que le nombre de soustractions d'un est inférieur à 1+⌊log2⌋.
Tout cela montre que le temps de calcul de la puissance est Θ(log n). Autrement dit il est compris entre A log n et B log n pour deux constantes A et B strictement positives.
Quel est le nouveau temps de calcul de valpolrecn2 ?
Le temps f(n) nécessaire pour évaluer un polynôme P de degré n en un point a est inférieur à la somme de On a donc
f(n)&le a+B ln n +f(n-1)
En additionnant les n inégalités
f(1)&le a+B ln 1 +f(0)
f(2)&le a+B ln 2 +f(1)
f(3)&le a+B ln 3 +f(2)
...
f(n)&le a+B ln n +f(n-1)
On obtient
f(n)&le n a+B(ln 1+ln 2+ln 3+...+ln n)+f(0)
Donc f(n)≤n a+B n ln n+c=O(n ln n).
En faisant des calculs un peu plus soignés on pourrait démontrer que f(n)=Θ(n ln n).

recherche dichotomique dans un tableau déjà trié

Premier algorithme : On cherche x parmi les nombres T[a]<T[a+1]<...T[b]. tant que a<=b faire m=(a+b)/2 arrondi à l'entier le plus proche si T[m]==x alors on retourne m sinon si x<T[m] alors b=m-1 // l'intervalle de recherche [a..b] est remplacé par [a..m-1] sinon a=m+1 // l'intervalle de recherche [a..b] est remplacé par [m+1..b] finsi fait on retourne -1 Deuxième algorithme : On cherche x parmi les nombres T[a]<T[a+1]<...T[b]. tant que a<b faire m=(a+b)/2 arrondi à l'entier inférieur si x<=T[m] alors b=m // l'intervalle de recherche [a..b] est remplacé par [a..m] sinon a=m+1 // l'intervalle de recherche [a..b] est remplacé par [m+1..b] finsi fait si a==b et T[a]==m alors on retourne m sinon on retourne -1 finsi Ces deux algorithmes se traduisent en C :int dicho1(int T[], int n, int x) { int a=0, b=n-1; while(a<=b) { const int m=(a+b)/2; if(T[m]==x) return m; if(x<T[m]) b=m-1; else a=m+1; } return -1; } int dicho2(int T[], int n, int x) { int a=0, b=n-1; while(a<b) { const int m=(a+b)/2; if(x<=T[m]) b=m; else a=m+1; } if(a==b && T[a]==x) return a; else return -1; } On peut inclure ces deux procédures dans un programme qui contient aussi des procédures de tri par sélection ou à bulle.void echint(int *a,int *b) { int c=*a; *a=*b; *b=c; } int posmax(int T[],int n) { int i, m=0; for(i=1;i<n;i++) if(T[i]>T[m]) m=i; return m; } void triselec(int T[],int n) { while(n>1) echint(T+n-1,T+posmax(T,n)), n--; } void tribulle(int T[],int n) { int i,imax; while(n>1) { imax=0; for(i=1;i<n;i++) if(T[i-1]>T[i]) echint(T+i-1,T+i), imax=i; n=imax; } } Le reste du programme pourrait être :void talea(int t[],int n) { int i, x=0; for(i=0;i<n;i++) x=x*1123+1, t[i]=x%(n*2); } void afft(int t[],int n) { int i; for(i=0;i<n;i++) printf(" %d",t[i]); printf("\n"); } #define n 13 int main() { int t[n], i, p; for(p=0;p<2;p++) { talea(t,n); afft(t,n); (p?tribulle:triselec)(t,n); afft(t,n); for(i=-n*3;i<3*n;i+=n/3) printf("%d %d\n",i,(p?dicho2:dicho1)(t,n,i)); } return 0; }

Lundi 25 septembre 2006 : tri fusion itératif

fusion

On se donne deux tableaux de nombres triés par ordre croissant, on veut remplir un troisième tableau avec les contenus des deux premiers intercalés, de telle sorte que le résultat soit trié.tant que les deux tableaux donnés sont non vides faire on compare le premier le premier élément du premier tableau avec le premier élément du second tableau on enlève le plus petit des deux du tableau où il était on le met à la fin du nouveau tableau fait Les éléments restant à la fin du tableau non vide doivent être recopiés dans l'ordre à la fin du nouveau tableau. En C cela donne :void fusion(int t[], int n, int u[], int m, int v[]) { int i=0,j=0; while(i<n && j<m) if(t[i]<u[j]) v[i+j]=t[i], i++; else v[i+j]=u[j], j++; while(i<n) v[i+j]=t[i], i++; while(j<m) v[i+j]=u[j], j++; }

tri fusion

On considère que le tableau à trier est formé d'une succession de morceaux triés de longueur 1.
On prend deux morceaux consécutifs de longueur 1 et on les fusionne en un morceau trié de longueur 2. On recommence avec les deux suivants, puis les deux suivants, etc.. A la fin on a une suite de morceaux triés de longueur 2.
On recommence en fusionnant deux par deux les morceaux triés de longueur 2 pour obtenir des morceaux triés de longueur 4.
Puis on recommence en fusionnant deux par deux les morceaux triés de longueur 4 pour obtenir des morceaux triés de longueur 8.
On recommence ainsi jusqu'à ce que le tableau soit constitué d'un seul morceau trié.
La description précédente s'applique bien si on suppose que la taille du tableau à trier est une puissance de 2. Cela donne en C :void trifusion(int t[],int n) { int l, j, k, u[n]; for(l=1;l<n;l+=l) // pour l=1, 2, 4, 8 etc. faire for(j=0;j<n;j+=l+l) // pour j=0, 2*l, 4*l, 6*l, etc. faire { fusion(t+j,l,t+j+l,l,u); // on fusionne t[j..j+l-1] et t[j+l..j+2l-1] dans u[0..2l-1] for(k=0;k<2*l;k++) t[k+j]=u[k] // on recopie u[0..2l-1] dans t[j..j+2l-1] } // fait } // fait Si la taille du tableau à trier n'est pas une puissance de deux, le nombre de norceaux à trier à chaque étape n'est pas forcément pair et le dernier morceau peut être moins long que les autres. Cela donne :void trifusion(int t[],int n) { int l, j, k, u[n], j2l; for(l=1;l<n;l+=l) // pour l=1, 2, 4, 8 etc. faire for(j=0;j+l<n;j+=l+l) // pour j=0, 2*l, 4*l, 6*l, etc. faire { j2l=j+l+l; // j2l=min(j+2l,n) if(j2l>n) j2l=n; fusion(t+j,l,t+j+l,j2l-j-l,u); // on fusionne t[j..j+l-1] et t[j+l..j2l-1] dans u[0..j2l-j-1] for(k=j;k<j2l;k++) t[k]=u[k-j] // on recopie u[0..j2l-j-1] dans t[j..j2l-1] } // fait } // fait

analyse du temps de calcul

Lors de fusion i varie de 0 à n et j de 0 à m. Donc i++ est effectué n fois et j++ m fois. Le nombre total d'itérations effectuées dans toutes les boucle est donc exactement n+m. Le temps de calcxul est donc Θ(m+n). Il est donc en gros proportionnel à la taille du résultat de la fusion.
Lors du tri, pour une valeur de l données, tous les morceaux sont fusionnés deux par deux. Le temps pris pour cette valeur de l est donc égal à la somme des longueurs des morceaux fusionnés, c'est-à-dire à peu près n la taille du tableau à trié.
La taille des morceaux triés, l décrit toutes les puissances de 2 inférieures à n. Le nombre d'itérations de la boucle externe, sur l, est donc ⌈log2n⌉=&Theta(ln n). Le temps total du tri est donc Θ(n ln n).

Mercredi 27 septembre 2006 : allocation dynamique de mémoire, matrices

#include<stdio.h> #include<stdlib.h> typedef struct {int dim; long double *t;} vec; typedef struct {int dim; vec *t;} mat; void affv(vec a) { int i; for(i=0;i<a.dim;i++) printf("%Lf ",a.t[i]); printf("\n"); } void affm(mat a) { int i; printf("\n"); for(i=0;i<a.dim;i++) affv(a.t[i]); } vec addvvv(vec a,vec b) { if(a.dim!=b.dim) printf("somme de vecteurs de tailles %d et %d\n",a.dim,b.dim), exit(1); { vec c={a.dim,malloc(a.dim*sizeof(*a.t))}; int i; for(i=0;i<c.dim;i++) c.t[i]=a.t[i]+b.t[i]; return c; } } mat addmmm(mat a,mat b) { if(a.dim!=b.dim) printf("somme de matrices de tailles %d et %d\n",a.dim,b.dim), exit(1); { mat c={a.dim,malloc(a.dim*sizeof(*a.t))}; int i; for(i=0;i<c.dim;i++) c.t[i]=addvvv(a.t[i],b.t[i]); return c; } } vec mulmvv(mat a,vec b) { int i,j; vec c={a.dim,malloc(a.dim*sizeof(*b.t))}; for(i=0;i<c.dim;i++) { if(b.dim!=a.t[i].dim) printf("produit d'une matrice %dx%d par un vecteur %d\n",a.dim,a.t[i].dim,b.dim),exit(1); c.t[i]=0; for(j=0;j<b.dim;j++) c.t[i]+=a.t[i].t[j]*b.t[j]; } return c; }int main() { long double ta[]={2,3,5}, tb[]={4,2,1}; vec a={3,ta}, b={3,tb}, tm[]={a,b}, c, d; mat m={2,tm}, mm=addmmm(m,m); c=addvvv(a,b); d=mulmvv(mm,c); printf("a="); affv(a); printf("b="); affv(b); printf("m="); affm(m); printf("mm="); affm(mm); printf("c="); affv(c); printf("d="); affv(d); return 0; } Le programme précédent écrit :a=2.000000 3.000000 5.000000 b=4.000000 2.000000 1.000000 m= 2.000000 3.000000 5.000000 4.000000 2.000000 1.000000 mm= 4.000000 6.000000 10.000000 8.000000 4.000000 2.000000 c=6.000000 5.000000 6.000000 d=114.000000 80.000000

Vendredi 6 octobre 2006 : parcours de listes chaînées

Une liste chaînée est représentée par un pointeur sur son premier chaînon si elle est non vide, et par le pointeur nul si elle est vide.
Un chainon est une structure ayant deux champs : la valeur du premier élément de la liste et la liste des chaînons suivants, qui est donc représentée par un pointeur sur le chaînon suivant s'il existe, et sinon par le pointeur nul. #include<stdlib.h> #include<stdio.h> typedef struct chainon *liste; struct chainon{int val1; liste suite;}; void afflisterec(liste l) { if(l==0) printf("\n"); // si la liste est vide alors on passe à la ligne else // sinon { printf("%d ",l->val1); // on affiche le premier élément afflisterec(l->suite); // puis on affiche le reste de la liste } // finsi } void afflisteite(liste l) { while(l) // tant qu'on n'est pas au bout de la liste faire { printf("%d ",l->val1); // on affiche un élément l=l->suite; // on passe au suivant } // fait printf("\n"); // on passe à la ligne } liste cree(int x, liste s) // rend un pointeur { liste l=malloc(sizeof(*l)); // sur un nouveau chaînon, obtenu par malloc, l->val1=x; // et initialise les deux champs de ce chainon avec ses deux arguments. l->suite=s; return l; } int main() { struct chainon ch3={3,0}, ch2={4,&ch3}, ch1={1,&ch2}; // &ch3=(3) &ch2=(4,3) &ch1=(1,4,3) liste a=cree(6,cree(7,cree(10,0))); // cree(10,())=(10) cree(7,(10))=(7,10), cree(6,(7,10))=(6,7,10) afflisterec(&ch1); // 1 4 3 afflisteite(&ch1); // 1 4 3 afflisterec(a); // 6 7 10 afflisteite(a); // 6 7 10 return 0; }

Mercredi 11 octobre 2006 : insertion dans les listes chaînées

Compléter le programme suivant :#include<stdlib.h> #include<stdio.h> typedef struct chainon *liste; struct chainon{int val1; liste suite;}; void afflisterec(liste l); void afflisteite(liste l); liste cree(int x, liste s); int sommelisteite(liste a); int sommelisterec(liste a); liste inseretete(liste l,int x); liste inserequeueite(liste l,int x); liste inserequeueite2(liste l,int x); liste inserequeuerec(liste a,int x); void insere3(liste a,int x); void insere10(liste a,int x);

Mercredi 18 octobre 2006 : insertion à la fin d'une liste chaînée

Dans le programme précédent compléter aussi :typedef struct{liste deb,fin;} debfin; void ajoutedftete(debfin *a,int x); void ajoutedfqueue(debfin *a,int x); int enlevedftete(debfin *a); int enlevedfqueue(debfin *a); Réponse :#include<stdlib.h> #include<stdio.h> typedef struct chainon *liste; struct chainon{int val1; liste suite;}; void afflisterec(liste l) { if(l==0) printf("\n"); // si la liste est vide alors on écrit un passage à la ligne else // sinon { printf("%d ",l->val1); // on affiche la valeur contenue dans le premier chaînon afflisterec(l->suite); // puis on affiche le reste de la liste } // fin si } void afflisteite(liste l) { while(l) // tant que la liste n'est pas vide faire { printf("%d ",l->val1); // on affiche la valeur contenue dans le premier chaînon l=l->suite; // on enlève le premier chaînon } // fait printf("\n"); // on écrit un passage à la ligne } liste cree(int x, liste s) { liste l=malloc(sizeof(*l)); // l est l'adresse d'un nouveau chaînon l->val1=x; // on copie les arguments dans les champs de ce chaînon l->suite=s; return l; // on rend l'adresse de ce chaînon } int sommelisteite(liste a) // somme des éléments d'une liste { int s=0; for(;a;a=a->suite) s+=a->val1; // on ajoute la valeur de chacun des chaînons à s return s; } int sommelisterec(liste a) // la somme des éléments d'une liste est { if(a) return a->val1+sommelisterec(a->suite); // la somme du premier élément et de la somme des autres, si la liste n'est pas vide, else return 0; // nulle si la liste est vide } //int sommelisterec(liste a) { return a ? a->val1+sommelisterec(a->suite) : 0; } liste inseretete(liste l,int x) {return cree(x,l);} liste inserequeueite(liste l,int x) // pour inserer un nouvel élément à la fin d'une liste { liste a; if(!l) return cree(x,0); // On rend une nouvelle liste avec un seul élément, si la liste était vide. for(a=l;a->suite;a=a->suite) ; // On parcourt la liste jusqu'au dernier chaînon. a->suite=cree(x,0); // On attache un nouveau chaînon derrière l'ancien dernier chaînon. return l; // La nouvelle liste est représentée par l'adresse du premier chaînon, qui n'a pas changée. } liste inserequeueite2(liste l,int x) { liste *a=&l; // a est un pointeur sur une variable de type liste (c'est un pointeur sur pointeur sur un chaînon) while(*a) a=&(*a)->suite; // *a est l puis l->suite, puis l->suite->suite, etc. On avance tant qu'on peut. A la fin *a contient 0 *a=cree(x,0); // Dans *a on remplace 0 par une nouvelle liste formée d'un seul chaînon. return l; // Si la liste initiale n'était pas vide alors l n'a pas changé de valeur. } // Si la liste était vide alors *a était l qui a donc changé de valeur. liste inserequeuerec(liste a,int x) { if(!a) return cree(x,0); // On rend une nouvelle liste avec un seul élément, si la liste était vide. a->suite=inserequeuerec(a->suite,x); // Sinon, on ajoute un nouvel élément à la fin de la liste qui suit le premier élément, return a; // et on rend l'adresse de l'ancien premier élément (qui est resté la tête de la liste) } //liste inserequeuerec(liste l,int x){ return a ? a->suite=cree(x,a->suite),a : cree(x,0); } void insere3(liste a,int x) // pour insérer un nouveau troisième élément, { a->suite->suite=cree(x,a->suite->suite); // on l'insère en tête de la liste suivant le deuxième élément. } void insere10(liste a,int x) { int i; for(i=0;i<8;i++) a=a->suite; // On avance 8 fois : on passe du premier au neuvième chaînon. a->suite=cree(x,a->suite); // On insère un chaînon derrière ce neuvième chaînon. } typedef struct{liste deb,fin;} debfin; void ajoutedftete(debfin *a,int x) { liste l=cree(x,a->deb); // l est un nouveau chaînon que l'on met devant l'ancien premier a->deb if(a->deb==0) a->fin=l; // si la liste était vide, alors le nouveau chaînon est le seul, donc le premier et le dernier a->deb=l; } void ajoutedfqueue(debfin *a,int x) { liste l=cree(x,0); // l est un nouveau chaînon que l'on met en queue if(a->deb==0) a->deb=l; // si la liste était vide, alors le nouveau chaînon est le seul, donc le premier et le dernier else a->fin->suite=l; // sinon on le met derrière l'ancien dernier a->fin=l; } int enlevedftete(debfin *a) { if(a->deb==0) printf("liste vide\n"), exit(1); // On ne peut pas enlever un chaînon d'une liste vide { struct chainon p=*a->deb; // on recopie l'ancien premier chaînon free(a->deb); // avant de libérer la place qu'il occupait a->deb=p.suite; // Le nouveau premier chaînon est le successeur de l'ancien premier chaînon return p.val1; // on rend la valeur contenue dans l'ancien premier chaînon } } int enlevedfqueue(debfin *a) { liste l=a->deb; if(l==0) printf("liste vide\n"), exit(1); // On ne peut pas enlever un chaînon d'une liste vide if(l==a->fin) return enlevedftete(a); // S'il n'y a qu'un chaînon, enlever le dernier revient à enlever le premier { int v=a->fin->val1; // La valeur rangée dans le dernier chaînon sera rendue par la fonction et doit donc être sauvée free(a->fin); // avant de libérer la place occupée par le dernier chaînon. while(l->suite!=a->fin) l=l->suite; // l avance dans la liste, du premier chaînon jusqu'à l'avant dernier. a->fin=l; // L'avant dernier chaînon devient le dernier. l->suite=0; // Il n'y plus rien derrière lui. return v; } } int main() { struct chainon ch3={3,0}, ch2={4,&ch3}, ch1={1,&ch2}; liste a=cree(6,cree(7,cree(10,0))); debfin b={0,0}; int i; afflisterec(&ch1); afflisteite(&ch1); printf("Somme : %d = %d\n",sommelisteite(&ch1),sommelisterec(&ch1)); afflisterec(a); afflisteite(a); printf("Somme : %d = %d\n",sommelisteite(a),sommelisterec(a)); for(i=10;i<40;i+=10) a=inseretete(a,i), a=inserequeueite(a,i+1), a=inserequeueite2(a,i+2), a=inserequeuerec(a,i+3); afflisteite(a); insere3 (a,103); afflisteite(a); insere10(a,110); afflisteite(a); for(i=0;i<10;i++) ajoutedftete(&b,i), ajoutedfqueue(&b,i+10); afflisteite(b.deb); while(b.deb) printf("%d %d\n",enlevedftete(&b),enlevedfqueue(&b)); return 0; } Ce programme écrit1 4 3 1 4 3 Somme : 8 = 8 6 7 10 6 7 10 Somme : 23 = 23 30 20 10 6 7 10 11 12 13 21 22 23 31 32 33 30 20 103 10 6 7 10 11 12 13 21 22 23 31 32 33 30 20 103 10 6 7 10 11 12 110 13 21 22 23 31 32 33 9 8 7 6 5 4 3 2 1 0 10 11 12 13 14 15 16 17 18 19 9 19 8 18 7 17 6 16 5 15 4 14 3 13 2 12 1 11 0 10

Exercice 1 extrait de l'examen du 6 septembre 2006

Exercice 1 : tris
Le tri par sélection d'un tableau de n entiers consiste à trouver l'élément maximum du tableau, l'échanger avec le dernier élément du tableau, et recommencer avec le tableau des n-1 premiers éléments.
Q1 : Ecrire un programme C permettant de réaliser ce tri.
Q2 : Dérouler son exécution sur le tableau suivant : 13 5 45 10 2 16 42 25
Q3 : Analyser sa complexité dans le pire des cas.
Q4 : En supposant que le tableau est au départ déjà trié par ordre croissant, est-ce que le tri est alors plus rapide (que dans le pire des cas ?).
Q5 : Supposons maintenant que le tableau est implémenté sous forme d'une liste simplement chaînée d'entiers. Implémentez un algorithme de tri par sélection qui retire à chaque étape le plus grand élément de la liste pour constituer la liste résultat (triée par ordre croissant).
Q6 : Cela change-t-il la complexité du tri ?
Q7 : réaliser un tri par tas du tableau de la question 2. (construire graphiquement les tas correspondants en précisant les permutations de clés effectuées)
Q8 : Rappeler la complexité dans le pire des cas du tri par tas. En supposant que le tableau est au départ déjà trié par ordre croissant, est-ce que le tri est alors plus rapide (que dans le pire des cas ?).

Corrigé


Q2 : 13 5 45 10 2 16 42 25 13 5 25 10 2 16 42 45 13 5 25 10 2 16 42 45 13 5 16 10 2 25 42 45 13 5 2 10 16 25 42 45 10 5 2 13 16 25 42 45 2 5 10 13 16 25 42 45 2 5 10 13 16 25 42 45 2 5 10 13 16 25 42 45
Q3 : La boucle externe est faite n fois. La boucle interne est faite n, puis n-1, puis n-2, ... puis 1 fois. A chaque itération de la boucle externe, la boucle interne est donc faite en moyenne (n+1)/2 fois. En tout elle est donc faite n(n+1)/2 fois. Le temps de calcul est donc en Θ(n²).
Q4 : Dans l'analyse précedente on a compté combien de fois la boucle interne est effectuée. Elle contient un if. Mais l'instruction qui est exécutée si le test du if est vrai est une simple affectation qui prend à peu près le même temps que le test du if. Quand il est toujours vrai (cas où le tableau est trié) la procédure prend donc à peu près deux fois plus de temps que quand il est toujours faux (cas ou le tableau est trié à l'envers). Il y a donc en gros un rapport 2 entre le temps maximal et le temps minimal. Le temps pris est donc toujours en Θ(n²).
Q5 : int maxl(liste a) { int x=a->val1; // fait une erreur d'exécution si la liste est vide for(;a;a=a->suite) if(a->val1>x) x=a->val1; return x; } liste otel(liste a,int x) { if(a->val1==x) { liste b=a->suite; free(a); return b;} a->suite=otel(a->suite,x); return a; } liste trisel(liste a) { liste b=0; while(a) { int x=maxl(a); a=otel(a,x); b=cree(x,b); } return b; } Autre version sans free ni malloc mais avec des pointeurs de pointeur. liste trisel(liste a) { liste b=0, c, *p, *m; while(a) { for(p=m=&a;*p;p=&(*p)->suite) if((*p)->val1>(*m)->val1) m=p; c=*m; *m=c->suite; // on détache c, le plus grand chainon c->suite=b; b=c; // on le met en tête de b } return b; }
Q6 : Le temps du tri est toujours Θ(n²).

Jeudi 26 octobre 2006 : lecture d'un graphe

Jeudi 2 novembre 2006 : recherche des composantes connexes et détection d'un circuit

#include<stdio.h> #include<stdlib.h> typedef struct chainon *liste; struct chainon{int val1; liste suite;}; typedef struct{int n; liste *voisins;} graphe; liste cree(int val1,liste suite) { liste a=malloc(sizeof(*a)); a->val1=val1; a->suite=suite; return a; } char next() { char a; do a=getchar(); while(a==' ' || a==10 || a==13); // On ignore les blancs, les passages à la lignes et les retours en début de ligne. return a; } graphe liregraphe(int oriente) { char a,b; int s,t,n; printf("Combien de sommets ? "); scanf("%d",&n); { graphe g={n,malloc(n*sizeof(liste))};// Le graphe g a n sommets, et un tableau de n listes (une pour chaque sommet) for(s=0;s<n;s++) g.voisins[s]=0; // Chacune de ces listes est initialement vide. for(;;) { a=next(); s=a-'a'; // a est une lettre représentant un sommet, s est son numéro. if(s<0) return g; // On a lu toutes les arêtes. b=next(); t=b-'a'; // b est une lettre représentant un sommet, t est son numéro. g.voisins[s]=cree(t,g.voisins[s]); // On ajoute t en tête de la liste des voisins de s. if(!oriente) g.voisins[t]=cree(s,g.voisins[t]); // On ajoute s en tête de la liste des voisins de t. } } } void comptevoisins(graphe g) { int a; for(a=0;a<g.n;a++) { int c=0; liste p; for(p=g.voisins[a];p;p=p->suite) c++; printf(" %d",c); } printf("\n"); } int cherchecc(int n, liste voisins[], int cc[]) { int nbcc=0; void visite(int a) // Pour visiter un sommet a, { liste p; // on commence par noter qu'il a été visité, en remplaçant le -1 contenu dans cc[a] cc[a]=nbcc; // par le numéro de la composante connexe en cours d'exploration. for(p=voisins[a];p;p=p->suite) // Puis chacun de ses voisins if(cc[p->val1]<0) // qui n'a pas encore été visité visite(p->val1); // est visité. } int a; for(a=0;a<n;a++) cc[a]=-1; // Pour chacun des sommets, on note qu'il n'a pas encore été visité. for(a=0;a<n;a++) if(cc[a]<0) // Pour chacun des sommets qui n'a pas encore été visité, { visite(a); // on visite ce sommets et ses voisins et leurs voisins, etc. nbcc++; // On compte une composante connexe de plus } return nbcc; } int sanscircuit(int n, liste succ[]) { int sans=1; enum {nonvu,encours,fini} t[n]; void visite(int a) // Pour visiter un sommet a, { liste p; t[a]=encours; // on commence par noter qu'il est en cours de visite. for(p=succ[a];p && sans;p=p->suite) // Puis on regarde chacun de ses successeurs : switch(t[p->val1]) { case encours: sans=0; // Si ce succeseur est en cours de visite, on a trouvé un circuit. case fini: break; // Si ce sucesseur à déjà été visité on l'ignore. case nonvu: visite(p->val1); // Si ce successeur n'a pas encore été visité, on le visite. } t[a]=fini; // On note qu'on a fini la visite du sommet a. } int a; for(a=0;a<n;a++) t[a]=nonvu; // Pour chacun des sommets, on note qu'il n'a pas encore été visité. for(a=0;a<n && sans;a++) if(t[a]==nonvu)// Pour chacun des sommets qui n'a pas encore été visité, visite(a); // on visite ce sommets et ses voisins et leurs voisins, etc. return sans; } int main() { graphe g=liregraphe(0); // graphe non orienté int cc[g.n]; comptevoisins(g); printf("Ce graphe a %d composantes connexes.\n",cherchecc(g.n,g.voisins,cc)); g=liregraphe(1); if(sanscircuit(g.n,g.voisins)) printf("Ce graphe est sans circuit.\n"); else printf("Ce graphe contient un circuit.\n"); return 0; }

Mercredi 8 novembre 2006 : recherche des composantes fortement connexes

Pour obtenir les composantes fortement connexes d'un graphe orienté, triées topologiquement, on peut : Tous les sommets visités ainsi à partir de chaque nouveau point de départ, forment une composante fortement connexe.
Dans le programme précédent on peut ajouter les deux procédures : void retourne(int n,liste vois[]) { liste soiv[n],p; int a,b; for(a=0;a<n;a++) soiv[a]=vois[a], vois[a]=0; for(a=0;a<n;a++) for(p=soiv[a];p;) { liste c=p; p=c->suite; // on détache le chaînon c en tête de la liste p b=c->val1; c->val1=a; // l'arc a->b devient l'arc b->a c->suite=vois[b]; vois[b]=c; // on le met en tête de la liste des prédécesseurs de b } } int cherchecfc(int n,liste succ[],int cfc[]) { int ordrefin[n], nbfini=0, nbcfc=n; void visite(int s) { liste p; cfc[s]=nbcfc; for(p=succ[s];p;p=p->suite) if(cfc[p->val1]>nbcfc) visite(p->val1); if(nbcfc==n) ordrefin[nbfini++]=s; } int a; for(a=0;a<n;a++) cfc[a]=n+1; // Au début cfc[a] vaut n+1 pour tous les sommets a for(a=0;a<n;a++) if(cfc[a]>n) visite(a); // lors de la première visite cfc[a] passe à n pour tous les sommets retourne(n,succ); // On change le sens des arcs nbcfc=0; // Nombre de composantes fortement connexes déjà trouvées while(nbfini) if(cfc[a=ordrefin[--nbfini]]==n) visite(a), nbcfc++; // Parcours d'une composante fortement connexe retourne(n,succ); // On rechange le sens des arcs, pour revenir au graphe initial return nbcfc; // Nombre de composantes fortement connexes trouvées } Dans le programme principal juste avant le return 0; on peut ajouter :
printf("Ce graphe a %d composantes fortement connexes\n",cherchecfc(g.n,g.voisins,cc));

Mercredi 15 novembre 2006 : parcours itératifs en profondeur et en largeur

Les deux procédures calchemin(n,succ,origine,dist,pere) et caldist(n,succ,origine,dist,pere) font un parcours en profondeur d'abord ou en largeur d'abord sur un graphe à n sommets numérotés de 0 à n-1, la liste chaînée des successeurs du sommet s étant rangée dans succ[s]. Le parcours se fait uniquement à partir du sommet origine. On obtient donc un arbre de tous les sommets atteints. Il a pour racine origine. Dans cet arbre un sommet b a pour père pere[b], la longueur du chemin allant de la racine au sommet s est dist[s]. Si un sommet a ne peut pas être atteint à partir d'origine, dist[a] garde sa valeur de départ n, et pere[a] n'est pas défini.
La procédure calchemin fait un parcours en profondeur d'abord et on obtient donc des branches très longues et des valeurs dans dist très grandes. La procédure calcdist fait un parcours en largeur d'abord et met donc dans dist[a] la longueur du plus court chemin possible d'origine à a.
Dans ces procédures la pile (pour calchemin) et la file d'attente (pour calcdist) contiennent les sommets que l'on a déjà atteints, mais dont on n'a pas fini d'examiner tous les successeurs.
Le programme principal crée un graphe à n sommets numérotés de 0 à n-1, qui contient tous les arcs de la forme a->a+1, a->3a et 2a->a. Avec la procédure calchemin on cherche un chemin dans ce graphe allant de 100 à 99. Avec la procédure calcdist on cherche le plus court chemin dans ce graphe allant de 100 à 99. #include<stdio.h> #include<stdlib.h> typedef struct chainon *liste; struct chainon { int v; liste suite;}; liste cree(int v, liste suite) { liste a=malloc(sizeof(*a)); a->v=v; a->suite=suite; return a; } void calchemin(int n,liste succ[],int origine,int dist[],int pere[]) { liste suc[n], p; int s,a,b,ip=0,pile[n]; for(s=0;s<n;s++) dist[s]=n, // Le sommet s n'a pas encore été visité. suc[s]=succ[s]; // Tous ses succeseurs doivent être examinés. dist[origine]=ip; // La distance d'origine à lui-même est nulle. pile[ip++]=origine; // On met origine dans la pile, while(ip) // Tant que la pile n'est pas vide if(p=suc[pile[--ip]],p) // on sort un sommet a de la pile et s'il lui reste des successeurs à examiner { a=pile[ip++]; // on remet a dans la pile b=p->v; // on met dans b le prochain successeur de a à examiner suc[a]=p->suite; // et on l'enlève de la tête de la liste if(dist[b]==n) // si b n'a pas encore été visité pere[b]=a, // on note qu'il a été visité à partir de a dist[b]=ip, // Le chemin pile[0]=origine, pile[1], pile[2], ... ,pile[ip]=b est de longueur ip. pile[ip++]=b; // On range b dans la pile : On va donc le ressortir tout de suite. } } void calcdist(int n,liste succ[],int origine,int dist[],int pere[]) { int queue[n], ip=0, iq=0, s, a, b; liste p; for(s=0;s<n;s++) dist[s]=n; // Le sommet s n'a pas encore été visité. dist[origine]=0; // La distance d'origine à lui-même est nulle. queue[ip++]=origine; // On met origine dans la file d'attente, while(ip>iq) // Tant que la file d'attente n'est pas vide for(p=succ[a=queue[iq++]];p;p=p->suite) // on sort un sommet a de la pile, et pour chacun de ses successeurs if(dist[b=p->v]==n) // b qui n'a pas encore été visité pere[b]=a, // on note qu'il a été visité à partir de a dist[b]=dist[a]+1, // le plus court chemin allant d'origine à b, a pour pour avant dernière étape a. queue[ip++]=b; // On range b dans la file d'attente. Il ressortira après tout ce qu'il y a déjà dedans. } int main() { int n=200, a, b, dist[n], pere[n]; liste succ[n]; // Le graphe a n sommets for(a=0;a<n;a++) succ[a]=0; // mais n'a aucun arc. for(a=0;b=a+1,b<n;a++) succ[a]=cree(b,succ[a]); // On ajoute tous les arcs de la forme a->a+1 for(a=0;b=3*a,b<n;a++) succ[a]=cree(b,succ[a]); // On ajoute tous les arcs de la forme a->3a for(b=0;a=2*b,a<n;b++) succ[a]=cree(b,succ[a]); // On ajoute tous les arcs de la forme 2b->b calchemin(n,succ,100,dist,pere); // Parcours en profondeur d'abord à partir de 100 for(a=99;a!=100;a=pere[a]) printf("%2d%4d\n",dist[a],a); // On affiche à l'envers un chemin menant de 100 à 99 calcdist(n,succ,100,dist,pere); // Parcours en largeur d'abord à partir de 100 for(a=99;a!=100;a=pere[a]) printf("%2d%4d\n",dist[a],a); // On affiche à l'envers un chemin de longueur minimale menant de 100 à 99 return 0; }

Jeudi 23 novembre 2006 : tas

#include<stdio.h> #include<stdlib.h> typedef int element; typedef struct{const int nmax; int n; element *t;} tas; tas creetas(int nmax) { tas a={nmax,0,malloc((nmax+1)*sizeof(element))}; return a; } void detruittas(tas a) { free(a.t); } void monte(tas a, int j) { while(j>1 && a.t[j]>a.t[j/2]) { element x=a.t[j]; a.t[j]=a.t[j/2]; a.t[j/=2]=x; } } void descend(tas a,int j) { element x=a.t[j]; for(;;) { int jj=j+j; if(jj>a.n) return; if(jj<a.n && a.t[jj+1]>a.t[jj]) jj++; if(x>=a.t[jj]) return; a.t[j]=a.t[jj]; a.t[j=jj]=x; } } void instas(tas *a,element x) { if(++a->n>a->nmax) printf("Le tas déborde\n"),exit(1); a->t[a->n]=x; monte(*a,a->n); } element otepgtas(tas *a) { element x=a->t[1]; if(!a->n) printf("Le tas est vide\n"),exit(1); a->t[1]=a->t[a->n--]; descend(*a,1); return x; } void tritas2(int n,element t[]) { tas a=creetas(n); while(a.n<n) instas(&a,t[a.n]); while(a.n) {element x=otepgtas(&a); t[a.n]=x;} detruittas(a); } void tritas1(int n,element t[]) { tas a=creetas(n); int j; while(a.n<n) a.t[1+a.n]=t[a.n], a.n++; for(j=n;j;j--) descend(a,j); while(a.n) {element x=otepgtas(&a); t[a.n]=x;} detruittas(a); } int main() { int j,f,n=10; for(f=0;f<2;f++) { element t[n]; for(j=0;j<n;j++) t[j]=j*3%n; (f?tritas1:tritas2)(n,t); for(j=0;j<n;j++) printf(" %d",t[j]); printf("\n"); } return 0; }