-
Notifications
You must be signed in to change notification settings - Fork 0
/
Relazione.html
174 lines (167 loc) · 34.3 KB
/
Relazione.html
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
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Algoritmi - Relazione di Laboratorio</title>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-D+9gmBxUQogRLqvARvNLmA9hS2x//eK1FhVb9PiU86gmcrBrJAQT8okdJ4LMp2uv" crossorigin="anonymous">
<style>
/*--------------------------------------------------------------------------------------------- * Copyright (c) Microsoft Corporation. All rights reserved. * Licensed under the MIT License. See License.txt in the project root for license information. *--------------------------------------------------------------------------------------------*/ body { font-family: "Segoe WPC", "Segoe UI", "SFUIText-Light", "HelveticaNeue-Light", sans-serif, "Droid Sans Fallback"; font-size: 14px; padding: 0 26px; line-height: 22px; word-wrap: break-word; } #code-csp-warning { position: fixed; top: 0; right: 0; color: white; margin: 16px; text-align: center; font-size: 12px; font-family: sans-serif; background-color:#444444; cursor: pointer; padding: 6px; box-shadow: 1px 1px 1px rgba(0,0,0,.25); } #code-csp-warning:hover { text-decoration: none; background-color:#007acc; box-shadow: 2px 2px 2px rgba(0,0,0,.25); } body.scrollBeyondLastLine { margin-bottom: calc(100vh - 22px); } body.showEditorSelection .code-line { position: relative; } body.showEditorSelection .code-active-line:before, body.showEditorSelection .code-line:hover:before { content: ""; display: block; position: absolute; top: 0; left: -12px; height: 100%; } body.showEditorSelection li.code-active-line:before, body.showEditorSelection li.code-line:hover:before { left: -30px; } .vscode-light.showEditorSelection .code-active-line:before { border-left: 3px solid rgba(0, 0, 0, 0.15); } .vscode-light.showEditorSelection .code-line:hover:before { border-left: 3px solid rgba(0, 0, 0, 0.40); } .vscode-light.showEditorSelection .code-line .code-line:hover:before { border-left: none; } .vscode-dark.showEditorSelection .code-active-line:before { border-left: 3px solid rgba(255, 255, 255, 0.4); } .vscode-dark.showEditorSelection .code-line:hover:before { border-left: 3px solid rgba(255, 255, 255, 0.60); } .vscode-dark.showEditorSelection .code-line .code-line:hover:before { border-left: none; } .vscode-high-contrast.showEditorSelection .code-active-line:before { border-left: 3px solid rgba(255, 160, 0, 0.7); } .vscode-high-contrast.showEditorSelection .code-line:hover:before { border-left: 3px solid rgba(255, 160, 0, 1); } .vscode-high-contrast.showEditorSelection .code-line .code-line:hover:before { border-left: none; } img { max-width: 100%; max-height: 100%; } a { text-decoration: none; } a:hover { text-decoration: underline; } a:focus, input:focus, select:focus, textarea:focus { outline: 1px solid -webkit-focus-ring-color; outline-offset: -1px; } hr { border: 0; height: 2px; border-bottom: 2px solid; } h1 { padding-bottom: 0.3em; line-height: 1.2; border-bottom-width: 1px; border-bottom-style: solid; } h1, h2, h3 { font-weight: normal; } h1 code, h2 code, h3 code, h4 code, h5 code, h6 code { font-size: inherit; line-height: auto; } table { border-collapse: collapse; } table > thead > tr > th { text-align: left; border-bottom: 1px solid; } table > thead > tr > th, table > thead > tr > td, table > tbody > tr > th, table > tbody > tr > td { padding: 5px 10px; } table > tbody > tr + tr > td { border-top: 1px solid; } blockquote { margin: 0 7px 0 5px; padding: 0 16px 0 10px; border-left-width: 5px; border-left-style: solid; } code { font-family: Menlo, Monaco, Consolas, "Droid Sans Mono", "Courier New", monospace, "Droid Sans Fallback"; font-size: 14px; line-height: 19px; } body.wordWrap pre { white-space: pre-wrap; } .mac code { font-size: 12px; line-height: 18px; } pre:not(.hljs), pre.hljs code > div { padding: 16px; border-radius: 3px; overflow: auto; } /** Theming */ pre code { color: var(--vscode-editor-foreground); } .vscode-light pre { background-color: rgba(220, 220, 220, 0.4); } .vscode-dark pre { background-color: rgba(10, 10, 10, 0.4); } .vscode-high-contrast pre { background-color: rgb(0, 0, 0); } .vscode-high-contrast h1 { border-color: rgb(0, 0, 0); } .vscode-light table > thead > tr > th { border-color: rgba(0, 0, 0, 0.69); } .vscode-dark table > thead > tr > th { border-color: rgba(255, 255, 255, 0.69); } .vscode-light h1, .vscode-light hr, .vscode-light table > tbody > tr + tr > td { border-color: rgba(0, 0, 0, 0.18); } .vscode-dark h1, .vscode-dark hr, .vscode-dark table > tbody > tr + tr > td { border-color: rgba(255, 255, 255, 0.18); }
</style>
<style>
/* https://raw.githubusercontent.com/isagalaev/highlight.js/master/src/styles/vs2015.css */ /* * Visual Studio 2015 dark style * Author: Nicolas LLOBERA <[email protected]> */ .hljs-keyword, .hljs-literal, .hljs-symbol, .hljs-name { color: #569CD6; } .hljs-link { color: #569CD6; text-decoration: underline; } .hljs-built_in, .hljs-type { color: #4EC9B0; } .hljs-number, .hljs-class { color: #B8D7A3; } .hljs-string, .hljs-meta-string { color: #D69D85; } .hljs-regexp, .hljs-template-tag { color: #9A5334; } .hljs-subst, .hljs-function, .hljs-title, .hljs-params, .hljs-formula { color: #DCDCDC; } .hljs-comment, .hljs-quote { color: #57A64A; font-style: italic; } .hljs-doctag { color: #608B4E; } .hljs-meta, .hljs-meta-keyword, .hljs-tag { color: #9B9B9B; } .hljs-variable, .hljs-template-variable { color: #BD63C5; } .hljs-attr, .hljs-attribute, .hljs-builtin-name { color: #9CDCFE; } .hljs-section { color: gold; } .hljs-emphasis { font-style: italic; } .hljs-strong { font-weight: bold; } /*.hljs-code { font-family:'Monospace'; }*/ .hljs-bullet, .hljs-selector-tag, .hljs-selector-id, .hljs-selector-class, .hljs-selector-attr, .hljs-selector-pseudo { color: #D7BA7D; } .hljs-addition { background-color: #144212; display: inline-block; width: 100%; } .hljs-deletion { background-color: #600; display: inline-block; width: 100%; } /* From https://raw.githubusercontent.com/isagalaev/highlight.js/master/src/styles/vs.css */ /* Visual Studio-like style based on original C# coloring by Jason Diamond <[email protected]> */ .vscode-light .hljs-function, .vscode-light .hljs-params { color: inherit; } .vscode-light .hljs-comment, .vscode-light .hljs-quote, .vscode-light .hljs-variable { color: #008000; } .vscode-light .hljs-keyword, .vscode-light .hljs-selector-tag, .vscode-light .hljs-built_in, .vscode-light .hljs-name, .vscode-light .hljs-tag { color: #00f; } .vscode-light .hljs-string, .vscode-light .hljs-title, .vscode-light .hljs-section, .vscode-light .hljs-attribute, .vscode-light .hljs-literal, .vscode-light .hljs-template-tag, .vscode-light .hljs-template-variable, .vscode-light .hljs-type, .vscode-light .hljs-addition { color: #a31515; } .vscode-light .hljs-deletion, .vscode-light .hljs-selector-attr, .vscode-light .hljs-selector-pseudo, .vscode-light .hljs-meta { color: #2b91af; } .vscode-light .hljs-doctag { color: #808080; } .vscode-light .hljs-attr { color: #f00; } .vscode-light .hljs-symbol, .vscode-light .hljs-bullet, .vscode-light .hljs-link { color: #00b0e8; } .vscode-light .hljs-emphasis { font-style: italic; } .vscode-light .hljs-strong { font-weight: bold; }
</style>
<style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
<style>
body {
font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'HelveticaNeue-Light', 'Ubuntu', 'Droid Sans', sans-serif;
font-size: 14px;
line-height: 1.6;
}
</style>
</head>
<body>
<style>
.center-image{
display: block;
margin-left: auto;
margin-right: auto;
width: 500px;
}
.text-center{
text-align: center;
}
.text-right{
text-align: right;
padding-right: 100px;
}
.pagebreak{
page-break-after: always;
}
</style>
<h1 id="algoritmi---relazione-di-laboratorio">Algoritmi - Relazione di Laboratorio</h1>
<br>
<br>
<br>
<div class="text-center">
<h2 id="di-lucchio-matteo">Di Lucchio Matteo</h2>
<h3 id="matricola-795310">Matricola 795310</h3>
<h3 id="email-matteodilucchioeduunitoit">Email <a href="mailto:[email protected]">[email protected]</a></h3>
<h3 id="anno-accademico-201718">Anno accademico 2017/18</h3>
</div>
<br>
<br>
<br>
<div class="pagebreak"></div>
<h1 id="esercizio-1---parte-1">Esercizio 1 - parte 1</h1>
<p>Lo scopo dell'esercizio 1 era di realizzare due librerie che permettessero di ordinare in ordine crescente o decrescente gli interi letti dal file <em>integers.csv</em> usando gli algoritmi <strong>insertion sort</strong> e <strong>merge sort</strong>.</p>
<h2 id="insertion-sort">Insertion Sort</h2>
<p>Considerando un vettore di interi, Insertion Sort e' un algoritmo di ordinamento in cui la parte sinistra del vettore e' ordinata (vero per vettori da un solo elemento) e ogni nuovo inserimento dalla parte destra alla parte sinistra mantiene il vettore ordinato. Ad ogni iterazione nel caso peggiore si scorre tutta la parte ordinata fino all'ultimo indice, nel caso migliore invece ci si blocca al primo elemento.<br>Questo algoritmo e' quindi ottimo per vettori gia' quasi ordinati.</p>
<p>Vista la mole di dati da analizzare ho deciso di modificare la normale implementazione di questo algoritmo per tentarne una versione ottimizzata di tipo <em>DIVIDE ET IMPERA</em>, in cui la ricerca dell'indice in cui inserire l'elemento analizzato avviene dimezzando di volta in volta l'area considerata.</p>
<h4 id="analisi-della-complessitadi-insertion-sort-iterativo">Analisi della complessita'di Insertion Sort iterativo</h4>
<p>Caso ottimo <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>T</mi><mrow><mi mathvariant="normal">c</mi><mi mathvariant="normal">m</mi></mrow></msub><mo>(</mo><mi>n</mi><mo>)</mo><mo>≈</mo><mi>a</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">T_{\mathrm{cm}}(n)\approx an</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.151392em;"><span style="top:-2.5500000000000003em;margin-left:-0.13889em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathrm mtight">c</span><span class="mord mathrm mtight">m</span></span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathit">a</span><span class="mord mathit">n</span></span></span></span></p>
<p>Caso peggiore <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>T</mi><mrow><mi mathvariant="normal">c</mi><mi mathvariant="normal">p</mi></mrow></msub><mo>(</mo><mi>n</mi><mo>)</mo><mo>≈</mo><mi>a</mi><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">T_{\mathrm{cp}}(n)\approx an^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.036108em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.15139200000000003em;"><span style="top:-2.5500000000000003em;margin-left:-0.13889em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathrm mtight">c</span><span class="mord mathrm mtight">p</span></span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">≈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord mathit">a</span><span class="mord"><span class="mord mathit">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span></p>
<h4 id="analisi-della-complessitadi-insertion-sort-divide-et-impera">Analisi della complessita'di Insertion Sort <em>Divide Et Impera</em></h4>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>∈</mo><mi mathvariant="normal">Θ</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo></mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">T(n)\in\Theta(n \log n)
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">Θ</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathit">n</span><span class="mclose">)</span></span></span></span></span></p>
<h3 id="fallimento-dellalgoritmo">Fallimento dell'algoritmo</h3>
<p>Nonostante i test positivi e il miglioramento delle prestazioni rispetto al primo approccio (Insertion Sort iterativo), <em>Divide et Impera</em> non e' stato fruttuoso, infatti dopo 10 minuti l'algoritmo aveva analizzato circa il 3% dei dati.</p>
<h2 id="merge-sort">Merge Sort</h2>
<p>Merge Sort e' un algoritmo di ricerca a partizioni bilanciate che opera per fusione.<br>
L'idea alla base dell'algoritmo e' di spezzettare il problema in sottoproblemi fino ad avere un sottoproblema facilmente risolvibile, per poi fondere la soluzione al sottoproblema precedente.</p>
<p>Anche in questo caso la complessita' e' la seguente</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>∈</mo><mi mathvariant="normal">Θ</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo></mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">T(n)\in\Theta(n \log n)
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">∈</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">Θ</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathit">n</span><span class="mclose">)</span></span></span></span></span></p>
<div class="pagebreak"></div>
<h2 id="algoritmi-a-confronto">Algoritmi a confronto</h2>
<div class="center-image">
<p><img src="https://w3.cs.jmu.edu/lam2mo/cs240_2014_08/images/sort_eval_graph.png" alt="insertionVSmerge"></p>
</div>
<div class="text-right">
<p><a href="https://w3.cs.jmu.edu/lam2mo/cs240_2014_08/pa04-sorting.html">fonte</a></p>
</div>
<p>Consideriamo i due algoritmi Insertion Sort iterativo e Merge sort.<br>
Dall'immagine e' facile capire come il quadrato rispetto al numero di elementi faccia crescere velocemente Insertion Sort rispetto a Merge Sort. All'aumentare dell'input il tempo di esecuzione aumenta in modo esponenziale.<br>
E' proprio questo che mi ha spinto a provare un approccio a partizione bilanciate per entrambi gli algoritmi.</p>
<p>Nonostante il tentativo, l'input e' risultato troppo grande lo stesso.</p>
<h1 id="esercizio-1---parte-2">Esercizio 1 - parte 2</h1>
<p>La seconda parte dell'esercizio chiedeva di leggere i 100 interi contenuti nel file <em>sums.txt</em>, salvarli in un array e, per ogni intero, trovare una possibile somma fatta con due entry diverse dei numeri analizzati nell'esercizio precedente.</p>
<h2 id="sumsfinder">SumsFinder</h2>
<p>Per realizzare questo esercizio ho deciso di realizzare una classe di supporto: <code>Sum</code> e di usare la struttura <code>HashTable</code> disponibile in <code>Java</code>.</p>
<div class="pagebreak"></div>
<h4 id="la-classe-sum">La classe Sum</h4>
<p>Questo oggetto serve semplicemente a rappresentare una somma e a controllare che sia corretta.</p>
<p>L'uso di questa classe mi ha permesso di salvare le somme trovate in una struttura dati di tipo <code>ArrayList<Sum></code> facilmente manipolabile.</p>
<h4 id="uso-di-una-hashtable">Uso di una HashTable</h4>
<p>L'algoritmo di ricerca in questa situazione ha una complessita' maggiore rispetto alla situazione precedente: prima bastava effettuare una ricerca per un singolo indice; ora ne servono due e l'array in cui cercare non e' ordinato.<br></p>
<p>Per risolvere a questo inconveniente mi sono servito della <code>HashTable</code>.<br>Ogni entry <code><chiave, valore></code> e' cosi' formata:</p>
<ul>
<li><strong>chiave</strong>: il numero letto;</li>
<li><strong>valore</strong>: l'indice in cui e' stato letto dall'array di input.</li>
</ul>
<p>Per trovare una somma ho usato questo algoritmo:</p>
<ul>
<li>per ogni elemento dell'array di somme scorri l'array per intero</li>
<li>per ogni valore letto dall'array (il primo addendo)
<ul>
<li>se esiste un secondo addendo si trova in <code>hashmap(somma-chiave)</code></li>
</ul>
</li>
</ul>
<p>In pratica:</p>
<p>Diciamo</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>F</mi><mo>(</mo><mi>k</mi><mo>)</mo><mo>=</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">F(k)=v
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.13889em;">F</span><span class="mopen">(</span><span class="mord mathit" style="margin-right:0.03148em;">k</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span></span></p>
<p>la funzione di hash che restituisce il valore <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span> data la chiave <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.69444em;vertical-align:0em;"></span><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span></span>.<br>
Data una somma <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathit" style="margin-right:0.05764em;">S</span></span></span></span> tale che</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>S</mi><mo>=</mo><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">S=x+y
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathit">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span></span></span></p>
<p>Per ogni chiave <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathit">x</span></span></span></span> letta dalla hashmap si ha che:<br>
se <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>F</mi><mo>(</mo><mi>S</mi><mo>−</mo><mi>x</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">F(S-x)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.13889em;">F</span><span class="mopen">(</span><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit">x</span><span class="mclose">)</span></span></span></span> esiste allora esiste <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>F</mi><mo>(</mo><mi>y</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">F(y)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.13889em;">F</span><span class="mopen">(</span><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="mclose">)</span></span></span></span> perche' <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>S</mi><mo>=</mo><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">S=x+y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathit">x</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span></span> e quindi <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>S</mi><mo>−</mo><mi>x</mi><mo>=</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">S-x=y</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.76666em;vertical-align:-0.08333em;"></span><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathit">x</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span></span>.</p>
<h4 id="il-problema-dei-doppioni">Il problema dei doppioni</h4>
<p>Rimane pero' un problema: ogni doppione viene eliminato perche' ogni successivo inserimento di uno stesso numero nella hashtable sovrascrive il valore calcolato dalla funzione di hash. Per risolvere a questo inconveniente ho utilizzato una seconda hashtable in cui ho salvato i numeri trovati piu' di una volta. Se un numero e' la meta' esatta della somma considerata e nell'array ce n'e' piu' di uno in questo modo e' possibile considerarlo nelle somme trovate.</p>
<h2 id="complessita-dellalgoritmo">Complessita' dell'algoritmo</h2>
<h4 id="creazione-della-hashtable">Creazione della hashtable</h4>
<p>Per creare la hashtable viene letto ogni elemento dell'array una sola volta: <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span></span></span></span></p>
<h4 id="ricerca-del-primo-addendo">Ricerca del primo addendo</h4>
<p>Si scorre l'array delle somme: <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>m</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(m)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">m</span><span class="mclose">)</span></span></span></span><br>
Per ogni somma si scorre l'array degli interi: <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span></span></span></span><br>
Per ogni intero si esegue una ricerca puntuale nella hashtable: <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>.</p>
<p>La complessita' totale e' quindi:</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>m</mi><mo>)</mo><mo>+</mo><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(m)+O(n)
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">m</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mclose">)</span></span></span></span></span></p>
<h3 id="fallimento">Fallimento</h3>
<p>Nonostante i test fossero positivi e i tempi di esecuzione fossero incredibilmente veloci grazie all'impiego delle hashmap, l'algoritmo non e' stato in grado di terminare a causa dell'impiego di troppa memoria per la JVM. Sperimentalmente ho potuto riscontrare che fino a 15 milioni di numeri in input consentono all'algoritmo di terminare positivamente in pochi minuti, ma con 20 milioni di numeri in input la JVM termina la memoria a disposizione. Auentando la memoria riservata alla JVM e' possibile terminare positivamente e molto rapidamente questa parte dell'esercizio.</p>
<div class="pagebreak"></div>
<h1 id="esercizio-2---parte-1">Esercizio 2 - Parte 1</h1>
<p>L'esercizio 2 richiede l'implementazione di una libreria in grado di stabilire la distanza minima di edit per trasformare una parola in un'altra, usando le sole operazioni:</p>
<ul>
<li>inserimento</li>
<li>cancellazione</li>
</ul>
<p>La prima versione e' da fare ricorsiva, la seconda deve utilizzare la programmazione dinamica per dimostrarne l'efficienza rispetto alla sola ricorsione.</p>
<p>Entrambe le versioni si basano su 3 funzioni principali che calcolano il costo dell'operazione che rappresentano:</p>
<ul>
<li>inserisci un carattere: <code>insEditDistance</code><br></li>
<li>cancella un carattere: <code>cancEditDistance</code><br></li>
<li>ignora il carattere corrente e passa al successivo: <code>noopEditDistance</code><br></li>
</ul>
<h3 id="costi">Costi</h3>
<p>Inserimento e cancellazione costano 1 + i costi dei sottoproblemi successivi, mentre ignorare il carattere costa 0 + i costi dei sottoproblemi successivi, ma solo se i caratteri considerati sono uguali, altrimenti ignorare il carattere ha costo infinito in quanto non e' un'operazione fattibile.</p>
<h2 id="editdistance-ricorsivo"><code>EditDistance</code> ricorsivo</h2>
<p>Questa versione calcola ricorsivamente il costo di edit senza sfruttare strutture dati in cui salvare gli esiti delle iterazioni. La stessa funzione con lo stesso input puo' essere richiamata numerose volte sprecando CPU inutilmente.</p>
<h2 id="editdistance-con-la-programmazione-dinamica"><code>EditDistance</code> con la programmazione dinamica</h2>
<p>Questa versione calcola ricorsivamente il costo di edit tra due stringhe ma usa delle strutture dati di supporto in cui salvare i costi delle iterazioni mano a mano che vengono effettuate, in modo da evitare di reiterare la stessa funzione con lo stesso input piu' di una volta.</p>
<p>Vengono utilizzare delle tabelle coi costi minimi dell'iterazione alla posizione <code>[i][j]</code>, una per ogni operazione (inserimento, cancellazione, passaggio al carattere successivo) grandi <code>m</code> x <code>n</code>, con <code>m</code> e <code>n</code> pari alla lunghezza delle due stringhe - 1.</p>
<p>La posizione <code>[i][j]</code> rappresenta l'operazione effettuata quando <code>s1</code> e' lunga <code>i+1</code> e <code>s2</code> e' lunga <code>j+1</code>. Prima di eseguire la funzione viene controllato che il suo valore non sia gia' stato scritto in tabella: se esiste viene letto,altrimenti viene calcolato e successivamente salvato.</p>
<h1 id="esercizio-2---parte-2">Esercizio 2 - Parte 2</h1>
<p>Viene chiesto di correggere ogni parola del file "correctme.txt" con le parole che hanno edit distance minino nel file "dictionary.txt".</p>
<p>Testando questo algoritmo con l'algoritmo ricorsivo il tempo richiesto per correggere la prima parola e' circa di 4 minuti, ma usando la versione che sfrutta la programmazione dinamica viene impiegata la meta' del tempo per correggere ogni parola della citazione e terminare correttamente.</p>
<h2 id="complessita">Complessita'</h2>
<ul>
<li>Versione ricorsiva: <code>O(m</code> x <code>n log n)</code></li>
<li>Versione che usa la programmazione dinamica: e' inferiore perche' spesso serve solo leggere il dato salvato in tabella con complessita' <code>O(1)</code>.</li>
</ul>
</body>
</html>