INFO719 : rappels d'algorithmique et programmation C

Ce wiki est un complément de cours pour le cours "info-719 : rappels d'algorithmique et programmation C". La participation au wiki n'est pas obligatoire mais fortement encouragée. Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Vous pouvez aller voir ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

Détails techniques

Nouvelles

Les nouvelles récentes sont en haut de la liste...

• Hyvernat 12 septembre 2008 à 15:43 (CEST) : création du wiki

Organisation des séances

Comme vous n'êtes pas nombreux, le cours sera entièrement en mode cours / TD.

• première séance (12/09/2008) : introduction, calcul du maximum,
• deuxième séance (16/09/2008) : introduction au C (partie I), début du TD1,
• troisième séance (23/09/2008) : TP0 (reprise du TD1 en salle machines),
• quatrième séance (30/09/2008) : fin du TP0,
• cinquième séance (07/10/2008) : approximations asymptotiques, début TD2,
• sixième séance (14/10/2008) : TD2,
• septième séance (21/10/2008) : fin TD2,
• TP1 (24/10/2008) : matrices de markov,
• huitième séance (4/11/2008) : cours de C, structures et pointeur,
• TP2 (5/11/2008) : le jeu de la vie,
• neuvième séance (18/11/2008) : tableaux et pointeurs, processus de compilation,

Les support de TD et TP

• TD1

• TP0

