les transparents

On distingue classiquement deux grandes catégories de données :

• données quantitatives:
  • numérique entier ou réel, discrètes ou continues, bornées ou non. ex: poids, taille, âge, taux d’alcoolémie,…
  • temporel : date, heure
  • numéraire
  • etc…
• données qualitatives:
  • de type vrai/faux (données booléennes). ex: marié/non marié, majeur/non majeur
  • de type appartenance à une classe. ex: célibataire/marié/divorcé/veuf, salarié/chômeur/retraité etc…
  • de type texte (autrement dit “chaine de caractères”). ex: nom, prénom, ville,…

<!-- <note> Parfois, la distinction entre quantitatif et qualitatif n’est pas nette: * Possibilité d’ordonner les chaînes de caractères (de type nom/prénom) par ordre alphabétique * On peut “traduire” une chaîne de caractères en entier (son code ASCII) * Les valeurs logiques vrai/faux sont souvent traduites en valeurs “entières” 1/0 * Plus subtil : il est possible de définir des ordres partiels, des hiérarchies sur des données qualitatives : * regroupement par secteur géographique * notion de distance (géographique et temporelle) entre catégories * Inversement, il est possible de rendre qualitatif des données quantitatives en réalisant des classes. Exemple : tranches d’âge 0-25/25-35/35-55/+55, mineur/majeur, recalé/passable/AB/B/TB etc... </note> --!>

• Les données manipulées par un programme:
  • sont codées sous un format binaire,
  • correspondant à un des types informatiques que vous connaissez déjà :
    • entier,
    • chaîne de caractères,
    • réel simple ou double précision etc…
  • ce qui implique en particulier :
    • une précision finie,
    • éventuellement des contraintes de place (le nom ou le prénom ne pouvant pas dépasser n caractères, les entiers pouvant être choisis sur un intervalle fini etc…).

<!-- <note> **Types de données standards**   Les principaux types de données SQL sont les suivants : * ''CHAR (longueur)'' : Ce type de données permet de stocker des chaînes de caractères de longueur fixe. ''longueur'' doit être inférieur à 255, sa valeur par défaut est 1. * ''VARCHAR(longueur)'' : Ce type de données permet de stocker des chaînes de caractères de longueur variable. ''longueur'' doit être inférieur à 2000, il n'y a pas de valeur par défaut. * ''TEXT'' : un texte de longueur quelconque * ''INTEGER'' : entier (codage classique su 4 octets) * ''NUMBER(longueur)'' : entier naturel, ''longueur'' précise le nombre maximum de chiffres significatifs stockés * ''DECIMAL (longueur,[précision])'' : Le type de données decimal peut stocker jusqu'à 38 chiffres pouvant tous se trouver à droite de la virgule décimale. Il stocke une représentation exacte du nombre décimal, sans aucune approximation de la valeur stockée. ''longueur'' précise le nombre maximum de chiffres significatifs stockés (par défaut 38), ''précision'' donne le nombre maximum de chiffres après la virgule (par défaut 38), sa valeur peut être comprise entre -84 et 127. Une valeur négative signifie que le nombre est arrondi à gauche de la virgule. * ''FLOAT'' : nombre à virgule flottante simple précision * ''DOUBLE'' : nombre à virgule flottante double précision * ''DATE'' : ce type de données permet de stocker des valeurs de type date. Format : '''2005-12-12''' (12 décembre 2005) * ''TIME'' : ce type de données permet de stocker des valeurs de type heure. Format : '''10:45:02''' (10 h 45 min 2 s) * ''DATETIME'' : donnée de type date-heure. Format : '''2005-12-12 10:45:02''' (12 décembre 2005, 10 h 45 m 02 s) * ''TIMESTAMP'' : donnée de type date-heure (correspond à un stockage plus ‘compact’ que le type ''DATETIME'') </note> -->

  x = 'a'

• x une variable de type caractère
• a la valeur numérique (encodé):

• • Codage ASCII :
    • codage de symboles du clavier numérique.
    • Le nombre de symboles étant inférieur à 256, on le code sur un octet : 2⁸ (= 256) valeurs différentes
  • Codage UTF-8 :
    • codage universel qui permet entre autre de coder les accents
  • Codage latin-1 (caractères latins étendus)
  • etc…

code = ord('/')
print(code)

code = ord('😃')
print(code)

print(chr(233))
print(chr(119070))

Chaîne de caractère :

s = "bonjour"

• s est une variable
• "bonjour" est une séquence de caractères
  • "chaîne" de caractères : type string en anglais
  • assimilable à un tableau de caractère :

for c in s :
  print (c)

Affiche :

b
o
n
j
o
u
r

Le programme affiche les caractère 1 par 1, c’est une "chaîne" de plusieurs caractères individuels.

Donnée texte

Un texte, au même titre qu'un mot, est une chaîne de caractères (dont la longueur est définie par la longueur de la séquence de caractères qui définissent le texte, ponctuations, espaces et caractères de retour à la ligne compris).

Codage du texte

L'ensemble des messages possibles peut être réduit à l'ensemble des entiers naturels. En effet, chaque caractère d'un texte peut être traduit en entier en interprétant le code binaire correspondant comme un entier.

Pour traduire une chaîne de caractères en entier, il faut "construire un nombre" à partir de chaque caractère de la chaîne en prenant en compte sa position.

• ainsi, dans le système décimal, la position du chiffre dans le nombre définit à quelle puissance de 10 il appartient (unité, dizaines, centaines, etc…) Le chiffre le plus à gauche a la puissance la plus élevée et celui le plus à droite la puissance la plus faible.
• Si on suppose, pour simplifier, que chaque caractère est codé par un entier entre 0 et 255 (soit le code ASCII "étendu"), alors toute séquence de caractères (de claviers européens) exprime un nombre en base 256.
  • Un tel nombre s'appelle un "bytestring" en python.
  • Il existe une fonction encode qui effectue une telle traduction
    • Exemple :

s = 'paul.poitevin@centrale-marseille.fr'
b = s.encode()

Un nombre en base 256 est difficile à lire et interpréter. On le traduit en base 10 :

i = int.from_bytes(b, byteorder='big')
print("i =", i)

Ce qui donne :

i = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058

• Bases de textes : ensemble constitué de plusieurs textes
  • Bases de documents,
    • Dossiers contenant des documents
    • Collections de livres (électroniques)
    • → 10 - 10⁴
  • Contenus en ligne (descriptifs de films, articles de journaux, descriptifs de produits.)
    • → 10⁵ - 10⁶
  • Ensemble du web (les pages web, en tant que telles, peuvent être considérées comme du texte mis en forme par du html).
    • → 10⁹
  • Messageries, Blogs, Forums :
    • 10³ - 10⁶

• → Recherche d’un terme : “artichaud”
• → Recherche d’un motif (expression régulière) : une adresse email, une URL, un expéditeur, un numéro tel

• temps de réponse des algorithmes :
  • l’utilisateur classique veut attendre moins de 2 à 3 secondes.
  • Sur des bases extrêmement grandes (type recherche web), il faut donc être très performant pour atteindre ces temps de réponses.
• Stockage des données :
  • intégralité des textes ou simple descriptif/résumé?
  • Les moteurs de recherche par exemple ne stockent aucune page web, ils ne stockent que des index et des références.

Un document texte pourra être décrit soit comme :

• une séquence de caractères (lettres)
• une séquence de termes (mots)

Recherche simple

d : document de taille m On cherche un algorithme qui retourne toutes les occurrences (position dans le doc) d’un certain terme t (de taille k<m)

t = "ami"

d :

"Les amis de mes amis sont mes amis."
     ^           ^             ^    
     4           16            30      

• → La position de la première occurrence du terme t :
• → Les positions de toutes les occurrences du terme t :
• Complexité : $O(m \times k)$

on note d le texte et t le motif recherché dans le texte

Algo : recherche_simple 
Données : d, t : chaînes de caractères
Début
    n = len (d)    
    m = len (t)
    i <-- 0
    tant que i < n - m:
        j <-- 0
        tant que j < m et d[i+j] = t[j] :
            j += 1
        si j == m :
           retourner i
        sinon :
           i <-- i + 1
Fin

Remarque : Il peut être nécessaire de vérifier que le terme est précédé et suivi par les caractères d’espacement pour éviter de détecter les mots dont le mot recherché est préfixe ou suffixe.

Cette approche a un inconvénient : après une comparaison infructueuse, la comparaison suivante débutera à la position i + 1, sans tenir aucun compte de celles qui ont déjà eu lieu à l'itération précédente, à la position i.

Algorithme de Knuth-Morris-Pratt

L'algorithme de Knuth-Morris-Pratt examine d'abord la chaîne t et en déduit des informations permettant de ne pas comparer chaque caractère plus d'une fois.

• On suppose qu'on peut tester si un caractère c appartient au motif t en temps constant
• Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif t.
• On commence par chercher la position i = m - 1
• On inspecte la chaîne d de i à i - m décroissant, et on s'arrête au premier caractère commun (i.e. j⇐ i t.q. d[i-j] appartient à t)
• Soit c = d[i-j] le caractère commun
• On note k la position de la dernière occurrence de c dans t[:m-j-1]
• Le décalage est égal à m - 1 - j - k
• Si on ne trouve rien, le décalage vaut m

RECHERCHE DE CHAINES CODEES EN MACHINE
CHINE
     CHINE
          CHINE
             CHINE
              CHINE
                   CHINE
                     CHINE
                          CHINE
                               CHINE
                                 CHINE
RECHERCHE DE CHAINES CODEES EN MACHINE

