Notes

How Bloom Filters Work A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is possibly in a set or definitely not in a set. It allows for false positives but never false negatives. One example of application is the membership query in Wide Column Storage, HBase. They make document lookup faster by completely skipping some HFiles. Structure and Initialization A Bloom filter consists of: A bit array of size $m$, initialized to all 0s. $k$ independent hash functions, each mapping an input element to one of the $m$ positions in the bit array. Common operations Insertion of an Element To insert an element $x$: ...

Gestione delle risorse Introduzione Definizione classe, fungibilità Classe di risorse sono un insieme di risorse fra loro equivalenti (nel senso che uno può rimpiazzare l’uso dell’altro), anche detti fungibili. Statico o dinamico Anche in economia ci sono tali definizioni! Queste risorse possono essere allocate staticamente o dinamicamente, in modo simile a quanto abbiamo detto in Gestione della memoria. Statico quando già in fase di compilazione del processo, o di avviamento del processo gli dò la memoria, e quella sarà per tutti il tempo della sua vita. ...

Merkle Trees: A Fundamental Structure in Cryptography Merkle trees, introduced by Ralph Merkle in 1979, are a pivotal data structure in cryptographic systems. These binary hash trees enable efficient and secure verification of data integrity within distributed systems. Their design capitalizes on hash functions to reduce computational overhead, making them indispensable in blockchain and peer-to-peer networks. What are Merkle Trees? Structure and Construction A Merkle tree is a rooted binary tree where: ...

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 fare bene queste singole operazioni Si vedrà che l’array modificato è il modo migliore per avere questo hash, solo generalizzando un modo per indicizzarlo che non saranno numeri (indici). ...

Most of times the pattern of proving and verifying it is like this $prove \to verify$, that is: there is an entity that generates the solution, andPo then another that tries to verify it. But more expressive algorithms could be possible if there is interaction between the two entities, ones that try to prove it, and others try to verify it. From some point of view, this is similar from what AlphaGo does when searching, there is a part that guides the search, another that actually searches for it. Or the modern alpha geometry in modern times. ...

In order to define the concept of probability formally, we need first to introduce some mathematical concepts. La probabilità Termini Esito ed esperimenti aleatorio L’evento è quello che accade, mentre un esperimento aleatorio qualcosa di cui vogliamo andare a misurare la probabilità diciamo. Esperimento aleatorio: esperimento di cui non conosciamo il risultato con certezza. Esito: risultato dell’esperimento aleatorio Spazio campionario ed evento Spazio campionatorio Lo spazio campionatorio è l’insieme di tutti gli stati possibili per una certa cosa da misurare (ossia di un esperimento aleatorio), gli stati sono talvolta anche chiamati sample points oppure outcomes in modo più semplice. ...

Questo documento è totalmente concentrato sull’analisi del problema della selezione del k-esimo elemento. 7.1 Introduzione al problema Dato un array di elementi vogliamo cercare di trovare un modo efficiente per selezionare il k-esimo elemento, ossia un elemento che sia maggiore di k-1 elementi 7.1.1 Note sull’utilizzo Questo algoritmo è utile per esempio per sapere cosa displayare in una pagina di ricerca, perché per esempio posso avere blocchi di tanta roba 140k, mentre ovviamente posso selezionare solamente un blocco ristretto. ...

Con questo documento iniziamo a parlare di logica, alcuni paradossi famosi all’interno di questo mondo. Paradossi Metalinguistici Antinomie e Paradossi Antinomia Definizione di antinomia è un ragionamento corretto da cui deriva una conclusione errata, probabilmente è l’insieme o campo in cui stiamo operando ad essere errato e bisogna cercare di ridefinirlo in modo più corretto, in quanto le premesse erano accettabili Paradosso Paradosso quando il ragionamento corretto va contro l’intuizione, come il paradosso dei gemelli in fisica e simili. premesse erano accettabili ...

Coppia ordinata Definizione di Kuratowsky Una coppia ordinata è definita dall’insieme $$ \langle X, Y \rangle = \{X, \{X, Y\}\} $$È quindi chiaro che due coppie ordinate sono uguali fra di loro nel caso in cui gli elementi sono uguali ma anche la loro posizione sono uguali Teorema caratterizzazione delle coppie Definizione di Wiener $$ (X,Y) := \{\{\{X\}, \varnothing\}, \{\{Y\}\}\} $$Definizione di Hausdorff $$ (X,Y) := \{\{X, 1\}, \{X,2\}\} $$Proprietà fondamentale coppie ordinate Due coppie ordinate si dicono uguali se e solo se il primo elemento dei due sono uguali e la stessa cosa per il secondo ...

I processi di Poisson sono dei processi stocastici, interpretabili come collezione indicizzata dal tempo di variabili aleatorie. Esempi semplici sono una uniforme, altri più complessi potrebbe essere una catena di Markov (see Markov Chains) (utile per modellare cammini randomici) o quella di Poisson spiegata qui. Introduzione ai processi di Poisson Arrival processes Sia una sequenza di variabili aleatorie $0 < S_{1} < S_{2} < \dots$ (il fatto che sia positivo significa che per ogni elemento del dominio vale che quell’elemento è <, non so se mi sono spiegato.) ...