• Compléments pour le TP 0 :
  • Pour compiler un programme, allez voir la page Comment compiler le C ?
  • Pour faire du C chez vous, vous pouvez :
    • soit installer linux (je vous conseille Ubuntu)
    • soit installer une "émulation Unix" pour Windows (Cygwin, en précisant à l'installation que vous voulez installer au moins gcc, gdb et make dans la partie Devel)
    • soit installer un environnement de programmation C pour Windows (par exemple, Dev-C++)

• TD2

• le TP2 est seulement disponible online.

• l'examen corrigé (voir aussi plus bas pour le code C...)

Correction TDP0

Question 1 : sur les minimums et maximums

#include <stdio.h>


#define N 10  /* la taille de mes tableaux */


/* la fonction qui échange le minimum et le maximum dans un tableau */
void change (int T[N]) {

 int i=0;
 int max=0;   /* indice du maximum */
 int min=0;   /* indice du minimum */

 for(i=0;i<N;i=i+1) {
   if (T[i] < T[min]) { min=i; }
   if (T[i] > T[max]) { max=i; }
 }

 i=T[min];
 T[min] = T[max];
 T[max] = i;

}

/* recherche et affichage des deux valeurs maximales dans un tableau */
void deux_max (int T[N]) {
 int i;
 int max,maxbis;

 if (T[0] < T[1]) { max=1 ; maxbis=0; }
             else { max=0 ; maxbis=1; }

 for(i=2;i<N;i=i+1) {
          if (T[i] > T[max])  { maxbis=max; max=i; }
   else { if (T[i] > T[maxbis]) { maxbis=i; } }
 }

 printf("Le grand maximum se trouve à l'indice %i et vaut %i ; ", max, T[max]);
 printf("le petit maximum se trouve à l'indice %i et vaut %i.\n", maxbis, T[maxbis]);

}


/* recherche et affichage des deux valeurs maximales distinctes dans un tableau */
void deux_max_bis (int T[N]) {
 int i;
 int max,maxbis;

 max=0;
 maxbis=0;

 for(i=1;i<N;i=i+1) {
         if (max==maxbis && T[i]<T[max])         { maxbis=i; }
   else {if (T[i] > T[max])                      { maxbis=max; max=i; }
   else {if (T[i] < T[max] && T[i] > T[maxbis])  { maxbis=i; }}}
 }

 if (max != maxbis) {
   printf("Le grand maximum se trouve à l'indice %i et vaut %i ; ", max, T[max]);
   printf("le petit maximum se trouve à l'indice %i et vaut %i.\n", maxbis, T[maxbis]);
 }
 else {
   printf("!!! Le tableau ne contient qu'une seule valeur : %i !\n",T[max]);
 }
}


int main () {
 int T[N] = { 0 , 1 , 2 , 3 , 4 , 55 , 666 , 42 , 0 , -7 };
 int i ;

 /* affichage du tableau */
 for (i=0;i<N;i=i+1) printf("T[%i] = %i\n",i,T[i]);
 printf("\n\n");

 change(T) ;

 for (i=0;i<N;i=i+1) printf("T[%i] = %i\n",i,T[i]);




 return(1);

}

Question 3 : renverser un tableau

(Merci à Diane et Florian... Leur solution était correcte, j'ai juste modifié un ou deux trucs sans grande importance.)

#include <stdio.h>
#define N 10

/* Fonction renverse */
void renverse (int T[N]) {
 int tmp;
 int i;
 for (i=0;i<N/2;i=i+1){
   tmp=T[i];
   T[i]=T[N-i-1];
   T[N-i-1]=tmp;
 }
}

/* permet d'afficher les valeurs du tableau dans le terminal */
void affiche_tableau(int T[N]) {
 int i;
 for (i = 0; i < N; i=i+1) {
   printf("T[%d]=%d\n",i,T[i]);
 }
}


/* Programme principal */
int main () {
 int T[N]={0,1,2,3,4,5,6,7,8,9};

 affiche_tableau(T);
 printf("Son tableau renversé est: \n");

 renverse(T);
 affiche_tableau(T);

 return 0;
}

Question 4 : palindromes

Écrire un test pour vérifier si un tableau est un palindrome. Si c'est le cas, il devra renvoyer la valeur -1; sinon, il devra renvoyer la plus grande valeur longueur du préfixe qu'on retrouve inversé en suffixe du tableau.

(Merci à Diane et Florian... Leur solution était correcte, j'ai par contre modifié la question pour renvoyer -1 dans le cas des palindromes. C'est plus logique.)

#include <stdio.h>
#define N 10

/* Fonction palindrome*/
int palindrome (int T[N]){
 int i;
 for (i=0;i<N/2;i=i+1){
   if (T[i] != T[N-i-1]) {return i;}
 }
 return -1;
}

/* permet de taper les 10 valeurs dans le terminal et de les afficher */
int lire_tableau(int T[N]) {
 int i;
 for (i = 0; i < N; i=i+1) {
   printf("T[%d]= ",i);
   scanf("%d",&(T[i]));
 }
 return 0;
}

/* Programme principal*/
int main () {
 int T[N];
 int x;
 lire_tableau(T);
 x=palindrome(T);
 if (x==-1)
   {printf("Le tableau est un palindrome. \n");}
 else
   {printf("La plus grande longueur d'u prefixe que l'on retrouve inversé en suffixe est %i. \n",x);}
 return 1;
}

Question 5 : recherche dans un tableau trié

On suppose que T est un tableau de taille N contenant des entiers triés par ordre croissant. Ecrivez une fonction qui va vérifier si un entier n aopparaît dans le tableau.

• Première méthode: recherche séquentielle

 #include <stdio.h>

/*fonction qui cherche un élément dans un tableau trié*/
int recherche_trier (int T[10],int cherche){
		int i=0;
		int trouve=0;
		
	if (cherche== T[0]){trouve=1;}
	else{
	    while ((!trouve) && (i<10) && (cherche >= T[i])){
		i=i+1;
		if (cherche==T[i]){trouve=1;}
 	    }
	}

	if (trouve==1){
 	   printf("L' entier %i a été trouvé à la case %i du tableau \n",cherche,i);
	}
	else {
	   printf("L' entier %i n'a pas été trouvé dans le tableau \n",cherche);
	}		
return 1;
}

 /*Programme principal*/
int main(){
	int T[10]={1,2,3,4,5,9,10,15,24,42};
	int cherche;

   /*permet à l'utilisateur de rentrer un entier a chercher*/
	printf("Rentrez un entier \n");
	scanf("%i",&cherche);
			
  	/*Appel de la fonction qui permet de rechercher l'entier*/
	recherche_trier (T,cherche);
 
return 1;
}

• Deuxième méthode: recherche dichotomique

#include <stdio.h>

/*Recherche dichotomique*/
int recherche_dicho(int T[10],  int cherche){
        int trouve;
        int indice;
        int inf;
        int sup;
        int milieu;
        trouve=0;

        if (cherche==T[0]){   /* on vérifie si l'élément est a la case 0 du tableau*/
		trouve=1;
		indice=0;
	}
	else{
	   if (cherche==T[9]){ /* on vérifie si l'élément est a la case 9 du tableau*/
		trouve=1;
		indice=9;
	   }
	   else{
	      inf=0;
	      sup=9;
				
	     while ((!trouve) && (inf<=sup)){
	       milieu=(inf+sup)/2;	    /*calcul du milieu du tableau*/
	       if (cherche==T[milieu]) { /* on vérifie si  l'élément du milieu est celui recherché*/
		 trouve=1;
    		 indice=milieu;
	       }
	       else {
		  if (cherche<T[milieu]){	
		      sup=milieu-1;
		  }
	          else{
	          inf=milieu+1;
	          }
	       }
	      }/*fermeture du while*/
      }
 }

 if (trouve==1){
     printf("L' entier %i a été trouvé à la case %i du tableau \n",cherche,indice);
 }
 else {
     printf("L' entier %i n'a pas été trouvé dans le tableau \n",cherche);
 }

return 0;
}



/*Programme principal*/
int main(){
	int T[10]={1,4,14,18,24,42,100,104,118,124};
	int cherche;

	/*permet à l'utilisateur de rentrer un entier a chercher*/
	printf("Rentrez un entier \n");
	scanf("%i",&cherche);
	
       /*appel de la fonction qui permet de recherche l'élément*/
	recherche_dicho (T,cherche);

return 1;
}

---

---

Code C de l'examen

Voila le code C des exercices de programmation de l'examen. Reportez-vous au sujet et à la correction pour des détails supplémentaires. Ce qui suit est un fichier C complet...

#include <stdio.h>

/* Recherche dans un tableau trié */
int cherche(int T[], int t, int e)
{
  int debut = 0;                       // le début du sous-tableau qui nous intéresse
  int fin = t;                         // la fin du sous-tableau qui nous intéresse
  int milieu;                          // le milieu du sous-tableau qui nous intéresse
  int indice = -1;                     // l'indice de l'élément que l'on cherche

  // on regarde au milieu du tableau, et si on trouve l'élément e, on 
  // s'arrête.
  // Sinon, on regarde dans la partie (droite ou gauche) pertinente.
  // On s'arrête quand on obtient un tableau vide.

  while ((indice == -1) && (fin - debut) > 1) {
    milieu = debut + (fin - debut) / 2;
    if (e == T[milieu]) {
      indice = milieu;
    } else {
      if (e < T[milieu]) {
        fin = milieu;
      } else {
        debut = milieu;
      }
    }
  }
  return (indice);
}


/* Calcul d'une approximation du sinus avec le developpement en série entière */
double devSinus(float x, int n)
{
  double numerateur = (double)x;       // la valeur de (-1)^n x^(2n+1)
  double X = (double)(-x * x);
  long int fact = 1;                   // la valeur de (2n+1)!
  int i;
  double resultat = x;

  for (i = 1; i < n + 1; i = i + 1) {
    numerateur = numerateur * X;
    fact = fact * (2 * i) * (2 * i + 1);
    resultat = resultat + (numerateur / fact);
  }

  return (resultat);
}


/* La fonction résidu très simple, mais il faut connaitre la propriété
 * mathématique associée...
 */
int residuSimple(int n, int b)
{
  int residu = n % (b - 1);
  if (residu == 0) {
    residu = b - 1;
  }
  return (residu);
}

/* le résidu un peu plus simple que dans l'enoncé : */
int residuMoinsSimple(int n, int b)
{
  int residu = n;
  while (residu >= b) {
    residu = (residu / b) + (residu % b);
  }
  return (residu);
}


/* le résidu comme dans l'enoncé : */

// (1) La fonction qui fait la somme des chiffres (en base n) du nombre n
int residuUneEtape(int n, int b)
{
  int residuPartiel = 0;

  while (n > 0) {
    residuPartiel = residuPartiel + (n % b);
    n = n / b;
  }
  return (residuPartiel);
}

// (2) La fonction résidu
int residuEtapes(int n, int b)
{
  int residu = n;
  while (residu >= b) {
    residu = residuUneEtape(residu, b);
  }
  return (residu);
}


/* fonction principale pour tester les fonctions... */
int main()
{

  /* // Pour tester la fonction cherche...
  int T[100000];
  int i;
  for (i = 0; i < 100000; i++)
    T[i] = 2 * i;

  int e;
  int indice;
  printf("Entrez un nombre : \n");
  scanf("%i", &e);
  indice = cherche(T, 100000, e);
  if (indice != -1)
    printf("%i apparait dans le tableau en position %i.\n", e, indice);
  else
    printf("%i n'apparait pas dans le tableau.\n", e);
  */


  int n, b;
  printf("Entrez un nombre : \n  ");
  scanf("%i", &n);

  printf("Entrez une base : \n  ");
  scanf("%i", &b);

  printf("Calcul du résidu de %i en base %i :\n", n, b);

  printf("  - méthode simple : %i\n", residuSimple(n, b));
  printf("  - méthode moins simple : %i\n", residuSimple(n, b));
  printf("  - méthode par étapes : %i\n", residuSimple(n, b));

  return (0);
}

Introduction

Objectifs

• mettre tout le monde à niveau sur les compétences de base en algorithmique
• donner des notions de base sur l'informatique concrète
• Étudier quelques techniques importantes d'algorithmique
• apprendre les bases du langage C

Plan

• intro, étude d'un exemple
• rappel d'algorithmique (probablement faits en TD)
• rappel mathématiques, complexité
• quelques techniques d'algorithmique
• notions de complexité

• le langage C

Rappels historiques

Vous pouvez partir de cette page pour avoir un peu plus de détails...

La préhistoire : le calcul

• le boulier chinois
• la pascaline de Pascal, inventée en 1641/42 : elle ne permet de faire que des additions (et des soustractions
• Leibniz rajoute la multiplication à la pascaline (1673)
• les "moulins à chiffres" de Charles Babbage (1834-36), malheureusement jamais construits...
• la "tabulating business machine" de Hollerith permet d'automatiser les calculs pour le recensement de la population américaine. Ceci donnera ensuite la société "international business machine" (IBM).
• l'apparition du relais électromécanique (1900) d'une fréquence de 100 Hz, permet la construction du Harvard Mark I en 1944

Les programmes et instructions

• les orgues de Barbarie
• les métiers à tisser de Vaucanson et Jacquard (1801)

Les ordinateurs "modernes"

• l'invention du tube à vide permet le développements d'ordinateurs entièrement électroniques : l'ENIAC en est le premier exemplaire (1946) ; il pèse environ 30 tonnes...
• la machine de Turing (ordinateur théorique)
• le Manchester Mark I (1948) et l'EDVAC (1951) améliorent l'ENIAC et commencent à ressembler à des ordinateurs modernes
• l'UNIVAC I est le premier ordinateur commercialisé, en 1951.

Rappels d'algorithmique

Un exemple

Exercice : écrivez un programme qui fait la chose suivante : on dispose d'un tableau d'entier T de taille n. L'élément i du tableau est noté T[i]. On veut modifier T en interchangeant le plus petit et le plus grand élément.

Solution possible

int i=0
int max=0   /* indice du maximum */
int min=0   /* indice du minimum */

if (n==0) then  exit  /* est-ce que le tableau est vide ? */

for i:=0 to n-1                /* j'ai pris la convention du C : les tableaux commencent à l'indice 0 */
  if T[i] < T[min] then min:=i
  if T[i] > T[max] then max:=i
end

i:=T[min]
T[min] := T[max]
T[max] := i

exit

Le langage C, partie 1

Un exemple caractéristique :

/* « ouverture » des bibliothèques utilisées */
#include <stdio.h>

/* première fonction : elle prend deux entiers en argument et renvoie un entier */
int minimum (int n, int m) {
  if (n<m) { return(n); }
  else  { return(m); }
}

/* la fonction principale */
int main () {
  int i=42,x;  /* i et x sont deux variables entières */
  int j;
  j=24;
  x=minimum(i,j*2);
  printf("Le minimum de %i et %i est %i.\n", i, j*2, x);
  return(1);
}

Quelques points importants :

• il faut explicitement déclarer les bibliothèques utilisées,
• on n'est pas obligé d'avoir des fonctions autre que la fonction main, mais les fonctions doivent être déclarées dans l'ordre
• la fonction main est obligatoire, et il est conseillé de lui donné le type de retour int.

• une variable ne « vit » qu'à l'intérieur du bloc { ... } dans lequel elle est déclarée
• les variables ne sont pas initialisées automatiquement à 0

Pour la syntaxe de base et des exemples concernant les conditions et les boucles, reportez-vous au chapitre « les bases » et « les tableaux » du polycopié de Bernard Cassagne.

Qelques exercices...

Voir le TD1 et les exemples de correction dans la correction du TP0.

Un peu de complexité

La notion de complexité d'un programme est fondamentale pour pouvoir évaluer l'intérêt pratique d'un programme. La complexité observée lors de test ou de benchmark est parfois suffisante mais ne prend en compte que certaines exécutions (celles qui sons testées par les tests). Il est souvent nécessaire de se faire une idée de la complexité théorique d'un programme pour pouvoir prédire son temps d'exécution (ou ses besoins en ressources) pour les exécutions futures.

Première approche de la complexité

Tout d'abord, nous ne nous intéresserons qu'à la complexité en temps, et (presque) jamais à la complexité en espace. Il ne faut pas en déduire que seule la complexité en temps est importante !

L'idée de base est de compter en combien de temps va s'exécuter un programme donné, mais la question elle même est mal posée :

• comment compte-t'on ?
• et surtout, que compte-t'on ?

Chronométrer le temps d'exécution ne permet pas de faire d'analyse fine, et ne permet pas facilement de prédire le comportement général de votre programme. Comme le temps dépend beaucoup du processeur utilisé, l'idéal serait de pouvoir compter le nombre de cycle nécessaires au programme. Cela est généralement impossible car cela dépend du type de processeur utilisé ainsi que des optimisations faites par le compilateur.

La complexité en temps d'un algorithme, c'est une estimation du nombre d'opérations atomiques effectuées par cette algorithme avant qu'il ne termine. Cette estimation doit être donnée comme une fonction dépendant de la taille de l'entrée sur laquelle est lancé l'algorithme.

La notion d'opération atomique est assez intuitive : c'est une opération algorithmique qui n'est pas divisible en sous-opérations. En première approximation, une opération est atomique si elle ne porte que sur des objets de type entier, caractère ou booléen. (Les types codés sur un ou deux mots). Un test (si (n==42) alors ...) ou une affectation (x:=3,1415926536) sont des opérations atomiques ; mais l'initialisation d'un tableau n'est pas atomique. (Il y a autant d'opérations qu'il y a d'éléments dans le tableau...)

Exemple : la recherche du maximum dans un tableau d'entiers positifs peut se faire comme suit

max := 0
pour i:=1 à taille
faire
  si (max < Tab[i])
  alors max:=Tab[i]
finfaire
affiche("Le maximum est %i.\n",max)

Le nombre d'opérations est le suivant :

• une opération pour l'initialisation de max
• une opération pour l'initialisation de i à 1
• un test pour voir si i==taille
• une opération pour le test max < Tab[1]
• "peut-être" une opération pour l'affectation max:=Tab[1]
• puis, pour chaque élément suivant du tableau :
  • un incrément du compteur
  • une affectation du compteur
  • un test pour voir si on a atteint la fin du tableau
  • un test
  • peut-être une affectation

Au total, si $n$ est la taille du tableau, on obtient entre $4n$ et $5n$ opérations. De manière générale, on s'intéresse surtout au pire cas ; on dira donc que cet algorithme s'exécute en "au plus $5n$ opérations".

Approximations asymptotiques

On ne peut habituellement pas compter de manière aussi précise le nombre d'opérations ; et ça n'a pas toujours du sens de vouloir être trop précis. (Est-ce que i:=i+1 correspond à une ou deux opérations atomiques ?) Nous allons donc utiliser les approximations asymptotique pour compter la complexité... Le but sera alors de distinguer les algorithmes "rapides", "lents", ou "infaisables". La notion de "grand O" permet de faire ça de manière systématique.

définition

si $f$ et $g$ sont des fonctions de $\mathbb {N}$ dans $\mathbb {N}$, on dit que $f$ est un "grand O" de $g$, et on écrit $f=O(g)$ si le quotient $|f(n)| \over |g(n)|$ est borné. Plus précisément, ça veut dire que $\exists B,\forall n,{|f(n)| \over |g(n)|}<B$

Le but de cette définition est multiple :

• elle cache une borne "au pire"
• elle permet d'identifier des complexités qui ne diffèrent que par une constante multiplicative ("$4n$ et $5n$, c'est presque la même chose")
• elle permet d'ignorer les cas initiaux et autres phénomènes négligeables
• elle permet de simplifier les calculs de complexité

Propriétés

• si $f=O(h)$ et $g=O(h)$ alors $\alpha f+\beta g=O(h)$
• si $f=O(g)$ et $g=O(h)$ alors $f=O(h)$
• si $f=O(g)$ et $f'=O(g')$ alors $f\times f'=O(g\times g')$
• si $f=O(g)$ et $f'=O(g')$ alors $f+f'=O(|g|+|g'|)$

Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : $\log$, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...
Pour $n$ très grand : $1<\log(\log(n))<n^{\epsilon }<n<n^{c}<n^{\log(n)}<c^{n}<n^{n}<c^{(c^{n})}$
Avec $0<\epsilon <1$ et $c>1$.

---À compléter ? Par exemple, vous pouvez rajouter les fonctions $\log(n)$ et $n\log(n)$...---

Références

• "The C programming language", de Kernighan et Ritchie,
• « Le langage C », version française du précédent,
• le polycopié de Bernard Cassagne, disponible ici, au format html (en ligne) ou pdf,
• « Programmation C », un livre collaboratif sur le mode Wikipedia, disponible ici.