Antoine Gademer

Professeur d'informatique

28 05 2010

Notes de contrôle continue et du projet

Voici les notes du projet d'informatique S2 pour la classe 12.

Vous trouverez aussi les moyennes provisoires pour le LAB1414. (Pour tout réclamation, contactez moi par mail)

Pour l'évaluation, je ne peux que vous conseiller de bien réviser les cours et les TP que nous avons fait ensemble et d'être capable de corriger / écrire des fonctions ou des programmes répondant aux problèmes qui vous seront posés.

Bonne révisions !

Annexe(s) :
20 05 2010

Squellette du voyageur de commerce

Le fichier sera mis à jour au fur et à mesure :

 #include<stdio.h>
 #include<stdlib.h>
 #include<time.h>
 #include<math.h>
 
 /* Compilation : gcc -Werror -g -lm main.c -o main.exe */
 
 #define NBVILLE 10
 #define XYMIN 0
 #define XYMAX 100
 
 /* Choisit aléatoirement une valeur entre A et B INCLUS */
 int randAB(int a, int b) {
 	return rand()%(b-a+1) + a;
 }
 
 /*Initialise aléatoirement les coordonnées des villes */
 void initCoord(int coordX[], int coordY[]) { /* A FAIRE */ }
 
 /*Permutation initiale du tour du voyageur*/
 /* On part du tour trié et on fait N permutation aléatoire */
 void initTour(int tour[]) { /* A FAIRE */ }
 
 /* Calcule la distance entre la ville v1 et v2 */
 /* Vous pourrez utiliser sqrt() */
 int distance(int v1, int v2, int coordX[], int coordY[]) {/* A FAIRE */ }
 
 /* Calcul la longueur totale du tour */
 int longeur(int tour, int coordX[], int coordY[]) { /* A FAIRE */ }
 
 /* Optimisation partielle */
 /* On fait N fois :      
  *   - On calcul la longeur du tour         
  *   - On choisit deux ville aléatoirement  
  *   - On echange ces deux villes           
  *   - On calcul la nouvelle longeur
  *   - Si la solution est moins bonne, 
  *          on rééchange les villes.
  */
 void optim_partielle(int tour[], int coordX[], int coordY[]);
 /* Plus proche voisin */
 /* 
  * Pour chaque ville
  *   on cherche la ville situé à la plus courte distance
  *      (pour tout les villes sauf la premier 
  *         on calcul la distance
  *         on verifie si la distance est minimal
  *         et on sauve l'indice de la ville) 
  *   on echange la ville suivante et la ville la plus proche dans le tour
  */
 void plusprochevoisin(int tour[], int coordX[], int coordY[]);
 
 
 
 int main() {
 
   /* Abscisses des villes */
   int coordX[NBVILLE];
   /* Ordonnées des villes */
   int coordY[NBVILLE];
 
   /* Ordre de passage du voyageur */
   int tour[NBVILLE];
   int i;
 
   /*Initialisation de l'aléa*/
   srand(time(NULL));
 
   /*Initialisation des coordonnées*/
   initCoord(coordX,coordY);
 
   /* Choix d'un tour non-optimal */
   initTour(tour);
 
   /* Affichage du tour */
   for(i=0; i < NBVILLE; i++) 
     printf("Ville n°%d (%d,%d)\n", tour[i], coordX[tour[i]], coordY[tour[i]]);
     
   /* Optimisation partielle */
   optim_partielle(tour, coordX, coordY);
     
   /* Plus proche voisin */
   plusprochevoisin(tour, coordX, coordY);
 
 }
19 05 2010

Projet 1A : fonction d'affichage et de transition progressive

