Alberi BST e AVL

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…

Sparse Matrix Vector Multiplication

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

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…

March 20, 2024 · Reading Time: 4 minutes · By Xuanqiang Angelo Huang

Model of Analogies

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…

March 20, 2024 · Reading Time: 2 minutes · By Xuanqiang Angelo Huang

Tabelle di hash

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…

Introduction to Algorithmic Information and Complexity

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,…

March 14, 2024 · Reading Time: 8 minutes · By Xuanqiang Angelo Huang

Algorithmic Probability

"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…

March 5, 2024 · Reading Time: 3 minutes · By Xuanqiang Angelo Huang

Central Limit Theorem and Law of Large Numbers

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…

March 5, 2024 · Reading Time: 9 minutes · By Xuanqiang Angelo Huang

Asymptotic Equipartition Property

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 ​…

Sulla Stocasticità

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…

February 29, 2024 · Reading Time: 5 minutes · By Xuanqiang Angelo Huang