Notes

Intuition $$ \frac{1}{\sqrt{ 2\pi }}, \frac{\cos(kx)}{\sqrt{ \pi }}, \frac{\sin(kx)}{\sqrt{ \pi }}, \dots $$$$ \int_{0}^{2\pi} (\sin (kx))^{2} \, dx = \int_{0}^{2\pi} (\cos(kx))^{2} \, dx = \pi $$$$ \int_{0}^{2\pi}\sin(kx)\sin(hx) \, dx = \int_{0}^{2\pi}\cos(kx)\cos(hx) \, dx = 0 $$$$ \int_{0}^{2\pi}\sin(kx)\cos(hx) \, dx = \int_{0}^{2\pi} \sin(kx) \, dx = \int_{0}^{2\pi}\cos(hx) \, dx = 0 $$Proofs of the relations In this section we quickly prove why the above equations hold. First we all agree that $\int_{0}^{2\pi} \sin(kx) \, dx = \int_{0}^{2\pi} \cos(hx) \, dx = 0$ because their period divides $2\pi$ and the sum of the area of a period is clearly 0. Or we can explicitly find the primitive and solve ...

This note briefly states and proves one of the most famous inequalities in geometry/analysis. Theorem Statement $$ \left( \sum_{i = 1}^{n} x_{i}y_{i} \right) ^{2} \leq \left( \sum_{i= 1}^{n} x^{2}_{i} \right) \left( \sum_{i = 1}^{n} y^{2}_{i} \right) $$$$ \lvert \langle u, v \rangle \rvert ^{2} \leq \langle u, u \rangle \cdot \langle v, v \rangle $$ with $u = \left( x_{1}, \dots, x_{n} \right)$ and $v = \left( y_{1}, \dots, y_{n} \right)$ and the $\langle \cdot, \cdot \rangle$ operator is the inner product. We have equality if and only if $u$ and $v$ are linearly dependent (this one is easy to prove if seen from the vectorial view). ...

Introduzione agli alberi di decisione Setting del problema Spazio delle ipotesi Definizione spazio ipotesi Per spazio delle ipotesi andiamo a considerare l’insieme delle funzioni rappresentabili dal nostro modello. Questo implica che l’allenamento ricerca l’ipotesi ossia la parametrizzazione ottimale del nostro modello, ottimale in quanto minimizza l’errore che viene compiuto nel training set. L’insieme iniziale si può anche considerare come inductive bias ossia il restringimento solamente a certe ipotesi e non tutte. Altrimenti abbiamo no free lunch. ...

I problem idi accoppiamento sono abbastanza comuni per ottimizzazione a grafi. In questa serie di note andiamo a trattare brevemente i problemi principali, con un accenno veloce ad alcuni algoritmi di soluzione per esse. Grafo bipartito Un grafo bipartito è un insieme $(O \cup D), (A)$ di nodi e di archi. Tutti i nodi sono o fra i nodi di origine oppure fra i nodi di destinazione, e gli archi sono solamente collegati fra nodi di origine e nodi di destinazione. ...

Questi problemi sono una sottoclasse della programmazione lineare con variabili reali. (Alcuni riescono a riconoscere se un problema è in questa forma, e lo risolvono in modo istantaneo se questo succede). Un problema dei router è un classico problema di flusso, che si risolvono con questi algoritmi polinomiali Note introduttive Rete, terminologia In questo caso andiamo ad indicare con rete un grafo con $G = (N, A)$ con $N$ nodi e $A$ archi, che solitamente sono diretti con pesi associati. Possiamo interpretare gli archi come canali in cui fluiranno un qualcosa (ad esempio acqua in un tubo). Questi possono essere discreti o continui (mi sembra di ricordare che il discreto stranamente è più facile del continuo, non so se vale anche in questo caso). Abbiamo poi i nodi che sono punti di ingresso e uscita della nostra rete. ...

Questa sezione la tengo separata rispetto agli altri per favorire lo studio, così questa roba nuova la ripasso più spesso, in seguito si può accorpare. Goldberg Tarjan/Push-relabel Questo algoritmo è importante perché introduce ragionamenti sul minimo locale che possa alla fine essere ricomposto come soluzione globale. Questa lezione youtube lo spiega da Dio Preflusso Slide La parte nuova di questa cosa è che i vincoli di bilanciamento possono diventare una disuguaglianza. (cioè quello che arriva è di più rispetto quanto va fuori. ...

Sembra essere molto simile a Central Limit Theorem and Law of Large Numbers però per Entropy. This is also called Shannon’s source coding theorem see here Enunciato AEP $$ -\frac{1}{n} \log p(X_{1}, X_{2}, \dots, X_{n}) \to H(X) $$ in probability (la definizione data in Central Limit Theorem and Law of Large Numbers#Convergence in probability). Un modo alternativo per enunciarla è così, segue il metodo in (MacKay 2003). $$ \left\lvert \frac{1}{N} H_{\delta}(X^{N}) - H(x) \right\rvert \leq \varepsilon $$Ossia a grandi linee: dato una variabile aleatoria $X$ e $N$ estrazioni della stessa, possiamo comprimere questa sequenza in $NH(X)$. ...

8.1 Introduzione 8.1.1 Il problema che risolve Vogliamo cercare di creare un metodo matematico che sia utile per calcolare area di qualunque curva. L’idea principale per risolvere questo problema è approssimare l’area, lo facciamo utilizzando rettangoli, la formalizzazione sarà molto aiutata dal limite. 8.1.2 Sottografico di funzione $$ A = \{ (x,y) \in \mathbb{R}^2 | x \in D(f(x)), 0\leq y \leq f(x)\} $$Praticamente sto prendendo tutti in punti positivi sotto al grafico. ...

Introduzione Definizione grammatica regolare Definizione In pratica posso avere solamente come terminali a, oppure un suffisso a su un non terminale. Queste grammatiche sono interessanti perché è molto facile costruire un automa che sia in grado di riconoscere questo linguaggio. Seguendo una definizione più lasca possono anche accettare dei nonterminali epsilon Espressione regolare a NFA Questa sezione è anche presente in Automi e Regexp, però è riportata qui così c’è l’insieme di tutte le cose in un unico posto. ...

7.1 De Hopital 7.1.1 Lemmi preliminari Questo lemma preliminare era già presente per la prova del teorema degli zeri Questo lemma è molto interessante perché mette in relazione il finito (le successioni) con l’infinito (i reali) In molte dimostrazioni si dà per scontato questo lemma, ma è una sottigliezza importante che giustifica l’utilizzo di successioni per limiti reali. Ci permette di semplificare molto le dimostrazioni perché riusciamo a trattare le successioni molto meglio. ...