Structures de données IFT-2000 Abder Alikacem Introduction Semaine 1 Département d’informatique...

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Introduction Semaine 1

Département d’informatique et de génie logiciel

Édition Septembre 2009

! +

Plan

• Introduction• Analyse et abstraction• Modélisation

• Types de données abstraits• Spécifications• Implantation

• Plan du cours et modalités

Viny, la mascotte du cours!!Viny, la mascotte du cours!!

Conventions de représentation

Conventions de représentation de l’information(Interface):• integer idem pour tout programme sur un même ordinateur,

utilisant le même langage: int x;

Conventions d’utilisation (Opérateurs):• integer pas de décimales: x = 5/2;

D’une manière générale, pour définir un type de données, on a besoin dedécrire éventuellement:

• son nom (syntaxe);• sa sémantique;• son domaine de valeurs;• ses contraintes;• etc..

+ son comportement: { opérateurs }

Interface publique

Conventions de représentation

0 0 00

0 0 ±00

± •bit de signe•complément à 1: C1

•complément à 2: C2

Structuration de base = types simples (ex. le type int)

• convention de représentation interne (Modèle interne):

• int x, y;

• choix de représentation interne {implantation de l’interface}

Modèles internes

Conventions transparentes

Transparence des types de base:

00011101010101000101010101010010101010000111111100000101….

0 0 0 1 1

int x;

y = x++;

Besoin de types plus complexes!

• Caractéristiques d’un système sont souvent difficiles à être représentées directement dans un ordinateur.

• Existences de distances conceptuelles.

• Comment réduire ces distances?• Analyse (décomposition descendante) du domaine• Abstraction (à partir des objets informatique de base jusqu’à une

possible représentation du réel)•Encapsulation• Masquage d’information

• Cacher les secrets d’une implémentation.

C’est la modélisation!

Modélisation:

• Réalité Modèle

Construction d’un modèle

Modélisation:

• Réalité Modèle

Construction d’un modèle

Modélisation:

• Réalité Modèle

Construction d’un modèle

x

Modélisation:

• Réalité Modèle

Construction d’un modèle

x

Modélisation:

• Réalité Modèle

float x;

Construction d’un modèle

struct Pt { float x; float y; float z; } ;

float x;

x

Modélisation:

• Réalité Modèle

Construction d’un modèle

struct Pt { float x; float y; float z; } ;

struct Plan { pt p[4]; } ;

x

Modélisation:

• Réalité Modèle

float x;

Construction d’un modèle

struct Boite { Plan pl[6]; };

struct Pt { float x; float y; float z; } Pt;

x

Modélisation:

• Réalité Modèle

float x; struct Plan { Pt p[4]; };

Construction d’un modèle

struct Pt { float x; float y; float z; };

Boite b1;

x

Modélisation:

• Réalité Modèle

float x; struct Plan { Pt p[4]; };

struct Boite { Plan pl[6]; };

Construction d’un modèle

Modélisation = transfert

Boite b1;…b1.rotation(b1,45);…

Modélisation:

• Réalité Modèle

Création d’un modèle

struct boite { Plan pl[6]; };

struct Pt { float x; float y; float z; };

struct Plan { Pt p[4]; };

float x;Boite b1;…b1.rotation(b1,45);…

Modélisation:• modèle près de la réalité• modèle distant des détails d’implantation

typedef struct { plan pl[6]; } boite;

typedef struct { float x; float y; float z; } pt;

typedef struct { pt p[4]; } plan;

float x;Boite b1;…b1.rotation(b1,45);…

boîte noire

Modélisation:• modèle près de la réalité• modèle distant des détails d’implantation

Les types de données abstraites (TDA)

Programme indépendant de l’implantation du type Boite:

Boite b1, b2, b3;b1.creer(…);b2 = b1;b3 = b2;b1.rotation(45);b2.poseSur(b3);

Boite est alors un type abstrait!