Quelques fonction exemple pour les questions d'affichage progressif et de transition

 /* Fonction d'affichage type A MODIFIER */
 void light(int image[], int taille, int pourcent) {
 
 
   int c;
 
   /* Pour chaque case */
   for(c=0; c < taille; c ++) {
     /* Met une couleur en fonction du pourcentage d'avancement entre noir (0%) et blanc (99%) */
     image[c] = color(255*pourcent/99, 255*pourcent/99, 255*pourcent/99);
   }
 }
 
 /* Fonction qui permet l'affichage progressif */
 void affichage(int image[], int largeur, int hauteur) {
 
   /* Pourcentage d'avancement */
   int prct;
   /* Timer de temporisation */
   int timer;
   /* Initialisation de l'image resultat */
   int resultat[largeur*hauteur];
   
   /* Ouverture de la fenêtre */
   mini_open("Affichage", largeur, hauteur);
   
   /* De 0 à 100% */
   for(prct = 0; prct < 100; prct ++) {
   
         /* J'applique la fonction de transition */
   	light(resultat, largeur * hauteur, prct);
   
   	/* Affichage et Temporisation */
         for(timer=0; timer < 100; timer++) {
 	  mini_update(resultat);
         }
 
   }
   
   /* Fermeture de l'image */
   mini_close();
 }
 
 /* Fonction de transition d'une image à l'autre A MODIFIER */
 int mix(int resultat[], int image_depart[], int image_fin[], int taille, int prct) {
  
   int rouge, vert, bleu, c;
 
   /* Pour chaque pixel */
   for(c=0; c < taille; c ++) {
   
     /* Resultat dépend de l'image de départ, de celle de fin et du pourcentage d'avancement */
     if(prct < 50)
       resultat[c] = image_depart[c];
     else
       resultat[c] = image_fin[c];
   }
   
   /* Si la transition est finie (nécessaire pour le random) on retourne 1, 0 sinon */
   if(prct >= 100)
     return 1;
   else
     return 0;
 
 }
 
 /* Fonction qui permet la transition progressive d'une image à l'autre */
 void transition(int image_depart[], int image_fin[], int largeur, int hauteur) {
 
   /* Timer de temporisation */
   int timer;
   /* Initialisation de l'image resultat */
   int resultat[largeur*hauteur];
   /* Booleen, condition d'arret */
   int fini = 0;
   /* Pourcentage d'avancement */
   int prct = 0;
   
   /* Ouverture de la fenêtre */
   mini_open("Transition", largeur, hauteur);
   
   /* Tant que la condition d'arret n'est pas atteinte */
   while(fini == 0) {
   
         /* On applique la fonction de transition */
   	fini = mix(resultat, image_depart, image_fin, largeur * hauteur, prct);
   	
   	/* Le pourcentage de progression avance */
   	prct += 1;
   
         /* Affichage et Temporisation */
         for(timer=0; timer < 100; timer++) {
 	  mini_update(resultat);
         }
 
   }
   
   /*Fermeture de la fenêtre */
   mini_close();
 }
18 05 2010

Bonus : image alternative

Voici une image PPM alternative pour le projet de 1A, ainsi qu'un petit script BASH qui vous permettra de transformer n'importe qu'elle image en une image PPM au format attendu.

Have fun.

Annexe(s) :
12 05 2010

Suite du projet

Pour ceux qui sont en avance, la suite du projet :

Annexe(s) :
12 05 2010

Bouée de sauvetage

Pour ceux qui sont un peu perdu avec la section 3.1

 #include<stdio.h>
 #include "libgmini.c"
 
 /* Créer la couleur à partir des composantes */
 int color(unsigned char red, unsigned char green, unsigned char blue) {
 	return red * 65536 + green * 256 + blue;
 }
 
 /* Récupère la composante rouge */
 unsigned char getRed(int color) {
 	return color/65536;
 }
 
 /* Récupère la composante vert */
 unsigned char getGreen(int color) {
 	return (color%65536)/256;
 }
 
 /* Récupère la composante bleu */
 unsigned char getBlue(int color) {
 	return color % 256;
 }
 
 /* Récupère la hauteur et la largeur de l'image */
 void sizePPM(char *name, int * p_width, int * p_height) {
 FILE * fp = NULL;
 char line[256];
 
 fp = fopen(name,"r"); /* Ouverture du fichier */
 if (fp == NULL)
   printf("File %s not found !\n",name);
 
 fgets(line,256,fp); /* On saute la ligne P3 */
 fgets(line,256,fp); /* On saute la ligne de commentaire */
 
 fscanf(fp, "%d %d", p_width, p_height); /* On lit la hauteur et la largeur*/
 
 fclose(fp); /* On ferme le fichier */
 
 }
 
 /* Charge l'image dans le tableau */
 void loadPPM(char* name, int image[]) {
 FILE * fp = NULL;
 char line[256];
 int width, height, depth;
 int col, row;
 int red, green, blue;
 
 fp = fopen(name,"r"); /* Ouverture du fichier */
 if (fp == NULL)
   printf("File %s not found !\n",name);
 
 fgets(line,256,fp); /* On saute la ligne P3 */
 fgets(line,256,fp); /* On saute la ligne de commentaire */
 
 fscanf(fp, "%d %d", &width, &height); /* On lit la hauteur et la largeur*/
 fscanf(fp, "%d", &depth); /* On lit la profondeur */
 for(row = 0; row < height; row ++) /* Pour toutes les lignes */ 
 {
   for(col = 0; col < width; col ++) /* Pour toutes les colonnes */
   {
     fscanf(fp, "%d %d %d", &red, &green, &blue); /*On récupère les composantes*/
     image[row * width + col] = color(red, green, blue); /*On met l'information de couleur dans le tableau image */
   }
 }
 
 fclose(fp); /* On ferme le fichier */
 
 }
 
 
 
 int main() {
 
 int hauteur, largeur;
 
 /*Récupération de la hauteur/largeur */
 sizePPM("image-logoESIEA-ascii.ppm", &largeur, &hauteur);
 
 /*Déclaration du tableau qui contiendra l'image*/
 int image[largeur * hauteur];
 
 /* initialise l'image avec des pixels blancs */
 mini_initImage(largeur, hauteur, image);
 
 /*Chargement de l'image*/
 loadPPM("image-logoESIEA-ascii.ppm", image);
 
 /* ouvre à l'écran une fenêtre de dimension LxH */
 mini_open("Projet super-cool", largeur, hauteur);
 
 printf("press ESC to quit\n");
 
 while(1) {
 	// affiche à l'écran l'image avec (0;0) en haut à gauche tant que ESC n'est pas pressé
 	mini_update(image);
 }
 
 mini_close ();
 
 
 
 return 0;
 
 }
