Notes

There is a close relationship between topologies and metric spaces. We will see that every metric space directly induces a topology based on its metric. (from a CS point of view, this means topologies are more general than metric spaces). Definition of Metric Space We say that $(\mathcal{X}, d)$ is a metric space if $\mathcal{X}$ is a set and $d$ a function $\mathcal{X} \times \mathcal{X} \to \mathbb{R}$ such that: Distance from it self is zero $d(a, b) = 0 \iff a = b$ Symmetric function: $d(a, b) = d(b, a), \forall a, b \in \mathcal{X}$ Triangle inequality is satisfied: $\forall a, b, c \in \mathcal{X}: d(a, b) + d(b, c) \geq d(a, c)$ Induced topology If we define the sets $B(c, r) = \left\{ p \in \mathcal{X} \mid d(p, c) < r \right\}$ to be open, this induces a topology $(\mathcal{X}, \mathbb{B})$ where $\mathbb{B} := \left\{ B(c, r) \mid c \in \mathcal{X}, r \in\mathbb{R} \right\}$. This should be easy to verify, but it is mostly uninteresting and quite intuitive (i’m not reasoning like a mathematician now). ...

In this note we explore a theme of time and space complexity. Those are cardinal themes in Theoretical CS. Time -> execution step bounds on algorithms Space -> the cells visited by a Turing Machine when executed. Introduction to Time Complexity This note will build upon know techniques of algorithms analysis explained in Notazione Asintotica. We will need big-$O$ notation and $o$ notation. L’idea è che il problema di decisione è decidibile se limito la lunghezza del teorema. Simile al numero di Chaitin, che non è computabile, ma è approssimabile quanto si vuole. In un certo senso è computabile. The general idea is to ask how the function $\varphi$ that maps the longest $n$ proof to the number of steps of computation behaves. ...

8.1 Dimostrazione teorema invarianza 8.1.1 Introduzione Basi: Due proposizioni sono equivalenti quando valgono sugli stessi mondi. quindi $\forall v, \llbracket F \rrbracket ^v \equiv \llbracket G \rrbracket ^ v$. Vogliamo dire che dati un buco presente in una proposizione, queste valgono sempre, sono in effetti equivalenti. Il buco la prendo come una variabile proposizionale. (riempire = rimpiazzare il buco) 8.1.2 Operazione di sostituzione Si può notare che ci sono 4 casi base, mentre le altre 4 sono per ricorsione strutturale. ...

Introduzione This is a short introduction to statistical learning, made with the help of the book (James et al. 2023). statistical learning refers to a set of approaches for estimating $f$ . Utilizzi del statistical learning Solitamente sono due gli utilizzi Predizione e inferenza. Per predizione intendiamo il miglior modello che possa produrre le Y che ancora non conosciamo. Per inferenza significa il miglior modello f per predire Y che conosciamo. ...

Andremo ad analizzare integrali di funzioni continue su insiemi semplici (domini normali) . Introduzione Y-semplice e regolarità È un insieme semplice di punti, in pratica, se considero un intervallo limitato e due funzioni definite in questo intervallo tale che una è sempre minore dell’altra, l’insieme y-semplice sono i punti compresi fra queste Definizione del libro Intuizione integrale Definizione del prof. Dato un insieme semplice A e una funzione continua $f:A \to R$ allora è ben definito l’integrale $$ \int_Af(x, y) dxdy \in R $$ Osservazione 1: ...

This small note is an introduction to Topology that follows the introductory arguments of (Armstrong 2013). Euler’s Theorem We will start our journey in topology following a classical example in the history of Mathematics the relation: $$ v - e + f = 2 $$ Valid for classical Polyhedrons. Basic definitions Polyhedron It’s a collection of plane polygons (see Programmazione lineare#Poliedro) such that: Every polygon shares each of its edges with exactly another polygon We have vertexes that can be shared by many polygons. Informally we have a piece of surface with a vertex. Theorem statement If we have a Polygon $P$ such that ...

This note will introduce the ideas presented by Vapnik, presented in ({Shalev-Shwartz} & {Ben-David} 2014) chapter 6. Briefly this says that infinite-size classes are indeed learnable. This set of note is still a work in progress. But it’s very important for statistical learning theory. We have that if $\lvert \mathcal{H} \rvert < \infty \implies vc(\mathcal{H} \rvert) \leq \log_{2} \lvert \mathcal{H}$ Example: if $\mathcal{H}$ is the set of linear classifiers on $\mathbb{R}^{d}$ then we have that the dimension is $d + 1$. ...

Omnidirezionali Antenne omnidirezionali Slides antenne omnidirezionali Il senso di omnidirezionale è in tutte le direzioni dell’antenna (nota: non è isotropico, perché non è da un singolo punto). in passato era importante andare a guardare la direzione per trovare la polarizzazione migliore. Praticamente irradia a 360 gradi sul piano permedicolare all’antenna. Esempio pattern di radiazione Questo genere di antenne sono irrealizzabili la più simile è la antenna dipolo dipolo, ma comunque non rispetta le antenne in questo verso diciamo. ricorda i dBi che abbiamo citato in Fisica del Wireless. ...

Perché a stack Capire l’architettura significa capire la struttura (l’organizzazione) del nostro app e comprenderne i motivi (i sottoproblemi risolti) che ogni livello prova a risolvere La soluzione che è stata individuata, e ha rappresentato uno dei principali cardini del successo delle reti e della nascita di Internet, è data dalla separazione delle classi di protocolli in livelli. La struttura dei livelli dei protocolli di rete prende il nome di architettura dei protocolli di rete. Il concetto di architettura dei protocolli, suddivisa in livelli, è semplice ed è basato su alcune condizioni. ...

1.1 Il cammino minimo 1.1.1 Definizione e caratteristiche 1.1.2 Costi negativi Sono cose molto brutte 1.1.3 Cammino minimo semplice Costruzione di cammini minimi 1.2 Vertici 1.2.1 definizione distanza fra due vertici Costo del cammino minimo che li connette Condizione di bellman Albero dei cammini minimi Rilassamento Definizione Si va a vedere dove non funziona la disuguaglianza triangolare, se localmente non funziona ovvero se per esempio succede $D_{xu} + \omega(u,y) < D_{xy}$ per qualche vertice all’interno del grafo, so di per certo che la distanza $D_{xy}$ non è una distanza, quindi possiamo riassegnarla in modo che verifichi la disuguaglianza ...