Les types de données abstraites (TDA)

• est défini uniquement• par ses conventions d’utilisation• par le comportement des objets de ce type (i.e., par les méthodes applicables sur les objets de ce type)

• ne décrit pas le modèle d’implantation choisi

• sert à isoler les programmes des données (structuration interne)• crée une indépendance des applications face aux modèles d’implantation (continuité de la programmation structurée)

Incarnation d’un TDA

Une incarnation (une réalisation, une mise en œuvre, une « implémentation ») d'un TDA se concrétise par :

•L’interface (fichier .h)•Et la définition (i.e le code) des opérations primitives dans un langage particulier

L’implémentation (fichier .cpp)

les programmeurs ont deux casquettes:• le concepteur du TDA qui met en œuvre les primitives et doit connaître la représentation interne adoptée. On parle de programmation de bas niveau.• l'utilisateur du TDA qui ne connaît que les services (les opérations) et n'accèdent jamais à la représentation interne. On parle de programmation de haut niveau.

//Fichier ModeleImplantationListe.h#ifndef _LISTEC__H#define _LISTEC__H#define MAX_LISTE 100typedef enum {FAUX, VRAI} Bool;

typedef struct{

int tab[MAX_LISTE];int cpt;

} Liste; #endif

//Fichier Liste.h#include "ModeleImplantationListe.h"#include "CodesErreur.h"

Liste initListe(int * err);/* */int tailleListe(Liste l, int *err);/* */Bool estVideListe(Liste l, int *err);/* */Liste ajouterListe(Liste l, int x, int pos, int *err);/* */// etc..

// Fichier Liste.h#include <iostream>

#ifndef _LISTEC__H #define _LISTEC__H

class Liste {public: Liste(); //constructeur ~Liste(); //destructeur void ajouter (int x, int pos)

throw(range_error, length_error); int taille() const ; bool estVide() const; //etc…private: static const int MAX_LISTE = 100; int tab[MAX_LISTE]; int cpt;

};#endif

Interface en C++

Interface en C

Exemple d’une interface d’un type abstrait

C’est la partie publique

main()

//Fichier ModeleImplantationListe.h#ifndef _LISTEC__H#define _LISTEC__H#define MAX_LISTE 100typedef enum {FAUX, VRAI} Bool;

typedef struct{

int tab[MAX_LISTE];int cpt;

} Liste; #endif

// Fichier Liste.h#include <iostream> using namespace std;

#ifndef _LISTEC__H#define _LISTEC__H