Algo : recherche améliorée (Knuth-Morris-Pratt)
Données : d, t : chaînes de caractères
Début:
    n = len (d)    
    m = len (t)
    i <-- m - 1
    tant que i < n :
      # PRE-TRAITEMENT
      j <-- 0
      tant que j < m  - 1:
        c = d[i - j]  
        si c appartient à t[:m-j-1]
           k <-- dernière_occurrence(c, t[:m-j-1])  
           decalage <--  m - 1 - j  - k
           break
        sinon
           j += 1  
      si j == m - 1:
         decalage <-- m
      # TRAITEMENT
      j <-- 0
      tant que j < m :
         si t[m - j - 1] = d[i - j]
            j += 1
         sinon
            break
      si j = m:
        retourner i - m + 1          
      # DECALAGE      
      i <-- i + decalage      
    retourner -1 
Fin

Lecture séquentielle des caractères :

"Les amis de mes amis sont mes amis."
 ^            
 position initiale de la tête de lecture

• Il ne faut compter que les debuts de mots
• Un début de mot est un caractère alphanumérique :

{a,à,ä,b,c,ç,d,e,é,è,ê,ë,...,z,A,B,C,...,Z,1,2,3,...,0}

• Tout ce qui n'est pas alphanumérique est un caractère séparateur

