Source Latex: TP de mathématiques

Fichier

Type: TP

File type: Latex, tex (source)

Télécharger le document pdf compilé

Description

TP sur la compression de données - Initiation à la compression et à la programmation en Matlab

Niveau

Algorithmique et programmation: Terminale, BTS, Post-Bac

Mots clé

Matlab, programmation, initiation, compression, type de données, structures de données

Quelques devoirs

Voir aussi:

Documentation sur LaTeX

Source Latex

Source Latex

\documentclass[12pt]{article}
%\usepackage{french}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage{a4wide}
\usepackage{graphicx}
\usepackage{epsf}
\usepackage{pst-all}
\usepackage{ifthen}
\usepackage{calc}
\usepackage{pst-all}

\usepackage{hyperref}
\hypersetup{
    pdfauthor={Yoann Morel},
    pdfsubject={Matlab},
    pdftitle={Initiation et travaux pratiques en Matlab},
    pdfkeywords={Matlab, simulation, programmation, 
      compression de données, traitement données, type de données}
}
\hypersetup{
    colorlinks = true,
    linkcolor = red,
    anchorcolor = red,
    citecolor = blue,
    filecolor = red,
    urlcolor = red
}
\voffset=-1cm
% Raccourcis diverses:
\newcommand{\nwc}{\newcommand}
\nwc{\dsp}{\displaystyle}
\nwc{\bge}{\begin{equation}}\nwc{\ene}{\end{equation}}
\nwc{\bgar}{\begin{array}}\nwc{\enar}{\end{array}}
\nwc{\bgit}{\begin{itemize}}\nwc{\enit}{\end{itemize}}
\nwc{\bgmp}{\begin{minipage}}\nwc{\enmp}{\end{minipage}}