class Liste { public: … //l’interface publique private: static const int MAX_LISTE = 100; int tab[MAX_LISTE]; int cpt; };#endif

En C++En C

Modèle d’implantation

C’est la partie privée

Exemple

Exemple d’une implémentation en C

#include "Liste.h« 

/* Commentaires d’implémentation de la fonction*/Liste ajouterListe (Liste l, int x, int pos, int *err){ if (l.cpt >= MAX_LISTE)

{/* La liste est pleine. */*err = PAM;return l;

}/*A: La liste n'est pas pleine */

if ((pos < 1) || (pos > (l.cpt + 1))){

/* Le paramètre pos est invalide */*err = PERR;return l;

}

/*A: pos >= 1 et pos <= taille de la liste + 1 */*err = OK;

//etc...return l;

}

Exemple d’une implémentation en C++

void Liste::ajouter (int x, int pos) throw(out_of_range, length_error){

if (cpt==MAX_LISTE) throw length_error("Ajouter:La liste est pleine");

if (pos < 1 || pos > this->taille() +1) throw out_of_range("Ajouter:Position d'ajout erronée"); //etc…}

#include "Liste.h"

int main(){ Liste l;

try //on essaie un ajout{l.ajouter(1,1); l.ajouter(2,2); l.ajouter(4,8); // erreur..//…

} catch(exception& e) { cerr<<"ERREUR: " <<e.what(); …; } .... return 0;}

/** Commentaire style Doxygen * \fn void Liste:: ajouter (int x, int pos) * * \param[in] x Élément à ajouter * \param[in] pos Position où insérer l'élément * */

Un main de test:Fichier Main.cpp

#include "Liste.h"

Interface =

ensemble d’opérations ou servies fournies sur un type abstrait

= (conventions et contraintes + comportement)

={ prototypes des opérateurs} + spécifications formelles

donnéesprogramme

int x, y;

y = x + 1;

Spécifications d’une interfacemain()

Spécifications « langage C »

Exemple: ajout dans une liste ordonnée L L +i x

• prototype de la fonction implantant l’opérateur:• Liste ajouterListe(Liste l, int x, int pos, int *err);

• préconditions conditions devant être vraies au départ pour assurer le bon fonctionnement de l ’opérateur

• l ne doit pas être pleine et pos [1,|L|+1]

• postconditions conditions étant vraies (observables) après l’application (correcte) de l’opérateur

• l contient x et *err = OK si les préconditions sont respectées• l est inchangée sinon et

*err contient:PAM si L est pleine,PERR si pos [1,|L|+1]

• valeur retournée en output de l’application de l ’opérateur:• l mise à jour ou l inchangée en cas d'erreurs

Spécifications version dOxygen (dans une classe)// Le type Liste

class Liste{

public://L'interface...

/**

* \brief Ajouter un nouvel élément dans la liste

*

* \pre il y a assez de mémoire pour ajouter l'élément x

* \pre la position d'ajout, pos, est comprise entre 1 et |L|+1

*

* \post la liste comprend un élément de plus

* \post la liste est inchangée sinon

*

* \exception range_error si la position est erronée

* \exception length_error si pas assez de mémoire

*/

void ajouter(int x, int pos) throw(range_error, length_error);

...

private:

...//Modèle d'implantation

};

Fichier Liste.h

Objectifs du cours

Programmation des structures de données et des algorithmes qui les manipulent.

• Concepts : abstraction, généricité, encapsulation, programmation orienté objet

• Techniques : la manipulation des pointeurs, la gestion de la mémoire dynamique

Structures de données

•Listes, Piles, Files, Arbres, Graphes, Tables de dispersion

•Tris

Choix : Présentation sous forme de Types de Données Abstraits• Analyse d’algorithmes (notation asymptotique)• Écriture de programmes lisibles et efficaces (complexité)

Discussion sur le plan de cours

• Contenu du cours• Pré-requis• Évaluations• Apprentissage du langage C++• Compilateurs, OS• Notes de cours et le manuel recommandé• Site Web, liste de diffusion, forum, courriel• Laboratoires, autres exercices• SVN, dOxygen, Eclipse, VS 2008• Les équipes dans les TPs• Charge de travail• Conseils

•Méthode de travail•Utilisation du site Web du cours

Structures de données

IFT-2000

Abder AlikacemAbder Alikacem

Analyse d’algorithmesSemaine 1 (suite…)

Département d’informatique et de génie logiciel

! +

Édition Septembre 2009

Plan

Introduction Efficacité des algorithmes Analyse algorithmique Notation O (big-oh) Instruction Baromètre Comparaison entre les classes de complexité

Efficacité des algorithmes

Habituellement on mesure l’efficacité d’un algorithme par sa vitesse.

• C’est-à-dire la durée que met l’algorithme à produire ses résultats.

On veut savoir combien de temps cela prend de résoudre une instance de taille n du problème P:

• données(n) + Algorithme(P) ==> résultat(n).• temps mis ? (en microsecondes, cycles d’horloge, nombre

d’instructions exécutées, etc..)On prend en compte la taille n des données

Parfois, on considère aussi la mémoire nécessaire.

Efficacité des algorithmes

Approche empirique: mesure de performances.• essayer l’algorithme sur différents jeux de données bien

choisis.

Avantages: • résultats réalistes.

Inconvénients:• coûteux et long• dépend du processeur, de l’OS • dépend de l’implémentation

Efficacité des algorithmes

Approche algorithmique:• estimer le nombre de pas de l’algorithme en fonction de la taille

des données.

Avantages: • résultats généraux: on ne dépend pas du processeur, de l’OS ou de l’implémentation

• Estimation rapide et peu coûteux

Inconvénients:• prédictions parfois approximatives.

Dans notre cours, on va s’intéresser à l’approche algorithmique pour la détermination de l’efficacité d’un algorithme. Relevez qu’on parle souvent de complexité d’un algorithme lorsqu’on s’intéresse à son efficacité.

Approche algorithmique

Analyse détaillée :• Avantage :Très précise• Désavantage : Long à calculer

Solution: Analyse asymptotique du comportement de l’algorithme lorsque le(s) paramètre(s) de l’algorithme tendent vers l’infini:

• Avantage: Parfois facile à calculer• Désavantage: Parfois moins précis

Notation O (big-oh)

On Cherche une fonction simple qui dépend de la taille n de l’instance en entrée dans un algorithme qui résout un problème donnée et qui décrit la borne supérieure de la complexité de l’algorithme.

Pour déterminer la complexité d’un algorithme dans la notation O(), on doit d’abord identifier des opérations de base (instructions baromètres), puis trouver la fonction f(n) qui compte le combien de fois cette instruction baromètre est effectuée dans l’algorithme.

Nous verrons à partir d’un exemple qui suit comment déduire la

complexité d’un algorithme dans la notation O() à partir de la fonction f(n).

Exemple

void triSelection(int tab[MAXTAB], int n){

int PositionMin, temp, i, j;

for (i = n-1; i > 0; i--){

PositionMin = i;for (j = 0; j < i; j++){

if (tab[j] < tab[PositionMin]){

PositionMin = j;}

}temp = tab[i];tab[i] = tab[PositionMin];tab[PositionMin] = temp;

}}

void triSelection(int tab[MAXTAB], int n){

int PositionMin, temp, i, j;

for (i = n-1; i > 0; i--){

PositionMin = i; //b1for (j = 0; j < i; j++){

if (tab[j] < tab[PositionMin]){

PositionMin = j;}

}temp = tab[i];tab[i] = tab[PositionMin];tab[PositionMin] = temp;

}}

