Épreuve d’Informatique – Session 2017 – Filière MP/ PSI/ TSI Page 1 sur 12 Les

Épreuve d’Informatique – Session 2017 – Filière MP/ PSI/ TSI Page 1 sur 12 Les candidats sont informés que la précision des raisonnements algorithmiques ainsi que le soin apporté à la rédaction et à la présentation des copies seront des éléments pris en compte dans la notation. Il convient en particulier de rappeler avec précision les références des questions abordées. Si, au cours de l'épreuve, un candidat repère ce qui peut lui sembler être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre. Remarques générales :  L'épreuve se compose de trois parties indépendantes.  Toutes les instructions et les fonctions demandées seront écrites en Python.  Les questions non traitées peuvent être admises pour aborder les questions ultérieures.  Toute fonction peut être décomposée, si nécessaire, en plusieurs fonctions. - * - * - *- * - * - *- * - * - *- * - * - * - Partie I : Base de données et langage SQL La compression des fichiers est une pratique aussi courante qu'indispensable en informatique. Elle consiste à stocker les données dans un nouveau format moins encombrant que l'original. Ce gain de place induit d'autres bénéfices dont le principal est l'accélération des transferts entre ordinateurs. Faire circuler moins de bits sur les réseaux diminue le temps de connexion, encombre moins les lignes de communication et limite les dépenses télématiques. La décompression rétablit le fichier dans son état initial. De nombreux algorithmes de compressions existent, chacun ayant sa particularité et surtout un type de données cible. Car toutes les données ne se compressent pas de la même manière. Un algorithme de compression de texte travaillera sur les répétitions du nombre de caractères ou de parties de phrases. Un algorithme de compression d’images travaillera quant à lui sur d’autres domaines comme la différence entre un pixel et un autre. On imagine cependant mal le second algorithme en train de compresser un texte. Néanmoins, tous les algorithmes de compression ont un point commun : leur objectif est de récupérer les données initiales partiellement, voire totalement. La décompression consiste à rétablir les données d’origine à l’aide du fichier compressé. Elle consiste souvent à appliquer l’algorithme de compression en sens inverse. Types de compressions : Il y a deux types majeurs de compressions : la compression sans perte et la compression avec perte. a- La compression sans perte : Une compression est dite sans perte si les données après décompression sont identiques aux données originelles. Ces compression se basent toutes sur le même principe : la répétition d’une donnée est une répétition de trop. L’objectif va être de supprimer le maximum de répétition pour obtenir une compression plus importante tout en étant capable de retrouver les répétitions retirées. En somme, ces compressions écrivent exactement les mêmes données mais de façon plus concise. Elles sont appliquées à tous types de données et les formats compressés sont très nombreux. Pour ne citer que les plus connus, nous retrouvons les formats : zip, rar, 7z, bz2, gz, ... Les algorithmes, moins connu du grand public, sont aussi très nombreux. Nous retrouvons par exemple le codage de Huffman, les codages de Lempel-Ziv, … b- La compression avec perte : Une compression est dite avec perte si les données après décompression sont différentes des données originelles. Épreuve d’Informatique – Session 2017 – Filière MP/ PSI/ TSI Page 2 sur 12 Elles sont appliquées à des données perceptibles, c'est-à-dire à des images, des sons ou des vidéos. Le principe va consister à supprimer les informations là où les sens de la vue et de l’ouïe ne les perçoivent que très peu. Par exemple, l’œil humain ne distingue que très peu les zones de contraste. Aussi, nous pouvons retirer des détails à ces zones sans trop impacter sur la qualité de l’image. Le nom de format représente directement le type de compression employé : jpeg, mpeg, mp3, divx, ... Taux de compression : Le taux de compression est une mesure de la performance d'un algorithme de compression. Il est exprimé en pourcentage. Le taux de compression est le gain en volume rapporté au volume initial des données. Plus le taux de compression est élevé, plus la taille du fichier compressé résultant est faible. La formule correspondante s'écrit :  = ( −       é        ) ∗ On dispose d’une base de données de chemin absolu : "C:\BDcompressions.sql", composée de trois tables : la table Algorithme, la table Fichier et la table Compression, dont les structures sont les suivantes :  Algorithme ( format (texte), type (entier) ) La table Algorithme contient différents formats d’algorithmes de compressions. Le champ format est la clé primaire. Le champ type contient la valeur 1, si l’algorithme de compression est du type avec perte de données, ou 0 sinon. Exemples de données de la table Algorithme : format type 7z 0 bz2 0 gz 0 jpeg 1 rar 0 zip 0 mp3 1 huffman 0 … …  Fichier ( numeroF (entier), nomF (texte), tailleF (entier) ) La table Fichier contient des fichiers de différents types : texte, image, son, vidéo … . Le champ numeroF est la clé primaire. Le champ nomF contient le nom complet de chaque fichier. Le champ tailleF contient la taille originale du fichier, exprimée en Octet. Exemples de données de la table Fichier : numeroF nomF tailleF 1 Cours Python.pdf 6 420 768 2 Nature.bmp 5 760 054 3 Langage SQL.doc 345 600 4 Chanson.wav 47 185 920 … … … Épreuve d’Informatique – Session 2017 – Filière MP/ PSI/ TSI Page 3 sur 12  Compression (numeroF (entier), format (texte), tailleC (entier) ) La table Compression contient les compressions de certains fichiers de la table Fichier. Les champs numeroF et format sont des clés étrangères. Le champ tailleC contient la taille du fichier compressé, exprimée en octet. Un fichier de la table Fichiers peut être compressé plusieurs fois, par différents algorithmes de compressions. Exemples de données de la table Compression : numeroF format tailleC 2 jpeg 291 441 2 png 2 622 545 2 zip 2 160 937 1 cab 5 768 938 1 zip 5 818 538 4 mp3 11 364 3 zip 145 366 3 7z 133 396 … … … I. 1- Écrire, en algèbre relationnelle, une requête qui donne pour résultat : Les noms des fichiers dont la taille originale est comprise entre 1 Kilo-octet et 1 Méga-octet. I. 2- Écrire une requête SQL, qui donne pour résultat : Les noms et les tailles des fichiers textes, dont le nom se termine par : .doc ou .docx, triés dans l’ordre alphabétique des noms des fichiers. I. 3- Écrire une requête SQL qui donne pour résultat : Les noms des fichiers compressés, les formats de compression, les types de compression, et le taux de compression de chaque fichier, dont le taux de compression dépasse 40%, triés dans l’ordre des numéros des fichiers. I. 4- Écrire une requête SQL qui donne pour résultat : Les algorithmes sans perte de données et le compte des fichiers compressés par chacun de ces algorithmes, dont ce compte est égal à 3, 5 ou 8. I. 5- Écrire une requête SQL qui donne pour résultat : Les 3 premiers grands taux de compressions, triés dans l’ordre croissant. I. 6- Écrire un programme Python qui saisi un format de compression, et qui affiche le taux moyen des taux des compressions de ce format, si le format saisi existe dans la base de données. Si le format saisi n’existe pas, le programme doit afficher le message : « Le format saisi n’existe pas dans la BD ». On suppose que le module sqlite3 est importé. Ce module contient les fonctions et les méthodes permettant de manipuler les bases de données : Connexion à une base de données : connect() Exécuter une requête : execute() Créer un curseur : cursor() Récupérer le résultat d’une requête : fetchone(), fetchall() Épreuve d’Informatique – Session 2017 – Filière MP/ PSI/ TSI Page 4 sur 12 Partie II : Programmation Python La compression de HUFFMAN La compression de Huffman est une méthode de compression de données sans perte proposé par « David Huffman » en 1952. C’est un processus qui permet de compresser des données informatiques afin de libérer de la place dans la mémoire d'un ordinateur. Or tout fichier informatique (qu'il s'agisse d'un fichier texte, d'une image ou d'une musique …) est formé d'une suite de caractères. Chacun de ces caractères étant lui- même code par une suite de 0 et de 1. L'idée du codage de Huffman est de repérer les caractères les plus fréquents et de leur attribuer des codes courts (c'est-a-dire nécessitant moins de 0 et de 1) alors que les caractères les moins fréquents auront des codes longs. Pour déterminer le code de chaque caractère on utilise un arbre binaire. Cet arbre est également utilisé pour le décodage. Dans uploads/Geographie/ cnc-2017.pdf

Tags
Administrationmatrice liste fonction compression écrire
Documents similaires
  • 21
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager