-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathnotex.tex
More file actions
6431 lines (5977 loc) · 350 KB
/
notex.tex
File metadata and controls
6431 lines (5977 loc) · 350 KB
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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass{article}
\usepackage[OT1]{fontenc}
\usepackage{mathpazo}
\usepackage[italian]{babel}
%math
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage[utf8]{inputenc}
\usepackage{cancel}
\usepackage{listing}
\usepackage{listingsutf8}
\usepackage{listings}
%table
\usepackage{booktabs} % for better looking tables
\usepackage{siunitx} % for units of measure and data in tables
\usepackage{array}
\usepackage{multirow}
\usepackage{hhline,booktabs,amsmath}
\usepackage{makecell}
%Graphics&Float
\usepackage{graphicx}
\usepackage{float}
\usepackage{chngcntr}
\counterwithin{figure}{section}
%
%Hypelinks
\usepackage{hyperref}
\hypersetup{
colorlinks,
citecolor=black,
filecolor=black,
linkcolor=black,
urlcolor=black
}
% TIKZ
\usepackage{tikz}
\usetikzlibrary{shapes.geometric, arrows}
\tikzstyle{arrow} = [thick,->,>=stealth]
\tikzstyle{startstop} = [rectangle, rounded corners, minimum width=3cm, minimum height=1cm,text centered, draw=black, fill=red!30]
\tikzstyle{io} = [trapezium, trapezium left angle=70, trapezium right angle=110, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=blue!30]
\tikzstyle{process} = [rectangle, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=orange!30]
\tikzstyle{decision} = [diamond, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=green!30]
%Algorithm
\usepackage[]{algorithm2e}
\RestyleAlgo{ruled}
%% This is needed if you want to add comments in
%% your algorithm with \Comment
\SetKwComment{Comment}{/* }{ */}
\SetKwRepeat{Do}{do}{while}
\title{%
\textbf{Informatica Teorica}
\\[1cm]
\includegraphics[scale=0.12]{images/Logo_Università_degli_Studi_di_Milano.svg.png}~
\\[1cm]
\large Prof. Mereghetti Carlo\\
Università degli Studi di Milano\\
Laurea Magistrale in Informatica, A.A. 2020/2021}
\author{Appunti a cura di Manuel Pagliuca}
\begin{document}
\maketitle
\pagebreak
\tableofcontents
\pagebreak
\newpage
\section{Introduzione}
Nei corsi di informatica applicata come quelli di: Sistemi Operativi, Basi di dati, ecc... l'oggetto di studio è definito dal corso, e l'informatica è lo strumento per studiare questo oggetto.
Nel corso di informatica teorica l'oggetto di studio è l'informatica stessa, si studiano i fondamenti dell'informatica (come un corso di sistemi operativi effettua uno studio sui fondamenti dei sistemi operativi).
Per eseguire lo studio di questa disciplina ci si pone le due domande fondamentali nei confronti dell'informatica \textit{cosa} e \textit{come}.
\subsection{Cosa studia l'informatica?}
L'informatica è una disciplina che studia l'informazione e l'elaborazione automatica mediante sistemi di calcolo che eseguono programmi.
Ma sappiamo che tutti i problemi sono risolubili per via automatica, e questo porta proprio alla nostra domanda, quali problemi sono in grado di risolvere \textit{automaticamente}?
Ciò che studia il \textit{cosa} dell'informatica si chiama \textbf{teoria della calcolabilità}, mostreremo nelle successive lezioni che non è una domanda cosi facile da rispondere, poiché esistono delle cose che non sono calcolabili. Quindi dato che non ci sono cose calcolabili, la teoria della calcolabilità si domanda \textit{che cosa è calcolabile?}.
\newline
Nella teoria della calcolabilità vogliamo una risposta generale, non cerchiamo dei casi particolari per dire questo è calcolabile o meno, esistono delle proprietà che accomunano tutto ciò che è calcolabile ? La risposta è si, la nozione di calcolabilità è denotabile attraverso la matematica e quindi posso affrontare l'insieme di cose fattibili dell'informatica con gli strumenti della matematica.
\subsection{Come l'informatica risolve i problemi?}
La branca dell'informatica che si chiama \textbf{teoria della complessità} risponde alla domanda \textit{come è risolubile questo problema ?}. Essa studia la quantità di risorse computazionali richieste dalla \textit{soluzione automatica} dei problemi. Una \textit{risorsa computazionale} è qualsiasi cosa venga sprecata per l'esecuzione dei programmi:
Le principali risorse su cui ci concentreremo sono il \textbf{tempo} e \textbf{spazio di memoria}, dovremo quindi dare una definizione rigorosa di queste risorse computazionali. Successivamente si potrà porre delle domande ovvie : \textit{quale è la classe di problemi che vengono risolti efficientemente in termini di tempo e di memoria ?}. Notare che nella teoria della complessità non si parla solo di \textbf{risolubilità} (come nella teoria della calcolabilità) ma anche dell'\textbf{efficienza} con cui risolvo questo problema.
\newline
Esistono problemi che si trovano in una zona grigia, che non sappiamo se hanno una risoluzione efficiente, ma sono problemi molto importanti, nessuno è riuscito a dimostrare se avranno soluzioni efficienti ma nemmeno il contrario, ovvero nessuno è riuscito a dimostrare che saranno risolubili efficientemente. Questa classe di problemi è la classe di problemi NP, vedremo poi di cosa si tratta.
\section{Syllabus}
\begin{itemize}
\item Teoria della calcolabilità: individuare la qualità della calcolabilità dei problemi, quali sono le categorie di problemi calcolabili e distinguerla da quella dei problemi non calcolabili.
\item Teoria della complessità: studio quantitativo dei problemi, dopo aver delimitato il confini di ciò che è calcolabile cercare un sotto insieme di problemi \textbf{efficientemente calcolabili}.
\end{itemize}
\pagebreak
\section{Il nostro linguaggio: la matematica}
\subsection{Funzione}
Una funzione dall'insieme $A$ all'insieme $B$ è una \textbf{legge}, che chiamiamo solitamente $f$, che spiega come associare ad ogni elemento di $A$ un elemento di $B$.
\newline
Dal punto di vista formale l'espressione della funzione viene definita \textbf{globalmente}:
$$f:A\rightarrow B$$
Dove solitamente $A$ viene chiamato \textbf{dominio} e $B$ \textbf{codominio}, questa notazione dice che ogni elemento del dominio è associato attraverso una legge $f$ ad un elemento del codominio. Esiste anche una notazione che permette di stabilire localmente l'operato della funzione, essa rappresenta l'operato della legge $f$ sull'elemento $a$ che porta all'elemento $b$.
$$a \xrightarrow[\text{}]{\text{f}} b$$
\newline
La notazione comunemente più utilizzata (in particolare nei libri di testo, ma anche nei corsi di matematica), è la seguente:
$$f(a)=b$$
Solitamente $b$ è l'\textbf{immagine} di $a$ secondo $f$, e meno usualmente si dice che $a$ è la \textbf{controimmagine} di $b$ (sempre secondo $f$).
\newline
\newline
Per esempio:
$$f:\mathbb{N} \rightarrow \mathbb{N}$$
Dove $\mathbb{N}$ è l'insieme dei numeri naturali ${0,1,2,3,...}$, e per utilizzi futuri denotiamo con $\mathbb{N}^+$ l'insieme dei numeri naturali positivi (zero escluso) ${1,2,3,4,...}$.
\newline
Ora vediamo la specifica della funzione $f$
$$f(n)=\lfloor \sqrtsign{n}\rfloor$$
Considerando $n=5$ l'immagine di quest'ultima sarà $f(5)=\lfloor\sqrt{5}\rfloor=2$.
\newline
Quindi possiamo dedurre che per più elementi del dominio una \textbf{funzione} effettua un mapping ad uno ed un solo valore del codominio (nel caso in cui un valore del dominio venga mappato a più valori del codominio allora si parla di relazione, ma non più di funzione).
\subsection{Classi di funzioni}
\subsubsection{Funzioni iniettive}
Una funzione è \textbf{iniettiva} se e solo se elementi diversi del dominio vengono mappati in elementi diversi del codominio.
$$f:A\rightarrow B\text{ è iniettiva sse } \forall a_1,a_2\in A \text{ dove } a_1\neq a_2 \implies f(a_1)\neq f(a_2)$$
\newline
\textit{Esempio 1}
$$f(n)=\left\lfloor\sqrt(n)\right\rfloor$$
Abbiamo visto precedentemente che questa funzione non è iniettiva, perché avviene un mapping per più elementi del dominio ad un unico elemento del codominio.
\newline
\newline
\textit{Esempio 2}
$$f(n)=[n]_2$$
Questa funzione è fortemente non iniettiva, le due metà dell'insieme dei numeri naturali vengono mappate solamente su due numeri $f(2k)=0$ e $f(2k+1)=1$.
\newline
\newline
\textit{Esempio 3}
$$f(n)=n^2$$
Questa è una funzione iniettiva, poiché ad ogni controimmagine corrisponde una immagine distinta.
\subsubsection{Funzioni suriettive}
Una funzione è suriettiva quando tutti gli elementi del codominio hanno una corrispondenza con un elemento del dominio.
$$f:A\implies B\text{ sse } \forall b\in B, \exists a \in A : f(a)=b$$
\noindent
\textit{Esempio 1}
\newline
$f(n)=\lfloor\sqrt{n}\rfloor$ è suriettiva, questo perché $\forall m\in \mathbb{N}, m=\lfloor\sqrt{m^2}\rfloor=f(m^2)$. Sostanzialmente, posso tornare con facilità al dominio perché mi basta elevare al quadrato l'immagine, e questo è fattibile per tutto l'insieme dei numeri naturali.
\noindent
\newline
\linebreak
\textit{Esempio 2}
\newline
$f(n)=[n]_2$ non è una funzione suriettiva, questo perché per esempio $3$ non è immagine di niente rispetto a $f$ (il codominio è tutto $\mathbb{n}$).
\subsection{Insieme immagine di una funzione}
$$Im_f={b\in B:\exists a,f(a)=b}:a\in A$$
Data $f$ definiamo l'\textbf{insieme immagine di $f$} come gli elementi del codominio $\in B$ che sono immagine di un elemento del dominio $A$.
\newline
La relazione tra questo insieme $Im_f$ ed il codominio stesso di $f$ quale è $B$, consiste in:
$$Im_f\subseteq B$$
Allora possiamo dire che una funzione è suriettiva quando:
$$Im_f=B$$
\newline
\textit{Esempi}
$$Im_{\lfloor\sqrt{n}\rfloor}=\mathbb{N}\implies f(n)=\lfloor\sqrt{n}\rfloor \text{ è suriettiva}$$
$$Im_{[n]_2}={0,1}\subseteq \mathbb{N} \implies f(n)=[n]_2 \text{ non è suriettiva}$$
\subsection{Funzioni biettive}
Una funzione si dice biettiva quando è sia suriettiva che iniettiva, devono valere entrambe le due condizioni (questo due condizioni è possibile fonderle in un unica condizione).
$$f:A\rightarrow B \textbf{ sse }$$
$$\forall a_1,a_2 \in A, a_1\neq a_2 \implies f(a_1)\neq f(a_2) \land \forall b\in B, \exists a\in A:f(a)=b$$
Che converge in un unica definizione:
$$\forall b \in B,\exists !a\in A : f(a)=b$$
Per esempio: $f(n)=n$, oppure considerando gli insiemi dei numeri reali $f(x)=x^3$. Solo per questa tipologia di funzioni esiste il concetto di \textbf{funzione inversa}.
\subsection{Inversa di una funzione}
Data una funzione $f$ biettiva si definisce l'inversa come $f^{-1}$ la funzione tale che crei un mapping tra l'immagine del codominio rispetto alla controimmagine del dominio.
$$f:A\rightarrow B$$
$$f^{-1}:B\rightarrow A \text{ tale che } f^{-1}(b)=a \Longleftrightarrow (a)=b$$
Per esempio l'inversa di $f(n)$ è $f^{-1}=n$, oppure l'inversa di $f(x)=x^3$ è $f^{-1}=\sqrt[3]{x}$ (considerando l'insieme dei numeri reali).
\subsection{Composizione di funzioni}
Date due funzioni $f:A\rightarrow B$ e $g:B\rightarrow C$, notiamo che queste funzioni hanno una caratteristica in comune, ovvero che il codominio di una è il dominio dell'altra.
Definiamo la composizione di funzione $g\circ f:A\rightarrow C$ come la funzione che va da dal dominio di $f$ al codominio di $g$, definita come $g(f(a))$.
$$g\circ f=g(f(a))$$
Per esempio $f(n)=n+1 \text{ e } g(n)=n^2$:
\begin{itemize}
\item $f \text{ composto } g: g\circ f(n)=(n+1)^2$
\item $g \text{ composto } f: f\circ g(n)=n^2+1$
\end{itemize}
N.B. L'operazione di composizione restituisce una funzione, e l'operatore $\circ$ non è commutativo, però quando dominio e codominio lo permettono è \textbf{associativo}: $(f\circ g)\circ h=f\circ (g \circ h)$.
\subsubsection{Funzione identità}
La funzione identità sull'insieme $A$ è una funzione che effettua un mappaggio ricorsivo sullo stesso elemento.
$$i_A:A\rightarrow A : i_A(a)=a,\text{ }\forall a\in A$$
Per esempio la funzione identità sull'insieme $\mathbb{N}$ è $i_\mathbb{N}(n)=n$.
\subsubsection{Definizione alternativa di funzione inversa}
Data una funzione $f:A\rightarrow B$ biettiva, la sua inversa è l'unica funzione $f^{-1}:B\rightarrow A$ che soddisfa:
$$f^{-1}(b)=a \longleftrightarrow f(a)=b$$
$$oppure$$
$$f^{-1}\circ f=i_A \land f\circ f^{-1}=i_B$$
Infatti considerando $f^{-1}\circ f(x) = \sqrt[3]{x^3}=x=i_\mathbb{N}(x)$ e $f\circ f^{-1}(x)=(\sqrt[3]{x})^3=x=i_\mathbb{N}(x)$
\subsubsection{Funzioni totali e parziali}
Considerando una funzione $f:A\rightarrow B$ essa è una legge che ad \textbf{ogni} elemento di $A$ si associa
un elemento di $B$, questo significa che ogni immagine $f(a)$ è definita per ogni elemento $a\in A$. Esiste
un apposita notazione:
$$f(a)\downarrow \forall a\in A$$
Una funzione di questo tipo viene chiamata \textbf{totale} poiché risulta definita sulla totalità del suo dominio.
Certe funzioni potrebbero \textit{non essere definita} per quale che elemento di $a\in A$, e quindi non avere delle immagini corrispondenti, la notazione:
$$f(a)\uparrow$$
Ovvero, che per un elemento $a$ non esiste immagine nell'insieme $B$ tramite la funzione $f$.
Consideriamo il seguente esempio:
$$f:\mathbb{N}\rightarrow\mathbb{N}$$
$$f(n)=\left\lfloor\frac{1}{n}\right\rfloor \text{ non è definita su } n=0\implies f(0)\uparrow \forall n\in\mathbb{N}\setminus{0}, f(n)\downarrow$$
Una funzione viene definita \textbf{parziale} se a \textit{qualche} elemento di $A$ si associa un elemento di $B$. Si amplia un nuovo concetto che è quello del \textbf{dominio} (o campo di esistenza) della funzione,
ovvero quell'insieme costituito da tutti gli elementi di $A$ tali per cui è definita una immagine appartenente a $B$.
$$Dom_f=\left\{\forall a\in A : f(a)\downarrow \right\}\subseteq A$$
Allora vale precisare le due seguenti regole:
$$Dom_f\subsetneq A\implies f\text{ parziale}$$
$$Dom_f\equiv A\implies f \text{ totale}$$
Alcuni esempi:
$$f(n)=\left\{\frac{1}{n}+\frac{1}{(n-1)(n-2)}\implies Dom_f=\mathbb{N}\setminus\{0,1,2\}\right\}$$
$$f(n)=\lfloor\log{n}\rfloor\implies Dom_f=\mathbb{N}\setminus\{0\}$$
$$f(n)=\lfloor\sqrt{-n}\rfloor \implies Dom_f=\{0\}$$
\subsubsection{Totalizzazione di una funzione parziale}
Teniamo conto di una cosa, possiamo convenzionalmente rendere totale una funzione parziale, basta estendere
il codominio con un \textbf{simbolo convenzionale} $\bot$ che utilizziamo
tutte le volte che la funzione non è definita.
$$f:A\rightarrow B\text{ parziale } \implies \widetilde{f}:A\rightarrow B\cap\{\bot\}$$
La totalizzazione di $f$ viene raggiunta con l'aggiunta di questo simbolo.
\[
\widetilde{f}(a) =
\begin{cases}
f(a) & \quad\text{se }a\in Dom_f \\
\bot & \quad\text{altrimenti} \\
\end{cases}
\]
Quindi per i punti dove il campo di esistenza non è definito verrà restituito $\bot$, per convenzione
quando una funzione parziale viene totalizzata ovvero $B\cap\bot$ possiamo utilizzare la seguente
notazione $B_{\bot}$.
\subsubsection{Prodotto cartesiano}
$$A\times B=\{(a,b):a\in A \land b\in B\}$$
Il \textbf{prodotto cartesiano} di due insiemi è l'insieme di coppie dove il primo elemento della coppia appartiene al primo insieme, ed il secondo elemento della coppia appartiene al secondo insieme.
Il prodotto cartesiano è un'operazione che non commuta.
$$A\times B \neq B\times A$$
Ovviamente l'unico caso dove un prodotto cartesiano è commutativo è quando $A\equiv B$.
Il prodotto cartesiano può essere esteso al prodotto di ennuple di più insiemi cartesiani,
dove questa volta il risultato è costituito da un insieme ordinato (non più di coppie) delle ennuple
rispettive agli insiemi di provenienza:
$$A_1\times A_2 \times ... \times A_n=\{(a_1,a_2,...,a_n):a_i\in A_i\}$$
Associato alla definizione di prodotto cartesiano abbiamo anche quella di \textbf{proiettore i'esimo},
essa è una funzione che agisce su un prodotto cartesiano. Ha come dominio l'insieme i-esimo di questo prodotto data una tupla del prodotto cartesiano non fa altro che estrapolare la componente i-esima di quella tupla (\textit{destruttura la tupla}).
$$\pi_i:A_1\times ...\times A_n\rightarrow A_i$$
$$\pi_i(a_1,...,a_n)=a_i$$
Utilizzeremo la seguente notazione esponenziale per calcolare il prodotto cartesiano di un insieme cartesiano
con se stesso:
$$A_1\times A_2\times A_3 \times ... \times A_n = A^n$$
Alcuni esempi:
$$C=\{(x,y)\in\mathbb{R}^2 : x^2+y_2=1\}\implies \text{ punti che si trovano lungo la circonferenza}$$
$$I=\{(x,y)\in\mathbb{R}^2 : x^2+y_2<1\}\implies \text{ punti che si trovano all'interno della circonferenza}$$
$$E=\{(x,y)\in\mathbb{R}^2 : x^2+y_2>1\}\implies \text{ punti che si trovano all'esterno della circonferenza}$$
$$C\cap I\cap E = \mathbb{R}^2$$
\subsubsection{Insieme di funzioni}
L'insieme delle funzioni che vanno dall'insieme $A$ a $B$ viene indicato con:
$$B^A=\{f:A\rightarrow B\} = \text{ insieme delle funzioni da } A \text{ a } B$$
L'insieme delle funzioni \textit{parziali} che vanno da $A$ a $B$:
$$B_{\bot}^A =\{f:A\rightarrow B_{\bot}\}=\text{ insieme delle funzioni parziali che va da A a B}$$
\subsubsection{Funzione di valutazione}
Dati due insiemi $A,B$ e $B_{\bot}^A$ si definisce una funzione di valutazione come:
$$\omega : B_{\bot}^A\times A \rightarrow B \text{ con } \omega (f,a)=f(a)$$
Essa è una funzione che valuta il punto del codominio $A$ in termini di $B$, ovvero restituisce un
$f(a)$, quindi il suo compito è strettamente quello di valutare.
\begin{itemize}
\item Tenendo fisso $a$ e facendo variare $f$, è come se $a$ fosse un \textit{benchmark}
su cui testiamo una serie di funzioni.
\item Tenendo fisso $f$ e facendo variare $a$ ottengo il grafico di $f$.
\end{itemize}
\subsection{Modellare teoricamente un sistema di calcolo}
Un sistema di calcolo è architettato come un architettura di Von Neumann, è un sistema che dato
in input un \textit{dato} $x$ ed un \textit{programma} $P$. L'output può essere indicato con $y$ quando è definito,
mentre con $\bot$ quando va in \textit{loop}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[node distance=2cm]
\node (dati)[
minimum width=1cm,
minimum height=1cm] at (0,1) {$x$};
\node (prog)[
minimum width=1cm,
minimum height=1cm] at (2,1) {$P$};
\node (model)[draw,
minimum width=2cm,
minimum height=1cm] at (1,-1) {$\mathcal{C}$};
\draw [arrow] (dati) -- (model);
\draw [arrow] (prog) -- (model);
\node (output)[
minimum width=1cm,
minimum height=1cm] at (1,-3) {$y$ o $\bot$};
\draw [arrow] (model) -- (output);
\end{tikzpicture}
\end{figure}
$P\in PROG$: Un programma è una \textbf{sequenza di regole} scritte in un certo linguaggio
che prende un input e lo trasforma in un output (o in un loop).
Essenzialmente un programma è la definizione di una funzione scritta a mano, esso
realizza una funzione che parte dai dati in input ed ottiene i dati in output.
$$P\in DATI_{\bot}^{DATI}\text{ è una funzione in un linguaggio di programmazione.}$$
Quindi, ribadendo per l'ennesima volta un programma è la realizzazione di una
funzione, che va da un insieme di dati ad un altro.
Il sistema di calcolo in se prende in input dei dati ed una funzione (il programma),
che mi da un output, esso è definito come una \textbf{funzione di valutazione} $\mathcal{C}$.
$$\mathcal{C}:DATI_{\bot}^{DATI}\times DATI\rightarrow DATI_{\bot}$$
Quindi $\mathcal{C}$ è una funzione di valutazione, e $\mathcal{C}(P,x)$ è la funzione di valutazione
del programma $P$ sul dato $x$.
Per esempio, consideriamo il seguente programma:
\begin{algorithm}[H]
\KwIn{$x$}
\eIf{$\langle x\rangle_2==0$}{
return $x$;
}
{
\lWhile{$1<2$}{return $1$;}
}
\caption{Semantica di $P$}
\end{algorithm}
Voglio capire la semantica di questo programma è per capirlo voglio definire una
funzione che mi rappresenti il legame input-output rispetto ad un dato elemento.
Il programma prende in ingresso un numero intero, se il numero è pari restituisce
esattamente il numero intero, altrimenti entra in un loop (non termina).
$$\mathcal{C}(P,\_):\mathbb{N}\rightarrow\mathbb{N}_{\bot}$$
La \textbf{semantica} è la seguente :
\[
\mathcal{C}(P,n) =
\begin{cases}
n & \quad\text{se }n\text{ è pari} \\
\bot & \quad\text{altrimenti} \\
\end{cases}
\]
\subsubsection{Potenza computazionale}
I sistemi di calcolo servono per calcolare le funzioni, ogni programma che immetto
nel mio sistema di calcolo mi viene calcolato. Indico con potenza computazionale
del mio sistema di calcolo come "\textit{tutto quello che sa fare}" il mio sistema di
calcolo, o meglio, tutte quelle funzioni che il mio sistema di calcolo può calcolare.
\newline\newline
Tutte le funzioni che può calcolare il mio sistema di calcolo è un sottoinsieme
di tutte le funzioni immaginabili che possono andare da dati in dati. I programmi
in generale sono delle funzioni da dati in dati, quindi il mio sistema di calcolo
è ovvio che calcoli questo tipo di funzioni, è un sottoinsieme perché non so quali
funzioni è in grado di risolvere il mio sistema di calcolo (e questa è la domanda
a \textit{cosa} a cui deve rispondere l'informatica teorica).
$$F(\mathcal{C})=\{\mathcal{C}(P,\_):P\in PROG\}\subseteq DATI_{\bot}^{DATI}$$
Questo significa che esistono delle funzioni che non possono essere risolte dal mio
sistema di calcolo, e che quindi \textbf{non sono automatizzabili}.
$$F(\mathcal{C})\subsetneq DATI_{\bot}^{DATI}$$
Sono presenti funzioni che l'informatica può risolvere e fare tutto, ma non tutte
le funzioni possibili possono essere risolvibili dall'informatica.
$$F(\mathcal{C})=DATI_{\bot}^{DATI}$$
Quindi abbiamo ridotto il quesito \textit{che cosa sono in grado di fare i programmi},
ad un quesito matematico di inclusione propria ed impropria.
\subsubsection{Importanza del calcolo di funzione}
Calcolare una funzione significa risolvere problemi in \textit{generale}. Questo
perché ad ogni problema posso associare una \textit{funzione soluzione}, non è altro che
quella funzione che ad un dato input associa una determinata \textit{soluzione}.
Per esempio, il \textit{problema del calcolo del determinante}:
\begin{algorithm}[hbt!]
\caption{DET}\label{alg:det}
\KwIn{$M\in \mathbb{R}^{n\times n}$}
\KwOut{Determinante di $M$}
\end{algorithm}
La rispettiva funzione soluzione:
$$f_{DET}:\mathbb{N}^{n\times n}\rightarrow \mathbb{Z}$$
$$f_{DET}(M)=Det(M):$$
Vediamo che risolvere il dato problema consiste nel calcolare la funzione soluzione,
o risolvere il problema significa sostanzialmente avere un programma in grado
di risolvere quella funzione.
\begin{algorithm}[hbt!]
\caption{Find-Replace}\label{alg:find-replace}
\KwIn{Testo, parola da cercare, parola da sostituire}
\KwOut{Testo in cui ogni occorrenza della parola da cercare è sostituita dall'altra}
\end{algorithm}
La funzione soluzione:
$$f_{Find-Replace}:TESTI\times PAROLE\times PAROLE\rightarrow TESTI$$
$$f_{Find-Replace}(\text{La nostra vita,nostra,vostra})=\text{La vostra vita}$$
\subsubsection{Cardinalità degli insiemi - I°}
Siamo arrivati al primo punto fondamentale, il \textit{cosa} dell'informatica, ed
abbiamo visto che si concretizza nell'interrogarsi sulla relazione tra l'insieme della
potenza computazionale e quello di tutte le funzioni che vanno da dati in dati possibili.
$$F(\mathcal{C})\text{ ? }DATI_{\bot}^{DATI}$$
\newline\newline
Per cercare di dare una dimostrazione sul carattere dell'inclusione, è molto utile
fare riferimento al concetto matematico di \textbf{cardinalità}.
\newline\newline
Dato un insieme $A$, la sua cardinalità si indica con $|A|$. Intuitivamente che la cardinalità
di un insieme è il numero di elementi da cui è formato l'insieme. Questa idea intuitiva
è abbastanza corretta quando si ha a che fare con \textbf{insiemi finiti} (la cardinalità mi può
aiutare a capire quale insieme è più grande degli altri).
\newline\newline
Purtroppo però quando tiriamo in ballo insiemi di cardinalità \textbf{infinita}, questo potrebbe
portare a conclusioni più complicate da elaborare. Si potrebbe \textit{erroneamente}
pensare $|\mathbb{N}|=\infty=|\mathbb{B}|$, ma questo sappiamo che
non è assolutamente vero, perché l'insieme dei numeri reali è molto più \textbf{fitto}
di quello dei numeri interi.
\newline\newline
Quindi dobbiamo aggiungere dei nuovi concetti, visto che \textit{"l'infinito di $\mathbb{R}$"} è
diverso da quello di $\mathbb{N}$. Il concetto da introdurre è quello di \textbf{relazione}.
\subsubsection{Relazione}
Consideriamo un insieme $A$, si definisce \textbf{relazione binaria} $R$ su $A$,
il sottoinsieme del prodotto cartesiano di $A$ su se stesso.
$$R\subseteq A^2$$
Gli elementi $a,b\in A$ stanno in una relazione $R$ se e solo se $(a,b)\in R$. Sono
presenti due notazioni infisse per denotare l'esistenza della relazione tra i due
elementi:
$$a\text{ R }b \text{ oppure } a\text{ \cancel{R} }b$$
Consideriamo per esempio la relazione $R$ come la relazione che agisce sui numeri naturali,
tale che un numero divida l'altro.
$$R\equiv \text{divide}: 3\text{ R }6, 5\text{ R }45, ...,3\text{ \cancel{R} }10$$
$$R=\{(a,b)\in\mathbb{N}^2:\langle b\rangle_a=0\}$$
Introduciamo anche il concetto di \textit{equivalenza in modulo} $k$, la quale mi
descrive una relazione del tipo:
$$a\equiv_k b \text{ sse } \langle a\rangle_k =\langle b\rangle_k$$
Per esempio: $5\equiv_2 7, 4\equiv_2 16,...$ (quando il resto dato dal divisore $k$ è
uguale su entrambi gli operandi).
\newline
Parliamo di \textbf{relazione di equivalenza} se e solo se soddisfa le seguenti
proprietà:
\begin{itemize}
\item \textbf{Riflessiva}: $\forall a\in A, a\text{ R }a$
\item \textbf{Simmetrica}: $\forall a,b\text{, } a\text{ R }b \Leftrightarrow b\text{ R }a$
\item \textbf{Transitiva}: $\forall a,b,c\text{, }a\text{ R }b\land b\text{ R }c\implies a\text{ R }c$
\end{itemize}
Ora considerando le precedenti relazioni, vediamo che la relazione $R\equiv\textit{"divide"}$
non è una relazione di equivalenza:
\begin{itemize}
\item È riflessiva.
\item \textbf{Non è simmetrica}: $3\text{ R }6$ ma $6\text{ \cancel{R} }3$.
\item È transitiva.
\end{itemize}
Mentre per la seconda relazione $\equiv_k$ possiamo dire che essa è una
relazione di equivalenza:
\begin{itemize}
\item È riflessiva.
\item È simmetrica, vengono valutati i modulo non direttamente gli operandi.
\item è transitiva (per lo stesso motivo ancora).
\end{itemize}
Con una relazione di equivalenza è possibile effettua un \textbf{partizionamento
delle classi di equivalenza}.
\subsubsection{Relazioni di equivalenza e partizioni}
Considerando una relazione di equivalenza $R\subseteq A^2$ induce una
\textbf{partizione} su $A$.
Le partizioni sono dei sottoinsiemi $A_1,A_2,A_3,...\subseteq A$ tali che:
\begin{itemize}
\item $A_i\neq\emptyset$ (non sono vuoti).
\item $i\neq j\implies A_i \cap A_j =\emptyset$ (non sono sovrapponibili).
\item $\bigcup\limits_{i=1} A_i=A$ (la loro unione ricompone $A$).
\end{itemize}
Una \textbf{classe di equivalenza} di un elemento $a\in A$ è l'insieme di tutti
gli elementi che sono in relazione con $a$, notazione:
$$[a]_R=\{b\in A: a\text{ R }b\}$$
Si dimostra facilmente che :
\begin{itemize}
\item Non esistono classi di equivalenza vuote, questo per via della \textbf{proprietà
riflessiva} delle relazioni di equivalenza.
\item Se prendo due elementi diversi del dominio, le relative classi di equivalenza
possono essere \textbf{disgiunte} (portano all'insieme vuoto) oppure sono la \textbf{stessa} classe di equivalenza $a,b\in A$ vale che
$[a]_R\cap[b]_R=\emptyset\lor[a]_R = [b]_R$.
\item $\bigcup\limits_{a\in A}[a]_R=A$
\end{itemize}
Quindi la \textbf{partizione indotta} da una relazione di equivalenza non è altro che l'insieme
delle classi di equivalenza relative a quella relazione.
\begin{figure}[H]
\centering
\includegraphics[scale=0.4]{images/rel_equi_graph.png}
\caption{L'insieme delle classi di equivalenza di $R$ è la partizione indotta da $R$ su $A$.}
\end{figure}
L'insieme $A$ partizionato rispetto alla relazione $R$ è detto \textbf{insieme quoziente}:
$$A / R$$
Quindi il quoziente di $A$ rispetto a $R$ è lo \textit{"spezzettamento"} di $A$ in classi
di equivalenza.
Consideriamo il seguente esempio di insieme quoziente, consideriamo la relazione di equivalenza $\equiv_4\subseteq\mathbb{N}$.
\textit{Quali classi di equivalenza ammette questa relazione ?}
$$[0]_4={4k}\text{ tutti i multipli di 4 hanno lo stesso resto di 1}$$
$$[1]_4={4k+1}\text{ tutti i multipli di 4 aumentati di 1 hanno lo stesso resto 1}$$
$$[2]_4={4k+2}; [3]_4={4k+3};...$$
\textit{Ne esistono altre ?} No, non esistono altre classi di equivalenza perché
ogni caso successivo a quelli \textit{"base"} si riconduce a quelli \textit{"base"}.
$$\langle n\rangle_4\in\{0,1,2,3\}$$
Voglio vedere se queste classi di equivalenza può rappresentare una partizione:
\begin{itemize}
\item Nessuna classe è vuota.
\item Sono mutuamente disgiunte, poiché se prendo un numero esso ricadrà
solamente in una di queste classi di equivalenza.
\item L'unione di queste $3$ classi di equivalenza restituisce l'insieme originale
$\bigcup\limits_{i=0}^3 [i]_4=\mathbb{N}$.
\end{itemize}
\begin{figure}[H]
\centering
\includegraphics[scale=0.4]{images/rel_equi_quot.png}
\caption{Insieme quoziente di $\equiv_4$}
\end{figure}
$\{[i]_4 : 0\leq i\leq 3\}$ è una partizione di $\mathbb{N}$ indotta dalla relazione
$\equiv_4$, tale per cui mi dia il rispettivo insieme quoziente (a volte impropriamente
chiamato $\mathbb{Z}_4$):
$$N / \equiv_4 \text{ }=\{[i]_4 : 0\leq i\leq 3\}=\mathbb{Z}_4$$
Adesso abbiamo in mano gli strumenti per definire in maniera molto più fine il concetto
di cardinalità.
\subsubsection{Cardinalità degli insiemi - II°}
Sia $\mathcal{U}$ (insieme universo) la classe di tutti gli insiemi,
definiamo la relazione $\sim\subseteq\mathcal{U}^2$ detta relazione
di \textit{equi numerosità} (hanno la stessa dimensione numerica), tra le coppie degli insiemi, se e solo se esiste
una \textbf{biezione} tra $A$ e $B$ (ovvero, se riesco ad esibire una funzione
iniettiva e suriettiva che va da $A$ in $B$).
Questa relazione tra insiemi è una relazione di equivalenza, poiché:
\begin{itemize}
\item $\sim$ è riflessiva, se utilizzo la funzione identità $i_A$.
\item $\sim$ è simmetrica, se esiste una biezione $A\rightarrow B$ allora
esiste una biezione anche $B\rightarrow A$. Ovvero $A\sim B$ e $B\sim A$.
\item $\sim$ è transitiva, se compongo funzioni biettive ottengo ancora una
funzione biettiva.
\end{itemize}
Sue insiemi che stanno in questa relazione vengono detti \textbf{equi numerosi}. Ora
considerando l'insieme quoziente del nostro universo $\mathcal{U}$ rispetto alla
relazione di equi numerosità $\sim$ (quindi stesso numero di elementi in entrambi
i due insiemi), esso mi rappresenta il concetto di \textbf{cardinalità}
di un insieme rispetto ad un altro.
\begin{figure}[H]
\centering
\includegraphics[scale=0.4]{images/insieme_quoziente_cardinalità.png}
\caption{Insieme quoziente $\mathcal{U} / \sim$}
\end{figure}
Quindi spezzettando l'insieme $\mathcal{U}$ in classi di equivalenza
in questa classe di equivalenza ci sono tutti gli insiemi
che sono equi numerosi (seppur diversi).
Questo concetto mi permetterà anche di parlare in maniera molto precisa anche di
insiemi di cardinalità infinita.
\newline
\newline
Per esempio, consideriamo $n\in\mathbb{N}^+$, si consideri l'insieme $J_n=\{1,2,...,n\}$. Per questo
insieme è ovvio quale sia il concetto di cardinalità perché è finito.
Allora diciamo che un insieme $A$ ha cardinalità \textbf{finita} se è equi
numeroso con $J_n$ (ovvero $A\sim J_n$) per un dato $n$ ed in quel caso scriviamo che $|A|=n$.
Quindi nella classe di equivalenza $J_1$ troviamo tutti gli insiemi con un
elemento, nella classe di equivalenza di $J_2$ troveremo tutti gli insiemi con due elementi, ecc.
\begin{figure}[H]
\centering
\includegraphics[scale=0.5]{images/U_insiemi_esemp_card2.png}
\caption{Esempio $\mathcal{U}/\sim$ rispetto all'insieme $J_n$}
\end{figure}
Un insieme che non ha cardinalità si dice banalmente che ha cardinalità \textbf{infinità}. Fin qui abbiamo
parlato ancora di cardinalità finita, ma adesso faremo un esempio con cardinalità infinita.
\subsubsection{Insiemi numerabili}
$A$ si dice \textbf{numerabile} se è nella stessa classe di equivalenza dell'insieme dei numeri naturali
$\mathbb{N}$, ovvero se esiste una relazione di \textbf{equinumerosità} tra l'insieme $A$ e l'insieme $\mathbb{N}$.
$$A\sim\mathbb{N}$$
Siccome stanno in relazione di equi numerosità
vuol dire che è presente una biezione fra i due elementi, quindi due elementi non possono collidere.
\begin{figure}[H]
\centering
\includegraphics[scale=0.6]{images/A_numerabile_N.png}
\caption{$A$ è un insieme numerabile}
\end{figure}
La presenza di questa biezione significa che come $A$ può essere \textbf{listato} con
$f(0),f(1),f(2),...$ su $\mathbb{N}$ senza perdere un elemento, anche l'insieme $\mathbb{N}$ può essere
listato a sua volta su $A$.
Alcuni esempi di insiemi numerabili:
\begin{itemize}
\item I numeri pari $f(n)=2n$ , essi sembrerebbero la metà dei numeri naturali ma sono tanti quanto i numeri
naturali perché esiste questa biezione (vale anche per i dispari $f(n)=2n+1$).
\item L'insieme $\mathbb{Z}$, possono essere presenti diverse funzioni, per esempio
posso mappare i negativi sui numeri pari ed i positivi sui numeri dispari.
\item L'insieme $\mathbb{Q}$, vedremo più avanti.
\item L'insieme delle stringhe binarie che incominciano con $1$, ovvero $1\{0,1\}^*$,
dove una funzione $f(n)=bin(n)$ è in grado di associare un numero naturale (utilizzando
le potenze in posizione) ad una stringa binaria.
\end{itemize}
\subsection{Insiemi non numerabili}
Esistono degli insiemi che non sono listabili, dette in altre parole sono più fitti di $\mathbb{N}$,
è un altro tipo di categoria di infinito.
$$A\nsim\mathbb{N}$$
$\mathbb{R}$ è un insieme non numerabile.
\paragraph{Dimostrazione}\mbox{}\\
L'idea consiste nel dimostrare per assurdo che non esiste una biezione
perché sono presenti dei "buchi" tra le associazioni. Ordine della dimostrazione:
\begin{itemize}
\item Dimostro che $\mathbb{R}\sim[0,1]$ (si dice che è \textit{isomorfo/equi numeroso} all'intervallo $[0,1]$),
ovvero che è fitto quanto l'intervallo citato.
\item Dimostro che $\mathbb{N}\nsim[0,1]$
\item $\mathbb{R}\sim[0,1]\nsim\mathbb{N}\implies\mathbb{R}\nsim\mathbb{N}$
\end{itemize}
\paragraph{Dimostrazione $R\sim[0,1]$}\mbox{}\\
Significa riuscire a rappresentare una funzione
che mappa gli elementi tra i due insiemi in maniera che sia suriettiva ed iniettiva.
Prima di tutto abbiamo una retta cartesiana con un origine fissata e che copre tutti i numeri reali.
Pongo l'intervallo $[0,1]$ in modo che si trovi in corrispondenza del punto mediano della retta $0$,
successivamente prendo un compasso punto il centro nel mediano dell'intervallo e traccio la
semi circonferenza rispetto alla metà dell'intervallo.
\begin{figure}[H]
\centering
\includegraphics[scale=0.5]{images/dim_1.png}
\caption{Dimostrazione $R\sim[0,1]$}
\end{figure}
Gli elementi dell'insieme $\mathbb{R}$ vengono mappati tracciando una retta in direzione del punto
mediano di $[0,1]$, nel punto di intersezione si traccia la retta perpendicolare che interseca
l'intervallo ed in quel punto si trova il valore corrispondente. Si può fare lo stesso
in maniera opposta partendo da $[0,1]$, trovando l'intersezione si parte dal punto mediano
di quest'ultima e si attraversa l'intersezione toccando $\mathbb{R}$.
Questo dimostra che tutti i valori di $\mathbb{R}$ sono associabili
su $[0,1]$, quindi $\mathbb{R}\sim[0,1]$.
\paragraph{Dimostrazione $\mathbb{N}\nsim[0,1]$ (per diagonalizzazione)}\mbox{}\\Supponiamo per assurdo che $\mathbb{N}\sim[0,1]\implies[0,1]$,
ovvero che sia listabile (\textit{elencabile}) in maniera esaustiva così come lo è $\mathbb{N}$.
Siccome sto ipotizzando che sia elencabile, allora creo una lista di tutti gli elementi in $[0,1]$, i numeri
all'interno di questo numero seguono il formato "$0.$", quindi:
\[
\begin{array}{ccccc}
\underline{0.a_{11}} & a_{12} & a_{13} & a_{14} & ... \\
0.a_{21} & \underline{a_{22}} & a_{23} & a_{24} & ... \\
0.a_{31} & a_{32} & \underline{a_{33}} & a_{34} & ... \\
0.a_{41} & a_{42} & a_{43} & \underline{a_{44}} & ... \\
... & ... & ... & ... & ... \\
\end{array}
\]
Se riesco a costruire un numero che non fa parte di questa lista infinita (elusivo alla biezione),
allora vuol dire che la lista non è elencabile, e quindi $[0,1]$ non è numerabile.
Per costruire questo numero elusivo che non si trova in nessuno di questi elementi della lista,
vado a guardare le cifre sulla \textit{diagonale}.\\Costruiamo il numero elusivo alla lista
$$0.c_1c_2c_3c_4$$
Tale che rispetti la seguente regola rispetto alla diagonale del elenco dei numeri $\in [0,1]$
\[
c_i=
\begin{cases}
a_{ii} + 1\text{ se }a_{ii} < 9 \\
a_{ii} - 1\text{ se }a_{ii} = 9 \\
\end{cases}
\]
Ora usando questa regola non riuscirò mai a posizionare il mio nuovo numero
tra quelli elencati, questo perché ovviamente cambio le cifre (il perché questo accade
probabilmente è collegato al fatto che $\mathbb{R}$ è più fitto di $\mathbb{N}$, proprio
quello che vogliamo dimostrare).
Il numero $0.c_1c_2...\in[0,1]$, ma non appartiene nelle liste poiché:
\begin{itemize}
\item Differisce dal primo perché $c_1\neq a_{11}$
\item Differisce dal secondo perché $c_2\neq a_{22}$
\item Differisce da qualunque numero presente sulla diagonale
\end{itemize}
Quindi la lista non è esaustiva $\implies \mathbb{N}\nsim[0,1]$, significa che non cattura tutto l'intervallo $[0,1]$,
quindi non può esistere una biezione tra questo ed $\mathbb{N}$, ovvero $[0,1]$ \textbf{non è numerabile}.
\paragraph{Conclusione}\mbox{}\\
$$\mathbb{R}\sim[0,1]\nsim\implies\mathbb{R}\nsim\mathbb{N}$$
\begin{itemize}
\item $\mathbb{R}$ non è numerabile.
\item Esso è più \textit{"fitto"} di $\mathbb{N}$.
\item Qualsiasi tentativo di listare anche solo un segmento non è esaustivo.
\item $\mathbb{R}$ è un insieme \textbf{continuo}, e tutti gli insiemi equi numerosi
$\mathbb{R}$ si dicono continui.
\item Altri esempi di insiemi non numerabili:
\end{itemize}
\subsubsection{Insieme delle parti di $\mathbb{N}$}
Un altro insieme non numerabile è quello costituito dalla famiglia di sottoinsiemi possibili di $\mathbb{N}$,
quindi mettendo assieme uno dopo l'altro tutti i sottoinsiemi di differenti cardinalità (talvolta chiamato
\textbf{insieme potenza} o \textbf{booleano di} $\mathbb{N}$). Per esempio su un insieme $S=\{a,b,c\}$,
l'insieme delle parti è $\mathcal{P}(S)=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},S\}$.
$$\mathcal{P}(\mathbb{N})=2^{\mathbb{N}} = \{\text{sottoinsiemi di }\mathbb{N}\}\nsim\mathbb{N}$$
Anche questa dimostrazione avviene per diagonalizzazione, per assurdo suppongo che esista una
biezione che mi permetta di elencare tutti i sottoinsiemi di $\mathbb{N}$.
Posso rappresentare i sotto insiemi di $\mathbb{N}$ utilizzando un \textbf{vettore caratteristico}
$A\subseteq\mathbb{N}$, questo è un vettore dove metto il bit di appartenenza rispetto alla corrispondenza
dell'elemento.
\[
\mathbb{N}\rightarrow
\begin{array}{cccccccc}
0 & 1 & 2 & 3 & 4 & 5 & 6 & ... \\
\end{array}
\]
\[
A\rightarrow
\begin{array}{cccccccc}
0 & 1 & 1 & 0 & 1 & 1 & 0 & ... \\
\end{array}
\]
Allora se io suppongo per assurdo che $\mathcal{P}(\mathbb{N})\sim\mathbb{N}$, ovvero che è numerabile
rispetto all'insieme dei numeri naturali, allora posso elencare in maniera esaustiva i sotto insiemi
di $\mathbb{N}$, questo elencandone i vettori caratteristici.
\[
\begin{array}{ccccc}
\underline{b_{11}} & b_{12} & b_{13} & b_{14} & ... \\
b_{21} & \underline{b_{22}} & b_{23} & b_{24} & ... \\
b_{31} & b_{32} & \underline{b_{33}} & b_{34} & ... \\
b_{41} & b_{42} & b_{43} & \underline{b_{44}} & ... \\
... & ... & ... & ... & ... \\
\end{array}
\]
Se riesco a costruire un sottoinsieme di $\mathbb{N}$ (vettore caratteristico) che non fa parte da di questa lista,
allora l'insieme delle parti non è un insieme numerabile poiché non è equi-numeroso con $\mathbb{N}$. Questo
è possibile procedendo per \textit{diagonalizzazione}, per esempio se considerassi il seguente vettore negato:
\[
\begin{array}{ccccc}
\overline{b_{11}} & \overline{b_{22}} & \overline{b_{33}} & \overline{b_{44}} & ... \\
\end{array}
\]
riesco a constatare che esso non appartiene alla lista nonostante sia un sottoinsieme di $\mathbb{N}$
in quanto composto solo da valori booleani.
$$\mathcal{P}(\mathbb{N})\nsim\mathbb{N}$$
\subsubsection{Insieme $\mathbb{N}^{\mathbb{N}}$}
Consideriamo l'insieme di tutte le funzioni possibili che vanno da $\mathbb{N}$ in $\mathbb{N}$.
$$\mathbb{N}^{\mathbb{N}}=\{f:\mathbb{N}\rightarrow\mathbb{N}\}$$
Ipotizzando che $\mathbb{N}^{\mathbb{N}}$ sia numerabile ($\mathbb{N}^{\mathbb{N}}\sim\mathbb{N}$),
consideriamo la seguente tabella dove nella prima
colonna si trova l'elenco esaustivo di tutte le funzioni $\in\mathbb{N}$, e nelle colonne successive tutto
il dominio completo di $\mathbb{N}$. Significa che per ogni riga sara presente l'insieme dei valori che
fornisce il grafico di una funzione $f_i$.
\begin{center}
\begin{tabular}{c|ccccc}
\toprule
Elenco delle funzioni di $\mathbb{N}$ & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{...$\in\mathbb{N}$} \\
\midrule
$f_0$ & $\underline{f_0(0)}$ & $f_0(1)$ & $f_0(2)$ & $f_0(3)$ & $...$ \\
$f_1$ & $f_1(0)$ & $\underline{f_1(1)}$ & $f_1(2)$ & $f_1(3)$ & $...$ \\
$f_2$ & $f_2(0)$ & $f_2(1)$ & $\underline{f_2(2)}$ & $f_2(3)$ & $...$ \\
$f_3$ & $f_3(0)$ & $f_3(1)$ & $f_3(2)$ & $\underline{f_ 3(3)}$ & $...$ \\
$...$ & $...$ & $...$ & $...$ & $...$ & $\underline{...}$ \\
\bottomrule
\end{tabular}
\end{center}
Allora anche in questo caso per diagonalizzazione voglio costruire una funzione $\in\mathbb{N}^{\mathbb{N}}$ ma
elusiva all'elenco delle funzioni della tabella:
$$\varphi:\mathbb{N}\rightarrow\mathbb{N}\text{ come }\varphi(n)=f_n(n)+1$$
Siamo d'accordo che $\varphi$ sia ben definita, visto che per ogni immagine corrisponderà un immagine numero naturale,
ma notiamo che una qualsiasi $\varphi(n)$ presa sulla lista avrà per forza una immagine della diagonale discordante
rispetto a quelle elencate nella tabella.\\ Quindi abbiamo una funzione elusiva all'elenco, e la nostre ipotesi si rivela assurda:
$$\varphi(0)=f_0(0)+1\neq f_0(0)$$
$$\mathbb{N}^{\mathbb{N}}\nsim\mathbb{N}$$
N.B.: Gli insiemi $\mathcal{P}(\mathbb{N})$ e $\mathbb{N}^{\mathbb{N}}$ sono detti \textbf{insiemi continui},
e sono equi numerosi a $\mathbb{R}$.
\section{Teoria della calcolabilità}
\subsection{Cosa è calcolabile?}
Sappiamo che la potenza computazionale di un sistema di calcolo $\mathcal{C}$ corrisponde a:
$$F(\mathcal{C})=\{\mathcal{C}(P,\_):P\in PROG\}\subseteq DATI_{\bot}^{DATI}$$
Il nostro problema consiste nel comprendere se questa inclusione sia propria o impropria,
per dimostrare ciò posso utilizzare il concetto di cardinalità precedentemente appreso.\\
Se riesco a dimostrare che il primo insieme ha una cardinalità numerabile ed il secondo ha
una cardinalità continua allora il secondo insieme sarà molto più grande del primo.\\Prendiamo alcune
\textbf{assunzioni} che verranno dimostrate successivamente nel corso:
\begin{itemize}
\item $PROG\sim\mathbb{N}$, i programmi sono tanti quanti i numeri naturali, questo
perché un programma viene digitalizzato in una fila di bit (finiti). Questo vuol dire che per ogni
programma corrisponderà un numero che fa parte dei numeri naturali.
\item $DATI\sim\mathbb{N}$, i dati sono tanti quanto i numeri, questo per lo stesso motivo
di digitalizzazione (o traduzione) in binario delle informazioni.
\end{itemize}
Possiamo dire che la potenza computazionale sia equinumerosa rispetto al numero di programmi,
al variare del programma cambio la funzione di potenza computazionale. A questo punto agganciamo
la prima assunzione.
$$F(\mathcal{C})\sim PROG\sim\mathbb{N}$$
Sapendo che l'insieme dei dati in dati definito come $DATI_{\bot}^{DATI}$, grazie alla
seconda assunzione che abbiamo fatto allora possiamo asserire:
$$DATI_{\bot}^{DATI}\sim\mathbb{N}_{\bot}^{\mathbb{N}}$$
Abbiamo visto precedentemente che $\mathbb{N}^{\mathbb{N}}\nsim\mathbb{N}$, allora unendo le precedenti
dimostrazioni possiamo confermare:
$$F(\mathcal{C})\sim PROG\sim\mathbb{N}\nsim\mathbb{N}^{\mathbb{N}}\sim DATI_{\bot}^{DATI}$$
$$F(\mathcal{C})\nsim DATI_{\bot}^{DATI}$$
Ovvero, che l'insieme dei programmi (corrispondente all'insieme delle funzioni di potenza di calcolo)
non è equinumeroso (o \textit{isomorfo}) all'insieme delle funzioni che vanno da dati in dati. In parole
povere ho un numero di programmi nettamente inferiore (fitto quanto i numeri naturali) rispetto al numero
di funzioni (o problemi) calcolabili (fitto quanto i reali $\mathbb{N}_{\bot}^{\mathbb{N}}$).
\subsubsection{Dimostrazione $DATI\sim\mathbb{N}$}
Vogliamo stabilire una corrispondenza \textbf{biunivoca} tra dati e numeri naturali, ovvero
che devo riuscire a "nascondere" un dato all'interno di un numero naturale, tale che
se lo dovessi riportare all'insieme dei dati otterrei esattamente quel dato (e non un altro).
\newline\newline
Questa biezione la voglia rendere effettiva e programmabile, ovvero costruirci delle primitive che
operino direttamente sulla codifica numerica dei dati così che possiamo smaterializzare completamente
il mondo dei dati in quello dei numeri.
\newline\newline
Questa volta vogliamo dimostrare che l'\textbf{insieme delle coppie} $\mathbb{N}\times\mathbb{N}$
è numerabile. Questo avverrà per passi, prima dimostreremo che l'insieme delle coppie è isomorfo a
$\mathbb{N}^+$ (quindi escluso lo $0$) e poi di conseguenza che lo è per tutto $\mathbb{N}$.
Questo per effetto collaterali che anche l'insieme dei razionali $\mathbb{Q}$ è numerabile,
questo perché sono una frazione, quindi una coppia di interi.
\paragraph{Dimostrazione $\mathbb{N}\times\mathbb{N}\sim\mathbb{N}^+$}\mbox{}\\
$$\langle ,\rangle :\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}^+$$
$$\langle x,y\rangle =n$$
La \textbf{funzione coppia di Cantor} è definita per mezzo delle parentesi
angolari, prende due argomenti $x,y$ e restituisce un numero $n$, questo
in maniera iniettiva e suriettiva (biettività).
\newline\newline
Ovvero che coppie diverse vengono mappate in numeri diversi, e se
ho un numero devo essere in grado di tornare alla stessa coppia $x,y$. Quindi esibiremo sia
l'andata della funzione coppia di Cantor che il ritorno, esibiremo anche i due proiettori
\textit{sin} e \textit{des} tali che mi restituiscano i due argomenti in questione.
$$sin:\mathbb{N}^+\rightarrow\mathbb{N}\text{ e }des:\mathbb{N}^+\rightarrow\mathbb{N}$$
$$sin(n)=x\text{ e }des(n)=y$$
Vogliamo dare una rappresentazione grafica di questa funzione, Cantor ha pensato di realizzare
una tabella che ha come righe e colonne l'insieme $\mathbb{N}$. In questa tabella
il valore della coppia si trova esattamente posizionato all'incrocio tra l'$x$-esima riga
e della $y$-esima colonna.
\[
\begin{tabular}{c|ccccc}
x/y & 0 & 1 & 2 & 3 & 4 \\
\midrule
0 & 1 & 3 & 6 & 10 & 15 \\
1 & 2 & 5 & 9 & 14 & ... \\
2 & 4 & 8 & 13 & ... & ... \\
3 & 7 & 12 & ... & ... & ... \\
4 & 11 & ... & ... & ... & ... \\
\end{tabular}
\]
La disposizione ingegnosa della tabella evita di andare in un elenco infinito,
nel senso che se dovessi elencare tutti i numeri naturali andando verso il basso (o
destra) non riuscirei a finire mai, ed inoltre non sarebbe un buon approccio visuale per trovare
la corrispondenza con l'altro insieme. I numeri sono disposti in maniera che il successivo
si trovi sulla diagonale (andando verso l'alto).
$$\langle 2,1\rangle =8$$
Con questa rappresentazione, coppie diverse non riusciranno mai a confluire nella stessa
casella (coordinate di punti che individuano un punto univoco), e viceversa (iniettiva),
questo mi conferma che la funzione è biettiva.\\Adesso mettiamo da parte la forma tabellare e
consideriamo la \textbf{forma analitica} di $\langle ,\rangle $.
\begin{figure}[H]
\centering
\includegraphics[scale=0.4]{images/coord_dim.png}
\caption{Diagonale che passa per $\langle x,y\rangle $}
\end{figure}
Notiamo che per il valore che voglio valutare attraverso la funzione di Cantor passa una diagonale,
questa diagonale parte dalla colonna $0$ e dalla riga $x+y$ (il punto $\langle x+y,0\rangle $). La funzione
coppia nell'origine della diagonale assumerà un certo valore, e visto che i numeri sulla
diagonale incrementano in maniera crescente di una sola unità, allora potrò raggiungere $\langle x,y\rangle $
sommando $y$.\\A questo punto il mio problema si riduce a trovare delle coppie particolari ovvero,
la cui seconda coordinata è $0$, le chiamiamo $\langle z,0\rangle$. Notiamo nella prima colonna
c'è una correlazione con gli elementi di $x$, e vediamo che l'elemento $i$-esimo della prima
colonna corrisponde alla somma tra il corrispettivo elemento $x$ e l'elemento $i-1$ della colonna,
allora riusciamo ad esprimere una \textbf{legge matematica} per descrivere questa \textit{codifica}.
\begin{enumerate}
\item $\langle x,y\rangle =\langle x+y,0\rangle +y$
\item $\langle z,0\rangle ? \implies \langle z,0\rangle = \sum_{i=1}^z i+1=\frac{z(z+1)}{2}+1$
\end{enumerate}
\noindent Allora $(1)+(2)$:
$$\langle x,y\rangle = \langle x+y,0\rangle+y=\frac{(x+y)(x+y+1)}{2}+y+1$$
\paragraph{Come tornare da $\mathbb{N}^+$ a $\mathbb{N}^+2$}
Ovvero, come trovare le funzioni $sin$ e $des$.
$$\langle x,y \rangle = n \longrightarrow sin(n)=x \text{ e } des(n)=y$$
\begin{figure}
\centering
\includegraphics[scale=0.5]{images/coord_dim_2.png}
\caption{$n=13$}
\end{figure}
Partiamo da un elemento $n$ presente nell'intersezione dei due insiemi definiti da
$x$ e $y$ e vogliamo individuare le due relative componenti. Procedo trovando
le coordinate dell'origine della diagonale che passa per $n$, ovvero $\langle\gamma ,0\rangle$.
Considerando la dimostrazione precedente possiamo dire che $y = n-\langle\gamma ,0\rangle$, ovvero
procedo a ritroso sulla diagonale partendo da $n$ ed andando verso $\langle\gamma ,0\rangle$.\\Allora,
sapendo che $\gamma=x+y$ posso trovare facilmente le parti destre e sinistre.\\ Il problema principale
ora è trovare $\gamma$, questo non è altro che l'intero più grande tale per cui l'origine
della diagonale sia minore di $n$.
$$\gamma = \max\{z\in\mathbb{N}:\langle z,0\rangle\leq n\}$$
Quindi dobbiamo risolvere la disuguaglianza la quale ci darà un range su $n$, all'interno di questo
range $\langle z,0\rangle\leq n$ andiamo a prendere l'intero più grande che soddisfa questa disuguaglianza.
$$\langle z,0\rangle\leq n\longrightarrow\frac{z(z+1)}{2}+1\leq n\longrightarrow z^2+z+2-2n\leq 0$$
$$z_{1,2}=\frac{-1 \pm\sqrt{8n-7}}{2}$$
Quindi devo scoprire quale è l'intero più grande dati:
$$\frac{-1 -\sqrt{8n-7}}{2}\leq z\leq \frac{-1 +\sqrt{8n-7}}{2} $$
l'elemento a destra è il più grande valore, ma non so se è intero, quindi dovrò correggere ciò:
$$\gamma=\left\lfloor\frac{-1+\sqrt{8n-7}}{z} \right\rfloor$$
Questa è un formula che utilizza la variabile in input $n$, quindi riusciamo a ricavare il parametro
sinistro e destro della funzione di Cantor e ritornare allo stato iniziale:
$$des(n)=y=n-\langle\gamma ,0\rangle \text{ e }sin(n)=x=\gamma -y$$
\paragraph{Esempio andata e ritorno tra $\mathbb{N}^2$ e $\mathbb{N}^+$}
$$\text{Andata : }\mathbb{N}^2 \longrightarrow\mathbb{N}^+$$
$$\langle 10,20\rangle = \frac{30\cdot31}{2}+20+1=15\cdot31+21=485+21=486$$
$$\text{Ritorno : }\mathbb{N}^+\longrightarrow\mathbb{N}^2$$F
$$\gamma = \left\lfloor \frac{-1 + \sqrt{8 \cdot 486-7}}{2} \right\rfloor = \lfloor 30.6448\rfloor = 30$$
$$y=486- \langle 30,0\rangle = 486- \left(\frac{30\cdot31}{2}+1\right)=486-466=20=des(486)$$
$$x=30-20=10=sin(486)$$
Adesso noi abbiamo dimostrato che $\mathbb{N}^2\sim\mathbb{N}^+$.
\paragraph{Dimostrazione $\mathbb{N}\times\mathbb{N}\sim\mathbb{N}$}
Definisco una nuova funzione:
$$[,]:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}\text{ tale che }[x,y]=\langle x,y\rangle-1$$
Adesso ho una funzione esplicita per mappare $\mathbb{N}^2$ su $\mathbb{N}$.\\Nota: A questo
punto otteniamo che l'insieme dei razionali $\mathbb{Q}$ sono coppie di interi $(num,den)$. Dunque
$[,]$ mostra che $\mathbb{Q}$ è numerabile.
\paragraph{Dimostrazione rigorosa che $DATI\sim\mathbb{N}$}
Mostriamo le nozioni appena apprese sulle principali strutture dati.
\paragraph{Liste d'interi}\mbox{}\\
$$\textit{codifichiamo } x_1,x_2,...,x_n\rightarrow\langle x_1,x_2,...,x_n\rangle$$
Quindi il numero che rappresenta la codifica è indicato con il numero all'interno delle parentesi angolari.
L'idea consiste nell'incapsulare il risultato di una coppia di elementi come elemento destro
della coppia più esterna. Non sapendo quanto sia lunga la lista dovrò porre un elemento che mi
segnali il termine, e questo lo posso fare con $\langle x_n,0 \rangle$.
$$\langle x_1,x_2,...,x_n\rangle = \langle x_1,\langle x_2,\langle ...\langle x_n,0\rangle ...\rangle\rangle\rangle$$
Per esempio:
$$\textit{codifica }1,2,5\rightarrow\langle 1,2,5\rangle=\langle 1,\langle 2,\langle 5,0\rangle\rangle\rangle=$$
$$\langle 1,\langle2,16\rangle\rangle=\langle 1,188\rangle=$$
$$=18144$$
Per l'operazione di decodifica quello che facciamo è di considerare la codifica della mia lista $M$ (non il
risultato ma la lista di coppie incapsulate) come un albero binario.
\begin{figure}[H]
\centering
\includegraphics[scale=0.5]{images/bin.png}
\end{figure}
Allora dato questo albero il figlio
sinistro è l'elemento sinistro (la testa della lista) ed il figlio destro è la parte restante della lista,
allora continuando a considerare il figlio sinistro come una struttura dati lineare ottengo
la lista codificata, questo attraversamento dell'albero in pre-ordine terminerà quando incontrerà un
figlio destro $0$ (l'ultimo elemento, c'è solo un elemento con $0$).\\Vogliamo effettuare
delle implementazione in pseudo-codice (simile C), assumiamo $0$ come la lista nulla, e $\langle,\rangle,sin,des$
come la funzione di Cantor $\langle , \rangle$.
\paragraph{Implementazione codifica}\mbox{}
\begin{lstlisting}[mathescape=true]
int encode($x_1,...,x_n$){
int $k$ = 0;
for(int $i$ = $n$; $i$ >= 1; $i$--)
$k$ = $\langle x_i,k\rangle$;
return $k$;
}
\end{lstlisting}
\paragraph{Implementazione decodifica}\mbox{}
\begin{lstlisting}[mathescape=true]
void decode(int $n$){
if($n$!=0){
print($sin(n)$);
decode($des(n)$);
}
}
\end{lstlisting}
Altre operazioni utili possono essere sono quelle per calcolare la \textbf{lunghezza}:
\begin{lstlisting}[mathescape]
int length(int n){
return $n$==$0$ ? $0$ : $1$ + length($des(n)$);
}
\end{lstlisting}
Oppure per calcolare la \textbf{proiezione}:
\[
proj(t,b)=
\begin{cases}
-1 & \text{se } t>length(n)\text{ o }t==0 \\
x_t & \text{se }1\leq t\leq length(n)\text{ e }n=\langle x_1,...,x_t,..., x_m\rangle
\end{cases}
\]
\begin{lstlisting}[mathescape]
int proj(int $t$, int $n$){
if ($t$ == $0$ || $t$ > length($n$))
return $-1$;