// i * a

//b2

Possible baromètre

Exemple

Exemple (suite)

for (i = n-1; i>0; i--)

{Coût b1 /* PositionMin = i */

Coût i*a; /* pour exécuter la boucle interne*/

Coût b2; /* pour l'échange de tab[i] et tab[PositionMin] */

}

Exemple (suite)Exemple (suite)

1

1

( ) ( )n

i

f n ai b

b = b1 + b2

1 1

1 1

( )n n

i i

f n a i b

( 1)( ) ( 1)

2

n nf n a n b

2( ) 2 2

a af n b n bn

Comportement de la fonction f(n) = an2 + bn + c quand n est très grand (n )

a = 0.0001724, b = 0.0004, c = 0.1

n f(n) an2 % du n2

125 2.8 2.7 94.7

250 11.0 10.8 98.2

500 43.4 43.1 99.3

1000 172.9 172.4 99.7

2000 690.5 689.6 99.9

Notation O(g(n)) (big-oh)

Pour un nombre n assez grand f(n) an2

Temps d'exécution de l’algorithme est donné parf(n) = an2 + bn + c

g(n) = n2

On dit que l'algorithme est en O(n2)

f(n)

1

log n

n2n2n

Notation O(g(n)) (big-oh)

Il y a différentes classes de fonctions qu’on peut exprimer dans la notation O() : O(1), O(n), O(n2), O(n3), O(log n), …

n

Exemple (suite)

1

1

( ) ( )n