06 05 2010

Projet 1A 2009/2010 : Visualisation et Voyageur de commerce

Note pour les utilisateurs de PC personnel, l'archive pixels.tgz nécessite l'installation de paquet particulier :

 sudo apt-get install libx11-dev x11proto-xext-dev libxext-dev

Voici les fichiers du sujet :

Annexe(s) :
05 05 2010

TP 1A S2 - BONUS : ASCII ANIMÉ

Voici le sujet du TP :

Annexe(s) :
07 04 2010

Sujet Semaine d'éléction : TRON

Pour maintenir la motivation face à la concurrence du BDE, voici un sujet du tonnerre. :-)

Annexe(s) :
07 04 2010

Nouveau sujet : Dichotomie

Voici le nouveau sujet : Dichotomie

Annexe(s) :
07 04 2010

Contrôle continu de la classe 12

Voici la note actuelle de contrôle continue de la classe 12.

La note est calculé sur 4 exercices rendus (Fibbonacci, Compléments à 9, Compléments à 1, Compléments à 1 sur 32 bits). Chaque exercice a été noté sur 5 mais étant donné le temps limité les pondérations s'applique comme suit pour le calcul de la note : fib * 1 + c9 * 1,5 + c1 * 1 + c1_32 * 0,5 pour un total sur 20.

Vérifiez vos notes et venez me voir ensuite si vous pensez qu'il y a un oubli.

Annexe(s) :
06 04 2010

Fibbonacci, polynomes et complexités : corrigé

Voici le corrigé du TP (intitulé Karatsuba) concernant Fibbonacci sur des très grands entier représentés sous formes de polynomes.

Vous trouverez le fichier fibbonacci_polynomes.c qui contient le corrigé commenté des fonctions demandées en TP.

Vous trouverez aussi les fichiers calcul.sh et datation.sh qui permettent de calculer le temps d'exécution et l'occupation mémoire de votre programme.

Je le lance avec

 ./calcul.sh "./fibbonacci_polynomes.exe 2" log_optim.txt 150000

vous pourrez le lancer avec

 ./calcul.sh "./a.out" monlog.txt 150000

Vous trouverez aussi les images des courbes que j'obtiens à comparer aux vôtres.

Au travail !

Annexe(s) :
31 03 2010

S2 - Représenter la complexité

Cliquez pour avoir l'image en grand

On voit sur l'image ci-dessus la complexité de l'implémentation naive du calcul Fibbonacci sur des très grands entier représenté par des polynomes.

En rouge, l'évolution du temps d'exécution, qui suit une progression exponentielle dès le rang 30 ! On observe aussi une consommation de mémoire (en vert) croissant rapidement.

Cliquez pour avoir l'image en grand

On voit sur l'image ci-dessus la complexité comparée de deux implémentations du calcul Fibbonacci sur des très grands entier représenté par des polynomes.

Les mesures sont faites pour les rangs de la suite entre 0 et 200 000. (Fib(200 000) a environ 40 000 chiffres !)

En croix rouges, l'évolution du temps d'exécution de l'algorithme itératif, qui suit une progression en o(n²) en vert. On observe par contre que la consommation de mémoire est faible et constante.

En croix bleues, l'évolution du temps d'exécution de l'algorithme récursif (gérant la parité du rang), qui suit plus ou moins une progression en o(n) en magenta. On observe que la consommation de mémoire augmente doucement par palliers.

Vous trouverez, joins à ce billet, les fichiers log et gnuplot qui on servi à tracer ces courbes.

Annexe(s) :
17 03 2010

S2 - TP n°2 Karatsuba

Voici le nouveau TP.

Annexe(s) :
03 03 2010

Dater l'execution d'un programme à la microseconde

Voici un petit programme bash pour tester le temps d'execution de votre programme quand la commande time ne suffit plus

 time ./prog

Pour l'utiliser : 1. Télécharger le 2. Rendez le executable

 chmod +x datation.sh

3. Lancer le :

 ./datation.sh ./prog

4. Enjoy

Annexe(s) :