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…
Algorithms for Sparse Matrix-Vector Multiplication # Compressed Sparse Row # This is an optimized way to store rows for sparse matrices: Sparse MVM using CSR # void smvm(int m, const double* values, const int* col_idx, const int* row_start, double* x, double* y) { int i, j;…
Algebra modulare # Assunzioni # Andiamo ora ad assumere l'esistenza e correttezza di alcune cose di base. (in teoria si possono dimostrare da cose più di base, ma non ho tempo). Teorema fondamentale dell'algebra # Ogni numero intero si fattorizza in modo unico. Algoritmo di…
The human ability of making analogies proceeds in such a way as to keep complexity minimal. Perché facciamo questo? Perché è la cosa più semplice da fare! Anche su Vapnik's dimensions è simile questa idea! Occam razor, Epicuro, con Solomonoff che ha risolto problema…
Introduzione alle Tabelle di Hash # 5.1.1 Prototipo # Vogliamo implementare le operazioni del prototipo dizionario presentato in Strutture di dati elementari , e vogliamo fare solo queste 3 ma molto bene. Insert O(1) Delete O(1) Search in O(1) La struttura dati di hash riesce a…
Quick introduction # Si assume che la descrizione più intelligente di un qualcosa è la stringa più corta che descrive quella, un po' forse è arbitrario, perché minore complessità, non è detto che sia direttamente relazionata con la difficoltà di descriverla. Nel caso di AIT,…
"Information theory must precede probability theory, and not be based on it. By the very essence of this discipline, the foundations of information theory have a finite combinatorial character." Kolmogorov, A. N. (1983). Combinatorial foundations of information theory and the…
Bounds # Markov Bound # Questo bound è abbastanza banale se fatto da un punto di vista grafico, comunque afferma che P ( X ≥ y ) ≤ y E [ X ] Il motivo è che (assumendo che X sia una variabile aleatoria non negativa) y P ( X ≥ y ) = y ∫ x = y + ∞ f ( x ) d x ≤ ∫ x = y + ∞ x…
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 # Data una serie di variabili aleatorie X 1 , X 2 , … i.i.d. ∼ p ( x ) se vale che − n 1 lo g p ( X 1 …
Introduzione alla Randomicità # Questo è principalmente basato su (Li & Vitányi 2019) Capito 1.9 Sembra che la nozione di random sia alla fine una cosa molto profonda. Per esempio, un caso lampante che le definizioni non funzionano nel caso di numeri trascendenti è che…