i

f n ai b

b = b1 + b2

1 1

1 1

( )n n

i i

f n a i b

( 1)

( ) ( 1)2

n nf n a n b

2( ) 2 2

a af n b n bn

L’algorithme est en O(n2)

Exemple (suite et fin)

L’algorithme est en O(n2)

void triSelection(int tab[MAXTAB], int n){

int PositionMin, temp, i, j;

for (i = n-1; i > 0; i--){

PositionMin = i; for (j = 0; j < i; j++){

if (tab[j] < tab[PositionMin]){

PositionMin = j;}

}temp = tab[i];tab[i] = tab[PositionMin];tab[PositionMin] = temp;

}}

Le bon baromètre

int minimumOn2(int tableau[],int taille){ int i,j; for(i=0;i<taille;i++) { j=0; while(j<taille && tableau[i]<=tableau[j] ) {

j++; } if(j == taille) return tableau[i]; } return tableau[i];}

int minimumOn(int tableau[],int taille){ int i,min = tableau[0]; for(i=0;i<taille;i++) {

if( tableau[i]<min) min = tableau[i]; } return min;}

Algorithme #1

Algorithme #2

Exemple 2: chercher le minimum dans un tableau d’entiers

Autres exemples sur les boucles

void f(int n){

for(int i=0;i<n;i++) cout <<‘’Allo\n’’;}

Cet algorithme est en O(n)

void f(int n){

for(int i=0;i<n;i++)for(int j=0;j<n;j++)

cout << i << j << endl;}

Cet algorithme-ci est dans O(n²)

Autres exemples sur les boucles

void f(int n) {

for(int i=0;i<n;i++)for(int j=0;j<n;j++)

cout << i << j << endl;for(int i=0;i<n;i++)

cout << i << endl;}

Cet algorithme est en O(n²)

void f(int n){

for(int i=0;i<10000;i++)cout<<’’Allo\n’’;

}

Puisque son temps d’exécution ne dépend pas de n, même si la boucle est très longue, l’algorithme est en O(1). En effet, lorsque le temps d’exécution d’un algorithme ne dépend même pas du nombre d’éléments, ce temps est alors constant et il est dans O(1).

Autres exemples sur les boucles

void f(int n){

for(int i=0;i<5340*n;i++)cout <<‘’Allo\n’’;

}

Puisque qu’il faut faire abstraction de toute constante multiplicative, cet algorithme est en O(n).

void f(int n){

for(int i=0;i<n;i++)for(int j=0;j<i;j++)

cout <<‘’Allo\n’’;}

L’algorithme est en O(n²).

Annexe mathématique

• Les séries simplifiées• Rappel sur les logarithmes• Règles de simplification dans la notation O()

En plus, voir document RappelsMath.pdf sur le site Web du cours.

51

Exercice. Analyse d’algorithmes

1- En choisissant l’opération d’affectation comme baromètre, déterminez la fonction f(n) qui exprime le temps de calcul pour l’algorithmes suivant.

2- Déduisez sa complexité dans la notation du O().  

s 0 i 1 Tant Que i ≤ n début s s - 1 j 1

Tant Que j ≤ i début

s s + 2 j j+1

fin i i + 1 fin

Laboratoire de la semaine

Soit a1, a2, ..., an, une séquence d’entiers possiblement négatifs.

On veut trouver le couple (i,j) tel que la somme des ak, k=i, ..., j est maximale, avec 1≤ i ≤ j ≤ n

a1 a2 a3 a4 ... an-3 an-2 an-1 an

« Maximum Subsequence Sum Problem »

Laboratoire de la semaine

Il s’agit d’évaluer en termes de notation asymptotique quelques solutions proposées à cette problématique. Il s’agit également de comparer le temps d’exécution de ces solutions pour, d’abord, confirmer la complexité de chacune d’elles et, ensuite, de constater l’énorme différence en temps de calcul qui peut exister entre une solution naïve et une solution plus élaborée.

