Notes

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$. ...

Alberi BST e AVL 4.1 Alberi binari di ricerca (BST) Queste sono delle varianti rispetto all’albero, descritto in modo molto sommario sopra (binario perché ogni nodo ha al massimo due figli, mentre l’albero può averne quanti se ne vuole). 4.1.1 Introduzione La caratteristica principale dell’albero di ricerca è una condizione sulle chiavi (che hanno i figli). Infatti questo albero binario di ricerca si può vedere come una implementazione della struttura astratta del dizionario. (che ricordiamo, è un struttura in cui a ogni nodo sono presenti due valori, una chiave (tute differenti) e un dato, e sono definite tre operazioni principali, possiamo vederla come interfaccia). ...

Strutture algebriche Differenza matematica e informatica Una osservazione per quanto riguarda la logica intuizionista è che sta a metà fra matematica e informatica perché la dimostrazione intuizionista possiede in sé un algoritmo e una struttura di dati. Infatti di solito l’informatico scrive senza fare la dimostrazione dell’algoritmo mentre il matematico scrive la dimostrazione senza fare l’algoritmo (inoltre può definire degli enti ed oggetti che non siano rappresentabili come dati in quanto possono essere infiniti. ...

6.1 Introduzione 6.1.1 L’importanza del topic Gli algoritmi di ordinamento sono molto di base per la comprensione dell’ampio raggio degli algoritmi. Utilizzano l’analisi, introducono tecniche di risoluzione dei problemi computazionali come greedy, divide et impera e simile. Permettono un primo uso di astrazioni e l’analisi di sottoproblemi. 6.1.2 Il problema Il problema è trovare una permutazione di un insieme di numeri iniziali tale per cui tale insieme di numeri si ordinato: ...

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. ...

Public Key Encryption We now define a formally what is a public key encryption Formal definition of Public Key Encryption We define a 3-tuple formed as follows: $(G, E, D)$ where $G$ is the generator for the private and public keys, from now on identified as $(pk, sk)$ (public key and secret key) $E(pk, m)$ the encryption algorithm, that takes the $pk$ and the message in input $D(sk, c)$ the decryption algorithm, that takes the $sk$ and the ciphertext in input. Now is this definition useful? i don’t think so! We can’t create theorems for it, too general I suppose. Is it clear? yes! I think this is the usefulness of maths in many occasions, it delivers some complex information in a concise and understandable manner. ...

Utilizzano blocchi per cifra invece che stream generators. $n$ bits in input and $m$ bits in output generally a key is expanded into multiple keys, one for each rounds, and applied to a round function that iterates on the $m$. DES 56 bit 3DES 56*3 bit di chiave AES che può andare a 128, 196 o 256 Solitamente i stream ciphers studiati in OTP and Stream Ciphers sono più veloci. Cipher Speed MB/sec RC4 126 Salsa20 643 Sosemanuk 727 AES 13 3DES 109 Data Encryption Standard - 1974 da IBM su commissione di NSA (Horst Feistel designed Lucifer at IBM in early 1970) - 1976 DES is federal standard with key-len 56 bits and block-len 64 bits. in quel periodo era solamente fatta dalla intelligence, non c’era bisogno di comunicazioni per il pubblico in quel periodo. ...

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 ...