{!,#,$,%,&,",',...}

• Autrement dit on compte les couples (caractère séparateur, caractère alphanumérique)
  • remarque : le début de chaîne compte comme un caractère séparateur

remarque : pour extraire la liste des mots présents dans le texte, on doit identifier les débuts et les fins de mots :

• un début de mot est un couple (sep., alphanum.)
• une fin de mot est un couple (alphanum., sep.)

Algo : compte-mots
Données :
  - d : chaîne de caractères
Début:
nb_mots <-- 0
sep <-- Vrai
pour tout c dans d:
    si sep est Vrai et c est alphanumérique:
        sep <-- Faux
        nb_mots <-- nb_mots + 1
    sinon si sep est Faux et c est séparateur:
        sep <-- Vrai
retourner nb_mots
Fin

Code équivalent : compter les mots à l'aide d'un automate fini:

def compte_mots(d):
    state = 0
    cpt = 0
    for i in range(len(d)):
        if state == 0 and is_alpha(d[i]):
            state = 1
            cpt += 1
        if state == 1 and is_sep(d[i]):
            state = 0
    return cpt

Présentation: un automate fini décrit les différentes étapes d'un calcul sous la forme d'un graphe orienté.

• les sommets du graphe sont les états. Un état identifie une étape de calcul. L'ensemble des états représente la mémoire (finie) de l'automate. Il existe un état initial, qui est celui dans lequel l'automate démarre au début du calcul.
• les arêtes représentent les transitions d'état. Un transition correspond à l'exécution d'un calcul élémentaire.

Pour réaliser des calculs, on a besoin d'opérandes. Les opérandes sont lus séquentiellement en entrée de l'automate. Ils obéissent à un certain alphabet (ou ensemble de symboles, …) $\Sigma$.

Enfin, des résultats de calcul sont produits en sortie de l'automate.

Plus concrètement, à chaque symbole lu en entrée, l'automate consulte une table des symboles acceptés à partir de l'état courant. Si le symbole est accepté, l'automate effectue la transition d'état, et produit une sortie (par exemple incrémenter le compteur de mots). Dans le cas contraire, il s'arrête.

Définition:

Un automate fini est défini par :

• un alphabet d'entrée $\Sigma$ (symboles acceptés)
• un alphabet de sortie $\Sigma$'
• un ensemble (fini) de sommets : $S$
• un ensemble fini d'arêtes : $A : S \times \Sigma \rightarrow S \times \Sigma'$ qui a tout couple (état, symbole d'entrée) associe un couple (état, symbole de sortie)
• un état initial $s_0 \in S$

L'état initial et la séquence des symboles lus définit la séquence de symboles produits en sortie (le résultat du calcul)

La famille des automates finis définit une classe de calculs (l'ensemble des calculs réalisables par des automates finis):

• séquences
• boucles et branchements conditionnels

Mais pas :

• appels récursifs

remarque: il existe des automates de calcul plus puissants :

• automates à piles (calcul récursif)
• machines de Turing et machines de Turing universelles (calcul sur des automates)

permettant d'implémenter des calculs plus complexes

De manière plus générale recherche d’expressions peut être effectuée à l’aide d’automates finis non déterministes.

• Parmi les états on distingue les états initiaux et terminaux.
• Il existe (parfois) plusieurs transitions possibles pour un même symbole lu
• Lorsque l'automate s'arrête, on regarde si l'état est terminal. S'il est terminal, le mot est accepté (autrement dit le motif est "reconnu")

Remarque : pour tout automate fini non déterministe A, il existe un automate fini déterministe A′ qui reconnait le même langage (plus compliqué à écrire).

Représentation graphique :

• les états dans des cercles,
• l’unique état initial par une flèche pointant sur un état,
• les états terminaux par un double cercle concentrique sur l’état.
• Les transitions d’état quant à elles sont représentées par une flèche allant de l’état de départ jusqu’à l’état d’arrivée indexée par le caractère (ou le groupe de caractères) autorisant la transition.

Lecture séquentielle des caractères :

"Les amis de mes amis sont mes amis."
 ^            
 position initiale de la tête de lecture

ab
bab
abab
bbab
aabab
abbab
babab
bbbab
aaabab
etc..

Exemples:

• Reconnaître un nombre entier : +4, -455, 1024, 0

• Reconnaître un nombre réel :
  • TODO

Remarques :

• Les classes d'expressions qui peuvent être reconnues par un automate fini sont appelées des expressions régulières
• En python, les expressions régulières s'expriment à l'aide d'une syntaxe spécifique à l'aide de la librairie re

Traduction de l'automate non déterministe précédent sous forme d'expression régulière :

[ab]*ab

Remarque : les langages qui peuvent être reconnus par des expressions régulières sont appelés les langages réguliers.

Exemples de langages non réguliers:

• reconnaître les palindromes
• reconnaître une expression arithmétique
• vérifier la syntaxe d'un code informatique

Définition : Il s’agit d’une syntaxe “condensée” de description d’automates finis permettant de reconnaître des motifs dans un texte.

En Python, les expressions régulières sont implémentées dans la librairie re

import re
 
d = "Les astronautes de la mission Gemini 8 sont désignés le 20 septembre 1965 : Armstrong est le commandant et David Scott le pilote. Ce dernier est le premier membre du groupe d'astronautes à recevoir une place dans l'équipage titulaire d'une mission spatiale. La mission est lancée le 16 mars 1966. Celle-ci est la plus complexe réalisée jusque-là, avec un rendez-vous et un amarrage du vaisseau Gemini avec l'étage de fusée Agena et une activité extravéhiculaire (EVA) qui constitue la deuxième sortie américaine et la troisième en tout, réalisée par Scott. La mission doit durer 75 heures et le vaisseau doit effectuer 55 orbites. Après le lancement de l'étage-cible Agena à 15 h 00 UTC, la fusée Titan II GLV transportant Armstrong et Scott décolle à 16 h 41 UTC. Une fois en orbite, la poursuite de l'étage Agena par le vaisseau Gemini 8 s'engage."
 
liste_termes = re.findall(r"([1-9]\d*|0)", d)

• a : le caractère a
• [ab] : le caractère a ou le caractère b
• [a-z] : n'importe quel caractère minuscule entre a et z
• [^a] : n'importe quel caractère sauf le caractère a
• : le caractère espace
• \n : le caractère "passage à la ligne"
• . : n'importe quel caractère
• \. : le caractère "." uniquement
• [1-9] : un chiffre entre 1 et 9
• \w : n'importe quel caractère alphanumérique
• \s : n'importe quel caractère d'espacement
• \d : n'importe quel chiffre

Def : une expression est définie comme une suite de transition. Le mot est accepté lorsque la suite de transitions est respectée

Exemple :

r"chal[eu]t"

accepte chalet et chalut

r"\w\w\w"

accepte tous les mots de 3 lettres

Branchements et Récursion

• Les parenthèses permettent :
  • de factoriser une expression (qui peut alors être traitée comme une transition)
    • (artichaud)
  • de définir des branchements :
    • (chien|chat)

• * : le caractère ou l'expression précédente répété entre 0 et n fois
• + : le caractère ou l'expression précédente répété entre 1 et n fois
• ? : le caractère ou l'expression précédente répété entre 0 et 1 fois

• reconnaître une adresse mail :

 r'\w[\.\w\-]*\w@\w[\.\w\-]*\.\w\w\w?' 

Un algorithme de complétion est un mécanisme logique permettant d'anticiper la saisie et de proposer des mots automatiquement pour faciliter les recherches dans un formulaire sur une page web par exemple.

On utilise pour cela une structure de données arborescente, où chaque nœud de l'arbre est une étape de lecture et chaque arête correspond à la lecture d'une lettre. Les nœuds sont indexés par les lettres suivantes possibles du mot, avec un compteur par nœud pour savoir si celui-ci est final ou non (le nœud est final si le compteur est >0).

On commence par construire un arbre de complétion à partir de mots de vocabulaire,

L'arbre construit de cette manière est très large mais peu profond :

• Pour chaque nœud, le nombre de fils est de l'ordre de la taille de l'alphabet utilisé
• La hauteur maximale est celle de la taille maximale des mots de vocabulaire $n_{max}$
• Par construction, le nombre d'arêtes est borné par $|V|\times n_{max}$

Une fois l'arbre construit, on l'utilise pour compléter un début de mot proposé par l'utilisateur (souvent plusieurs complétions possibles).

Exemple :

• début de mot : ar
• complétions possibles : {art, arbre}

On cherche à exprimer une distance entre deux chaînes de caractères. Une distance entre 2 textes d1 et d2 est telle que :

• dist(d1,d2) = dist(d2,d1)
• dist(d1,d2) ≥ 0
• dist(d1,d2) + dist(d2,d3) ≥ dist(d1,d3)

La distance de Hamming entre deux chaînes de même taille est définie comme le nombre de caractères non appariés. Ainsi la distance de Hamming entre "passoire" et "pastèque" est égale à 4.

Exemple :

p a s s o i r e
| | | x x x x |
p a s t e q u e

distance = 4

Peut-on généraliser cette distance à des chaînes de taille différente?

La distance d’édition est définie, pour deux chaînes de longueur quelconque, comme le nombre minimal d’opérations permettent de transformer d1 en d2, avec les opérations suivantes :

• ins(a) ⇢ insertion du caractère a
• perm (a, b) ⇢ remplacement de a par b
• del (a) ⇢ suppression du caractère a

Il existe différentes manières de transformer la chaîne d1 en d2. On peut par exemple supprimer tous les caractères de d1 et insérer tous les caractères de d2, mais c'est rarement le nombre d'opérations optimal (|d1|+|d2|).

1. Exemples:
   • distance entre "robe", "arbre", et "porte".

  - r o b - e
  v | ^ | v |
  a r - b r e

dist = 3

  r o b - e
  x | x v |
  p o r t e

dist = 3

  a - r b r e
  x v | x ^ |
  p o r t - e

dist = 4

La résolution de ce problème repose sur les principes de la programmation dynamique.

Un problème d'optimisation combinatoire se caractérise par :

• un problème
• un ensemble de solutions à ce problème
• une fonction de coût (ou une fonction objectif) qui attribue un coût (resp un gain) à chacune des solutions possibles apportées au problème

Le nombre de solutions possibles à un problème d'optimisation combinatoire croît exponentielleemnt avec la taille du problème. Trouver une solution par énumération à un tel problème devient rapidement impossible pour des problèmes de taille modérée.

Certains problèmes d'OC peuvent être résolus selon le principe de la programmation dynamique qui consiste à décomposer le problème en sous-problèmes (et en sous-solutions):

• soit un problème P présentant une solution S de coût C
• Étant donné un sous problème $p \subset P$,
  • on liste l'ensemble des sous-solutions $s, s', s''$ applicables à p
  • et on sélectionne celle dont le coût est le plus faible
• on modifie S selon la sous-solution sélectionnée
• on met à jour le coût global
• on met à jour le sous-problème
• et on recommence jusqu'à la convergence (p = P)

Dans le cas de l'appariement de chaîne:

• une solution est un ensemble de transformations acceptables pour passer de la chaîne A à la chaîne B
• le coût est la somme des coûts des transformations appliquées
• un sous-problème consiste à apparier un morceau de A avec un morceau de B

En pratique:

• on représente l’ensemble des transformations de d1 vers d2 sous la forme d’un tableau de (m + 1) lignes et (n + 1) colonnes, avec m = |d1| et n = |d2|
• pour chaque case (i,j) du tableau,
  • le passage vers la case (i, j+1) correspond à ins(d2[j])
  • le passage vers la case (i+1, j) correspond à del(d1[i])
  • le passage vers la case (i+1, j+1) correspond à perm(d1[i],d2[j]) ou id(d1[i],d2[j]) si d1[i]=d2[j]
• la valeur de la distance au niveau de la case (i,j) est égale au minimum de :
  • 1 + dist(i, j+1)
  • 1 + dist(i+1, j)
  • dist(i+1, j+1) si d1[i]=d2[j], ou 1 + dist(i+1, j+1) sinon
• la distance au niveau de la case (m,n) vaut 0
• la distance d'édition est donnée par la valeur dans la case (0,0)

Préparation

variables globales : d1, d2 : chaînes de caractères
m = |d1|
n = |d2|

Récursif!!

algo : distance
données : 
  i, j : etape de calcul
début  
  si i = m et j = n :
     retourner 0
  sinon si i = m :
     retourner dist(i, j+1) + 1
  sinon si j = n :
     retourner dist(i + 1, j) + 1
  sinon si d1[i] = d2[j] :
     retourner min(dist(i, j+1) + 1, dist(i + 1, j) + 1, dist(i + 1, j + 1))
  sinon
     retourner min(dist(i, j+1) + 1, dist(i + 1, j) + 1, dist(i + 1, j + 1) + 1)
fin

• La transmission des données entre programmes nécessite l’ouverture d’un canal de communication
  • entre client et serveur
  • par lequel transitent les données (les requêtes et les réponses).
• Le transport est géré
  • par le système d’exploitation (lorsque les données transitent au sein d’un même ordinateur)
  • ainsi que par des routeurs (lorsque les données transitent d’un ordinateur à l’autre sur le réseau).
• Au niveau du client,
  • les réponses en provenance du serveur sont organisées sous la forme d’une liste,
  • qu’on appelle un flux de données.

Les principaux formats d'échange de données sont :

• csv
• json
• xml

Exemples :

• Clients
• Cours de l'Euro
• codes postaux
• codes postaux

La conservation des données repose principalement sur la structure de stockage,

• définissant la manière dont les données sont physiquement stockées sur le support,
• autrement dit la méthode de rangement de la série de mesures :
  • fichiers,
  • répertoires,
  • index,
  • etc…
• reposant sur des supports de stockage (ou mémoires) :
  • mémoire centrale,
  • mémoires secondaires (disque dur, CD-ROM, memoire flash (SSD), etc…).

Un jeu de valeurs encodé et stocké sur un support informatique est appelé un “enregistrement”,

• conservé sous la forme d'une trames de données.
• Une trame peut obéir à un format textuel ou binaire

Encodage binaire :

• Définition d’une trame, en général de taille fixe.
• Chaque rubrique occupe un nombre d’octets déterminé, afin que chaque jeu de données occupe la même place en mémoire.
• L’utilisation de trames de taille fixe facilite le stockage et la conservation des données sur les supports magnétiques (disque dur, etc…)
• Les données sont transmises dans un format numérique (type) identique à celui utilisé en mémoire centrale.

Encodage textuel :

• Le jeu de données est codé dans un format descriptif (contenant à la fois les valeurs et une description des données : types, attributs, …).
• Ce format facilite la transmission d’un programme à un autre (format “plat”) mais est moins propice au stockage.
• La “sérialisation” est l’opération qui consiste à encoder des données sous la forme d’un texte brut (codage ASCII ou utf8), en “perdant” le moins possible d’information.
• Des exemples de formats textes standards sont donnés en 2.1.3 Structures de données.

Un bloc de données correspond à une série d’enregistrements obéissant au même format:

• Chaque enregistrement est de taille identique;
• L'encodage des données est le même.

La structure de base servant à stocker à une série d’enregistrements est le tableau de données à 2 dimensions :

• Tableau de données (data frame) = intitulé de colonnes + liste de lignes
  • Intitulé de colonne = nom de l’attribut
  • Une ligne = un enregistrement

Structure sous-jacente : tableau à 2 dimensions (ou matrice de données)

Un bloc de données obéit formellement à une structure de type tableau statique:

• Un tableau statique est une structure séquentielle de taille fixe, constituée de $N$ "cases"
• Les cases peuvent être "libres" ou "occupées".

Les mémoires informatiques sont des structures statiques. Une fois les données sauvegardées sur le disque, il est difficile d’insérer ou de supprimer des éléments.

La difficulté consiste à définir une organisation logique du tableau permettant de gérer efficacement un tel ensemble (qui peut être de grande taille) :

• savoir où enregistrer les données
• savoir comment les retrouver

On parle de structure de stockage. Une telle structure doit permettre :

• d’ajouter des données
• d'effacer des données
• d’accéder rapidement à une case particulière

On considère un ensemble de k données stockés dans un tableau de données statique T de N cases (avec 0≤k ≤ N).

Remarques :

• Les cases du tableau sont numérotées de 0 à N-1
• Les données sont de type quelconque mais chaque case ne peut contenir qu'une donnée
• Si i est un indice de case, T[i] désigne le contenu de la case
• N est fixé mais k varie en fonction du nombre de données stockées

Propriété : les données sont stockés dans les k premières cases du tableau. Ainsi, les cases de 0 à k-1 sont occupées et l'indice k désigne la première case libre.

Opérations fondamentales :

• insertion de données : O(1)
• recherche de données : O(k)
• suppression de données : O(k)

On conserve une table des cases libres

• Index bitmap :
  • Chaque bit correspond à une case (libre/occupé).
  • Lors de l’écriture d'une nouvelle donnée (allocation), on fait passer le bit de 0 à 1
  • Lorsque la donnée est effacée, le bit correspondant passe de 1 à 0

$$B = \underset{0}{0}{10010100100.....}\underset{n-1}{01}$$

• Table d'allocation:
  • On considère un tableau de taille $n$ dans lequel $k < n$ cases sont occupées.
  • Chaque bloc de données $d$ est indexée par l'adresse $i < n$ donnant sa position dans le tableau
  • On connaît également sa taille $m$.
  • La table d'allocation donne pour chaque bloc :
    • sa position $i$
    • le nombre $m$ de cases occupées

Stratégies d’allocation

Stratégie par bloc: on alloue des blocs composés de plusieurs cases (S’il existe des blocs libres consécutifs, ils sont fusionnés en un seul)

On souhaite :

• minimiser le nombre de blocs libres
• maximiser la taille des blocs libres

• Plus proche choix : la liste des blocs libres est parcourue jusqu’à trouver un bloc de la taille demandée (ou sinon, le premier bloc de taille supérieure, qui est alors découpé en deux blocs).
  • first fit : le premier bloc suffisamment grand pour les besoins
  • best fit : le plus petit bloc qui ait une taille au moins égale à la taille demandée
  • worst fit : le plus grand bloc disponible (qui est donc découpé)

Autre stratégie (allocation rapide): On alloue des blocs de 1,2,4,8,…2K pages. Pour une taille donnée 2i-1 < n < 2i, on commence par chercher les blocs de taille 2i, puis 2i+1, … jusqu’à 2K , en divisant ces blocs le cas échéant.

Problème des stratégies par bloc: s’il y a trop de données, on obtient des blocs de taille 1 –> nécessité de réorganiser (défragmenter)

La mémoire secondaire n’est pas directement accessible (les programmes n’ont pas la possibilité d’aller écrire directement sur le disque). Le système d’exploitation assure ainsi l’indépendance du programme par rapport à l’emplacement des données, au travers d’instructions d’entrée/sortie spécialisées.

Pour que les programmes puissent écrire sur le disque, on introduit des objets intermédiaires : les fichiers. Un fichier est caractérisé par (nom, emplacement (volume, arborescence), droit d’accès, taille,…). Il s’agit d’une entité logique. Tout programme utilisant un fichier passe par le système d’exploitation qui, à partir des informations, détermine la localisation des données sur le support.

• La gestion des fichiers est une des fonctions essentielles des systèmes d’exploitation :
  • possibilité de traiter et conserver des quantités importantes de données
  • possibilité de partager des données entre plusieurs programmes.

Répertoires Chaque volume possède un numéro appelé le label du volume. Tous les descripteurs de fichiers sont regroupés dans une table des matières appelée Répertoire (Directory).

Remarque : cette table des matières est en fait un fichier dont le descripteur est contenu dans le label du volume.

Organisation hiérarchique :

• Lorsque le nombre de fichiers est élevé, les descripteurs de fichiers sont classés dans plusieurs répertoires, organisés sous une forme arborescente.
• Le répertoire de plus bas niveau hiérarchique est appelé racine → chemin d’accès (path)

Méthode traditionnelle pour le traitement de fichiers de petite taille. La consultation des données nécessite d’ouvrir une “communication” entre le programme et les fichiers. Ce canal de communication permet de recevoir un flux de données.

Pour établir la communication, il faut connaître : le “chemin d’accès” aux données (disque dur local) l’”adresse” des données (lorsqu’il s’agit de données stockées sur un serveur distant)

L’opération d’ouverture de fichier initialise un descripteur de fichier, qui sert à désigner (dans le programme) le fichier sur lequel on travaille, et d’accéder au contenu du flux.

Ouverture simple:

f = open('/chemin/vers/mon/fichier.dat','r')

Il est important de vérifier que cette opération d’ouverture s’effectue correctement avant de poursuivre le programme (nombreuses possibilités d’erreur : fichier effacé, erreur de nom, pas de droits de lecture,…). On utilise une instruction de test spécifique pour vérifier que l’ouverture du fichier s’est correctement effectuée, de type try…catch… (essaye … sinon …) permettant de prévoir une action de secours lorsqu’une une opération “risquée” échoue.

try :
  f = open('/chemin/vers/mon/fichier.dat','r')
except IOError:
  print "Erreur d'ouverture!"

Lorsque l’opération d’ouverture est réalisée avec succès, le flux de données devient accessible en lecture (les premières lignes du fichier sont chargées en mémoire et une tête de lecture se positionne sur le premier caractère de la première ligne). Il ne reste plus qu’à lire les données.

La consultation des données s’effectue séquentiellement à l’aide de l’opérateur de lecture readline. Chaque appel à cet opérateur charge les nouvelles données et déplace la tête de lecture vers les données suivantes. Cette opération peut être effectuée plusieurs fois jusqu’à atteindre la fin de fichier.

Si on suppose que les données sont rangées sous la forme d’un tableau de lignes, chaque opération de lecture consiste à consulter une ligne du tableau, et à positionner la tête de lecture sur la ligne suivante.

s = f.readline()

for s in f :
  print s

L’opération de sauvegarde des données est l’opération complémentaire de la lecture. De nouvelles données doivent être enregistrées sur le disque dur en vue d’une consultation future. Le format de sauvegarde peut être de type texte ou de type binaire. Nous présentons ici la sauvegarde des données dans des formats texte.

Comme dans le cas de l’opération de lecture, il faut au préalable définir dans le programme un descripteur de fichier servant de point d’entrée pour les opération d’écriture. On effectue ce qu’on appelle une ouverture en mode “écriture”.

Python

try :
  f = open('monfichier.dat','w')
except IOError:
  print "Erreur d'ouverture!!"
  

On notera qu’il existe en python (ainsi qu’en C, C++, …) plusieurs modes d’ouverture exprimés par le deuxième argument de la fonction open. On retiendra le mode ‘w’ (création d’un nouveau fichier vide) et le mode ‘a’ (ajout de nouvelles données à la suite d’un fichier déjà existant).

La sauvegarde dans le fichier s’effectue à l’aide d’un opérateur d’écriture. Dans le cas des chaînes de caractères, l’opérateur d’écriture sauvegarde ces données à la suite des données déjà écrites.

Python

f.write("Bonjour!\n")

La sauvegarde de données nécessite d’effectuer un choix sur le mode d’encodage, obéissant en général à une norme bien précise (csv, json, xml, etc…). Voir section 1.3.

Une fois les opérations de lecture ou d’écriture terminées, il est nécessaire de fermer le fichier. L’opération de fermeture assure que les données sont effectivement enregistrées sur le disque (et non simplement stockées dans la mémoire tampon - voir section XXX).

Voir aussi :

• Gestion des fichiers sous Unix

Pour une gestion efficace des données, il est nécessaire de pouvoir identifier chaque enregistrement de façon unique.

L'indexation des données repose sur un principe simple d'étiquetage consistant à attribuer une étiquette différente à chaque enregistrement. Cette étiquette peut être une suite de caractères arbitraires, un entier, ou un descripteur explicite. On parle en général de clé ou d'identifiant pour désigner cette étiquette.

• L'indexation des données consiste à attribuer à chaque donnée distincte un identifiant unique.
• On parle également de clé de l'enregistrement:

On peut représenter l'opération d'indexation sous la forme d'une fonction. Si $d$ est le jeu de valeurs, $k(d)$ désigne l'identifiant de ce jeu de valeurs.

L'indexation suppose l'existence d'une bijection entre l'ensemble des données et l'ensemble des clés, permettant d'assurer l'unité et la spécificité de la clé

L'existence d'un identifiant unique pour chaque jeu de valeurs $d$ permet la mise en œuvre d'une recherche par identifiant (ou recherche par clé).

La recherche par identifiant repose sur une fonction d'adressage $I$ qui à tout identifiant $k$ associe sa position (entrée) $i$ dans un tableau de données: $I : k \rightarrow i$. Ainsi si $k$ est l'identifiant servant à la recherche, l'extraction des informations se fait en 2 étapes:

• $i = I(k)$ (lecture de l'index des données)
• $d = D[i]$ (lecture des données elles mêmes)

L'identifiant doit en pratique tenir sur un nombre d'octets le plus petit possible pour que la liste $L$ puisse être manipulée en mémoire centrale. Autrement dit, il faut que :

• $|k| << |d|$

pour que :

• $|L| << |D|$

Définir un ordre sur les données

La présence d'un identifiant permet de définir un ordre total sur les données :

• ordre sur les entiers (identifiant entier)
• ordre alphabétique (identifiant texte)
• ordre ASCIIbétique (chaîne de caractères quelconque)

Lier les données

Dans le cas des bases de données, l'identifiant constitue une référence vers les jeux de valeurs des tableaux de données. Une référence permet de lier les données d'une table aux données d'une autre table.

Exemple :

• Artistes
• Albums
• Pistes

• Pour chaque album de la table des albums, l'identifiant d'artiste (ici un numéro) permet de lier l'album avec l'artiste (ou groupe) correspondant.
• Pour chaque piste de la table des pistes, l'identifiant d'album permet de lier la piste à l'album correspondant (et donc à l'artiste correspondant par transitivité)

Structure d'ensemble

L'index définit l'appartenance d'une donnée à un ensemble.

Soit $\mathcal{E}$ un ensemble de données indexées : $$ \mathcal{E} = \{d_1, d_2, ..., d_K\} $$ On a l'équivalence : $$ d \in \mathcal{E} \Leftrightarrow k(d) \in I $$

Ainsi, il ne peut y avoir de doublon car $\forall d$ :

• $k(d)$ est unique
• $i = I(k(d))$ est unique ssi $d \in \mathcal{E}$ et indéfini sinon.

L'exemple le plus simple d'indexation est celui fourni par les numéros de case d'un tableau.

• Soit $D$ un tableau de $n$ lignes
• le numéro $i < n$ est à la fois l'identifiant et l'entrée (ou adresse) de la ligne $D[i]$

Dans le cas général, l'identifiant n'est pas égal à l'entrée!

On sépare donc l'index $k$ de l'entrée $i$:

• $k$ est l'identifiant (ou clé) de la donnée $d$. Il s'agit d'une valeur numérique quelconque.
• $i$ est l'entrée de la donnée $d$, correspondant à sa position dans le tableau de données.

Il existe différentes méthodes permettant d'assurer l'intégrité de l'index:

• Le programme maintient une liste triée des identifiants déjà utilisées. Lors de l'ajout d'une nouvelle donnée, il s'assure que l'identifiant n'est pas déjà présente dans la liste.
  • Coût :
    • $O(n)$ en mémoire
    • $O(\log n)$ pour l'ajout
• Dans le cas où les identifiants sont des numéros (entiers), il est possible d'utiliser un compteur qui s'incrémente à chaque nouvelle insertion.
  • Coût :
    • $O(1)$ en mémoire
    • $O(1)$ pour l'ajout

Utilisation d'une fonction de hachage :

• qui "calcule" la valeur de l'identifiant à partir des valeurs du jeu de valeurs à insérer.
• La fonction de hachage doit être telle que la probabilité de choisir le même identifiant pour deux données différentes soit extrêmement faible.

Attribution d'un identifiant arbitraire entre 0 et n-1

• Etape 1 : transcodage binaire des données
  • i = int.from_bytes(d, byteorder='big')
  • avantage : les données différentes ont un code entier différent
  • mais : |i| = |d|

s = 'paul.poitevin@centrale-marseille.fr'
d = bytes(s, 'ascii')
i = int.from_bytes(d, byteorder='big')
print("i =", i)

donne :

i = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058

• Etape 2 : réduction du code
  • Méthode 1 : le modulo n (reste de la division entière par n)
    • k = H(i) = i mod n
    • Avantage :
      • $|k| << |d|$
    • Inconvénient:
      • deux données différentes peuvent avoir le même code
      • ce codage revient à sélectionner les bits de poids faible
      • deux données proches ou très similaires auront un index proche ou similaire : si j = i + 1, H(j) = H(i) + 1 (presque toujours)
      • —> il faut prendre n premier

• • • $n = 2^{32} = 4294967296$ :
      • H_code(paul.poitevin@centrale-marseille.fr) = 1697539698
      • H_code(martin.mollo@centrale-marseille.fr) = 1697539698
    • $n = 67280421310721$ (premier):
      • H_code(paul.poitevin@centrale-marseille.fr) = 36148249469507
      • H_code(martin.mollo@centrale-marseille.fr) = 65330032132071

• • Méthode 2 : combiner produit et modulo – soient m et n deux nombres premiers entre eux
    • k = H(i) = (i * m) mod n
    • Avantage :
      • $|k| << |d|$
      • deux entiers proches donneront auront des codes très différents : si j = i + 1, j * m - i * m = m
    • Inconvénient :
      • deux données différentes peuvent avoir le même code
        • le produit i * m peut etre coûteux à calculer

• Méthode 3 : Hachage cryptographique :
  • Le hachage cryptographique est construit de telle sorte qu'il soit très difficile de trouver un entier j != i tel que H(i) = H(j).
  • Un tel code est appelé une "signature".
    • Exemples :
      • MD4
      • SHA

Le gestionnaire de bases de données MongoDB utilise une indexation des données par clé cryptographique.

Que faire lorsque l'index ne tient pas en totalité dans la mémoire centrale ?

• L'index est découpé en "blocs"
• Les blocs sont organisés sous la forme d'un arbre (B-arbre = "Balanced Tree")

Considérons un index composé de couples (clé, numero de page). On suppose que l’index est également découpé en pages, chaque page d'index contenant au maximum b clés. Si l’index comporte beaucoup de pages, il est intéressant de l’organiser hiérarchiquement en pages et sous-pages, selon une organisation appelée "B-arbre" (Balanced Tree):

• chaque noeud de l’arbre contient une liste croissante de couples (clé, numéro d’une sous-page)
• chaque clé est dupliquée dans sa sous-page :
  • les clés contenues dans la sous-page sont inférieures ou égales à elle,
  • les clés contenues dans la sous-page sont strictement supérieures à celles de la sous-page précédente.
  • les feuilles contiennent des couples (clé, numéro de la page du tableau de données)

I ← charger la racine de l’arbre
tant que I n’est pas une feuille :
  k’ ← première clé de I
  tant que k > k’
    k’ ← clé suivante 
  I ← charger sous-page de k’

Remarque : Pour que l’accès aux données soit efficace,

• il faut que l’arbre soit le moins profond possible : arbre “équilibré”.
• Dans ce cas,
  • chaque noeud a b fils,
  • et la profondeur de l’arbre est de l’ordre de logb(N).
• Pour charger la page contenant le tuple cherché,
  • il faut donc logb(N) + 1 lectures sur disque.

En pratique, il existe des algos permettant d’assurer que chaque noeud contient entre b/2 et b clés (sauf la racine).

On introduit dans ce chapitre le modèle relationnel qui sert de fondation à la conception de bases de données.

Les différents modèles utiles en représentation des connaissances reposent sur des notions de base de la théorie des ensembles :

• Ensemble finis
• Éléments partiellement (ou totalement) discernables

Tout commence par une fiche à remplir…

• Un formulaire se présentant sous la forme d’un ensemble de rubriques à remplir.
• Le modèle de fiche définit le format des données à enregistrer:
  • liste des rubriques du formulaire,
  • domaine de valeurs attendues dans chaque rubrique.
• A toute fiche remplie correspond un jeu de valeurs (ou mesure) :
  • liste de valeurs correspondant au contenu d’une fiche particulière.

• D’un point de vue informatique, un jeu de valeurs recueilli est appelé un enregistrement
  • correspondant à l’encodage des données recueillies sur un support numérique
• Une structure de données définit les données de manière logique,
  • c’est à dire l’ordre dans lequel elles doivent être lues
  • et la manière dont elles doivent être interprétées par les programmes qui les utilisent.

• Les types des valeurs étant déterminés (selon les cas de taille fixe ou variable),
  • la structure de données correspond au “véhicule” qui servira à transporter et échanger les données (entre programmes, entre ordinateurs).
  • Différentes structures de données sont possibles pour l’encodage et le stockage d’un jeu de valeurs, voir :
    • Données non structurées
    • Données vectorielles
    • Tuples
    • Données structurées
    • Données Hiérarchisées

Le Tuple est la structure de données de base servant pour le recueil, le transport et le stockage des données.

("Dubois", "Martine", 22, "29/10/1994", "Orléans")

<!-- === Données brutes === *Textes, *comptes rendus, *série de notes, de valeurs sans format précis : -> format texte en général.   <note> Le format ''txt'' désigne des données non structurées de type “texte” regroupant différents modes d’encodage : * ASCII (caractères sans accent), * utf8 (caractères accentués et spéciaux), * ... </note>   === Données vectorielles=== * Chaque jeu de valeurs est codé sous la forme d’un **vecteur** * constitué de grandeurs entières ou réelles : * toutes les valeurs sont quantitatives (numériques). * C’est un encodage adapté aux grandeurs physiques : * chaque champ du formulaire est codé dans un format numérique * il est possible de représenter les données dans un espace vectoriel   <note important> Un **vecteur** est une séquence (ordonnée et finie) de valeurs quantitatives, chaque valeur obéissant au même format numérique. </note>   <note tip> **Exemple** : Considérons une station météorologique enregistrant à intervalle réguliers les données de ses capteurs : * thermomètre, * baromètre, * hygromètre * et anémomètre. Un jeu de valeurs sera constitué de //5 réels double précision// décrivant * la température, * la pression, * l’humidité, * la vitesse * et la direction du vent. </note>     === Tuples===   **NB**: * Les données sont organisées sous la forme d’une liste de valeurs qualitatives ou quantitatives. * Le tuple est la structure de base servant pour la transmission des données (simple, facile à coder et à échanger). -->

NB: un tuple est une séquence (ordonnée et finie) de valeurs, chaque valeur pouvant être de type qualitatif ou quantitatif, et pouvant obéir à un format numérique différent.

Dubois,Martine,"28, rue des Lilas, 45000 Orléans",45

• Données organisées sous la forme d’une liste d’attributs.
  • Chaque attribut est défini par un nom et un format (type).
  • Chaque valeur est stockée sous la forme d’un couple (attribut : valeur).

{"nom" : "Dubois", "prénom" : "Martine", "adresse" : "28, rue des Lilas, 45000, Orléans", "âge" : 45}

• Organisation des données correspondant à une structure d’arbre.
• Dans le cas d’un recueil de données, correspond à la définition de rubriques et sous-rubriques.

<nom> Dubois </nom>
<prénom> Martine </prénom>
<adresse>
  <num> 28 </num>
  <voie> rue des Lilas </voie>
  <code postal> 45000 </code postal>
  <ville> Orléans </ville>
</adresse>
<âge> 45 </âge>

{
  "nom" : "Dubois",
  "prénom" : "Martine",
  "adresse" :
  {
    "numero" : 28,
    "voie" : "rue des Lilas",
    "code_postal" : 45000,
    "ville" : "Orléans"
  },
  "âge" : 45
}

Un tableau de données est une liste (finie et ordonnée) de tuples, chaque tuple obéissant à un même schéma $R$.

2 approches en modélisation :

• approche ensembliste (plus général)
• modèle relationnel (plus pratique)

Rappel:

• Un enregistrement est un jeu de valeurs organisé sous forme de tuple
• A un tuple on associe en général un schéma de données.

• Définir un schéma consiste à définir :
  • une liste d'attributs (labels) associées à chacune des valeurs du tuples.
• A chaque attribut correspond :
  • un intitulé
  • un domaine de valeurs (type/format des données)

• Soit $R(A_1, ..., A_m)$ un schéma.
• On note $\text{dom}(A_i)$ le domaine associé à l'attribut $A_i$.
• On dit d'un tuple $t$ qu'il obéit au schéma $R$ si les valeurs qu'il contient correspondent aux domaines des attributs du schéma.

• Au sein d'un schéma $R$,
  • Il peut exister un ensemble de contraintes, noté $F$,
    • portant sur les attributs (plus précisément sur les valeurs prises par les attributs).
    • L'ensemble F est indépendant de R.
  • On parle de contraintes d’intégrité.
    • Ces contraintes s’expriment sous la forme de dépendances fonctionnelles.

• Il importe donc de bien réfléchir, au moment de l'étape de conception,
  • du réalisme et du caractère limitant de certaines dépendances fonctionnelles,
  • et du caractère éventuellement limitant du choix des attributs.
• Ainsi, le schéma décrivant les commandes (exemple 2)
  • ne permet pas de commander des articles de nature différente au sein d'une même commande
  • (un client, pour commander deux râteaux et une truelle, doit donc effectuer deux commandes, qui plus est à des dates différentes!).

• Soit un schéma $R(A_1, ..., A_m)$.

Soit $K$ une clé candidate. On démontre que $K \rightarrow R$ à l'aide des axiomes d'Amstrong à partir d'un ensemble de DF connues:

Tables mal construites

Les Formes normales

• Restreignent les dépendances admises dans un schéma relationnel
• Permettent d’éviter la duplication de l’information au sein des relations
• Définissent une méthode
  • de décomposition d’un schéma relationnel redondant
  • en plusieurs schémas liés entre eux:

• Lorsqu’un schéma relationnel n’est pas en deuxième forme normale, il doit être normalisé:

* Lorsqu’un schéma relationnel n’est pas en troisième forme normale, il doit être normalisé:

Une base de donnée est constituée de plusieurs ensembles d'objets et d'opérateurs participant au bon fonctionnement d'un système:

Exemple 1 :

• Ensembles d'employés
• Ensembles de commandes
• Ensembles d'articles
• Ensembles de clients

Exemple 2 :

• Ensembles d'étudiants
• Ensembles de séances
• Ensembles de cours
• Ensembles de copies

On parle plus généralement d'ensembles d'entités.

Une entité $x$

• est une représentation d'un objet du monde réel,
• appartenant au système/à l'organisation modélisée.
• Une entité est décrite par une ou plusieurs valeurs caractéristiques, appelées attributs.

Les informations conservées au sujet des entités d'un ensemble sont les attributs.

• Chaque attribut :
  • a un nom unique dans le contexte de cet ensemble d'entités : $A$, $B$, $C$, $A_1$, $A_2$, …, $A_m$, …
    • Exemples de noms concrets : couleur, nom, horaire, salaire.
  • prend ses valeurs dans un domaine bien spécifié,
    • également appelé le type de l'attribut.
    • Le domaine d'un attribut est noté $\text{dom}(Aj)= Dj$.
      • Exemples :
        • $\text{dom}(couleur)={rouge, vert, bleu, jaune}$,
        • $\text{dom}(nom) = $ensemble des chaînes de caractères,
        • $\text{dom}(salaire) =$ entiers naturels
        • etc…

Un ensemble d'entités est un ensemble fini d'éléments : $$E = \{x_1,…,x_n\}$$ Il regroupe (ou associe) plusieurs entités ayant des caractéristiques communes (descriptibles à l'aide du même ensemble d'attributs).

• Les éléments d’un ensemble d’entités sont partiellement discernables à travers les valeurs de leurs attributs :
  • les attributs $(A_1,...,A_m)$ servent à décrire les éléments de l’ensemble.
  • Le schéma $R$ de l’ensemble $E$ est une application de l'ensemble d'entités vers l'ensemble des tuples de schéma $R$
    • Soit :

$$ R : \mathcal{X} \rightarrow D_1 \times ... \times D_m$$ $$ x_i \mapsto (A_1(x_i),…, A_m(x_i))$$

Modéliser une base de données, c'est :

• Identifier les différents ensembles en interaction
• Identifier les liens de dépendance entre les différents ensembles

• Attribution : propriété, réservation, participation, supervision, auteur, rôle, pilote, …
• Événements : achat, vente, séance, épreuve, appel, consultation, réunion, transaction, transport …
• Aggrégation/Composition : tout/parties, contenant/contenu, supérieur/subordonné, pays/région, …
• Relations entre membres : parenté, collaboration, cercle d'amis, …
• …

Associations binaires

Associations ternaires

Associations de 1 à plusieurs (fonctionnelle)

Relation non symétrique entre les deux ensembles : […,1] d'un côté, […,N] de l'autre. Relation de type contenant/contenu, propriétaire/objet possédé, occupant/occupé, actif/passif etc… Il s'agit du type d'association le plus "courant".

Associations de plusieurs à plusieurs (croisée)

Dans une association “croisée”, les tous les lien de l’association sont de cardinalité multiple […,N]

Mesures

• Les mesures sont les données saisies sur les éléments d'un ensemble. Chaque mesure est associée à un attribut.
• Le schéma de l'ensemble est l'ensemble des attributs servant à caractériser ses éléments
• Les éléments de l'ensemble sont discernables ssi il existe un jeu de mesures différent pour chaque élément de l'ensemble
• Une clé est un ensemble d'attributs minimal (permettant de distinguer les objets) appartenant au schéma

Opérateurs

• On s’intéresse ici aux associations qui représentent une “opération” (inscription, achat, embauche, affectation…).
• Lors d’une mise à jour de la base, certains événements tels que l’emprunt ou le retour d’un ouvrage, l’affectation d’un employé à un poste, ou la liste des anciens clients disparaissent.
• Il est possible de garder une trace des événements passés en mettant un (ou plusieurs) attributs sur une association.
• Ainsi, certaines associations peuvent être "datées", c'est à dire
  • avoir lieu à une date
  • ou prendre place sur une durée précise (prêt,accès temporaire, statut temporaire…)
• On peut ainsi mémoriser :
  • "Monsieur Dupont a été employé au département logistique de tant à tant."…
  • "L'étudiant X a été élève Centrale Marseille de telle année à telle année"…

Exemple "Monsieur Dupont a été employé au département logistique de tant à tant."…

Exemple

• Chaque coureur est décrit par ses nom, prénom, nationalité et numéro de maillot.
• Chaque coureur appartient à une équipe qui possède un numéro, un sponsor associé.
• Chaque coureur participe à une ou plusieurs étapes. Une étape se caractérise par son numéro, son type (contre la montre/étape simple), ses points de départ et d'arrivée, sa date.
• A chaque étape est associée un classement d'arrivée pour chaque coureur, avec la durée totale de course.

Il est possible de traduire un modèle entité/association vers un modèle relationnel (en perdant quelques propriétés).

Un petit nombre de règles permettent de traduire un modèle entité/association vers un modèle relationnel.

• Selon ces règles, à la fois les ensembles d'entités et les associations sont transformés en schémas relationnels.
• Les liaisons et dépendances entre schémas de relation sont assurés par la définition des clés étrangères (attributs communs à plusieurs tables).

Exemple

Une association croisée ne contient que des contraintes de cardinalité de type [..,N]. Soit $R$ une telle association et $E_1$, …, $E_k$ les ensembles participant à l'association.

Traduction :

• Pays (nom_pays, superficie, population, PIB )
• Matière_première ( nom_matière, unité, prix )
• Exportation (nom pays, nom matière, quantité)

Traduction :

• Appareil (code_appareil, type, marque, modèle)
• Séance (date, heure, local)
• Réservation (code appareil,date, heure, local)

Soit une association fonctionnelle $R$. On suppose qu'il existe au moins un ensemble $A$ de cardinalité unique [1,1] participant l’association.

Exemple :

Remarque : lorsque l’association est valuée, les attributs de l’association sont également injectés dans la table représentant l’ensemble de gauche.

Exemple Traduction :

• Groupe_TD( num_groupe, LV1, LV2)
• Entreprise ( nom_entreprise, Adresse)
• Etudiant ( num_etudiant, Nom, Prénom, Date_naiss, num groupe, intitulé, date, durée, nom entreprise)

Un SGBD (Système de Gestion de Bases de Données) est un programme qui gère une (ou des) base(s) de données. Il s’agit d’un programme optimisé afin d’accélérer l’accès et rationaliser le traitement d’un grand ensemble d’enregistrements stockés sur un support informatique.

Le fonctionnement d'un tel programme repose sur :

• des méthodes de conception ensemblistes fondées sur le modèle relationnel (description des ensembles d’enregistrements et des relations entre ces ensembles)
• un langage de requête permettant de consulter et mettre à jour les données stockées dans la base
• des algorithmes de stockage et de classement efficace (afin d’accélérer les temps de recherche)

Il existe enfin un administrateur de bases de données. Celui-ci doit :

• installer la base de données,
• gérer sa sauvegarde régulière,
• garantir sa sécurité et
• gérer les droits des utilisateurs de la base.

SQL :

• est un langage de création et d'interrogation de bases de données,
• supporté par la plupart des systèmes de gestion de bases de données relationnelles du marché.

  CREATE TABLE Commande (
    num_commande INTEGER NOT NULL,
    nom_client VARCHAR(30),
    nom_fournisseur VARCHAR(30),
    composant VARCHAR(30),
    quantité INTEGER,
    montant DECIMAL(12,2) NOT NULL,
    PRIMARY KEY (num_commande),
    FOREIGN KEY (nom_client) REFERENCES Client,
    FOREIGN KEY (nom_fournisseur, composant) REFERENCES Catalogue);

INSERT INTO Client VALUES ("Durand", "7, rue des Lilas" , 335.00);

UPDATE Client SET adresse = "9, rue des Lilas" WHERE nom_client="Durand";

DELETE FROM Client WHERE nom_client="Durand";

Interroger une base de données , c’est sélectionner certaines données parmi l'ensemble des données proposés.

En informatique, une requête (en anglais query) est une demande de consultation ou d'édition, effectuée par un programme client à l’attention d’un programme serveur.

• Le programme client représente l’utilisateur, il s’agit du programme qui enregistre la demande de l’utilisateur, la transmet au serveur, puis met en forme visuellement la réponse du serveur.
• Les données sont centralisées au niveau du serveur, chargé de la gestion, de la manipulation et du stockage des données.Il traite la requête, consulte les données et transmet le résultat au client.

La requête peut être une simple référence vers un fichier, ou être l’expression d’une recherche plus spécifique (consultation de certaines fiches d’un fichier, croisement d’information (entre plusieurs fichiers), etc…). Dans ce cas, il est nécessaire d’utiliser un langage de requête (le plus souvent SQL).

On distingue quatre grands types de requêtes (approche “CRUD”):

• Création (Create) : ajout de nouvelles données dans la base
• Lecture/recherche (Read) : consulation du contenu de la base
• Mise à jour (Update) : changement du contenu existant
• Suppression (Delete) : suppression des données obsolètes

Lors d’une consultation de type lecture/recherche, il y a souvent plusieurs réponses qui correspondent à la demande. Le résultat d’une requête prend donc la forme d’un ensemble de réponses. Ces réponses sont éventuellement classées, selon la valeur d’un certain identifiant, ou selon le degré de pertinence.

SELECT *
FROM  Eleves
WHERE NOM = 'Dugenou'

Exemples :

• croisement de facteurs de recherche :
  • Donner la liste des pays exportateurs de pétrole
  • Liste des musiciens jouant à la fois du piano et du violon
  • Liste des artistes français disque d'or en 1977
  • Liste des suspects châtain taille moyenne présents à Poitiers la nuit du 12 au 13 février
• Analyse des données
  • faire ressortir des corrélations (exemple : type d'habitat/intentions de vote),
  • pour des enquêtes de consommation, du marketing ciblé …
• Information personnalisée :
  • ne retenir que les informations utiles à un instant et pour une personne donnée.
  • Emploi du temps de l'élève X pour la semaine Y.
  • Factures impayées du client Z

Extraction d'information à partir d'une table unique :

• projection $\pi$ = extraction de colonnes
• sélection $\sigma$ = extraction de lignes

SELECT    A1,A2, …, An    // liste d’attributs
FROM      R               // nom de la TABLE
WHERE     F               // condition sur les attributs

cette requête est semblable à :

• une sélection algébrique $σ_F$
• suivie par une projection algébrique $Π_{A1, …, An}$

soit : $$Π_{A1, …, An}( σ_F ( R ))$$

Exemples :

• Qui fournit des transistors ?

    SELECT nom_fournisseur
    FROM Fournisseur
    WHERE composant = ’transistor’;

• Liste de toutes les commandes de transistors :

    SELECT *
    FROM Commandes
    WHERE composant = ’transistor’

• Qui fournit des micro-controleurs à moins de 5$?

    SELECT nom_fournisseur
    FROM Catalogue
    WHERE composant = ’micro controller’ AND prix < 5

Algo de sélection :

pour tout tuple e de r:
  si e obéit à la condition  F:
        ajouter e à la réponse 

complexité : O(n)

Remarque : dans le cas d'une recherche ciblée, la présence d'un index sur le critère de recherche permet d'accélérer la sélection :

pour toute a ∈ F:
  i ← Index(a)
  ajouter r[i] à la réponse

Principe : recoupement d'informations présentes dans plusieurs tables :

• Croisement des critères de sélection : Jointure
• Recherche ciblée : Division

• La jointure est une opération qui consiste à effectuer un produit cartésien des tuples de deux relations pour lesquelles certaines valeurs correspondent.
• Le résultat de l'opération est une nouvelle relation.

Exemples de requêtes

• “Donner la liste des PIB/hab des pays exportateurs de pétrole” :

$$Π_\text{PIB/hab}( σ_\text{nom_matière = pétrole} ( \text{Pays} ⋈ \text{Exportations} ))$$

• “Donner le nom et l'adresse des clients qui ont commandé des micro controleurs” :

$$Π_\text{nom_client,adresse_client}( σ_\text{composant = 'micro-controller'} ( \text{Client} ⋈ \text{Commandes} ))$$

SELECT    A1,A2, …, An       // liste d’attributs
FROM      R1, …, Rm          // liste de TABLES
WHERE     F1 AND … AND Fl    // liste de conditions sur les attributs 
                             // (en particulier conditions sur les attributs 
                             // sur lesquel  s’effectue la jointure)

Pour exprimer la jointure sur l’attribut 'Aj' commun aux tables 'R1' et 'R2', on écrira : 'R1.Aj = R2.Aj'

Exemples :

• Approche prédicative :

SELECT PIB_par_hab 
FROM Pays NATURAL JOIN Exportations
WHERE nom_matiere = 'petrole'

SELECT PIB_par_hab 
FROM Pays, Exportations
WHERE nom_matiere = 'petrole'
AND Pays.nom_pays = Exportations.nom_pays

• Approche ensembliste :

SELECT PIB_par_hab 
FROM Pays
WHERE nom_pays IN (
  SELECT  nom_pays 
  FROM Exportations
  WHERE nom_matiere = 'petrole'
  )

Lors d’une opération de jointure, on distingue en général la “table de gauche” de la “table de droite”.

Il y a deux stratégies possibles pour faire une jointure :

• double boucle : c'est l'algorithme le plus simple. La table de droite est examinée une fois pour chaque tuple de la table de gauche. Cette stratégie est facile à implémenter mais peut être très coûteuse. Toutefois, si la table de droite est indexée sur l'attribut qui sert pour la jointure (cas le plus courant), elle peut donner de bons résultats;
• tri-fusion : chaque table est triée sur les attributs de jointure avant que la jointure soit effectuée. Une fois le tri fait, les tables peuvent être fusionnée : chaque table n'est examinée qu'une seule fois (ici, la jointure n'est pas coûteuse, c'est bien sûr sur l'opération de tri que tout est reporté).

Exemple :

On considère les schémas R(a1,a2,a3) et S(a3,a4,a5) ayant l’attribut a3 en commun :

• L’attribut a3 est une clé étrangère du schéma R.
• R est “à gauche” (contient la clé étrangère), et S est “à droite”.

Soient r et s deux tables obéissant aux schémas R et S, et de taille |r| et |s|.

Algo naif :

Pour chaque tuple e de r:
    Pour chaque tuple f de s:
       Si e(a3)=f(a3):
          ajouter e U f à la réponse

Complexité : O (|r| ×|s|)

Si la table de droite est indexée sur l'attribut a3 qui sert pour la jointure, l’algo suivant peut donner de bons résultats :

Pour chaque tuple e de r: # table de gauche
  x ← e(a3)
  i ← Index(x) # index sur la table de droite
  f ← s[i]
  ajouter e U f à la réponse

• si la recherche dans l'index est en est en log(|s|)
• Complexité : O (|r| × log |s|)

Exemples :

• Liste des pays qui exportent tous les types de matières premières
• Liste des pays qui exportent les mêmes matières premières que l'Arabie Saoudite
• Liste des élèves présents à tous les cours magistraux d'informatique de première année

• Certaines requêtes, peuvent être le résultat de la combinaison de plusieurs critères de recherche
• La combinaison de résultats est généralement réalisée à l'aide des opérations ensemblistes classiques (intersection, union…) pour exprimer «et», «ou», «non»…
• Pour alléger les formules, il est possible d'utiliser des tables intermédiaires.

Exemples :

• Donner la liste des pays qui exportent à la fois du gaz et du pétrole :

$$\pi _{Pays} σ_\text{matière = gaz} (\text{Exportations}) \cap \pi _{Pays} σ_\text{matière = pétrole} (\text{Exportations})$$ en SQL :

SELECT pays FROM Exportations
WHERE matière = 'gaz'
INTERSECT (     SELECT pays FROM EXPORTATIONS
                WHERE matière = 'pétrole');

• Donner la liste des pays qui exportent du gaz mais pas du pétrole :

$$\pi _{Pays} σ_\text{matière = gaz} (\text{Exportations}) - \pi _{Pays} σ_\text{matière = pétrole} (\text{Exportations})$$ en SQL :

SELECT pays FROM Exportations
WHERE matière = 'gaz'
EXCEPT (     SELECT pays FROM EXPORTATIONS
            WHERE matière = 'pétrole');

* Donner la liste des clients qui commandent uniquement des produits 'Moxcom' : $$\pi_{nom\_client}Client - \pi_{nom\_client} \sigma_{fournisseur \neq 'Moxcom'} Client ⋈ Commande$$ en SQL :

SELECT nom_client FROM Client
EXCEPT (    SELECT client FROM Client NATURAL JOIN Commande
            WHERE fournisseur <> 'Moxcom');

L’analyse des données a pour but de recomposer l’information contenue dans les données recueillies afin d’en fournir une vue plus synthétique, ou d’extraire des informations qui n’apparaissent pas de façon explicite dans la série de mesures initiale :

Exemples de grandes masses de données :

• Masses de données (pullulantes) : tickets de caisse, clics web, appels tel, operations bancaires, remboursements no URSSAF, trajets SNCF…
• Données importantes : fichiers de clients, données biométriques, campagnes de mesures, sondages,…
• Données géographiquement localisées (gestion d’un “territoire”) : appels tel, centres de production, consommation eau-électricité-gaz, infractions pénales, arrêts maladie, prêts bancaires, allocations chômage, jugements des TGI, accidents du travail…

Le but est de dégager :

• des tendances (covariables)
• des modes de la distribution (présence de plusieurs maxima)

à partir d’un grand ensemble de données (chiffre d’affaires, nb de ventes, masse salariale, …) évoluant dans le temps et dans l’espace, afin de

• définir des indicateurs pertinents
• faciliter la prise de décision.

L'agrégation consiste:

• à organiser les données en classes selon la valeur d'un attribut.
• à utiliser des opérateur d’aggrégation :
  • comptage, somme, moyenne, ecart-type, max, min, …
  • (count, sum, mean, avg, max, min…)
• afin de dégager :
  • des tendances (selon une dimension)
  • des modes (analyse par histogramme)

cas d’utilisation :

• Quels sont les catégories de films/livres les plus fréquemment empruntés?
• A quelles heures de la journée la messagerie est-elle la plus sollicitée?
• Comment se répartissent géographiquement les utilisateurs de la messagerie?

En SQL, l'opérateur d'agrégation est GROUP BY:

• définit des regroupements de données à partir des valeurs de l'attribut mentionné
• il est possible de faire des regroupements selon les valeurs de plusieurs attributs

Exemples de requêtes faisant appel aux fonctions d’agrégation :

Nombre d’élèves par groupe de TD / par prépa d’origine etc..:

SELECT groupe_TD , COUNT(num_eleve)
FROM Eleve
GROUP BY groupe_TD

Donner les chiffres des ventes du magasin pour chaque mois de l’année

SELECT mois, SUM(montant)
FROM Vente
GROUP BY mois

Donner le nombre de ventes d’un montant > à 1000 euros pour les mois dont le chiffre d'affaires est supérieur à 10000 euros

SELECT mois, COUNT(num_vente)
FROM Vente
GROUP BY mois
HAVING SUM(montant) >= 10000

Tester les disparités salariales entre hommes et femmes

SELECT sexe, avg( salaire )
FROM Employé
GROUP BY sexe

Tester les disparités salariales selon le niveau d’éducation

SELECT niveau_educatif, avg( salaire )
FROM Employé
GROUP BY niveau_éducatif

La découverte d'informations consiste à développer des outils de mise en forme des données facilitant leur analyse. Elle repose sur deux aspects :

• projection de données qualitatives sur des espaces vectoriels ("quantification" des données)
• production d'histogrammes multivariés dans le but d'analyser la distribution des données dans l'espace de reconstruction

Le but est ici de dégager :

• des corrélations (analyse croisée)

Exemples de corrélations :

• Réussite / taux d’embauche / salaire en fonction de la prépa d’origine / sexe / profession des parents
• Tester les disparités salariales hommes/femmes en fonction du niveau d’éducation.
• Donner le taux de réussite aux examens par groupe de matière en fonction de la filière d’origine (MP, PSI, PC, PT, …)
• Y a-t-il une corrélation entre le lancement d’une campagne publicitaire et les chiffres de vente? quels sont les supports les plus efficaces?

Sites de données :

• www.data.gouv.fr
• scientific data
• Liste de ressources open data
• data.gov
• open food facts

• Notion de fait élémentaire (fact): transaction ou opération localisée dans le temps et dans l’espace

Remarque : Les transactions marchandes sont un cas classique (acte d’achat bien répertorié et enregistrés, livres de comptes, …)

Exemples de “fait”:

• Achat/Vente
• Opération bancaire (débit/crédit)
• Consultation (site web)
• Souscription à un contrat d’assurance
• Appel téléphonique
• Inscription

Tous ces faits peuvent être localisés. Des mesures peuvent être effectuées sur ces faits (montant d’une vente, durée d’un appel, montant d’une opération bancaire, …)

Points clés :

• distinction entre Dimension et Mesure.
  • Notion de dimension : qui? quoi? où? quand? Comment? : associe des coordonnées à l’événement (géographiques, temporelles) et par extension une catégorie.
  • Notion de mesure(s) associées à l’événement (exemple : montant de la vente)
• distributions, répartitions, etc… cf analogie proba/stats : événement aléatoire, vecteur aléatoire, …
  • les événements sont associés par paquets sur des intervalles réguliers ou selon des catégories discretes.
  • Fonctions d’aggrégation : réalise la mesure sur les groupe : somme, comptage, moyenne, min, max, etc…
  • histogramme : nb d’événements observés par secteur sur un maillage régulier de l’espace des coordonnées. Par extension mesure sur ce maillage par une fonction d’aggrégation.

Les tables pivot permettent d'analyser des faits selon deux dimensions organisées sur les deux axes d'un tableau.

L'utilisation de données structurées dans un programme Python nécessite de faire appel à des librairies spécialisées. Nous regardons ici la librairie pandas qui sert à la mise en forme et à l'analyse des données.

import numpy as np
import matplotlib.pyplot as plt
import pandas

Considérons des informations stockées dans un fichier au format ‘csv’ (comma separated values) : ventes_new.csv

On utilise:

• pandas.read_csv. Voir dataframes pandas. Pandas permet également de lire les données au format xls et xlsx (Excel).

with open('ventes_new.csv') as f:
    data = pandas.read_csv(f)
print(data)

avec data une structure de données de type DataFrame.

exemple : on représente les ventes selon (1) la dimension géographique et (2) la dimension temporelle

T = pandas.pivot_table(data, values = 'MONTANT', index = ['PAYS'], columns = ['ANNEE'], aggfunc=np.sum)
print(T)

Evolution des ventes au cours de l'année pour la France seulement:

selection = data[data.PAYS == "France"]
T2 = pandas.pivot_table(selection, values = 'MONTANT', index = ['ANNEE'], columns = ['VILLE'],  aggfunc=np.sum)
print(T2)
 
T2.plot(kind='bar', subplots = 'True')
plt.show()

Ici les données sont organisées autour de plusieurs dimensions. L'agrégation consiste:

• à positionner les données sur des axes (temporels, géographiques,…)
• ou à les organiser de manière hiérarchique en classes (et sous-classes) selon la valeur d'un ou plusieurs attributs.

Exemple de hiérarchie:

• pays > région > département

• (qui?) Quels sont les magasins les plus rentables? doit-on ouvrir / fermer des magasins?
• (Où?) répartition des appels/consultation des sites en fonction de l'heure de la journée
• (qui?) Quelle est la liste des clients à contacter?
• (quand?) De quelle quantité doit-on approvisionner quels magasins en fonction de la période de l’année?

Problèmes :

• définir les bons intervalles temporels?? créneaux horaires?
• définir des secteurs géographiques?

• un fait est une association située au centre du schéma. Les attributs de l’association sont les mesures effectuées
• une dimension est une relation participant au fait. Les dimensions sont donc décrites par des attributs (ex : attributs année, trimestre, mois, jour, heure, minute, seconde,…pour une dimension temporelle)
• pour chaque dimension, on décrit une hiérarchie sur les différents attributs de la dimension en définissant un ordre, du particulier au général.

• sur la dimension temporelle : mois ⊂ trimestre ⊂ année
• sur la dimension promotion : nom ⊂ catégorie ⊂ média ⊂ type de média

etc…

• Ventes

• Ventes

• Pistes

Un cube de données est une structure de données organisée sur le principe des espaces vectoriels. Différents axes sont définis, chaque axe étant associé à une dimension particulière.

• Les dimensions peuvent correspondre à des valeurs discrètes (catégories : type de produit, catégorie de client,…) ou continues (valeurs temporelles ou géographiques, …).
• Chaque fait est décrit comme un point de l’espace vectoriel. Il est positionné dans une cellule du cube. A ce point sont associées une ou plusieur mesures.
• Le cube est un ensemble de cellules (voir figure), chaque cellule correspondant à un intervalle (sur les axes continus) ou une valeur (sur les axes discrets).

Un élément essentiel du modèle de données est la définition de hiérarchies sur les dimensions du cube. Chaque dimension se divise en intervalles et sous-intervalles (pour le continu/ quantitatif) ou en catégories et sous-catégories (pour le discret/qualitatif)

Les hiérarchies sur les différentes dimensions permettent de définir le “niveau de résolution” sur les différentes dimensions.

• On peut ainsi s’intéresser à l’évolution d’une certaine grandeur au cours du temps année par année, trimestre par trimestre ou mois par mois selon le niveau de résolution choisi.
• → Hiérarchie : description arborescente d’intervalles et de sous-intervalles sur une dimension. Implemente differentes granularités sur la dimension considérée.

La structure de cube de données est adaptée pour la réalisation d’histogramme multidimensionnels, selon les axes choisis et le niveau de résolution choisi, à l’aide de fonctions d’aggrégation.

• Histogramme et aggrégation
  • (vue quantitative) comptage/répartition d’événements sur un intervalle (discrétisaton d’une distribution d’événements)
  • (vue qualitative) comptage d’événements par catégorie
  • (vue intermediaire) comptage d’événements par catégories hiérarchisées

REPRESENTATION DES DONNEES : Représenter des jeux de valeurs de grande taille de façon plus synthétique (algorithmes de réduction de dimension)

REGROUPEMENT (“CLUSTERING”) : Définir des regroupements (ou des classements simples ou hiérarchiques) entre jeux de valeurs

COMPLETION : Méthodes de classification automatique (ou d’interpolation) visant à deviner soit la classe, soit certaines valeurs non mesurées, à partir d’un jeu de valeurs et d’une base d’exemples complets. Il existe des méthodes paramétriques ou non paramétriques.

ESTIMATION ET DECISION : Méthodes visant à estimer la “valeur” associée à un jeu de données (pour l’aide à la décision)