« Maximum Subsequence Sum Problem »

Fichiers fournis• ModeleTranchesMax.h (définitions de types + inclusions de librairies C++• TrancheMax.h (prototypes des fonctions à implanter)• Algorithmes.cpp (à compléter par l’implémentation des fonctions demandées)• Main.cpp (le programme principal: appel des fonctions implémentant les algorithmes proposés pour déterminer la tranche max dans un tableau d’entiers, mesure du temps d’exécution de chaque algorithme pour des fins de comparaison).

Laboratoire de la semaine

Tous les fichiers fournis dans ce laboratoire ont été documentés avec les balises de Doxygen. Afin de vous familiariser avec, nous vous demandons de compiler tous les fichiers avec cet outil afin de générer la documentation attendue. Nous vous fournissions le fichier de configuration sdd.doxyfile pour cette fin.

Vous trouverez un tutoriel pour utiliser Doxygen (avec le Doxywizard ou bien dans Eclipse si vous utilisez cet IDE) dans la section Travaux Examen/Travaux Pratiques/Doxygen sur le site Web du cours).

Utilisation de Doxygen (génération de documentations automatisée)

L'interface...

/**

* \brief

*

* \pre

* \pre

*

* \post

* \post

*

* \exception

* \exception

*/

Implémentation

...

/**

* \fn

*

* \param[in]

* \param[out]

*

* \return

Section Documentations/Normes de programmation:

•Resume.h (à propos des commentaires Doxygen)

En-tête de fichiers

/**

* \file Liste.cpp

* \brief Le code des opérateurs de la liste.

* \author Abder

* \version 0.1

* \date septembre 2009

*

* Implémentation de la classe générique Liste.

*

*/

Résumé des balises Doxygen utiles pour le cours

Laboratoire de la semaine

Éléments du C++ à découvrir lors de ce laboratoire

• Les entrées/sorties• #include <iostream> // Librairie pour les entrées/sorties• using namespace std;

• ne jamais mettre cette instruction dans les fichiers .h• cin (stdin), cout (stdout), • << (printf du C), >> (scanf du C), endl (saut de ligne)

• Les structs: différence entre le C et le C++ struct SousSequence { int debut; /*!< Indice de début de la sous-séquence dans Sequence*/ int fin; /*!< Indice de fin*/ int somme; /*!< La somme (max) de la sous-séquence*/ };

En C++, le typedef est inutile…

Laboratoire de la semaine

Éléments du C++ à découvrir lors de ce laboratoire

• Gestion des exceptions

• #include <stdexcept> • Le mécanisme try…catch..throw…(voir fichier Main.cpp)

int main(){

... try {

... affiche(trancheMax3(seq, tailleSeq)); ...

} catch (invalid_argument& ia) { cerr << "Invalid argument: " << ia.what() << endl;

} ... return 0;}

Laboratoire de la semaine

Éléments du C++ à découvrir lors de ce laboratoire

• Gestion des exceptions

• Gestion des exceptions dans une fonction…(fichier Algorithmes.cpp)

SousSequence trancheMax1(Sequence a, int taille){ … if (taille<=0) throw invalid_argument("TrancheMax1: argument invalide\n"); …

}

La classe invalid_argument fait partie de <stdexcept>

Éléments du C++ à voir courant la semaine

•Du C au C++•Les entrées/sorties (important pour cette semaine)•L'espace de nommage•Les types vector et string  

Voir Section « C++ primer » dans le semainier sur le site Web

Le point sur les normes de programmation

Normes de programmation:

• Commentaires d’interface• Commentaires d’implémentation• Découpage logique d’un programme• La gestion des exceptions• Style de programmation

Voir sur le site Web du cours, section Documentations/Normes de programmation:

•NormesProgrammation.pdf•Resume.h (à propos des commentaires Doxygen)