Une donnée informatique est un élément d'information ayant subi un encodage numérique
Possibilité de la conserver sur un support de stockage numérique (CD-ROM, disque dur, SSD, …)
Les informations peuvent être stockés dans un fichier (ex : fichier csv).
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…
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,…
un champ de bits (dont la longueur est exprimée en octets)
un processus de décodage : le format (ou type)
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…).
Tout commence par une fiche à remplir…
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.
Exemples de structures de données (cours d'algorithmie):
listes,
listes de listes,
dictionnaires,
arbres,…
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.
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.
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
Exemples :
Requêtes http :
demande de consultation d’une page web
URL = référence vers un fichier
Moteur de recherche :
recherche de pages contenant les mots-clés spécifiés
Bases de données : utilisation d’un langage de requête :
SELECT *
FROM Eleves
WHERE NOM = 'Dugenou'
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…).
Le tableau statique correspond à l'organisation séquentielle fondamentale des mémoires informatique :
taille limitée du support matériel
données accessibles grâce à leur adresse (position dans le tableau)
problème de rangement:
il faut conserver une information sur la position des données déjà enregistrées
organisation logique des données sur le support.
Dans un tableau statique T, la position des cases reste fixe au cours de l'utilisation :
T[i] désigne toujours la mếme zone mémoire
Analogie : les pages d'un cahier
Dans un tableau dynamique (liste python par exemple), la position des cases varie au cours de l'utilisation :
T[i] ne désigne pas toujours la mếme zone mémoire
Analogie : briques de lego, puzzle glissant
Adresse
savoir où enregistrer les données
savoir comment les retrouver
d’ajouter des données
d'effacer des données
d’accéder rapidement à une case particulière
Problème : définir des opérations :
qui conservent la propriété du tableau
Algo : insertion
Données :
- d : donnée à insérer
- T : tableau de données
- k : indice
Début :
T[k] <-- d
k <-- k + 1
Fin
Algo : recherche
Données :
- d : donnée à trouver
- T : tableau de données
- k : indice
Retourne :
un indice
Début :
pour i de 0 à k-1 :
si T[i] = d:
retourner i
retourner -1
Fin
Algo : suppression
Données :
- d : donnée à supprimer
- T : tableau de données
- k : indice
Début :
i <-- recherche(d,T,k)
si i != -1:
T[i] <-- T[k-1]
k <-- k-1
Fin
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 :
son adresse i
le nombre m de cases occupées
un indicateur LIBRE/OCCUPE
Stratégies d'allocation
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é)
Écrire un algorithme permettant d'insérer une donnée d de taille m dans le premier bloc libre disponible (pensez à mettre à jour la table d'allocation B).
Algo : insertion
Données :
- T: tableau de données
- d: donnée à insérer
- m: taille de la donnée
- B: table d allocation
Retourne:
adresse de d après insertion
Début
pour tout triplet (i,m_i,f_i) dans B:
si m_i <= m et f_i = LIBRE:
T[i] <-- d
supprimer (i, m_i, f_i) dans B
insérer (i, m, OCCUPE) dans B
insérer (i+m, m_i-m, LIBRE) dans B
retourner i
retourner -1
Fin
On appelle liste une structure abstraite ordonnée telle que:
l'on puisse accéder de manière directe à l'élément i
et à laquelle on puisse ajouter (et supprimer) autant d'éléments que l'on souhaite.
Une caractéristique importante de cette structure est son nombre d'éléments.
On commence par créer un tableau de taille n = 1,
Le nombre initial d éléments est k = 0
A chaque ajout d élément:
si k < n,
ajouter l élément à la position k
k ← k + 1
sinon :
allouer un tableau à 2 * n éléments
n ← n * 2
copier les k premiers éléments du tableau initial dans le nouveau tableau
supprimer le tableau initial
ajouter l élément à la position k
k ← k + 1
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 suppose l'existence d'une bijection entre l'ensemble des données et l'ensemble des clés, permettant d'assurer l'unicité et la spécificité de la clé.
Soient d1 et d2 deux enregistrements,
Unicité :
si d1=d2 alors id(d1)=id(d2).
Spécificité:
si id(d1)=id(d2), alors d1=d2.
La recherche par identifiant repose sur une fonction d'adressage H qui à tout identifiant id(d) associe sa position (adresse) ref(d) dans un tableau de données:
H: ens. des identifiants → ens. des adresses
id(d) → ref(d)
Ainsi si id est l'identifiant servant à la recherche, l'extraction des informations se fait en 2 étapes:
ref=H(id) (lecture de l'adresse des données)
d=T[ref] (lecture de la donnée elle-même)
Exemple : avec des listes:
Soit une liste:
L=((id1:ref1),(id2:ref2),…,(idN:refN))
telle que id1<id2<…<idN,
La recherche de l'adresse dans lune liste triée s'effectue en O(log N) (recherche dichotomique).
Exemples d'adressages:
Définition : On appelle index la structure de données qui implémente la fonction d'adressage
Un identifiant entier, codé sur 4 octets, permet d'indexer jusqu'à données différentes.
Index
E
ref
id
L'exemple le plus simple d'indexation est celui fourni par les numéros de case d'un tableau.
!! L'ajout ou la suppression
de données viole
le principe d'unicité
de l'index
Maintenance centralisée d'un index
l'unicité de l'identifiant
d --> id
l'intégrité de l'index (fonction d'adressage)
id --> d
Exemple :
Coût :
O(n) en mémoire
O(log n) pour la vérification, O(n) pour l'ajout
Exemple :
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(n) en mémoire (adressage)
O(1) pour l'ajout
Exemples d'indexation centralisée :
numéro INE (étudiants)
numéro URSSAF (sécurité sociale)
numéro d'immatriculation (véhicules)
numéro de compte en banque
code barre
etc.
Utilisation d'une fonction de hachage :
H : ens des données --> ens. des identifiants
d --> id = H(d)
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.
id = int.from_bytes(d, byteorder='big')
avantage : les données différentes ont un code entier différent
mais : |int(d)| = |d| donc |id| =|d|
s = 'paul.poitevin@centrale-marseille.fr'
d = bytes(s, 'ascii')
id = int.from_bytes(d, byteorder='big')
print("id =", id
Donne :
id = 852806586114976881510056778471769180697471859150728801241505293627173168229624211058
!! viole le principe de compacité
Soit i = int(d):
Méthode 1 : le modulo r (reste de la division entière par r)
id = H(i) = i mod r
Avantage :
Inconvénient:
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)
ce codage revient à sélectionner les bits de poids faible
deux données différentes peuvent avoir le même code
—> il faut prendre r premier
Soit i = int(d):
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
On commence par créer un tableau de taille n = 1, le nombre initial d'éléments étant m = 0
A chaque ajout d'un élément d : id <-- H(d)
si T[id] n'est pas occupé,
ajouter l'élément à la position id
sinon :
si T[id] != d
allouer un tableau à 2 * n éléments et n ← n * 2
copier les m premiers éléments du tableau initial dans le nouveau tableau & supprimer le tableau initial.
répéter l'opération si nécessaire jusqu'à pouvoir ajouter l'élément d à la position H(d)
id
H(id)
d
unicité
intégrité
intégrité
M E M O I R E
H - S E T
dict = {}
commande = {'entree': 2, 'plat': 4, 'dessert': 2, 'café': 1}
commande['aperitif'] = 3
commande['café'] += 1
del commande['entree']
if 'café' in commande :
commande['café'] += 1
else:
commande['café'] = 1
Le dictionnaire Python est une structure de données extrêmement flexible et expressive:
arbre = {val : 12,
gauche: {val:6,
gauche:None,
droit:None},
droit: {val:15,
gauche:None,
droit:None}}
}
promo2022 = {'demi promo A' :
{
'TD1' : 26,
'TD2' : 25,
...
},
'demi promo B' :
{
'TD6' : 27,
'TD7' : 25,
...
}
}
Le volume est le support sur lequel sont enregistrées les données.
On parle de mémoire secondaire (Disque dur, disquette,CD-ROM, etc…).
Un volume est divisé en pistes concentriques numérotées de 0 à n ( par ex n = 1024).
Chaque piste supporte plusieurs enregistrements physiques appelés secteurs, de taille constante (1 secteur = 1 page).
Les pages sont les unités de base pour la lecture et l'écriture.
une page est une zone contiguë de la mémoire secondaire qui peut être chargée en mémoire centrale en une opération de lecture.
Taille standard : une page = 1-2 ko.
La mémoire secondaire est donc organisée comme un tableau de pages : (T[0],…,T[n-1]),
où n est le nombre de pages.
Chaque page fait m octets.
Chaque page peut être libre ou occupée (allocation).
La mémoire secondaire n’est pas directement accessible (les programmes n’ont pas la possibilité d’aller écrire directement sur le disque).
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.
A retenir :
Un fichier est une référence vers un ou plusieurs blocs de données, enregistrés sur un support physique.
Un fichier est caractérisé par son descripteur, constitué de
son nom,
son chemin d’accès,
ses droits d’accès (lecture/écriture/exécution) selon les utilisateurs,
sa position sur le support,
sa taille, etc…
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:
ouverture : initialisation d'un flux en lecture ou en écriture
lecture : consultation des lignes l'une après l'autre (à partir de la première ligne), dans l'ordre où elles ont été écrites sur le support
écriture : ajout de nouvelles données à la suite ou en remplacement des données existantes
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)
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,
s = f.readline()
for s in f :
print s
try :
f = open('/chemin/vers/mon/fichier.dat','w')
except IOError:
print "Erreur d'ouverture!"
Lorsque l’opération d’ouverture est réalisée avec succès,
f.write("Commande enregistrée:")
for k in commande:
f.write(k + ':' + str(commande(k)))