From 5cc0d45db39afff3bceae05977c89709cf9dd30a Mon Sep 17 00:00:00 2001 From: Pixel Date: Wed, 2 May 2001 00:39:39 +0000 Subject: Plop --- doc/Dumb.doc.fr | 0 doc/Makefile.am | 11 ++++- doc/Makefile.doc | 30 +++++++++++++ doc/bib.tex | 7 +++ doc/conclusion.tex | 9 ++++ doc/description.tex | 19 ++++++++ doc/intro.tex | 11 +++++ doc/manuel.tex | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++ doc/outils.tex | 21 +++++++++ doc/polynom.tex | 83 +++++++++++++++++++++++++++++++++++ 10 files changed, 314 insertions(+), 1 deletion(-) delete mode 100644 doc/Dumb.doc.fr create mode 100644 doc/Makefile.doc create mode 100644 doc/bib.tex create mode 100644 doc/conclusion.tex create mode 100644 doc/description.tex create mode 100644 doc/intro.tex create mode 100644 doc/manuel.tex create mode 100644 doc/outils.tex create mode 100644 doc/polynom.tex (limited to 'doc') diff --git a/doc/Dumb.doc.fr b/doc/Dumb.doc.fr deleted file mode 100644 index e69de29..0000000 diff --git a/doc/Makefile.am b/doc/Makefile.am index 54d0db0..c894a53 100644 --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -1 +1,10 @@ -EXTRA_DIST = Dumb.doc.fr +ps: + make -f Makefile.doc ps + +clean: + make -f Makefile.doc clean + +distclean: + make -f Makefile.doc clean + +EXTRA_DIST = bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex polynom.tex diff --git a/doc/Makefile.doc b/doc/Makefile.doc new file mode 100644 index 0000000..f71be85 --- /dev/null +++ b/doc/Makefile.doc @@ -0,0 +1,30 @@ +PROJET=polynom + +all: $(PROJET).dvi + +$(PROJET).dvi: bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex polynom.tex source.tex + echo + echo pass1 + echo + latex $(PROJET) + echo + echo pass2 + echo + latex $(PROJET) + +source.tex: + echo '\section{Includes}' > source.tex + for i in `find ../include -name *.h` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex + echo '\section{Sources de la librairie}' >> source.tex + for i in `find ../lib -name *.c` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex + echo '\section{Sources du frontend}' >> source.tex + for i in `find ../src -name *.c` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex + +ps: $(PROJET).ps + +$(PROJET).ps: $(PROJET).dvi + dvips $(PROJET) + +clean: + rm -f *.dvi *.aux *.toc *.ps *.log source.tex + diff --git a/doc/bib.tex b/doc/bib.tex new file mode 100644 index 0000000..1203fbb --- /dev/null +++ b/doc/bib.tex @@ -0,0 +1,7 @@ +\begin{thebibliography}{WWW99} +% pour citer le Tanenbaum : \cite{Tanenbaum} +% pour citer le Tanenbaum page 238 : \cite[page 238]{Tanenbaum} + +\bibitem[COR]{Cormen} T. Cormen, C. Leiserson, R. Rivest \textit{Introduction à l'algorithmique}, Dunod. + +\end{thebibliography} diff --git a/doc/conclusion.tex b/doc/conclusion.tex new file mode 100644 index 0000000..e5d9edf --- /dev/null +++ b/doc/conclusion.tex @@ -0,0 +1,9 @@ +\chapter*{Conclusion} +\addcontentsline{toc}{chapter}{Conclusion} +\markboth{CONCLUSION}{CONCLUSION} + +Ce projet a été mené à terme, et l'ensemble des conditions du sujet ont été respectées. +L'effort de recherche mené sur la manière d'implémenter les algorithmes en C++ a +sans aucun doute été profitable pour notre connaissance personnelle. De plus, les algorithmes +implémentés sont "durables": ils peuvent nous resservir dans n'importe quel autre projet nécessitant +des structures de files de priorités, ce qui porte un intérêt quant au développement de ce projet. diff --git a/doc/description.tex b/doc/description.tex new file mode 100644 index 0000000..e86c698 --- /dev/null +++ b/doc/description.tex @@ -0,0 +1,19 @@ +\chapter{Description} +\paragraph{} +Nous allons décrire dans cette première partie tous ce que nous avons effectué comme travail de réflexion afin de +programme ce projet. Il y a beaucoup de détails relatifs à l'implémentation dont nous ne parlerons pas, comme les structures +sur les listes chaînées, ou l'initialisation du terminal pour gérer le menu du programme de test. En revanche, nous appuyerons +sur les détails d'implémentation purement algorithmiques qui nous ont posé problème. +\paragraph{} +En ce qui concerne le langage de programmation, nous avons choisi le C++, car c'est le langage qui nous semblait le plus +adapté pour créer les structures de données nécessaire à la programmation de ce projet. +\paragraph{} +Nous avons implémenté les algorithmes de files de priorités suivants: +\begin{itemize} +\item Tas Binaire +\item Tas Binomial +\item Tas de Fibonacci +\item Liste chaînée triée +\end{itemize} +\paragraph{} +L'algorithme utilisant les files de priorité implémenté est l'algorithme de compression de dictionnaire Huffman. diff --git a/doc/intro.tex b/doc/intro.tex new file mode 100644 index 0000000..46d0e3c --- /dev/null +++ b/doc/intro.tex @@ -0,0 +1,11 @@ +\chapter*{Introduction} +\addcontentsline{toc}{chapter}{Introduction} +\markboth{INTRODUCTION}{INTRODUCTION} + +\paragraph{} +Ce projet a pour but d'une part l'implémentation d'algorithmes de files de priorités et l'implémentation d'un algorithme +utilisant ces files de priorités d'autre part. + +\paragraph{} +Ce présent document va tenter de décrire en totalité la progression de la +mise en forme de ce projet. Nous vous souhaitons bonne lecture. diff --git a/doc/manuel.tex b/doc/manuel.tex new file mode 100644 index 0000000..fcdc3af --- /dev/null +++ b/doc/manuel.tex @@ -0,0 +1,124 @@ +\chapter{Manuel d'utilisation} +\paragraph{} +Ce projet génère deux binaire. Le premier appelé testTas n'est qu'une petite application nous permettant d'utiliser l'API +C++ générée par notre classe de file de priorités. Voici un exemple d'exécution: +\begin{verbatim} +Priority list type: 0 - Binary Heap +Choice: Please select an action +a - Add a key into the priority list +c - Change priority list type +d - Delete a Key from the priority list +e - Extract Min onto the priority list +l - Lower Key onto a key of the priority list +p - Print the current priority list on the screen +r - Remove the whole priority list +t - Test the priority list algorithms +q - Quit +\end{verbatim} + +A partir de cet instant, le programme nous propose un menu nous permettant d'effectuer plusieurs actions sur le tas. La +fonction 'a' permet d'ajouter une clef dans le tas en cours. Comme il est impossible d'effectuer une recherche sur un tas +pour y retrouver le pointeur d'un élément, le programme nous propose de sauvegarder le pointeur résultat dans un tableau: + +\begin{verbatim} +Choice: Please select a slot to save the cell +0 - Empty slot +1 - Empty slot +2 - Empty slot +3 - Empty slot +4 - Empty slot +5 - Empty slot +6 - Empty slot +7 - Empty slot +8 - Empty slot +9 - Empty slot +n - Don't store +c - Cancel +\end{verbatim} + +Ce tableau apparaitra régulièrement dans toutes les fonctions du menu afin de choisir une cellule sur laquelle agir. Toutes +les fonctions du menu parlent d'elles mêmes. La fonction 't' va lancer une batterie de tests sur les algorithmes de la +file de priorité sélectionnée. + +\paragraph{} +Le deuxième binaire généré est 'Huffman'. Il sert à utiliser l'algorithme d'huffman implémenté. Voici sa ligne d'aide: +\begin{verbatim} +$ ./Huffman -h +Huffman [{-f|-i} file] {type} +Huffman -h +This will encode the input file with the Huffman code +using the priority list defined by type. +Type is a number taken from this list: + 0 : Binary Heap (default) + 1 : Binomial Heap + 2 : Fibonacci Heap + 3 : Sorted chained list +-f file means that you specify a dictionnary file which is + structured as described into the README file. +-i file means that you specify a file to encode. It will + built a quiet dumb dictionnary. +By default, a dictionnary will be built from stdin. +-h prints this help and exit. +\end{verbatim} + +La structure d'un dictionnaire est la suivante: +\begin{verbatim} +Mot1 : Fréquence1 +Mot2 : Fréquence2 +... +\end{verbatim} + +Chaque mot est une chaîne de caractères servant à identifier la fréquence associée. Voici un exemple complet de dictionnaire +et d'utilisation du programme avec ce dictionnaire: + +\begin{verbatim} +Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ cat dict.sample +MOT1 : 2000 +MOT2 : 1234 +MOT3 : 15987 +MOT4 : 1203 +MOT5 : 192837 +MOT6 : 12987 +Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ ./Huffman -f dict.sample +MOT3 (15987) = 00 +MOT1 (2000) = 0100 +MOT4 (1203) = 01010 +MOT2 (1234) = 01011 +MOT6 (12987) = 011 +MOT5 (192837) = 1 +Bitstream length : 283957 bits (= 35495 bytes) +Real size input : 7239936 bits (= 904992 bytes) +Size squeezed by : 96.0779 percents +Dictionnary size : 336 bits (= 42 bytes) +Total bitstream length : 284293 bits (= 35537 bytes) +Real gain (4 bytes header) : 96.0728 percents +\end{verbatim} + +Il est indiqué que le programme est capable de générer un dictionnaire à partir d'un fichier. Il s'agit simplement de compter +les caractères provenant de l'entrée et d'en générer un dictionnaire. Exemple: + +\begin{verbatim} +$ cat dict.sample | Huffman +\32 (12) = 00 +6 (1) = 01000 +4 (2) = 01001 +3 (4) = 0101 +0 (4) = 0110 +5 (2) = 01110 +7 (3) = 01111 +1 (6) = 1000 +M (6) = 1001 +: (6) = 1010 +\10 (6) = 1011 +O (6) = 1100 +8 (3) = 11010 +9 (3) = 11011 +2 (6) = 1110 +T (6) = 1111 +Bitstream length : 294 bits (= 37 bytes) +Real size input : 608 bits (= 76 bytes) +Size squeezed by : 51.6447 percents +Dictionnary size : 512 bits (= 64 bytes) +Total bitstream length : 806 bits (= 101 bytes) +Real gain (4 bytes header) : -38.1579 percents +\end{verbatim} diff --git a/doc/outils.tex b/doc/outils.tex new file mode 100644 index 0000000..69bbc53 --- /dev/null +++ b/doc/outils.tex @@ -0,0 +1,21 @@ +\chapter{Outils utilisés} +\paragraph{} +Pour développer ce projet, nous avons choisi d'utiliser une série d'outils GNU pour nous simplifier la tâche. +Nous utilisons entre-autres, GNU autoconf \& automake pour gérer notre arborescence de développement. Ainsi le +présent projet est découpé en ces répertoires: +\begin{itemize} +\item src contenant les sources des programmes exécutables. C'est notemment dans ce répertoire que seront stoqués +les binaires des exécutables produit par la compilation du projet. +\item lib contenant tous les sources purement algorithmiques, dont ne dépend pas l'implémentation finale. +\item include contenant tous les fichiers .h +\item doc contenant le source \LaTeX\ de cette présente documentation +\item po contenant les fichiers d'internationalisation (traduction française) +\item intl contenant le code source nécessaire au support de l'internationalisation. +\end{itemize} +En dehors de autoconf \& automake, nous avons utilisé un serveur CVS (Concurrent Version System) qui nous a permis +de travailler à plusieurs sur ce projet, sans avoir à nous soucier de rapatrier et de fusionner les codes sources +de tout le monde. +\paragraph{} +Enfin, pour pouvoir compiler ce projet, il suffit de taper la commande './configure' au shell et de suivre les instructions. +Les binaires seront placés dans le répertoire src. Pour générer cette documentation, il suffit d'aller dans le répertoire doc +et de taper 'make ps'. diff --git a/doc/polynom.tex b/doc/polynom.tex new file mode 100644 index 0000000..c4d4157 --- /dev/null +++ b/doc/polynom.tex @@ -0,0 +1,83 @@ +%initialisations---------------------------------------------------------------- +\documentclass[french,11pt,a4paper,twoside,openright]{report} +\usepackage[T1]{fontenc} +\usepackage[latin1]{inputenc} +\usepackage[francais]{babel} +\usepackage{a4} +\usepackage{ulem} +\usepackage{multirow} +\usepackage[dvips]{graphics} +\usepackage{vmargin} +\usepackage{fancyhdr} +\usepackage{oldstyle} +\usepackage{listings} +\usepackage{verbatim} +%fin des initialisations-------------------------------------------------------- + +\pagestyle{fancyplain} +\addtolength{\headwidth}{\marginparsep} +\addtolength{\headwidth}{\marginparwidth} +% titre de chapitre +\renewcommand{\chaptermark}[1]{\markboth{#1} {}} +% titre de section +\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}} + +\lhead[\fancyplain{}{\bfseries\textos{\thepage}}]{\fancyplain{}{\bfseries\rightmark}} +\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\textos{\thepage}}} +\cfoot{\fancyplain{\textos{\thepage}}{}} + +\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}} + +\def\addcontentsline#1#2#3{% + \addtocontents{#1}{\protect\contentsline{#2}{#3}{\textos{\thepage}}}} +% \setmargrb{leftmargin}{topmargin}{rightmargin}{bottommargin} +\setmargrb{1.5cm}{2cm}{1.5cm}{4cm} + +\begin{document} +\renewcommand{\chaptername}{Section} +\newcommand{\bracebits}{$\underbrace{\hspace{2cm}}$} + +%page de garde +\title{Projet de C\\ + Rapport \vspace{1.0cm}} +\author{Vagner Alain, Noble Nicolas\vspace{2.0cm}} +\date{\textit{dernière révision: \today}} +\maketitle +\strut\thispagestyle{empty} +\vfill +\pagebreak +\setcounter{page}{1} + + + +\tableofcontents + +\clearemptydoublepage + +\input{intro} +\clearemptydoublepage +\part{Analyse} +\input{description} +\clearemptydoublepage +\part{Synthèse} +\input{manuel} +\clearemptydoublepage +\input{outils} +\clearemptydoublepage + +\chapter{Code source} +\lstset{language=C++,basicstyle=\scriptsize,stringspaces=false} +\input{source} + +\clearemptydoublepage +\input{conclusion} +\clearemptydoublepage +\input{bib} +\clearpage +\strut\thispagestyle{plain} +\begin{tiny} +\begin{center} +Cette documentation a été réalisée sous Linux Slackware 7.1 à l'aide de \LaTeX\ et cvs. +\end{center} +\end{tiny} +\end{document} -- cgit v1.2.3