-
Notifications
You must be signed in to change notification settings - Fork 2
/
Elaborato.tex
executable file
·207 lines (176 loc) · 7.09 KB
/
Elaborato.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
\documentclass[twoside,openright,titlepage,fleqn,
headinclude,11pt,a4paper,BCOR5mm,footinclude
]{scrbook}
%--------------------------------------------------------------
\input{custom-commands-for-title-page.tex}
%--------------------------------------------------------------
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[square,numbers]{natbib}
\usepackage[fleqn]{amsmath}
\usepackage[english]{babel}
\usepackage{ae,aecompl}
\usepackage[pdftex]{graphicx}
\usepackage{latexsym}
\usepackage{amsthm, amssymb}
\usepackage{rotating}
\usepackage{boxedminipage}
\usepackage{multicol}
\usepackage{rotating}
%--------------------------------------------------------------
\usepackage{dia-classicthesis-ldpkg}
%--------------------------------------------------------------
% Options for classicthesis.sty:
% tocaligned eulerchapternumbers drafting linedheaders
% listsseparated subfig nochapters beramono eulermath parts
% minionpro pdfspacing
\usepackage[eulerchapternumbers,subfig,beramono,eulermath,
parts]{classicthesis}
%--------------------------------------------------------------
\newlength{\abcd} % for ab..z string length calculation
% how all the floats will be aligned
\newcommand{\myfloatalign}{\centering}
\setlength{\extrarowheight}{3pt} % increase table row height
\captionsetup{format=hang,font=small}
%--------------------------------------------------------------
% Layout setting
%--------------------------------------------------------------
\usepackage{geometry}
\geometry{
a4paper,
ignoremp,
bindingoffset = 1cm,
textwidth = 13.5cm,
textheight = 21.5cm,
lmargin = 3.5cm, % left margin
tmargin = 4cm % top margin
}
%--------------------------------------------------------------
\usepackage{listings}
\usepackage{hyperref}
\usepackage{pdfpages}
% My Theorem
\newtheorem{oss}{Observation}[section]
\newtheorem{exercise}{Exercise}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newcommand{\vect}[1]{\boldsymbol{#1}}
% questo comando e' relativo alle correzioni che puo
% apportare il prof se lo desidera.
\newcommand{\prof}[1]{\boldsymbol{#1}}
\DeclareRobustCommand{\ticket}[1]{\setlength{\fboxsep}{2pt}\ensuremath{\framebox{\small\makebox[\totalheight]{#1}}}}
% instead of boldsymbol I can use the arrow above the letter with
%\newcommand{\vect}[1]{\vec{#1}}
% page settings
% \pagestyle{headings}
%--------------------------------------------------------------
\begin{document}
\frenchspacing
\raggedbottom
\pagenumbering{roman}
\pagestyle{plain}
%--------------------------------------------------------------
% Frontmatter
%--------------------------------------------------------------
\include{titlePage}
\pagestyle{scrheadings}
%--------------------------------------------------------------
% Mainmatter
%--------------------------------------------------------------
\pagenumbering{arabic}
% settings for the lstlisting environment
\lstset{
language = R
, numbers = left
, basicstyle=\sffamily%\footnotesize
% , frame=single
, tabsize=2
, captionpos=b
, breaklines=true
, showspaces=false
, showstringspaces=false
}
\tableofcontents
% \part{Analysis part}
\chapter{Lectures notes}
\input{on-combinatorics.tex}
\input{generating-functions-basics.tex}
\input{generating-functions-examples.tex}
\input{generating-functions-applied-to-qs-about-checks.tex}
\input{generating-functions-applied-to-qs-about-swaps.tex}
\input{inverse-of-G-operator.tex}
\chapter{Sequential search simulation}
\input{sequential-search-simulation.tex}
\chapter{Generating binary trees at random}
\input{random-binary-trees.tex}
\chapter{Appendix}
\label{chapter:appendix}
\section{Project description}
In this section we explain some details ``under the hood'' of the
implementation of this project.
We've used the statistical environment R to use its very efficient
functions to perform uniform sampling (required by the Atkinson and
Sack algorithm) and $\chi^2$ test in order to check the randomness of
the generator. To produce the images with all different trees with $n$
nodes, we've used the OCaml language to use its functional power.
The two programs works together: the entry point for the user are the
R functions (which can be loaded in any R interpreter). During their
computation, they invoke an OCaml program giving their argument in
form a file written on the file system. The OCaml program parse the
input file, compute the representation of trees and write them back in
another file. The control return to R functions, which invoke the
\emph{graphviz} programs to build a representation of trees in image
form.
\section{Maxima interaction}
We've tested some the theoretical results with the engine Maxima, an
open source tool similar to Maple, saving all the stuff in the file
\texttt{maxima-worksheet.wxm}. It is possible to run Maxima, load the
file and experiment with it. It has been useful because has a feature
to export the results directly in \LaTeX ready form, for instance:
\\
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o179) }
\mathrm{leaves}\left( n\right) :=\frac{n\,\left( n+1\right)
}{2\,\left( 2\,n-1\right) }
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o181) }
[[1,1],[2,1],[3,1.2],[4,1.429],[5,1.667],[6,1.909],[7,2.154],[8,2.4],
[9,2.647]
\end{math}\\
%%%%%%%%%%%%%%%
\section{Project hosting}
This entire work, including the source code for the document you're
reading, the R functions and the OCaml implementations are completely
available for download at:\\
\href{https://github.com/massimo-nocentini/pacc}{https://github.com/massimo-nocentini/pacc}\\
It is possible to clone the entire Git repository typing the following
command in a Unix terminal:\\
\texttt{git clone git@github.com:massimo-nocentini/pacc.git}\\
A compiled version of this document is available at: \\
\href{https://github.com/massimo-nocentini/pacc/blob/master/compiled-versions/Elaborato.pdf}{https://github.com/massimo-nocentini/pacc/blob/master/compiled-versions/Elaborato.pdf}
\section{Original article about random binary trees generation}
In the last pages of this document we report the original article
about the algorithm for random trees generation written by Atkinson
and Sack (this isn't our work, we report it here because it is
difficult to find and it is just for getting the reading experience of
this document more complete).
\includepdf[pages={-}]{atkinson-sack-original-article.pdf}
% \section{Full code for random binary trees generation}
% The following block contains the functions written in \emph{R} to
% implement the algorithms related to the generation of binary
% trees. Those functions allow to generate the outputs attached in the
% previous chapters:
% \lstinputlisting{random-trees-generation/generator.R}
% \section{Full code for trees analysis and dot representation}
% The following block contains the functions written in \emph{OCaml} to
% implement the algorithms related to the analysis of the generated
% trees and its dot representation:
% \lstset{language=ML}
% \lstinputlisting{trees-generation-ocaml/main.ml}
\newpage
\input{licences.tex}
\end{document}