\nwc{\ct}{\centerline}
\nwc{\V}[1]{\overrightarrow{#1}}


\nwc{\la}{\left\{}\nwc{\ra}{\right\}}
\nwc{\lp}{\left(}\nwc{\rp}{\right)}
\nwc{\lb}{\left[}\nwc{\rb}{\right]}

\nwc{\bgsk}{\bigskip}
\nwc{\vsp}{\vspace{0.1cm}}
\nwc{\vspd}{\vspace{0.2cm}}
\nwc{\vspt}{\vspace{0.3cm}}
\nwc{\vspq}{\vspace{0.4cm}}


\newcounter{ntp}%[section]
\setcounter{ntp}{1}
\newenvironment{TP}[1]{%
\setcounter{equation}{0}\setcounter{subsection}{0}
\section*{ \underline{TP \arabic{ntp} :} #1}
\addcontentsline{toc}{section}{\underline{TP \arabic{ntp} :}\ #1}
\stepcounter{ntp}}{}

\nwc{\bgTP}{\begin{TP}}\nwc{\enTP}{\end{TP}}


\def\N{{\rm I\kern-.1567em N}}                              % Doppel-N
\def\No{\N_0}                                               % Doppel-N unten 0
\def\R{{\rm I\kern-.1567em R}}                              % Doppel R
\def\C{{\rm C\kern-4.7pt                                    % Doppel C
\vrule height 7.7pt width 0.4pt depth -0.5pt \phantom {.}}}
\def\Z{{\sf Z\kern-4.5pt Z}}                                % Doppel Z

% grec et autres
\nwc{\lbd}{\lambda}
\nwc{\vphi}{\varphi}
\nwc{\ga}{\gamma}
\def\epsi{\varepsilon}
\def\tht{\theta}

\nwc{\tm}{\times}

\nwc{\ul}{\underline}
\nwc{\scp}[1]{\scriptsize{#1}}

\author{Y. Morel}
\date{}

\headheight=0cm
\textheight=26cm
\topmargin=-1.8cm
\footskip=.8cm
\textwidth=17.6cm
\oddsidemargin=-1.cm
%\parindent=0.2cm

\usepackage{fancyhdr}

\newenvironment{centerpage}{\vspace*{\fill}}{
	\protect\vspace*{\fill}}

\begin{document}


\pagestyle{fancyplain}
\setlength{\headheight}{0cm}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.1pt}
\lhead{}\chead{}\rhead{}

\lfoot{Y. Morel - \url{https://xymaths.fr/Matlab/}}
\rfoot{Compression de données - \thepage/\pageref{LastPage}}
\cfoot{}

\vspace*{1cm}

\nwc{\TPtop}{}
\newlength{\lgr}
\newlength{\TPtopLarge}
\newlength{\EXX}
\newlength{\Tlgr}
\newlength{\TopHeight}
\newlength{\TopTitleHeight}

\newcommand{\ChapTitle}[3]{
  \renewcommand{\TPtop}{{\LARGE\bf #1} {\Huge\bf#2}}
  \settowidth{\lgr}{\LARGE\bf #1}
  \settowidth{\TPtopLarge}{\TPtop}
  \settoheight{\EXX}{\LARGE X}
  \settowidth{\Tlgr}{\LARGE T}
  \setlength{\Tlgr}{0.5\Tlgr}
  \settototalheight{\TopHeight}{\fbox{\bgmp{\linewidth}\begin{center}{\LARGE\bf#3}\end{center}\enmp}}
  %%
  \noindent
  \bgmp{\linewidth}
  \psline(\lgr,\EXX)(1.1\lgr,\EXX)
  \psline(\TPtopLarge,\EXX)(\linewidth,\EXX)%
  (\linewidth,-1.\TopHeight)(\Tlgr,-1.\TopHeight)%
  (\Tlgr,-0.05)
  \TPtop
  \vspace{-0.5\EXX}
  \begin{center}
    {\LARGE\bf#3}
  \end{center}
  \enmp%
  \vspace{0.5cm}
}


\setcounter{ntp}{6}
\ChapTitle{TP}{\thentp}{Compression de données}
\addcontentsline{toc}{section}{\ul{TP \arabic{ntp} :}\ Compression de données}

Un message, ou texte, numérique est une suite de nombres binaires 
(de 0 et 1). Cette suite de nombres provient, par exemple, du 
codage binaire d'un texte alphanumérique (en français par exemple...). 
Chaque caractère du texte, les lettres de l'alphabet (y compris les 
caractères spéciaux : espaces, virgules,...) sont remplacés par un 
nombre à $b$ chiffres constitué de 0 et 1. 

En général, on utilise un codage de chaque lettre sur 8 bits, 
i.e. une séquence de 8 chiffres binaires. On peut ainsi coder 
différemment $2^8=256$ caractères : c'est le code ASCII. 

Ainsi un texte alphanumérique composé de $N$ caractères est 
représenté par $N\times 8$ bits, soit $N$ octets. 
Le but de ce TP est de mettre en \oe uvre une méthode de compression 
de données, i.e. une méthode de réduction du nombre d'octets utilisés 
pour coder un message.


Il arrive fréquement qu'un texte donné présente des répétitions : 
des caractères utilisés bien sûr (seulement 26 lettres composent 
notre alphabet...), mais aussi répétitions de mots complets, voir 
séquences de mots...

C'est cette observation qui est à la base des méthodes de
compression : au lieu de coder un message par une suite de nombres 
binaires directement issue du codage de chaque caractère successif 
constituant le message, on code le message suivant deux listes : 
la liste des mots utilisés (bien sûr sans répétition cette fois), 
ou dictionnaire, et la liste des positions de chaque mots du
dictionnaire dans le message original. 

Sous réserve d'un nombre assez important de répétitions des mots du 
dictionnaire utilisé, la taille de ces deux listes peut-être bien 
moindre que celle du codage direct du message. 

\bgsk
\bgit
\item[1-] Ecrire une fonction Matlab générant un message de $N$ 
  mots codés sur 8 bits (soit un message de $8N$ bits, ou $N$ octets, 
  au total), n'utilisant (ou répétant) que $n$ mots d'un
  dictionnaire. 

  On pourra commencer par créer le dictionnaire comme étant une
  matrice (ou tableau) à $n$ lignes (une pour chaque mot) et $8$
  colonnes; chaque ligne de ce tableau étant une suite aléatoire de 8
  chiffres binaires. 

  Ensuite, le message peut se construire en choisissant aléatoirement
  des mots dans ce dictionnaire, que l'on concaténera. 

  \vspd
  Ce message étant construit, on considère par la suite que ce
  dictionnaire est inconnu; seul le message de $N$ mots est donné. 

\bgsk
\item[2-] Ecrire une fonction Matlab {\it Compress} qui permet de 
  compresser ce message.

  Le principe de cette fonction est le suivant. 
  On part du premier mot du message (premier octet), on l'ajoute à 
  au dictionnaire (liste des mots du message, sans répétition), 
  on recherche dans le message les autres occurences de ce mot, et 
  on enregistre dans un tableau la position dans ce message de ces 
  occurences. 

  On réitère ensuite le procédé à partir du mot suivant dans le message 
  qui n'est pas encore dans le dictionnaire. 

  On crée ainsi deux tableaux : le premier est le dictionnaire, le 
  deuxième contient la position de chacun des mots du dictionnaire 
  dans le message
  
  \vspd
  On pourra construire une fonction intermédiaire retournant le
  $n^{\mbox{\scriptsize{ème}}}$ mot du message. 

\bgsk
\item[3-] Ecrire une fonction Matlab {\it DeCompress} permettant, 
  à partir des deux tableaux précédants de reconstruire le message, 
  et s'assurer ainsi que l'on a bien un codage équivalent du message 
  original.

\bgsk
\item[4-] Calculer le taux de compression obtenu, i.e. le ratio 
  taille des deux tableaux "compressés" sur taille du message 
  initial. 
\enit

\label{LastPage}
\end{document}

Télécharger le fichier source