Notes

3.1 Successioni $$ \begin{cases} f: \mathbb{N} \to \mathbb{R} \\ n \to f(n) \\ \{a\}_{n \in \mathbb{N}} \vee a_n \end{cases} $$$$ \left\{ a \right\} _{n \in \mathbb{N}} $$3.1.1 Immagine e successione L’immagine di una successione (l’insieme dei suoi elementi) non è una successione! la successione è anche ordinata. 3.1.2 Limitazioni della successione Come per gli insiemi si può definire se l’insieme è limitato superiormente, inferiormente o entrambi, a seconda di come lo definiamo in questo modo possiamo poi farci altri ragionamenti ...

URI Sono stata LA vera invenzione di Berners Lee accennati in Storia del web. Il problema è avere un modo per identificare una risorsa in modo univoco sull’internet. Introduzione La risorsa Una risorsa è qualunque struttura che sia oggetto di scambio tra applicazioni all’interno del World Wide Web. Ora una risorsa può essere qualunque cosa, non solamente solo un file! Quindi è agnostico rispetto a contenuto oppure metodo di memorizzazione del dato, appare anche in questo ambiente importante vedere quanto siano importanti standard che permettano una comunicazione ...

Introduzione all’algebra relazionale Confronto con relazioni matematiche Le relazioni come le intendiamo in database sono leggermente diverse rispetto a quelle presenti per le relazioni matematiche: Non conta l’ordine Ci sono gli attributi Per il resto se introduciamo questo sistema per tenere conto delle astrazioni, possiamo analizzarle matematicamente, e questo ci fornisce qualche sicurezza in più diciamo. Four types of operations Set operations: union, intersection, difference Filter queries: Projecting or selecting Renaming queries: renames Join: correlare tuple di relazioni diverse Definition of tuples Le relazioni sono esattamente quelle definite in matematica, però noi aggiungiamo anche gli attributi, in modo da poter considerare l’ordine delle colonne non importante. ...

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

Questo è stato creato da 1948 Shannon in (Shannon 1948). Questa nozione è basata sulla nozione di probabilità, perché le cose rare sono più informative rispetto a qualcosa che accade spesso. Introduction to Entropy The Shannon Information Content $$ h(x = a_{i}) = \log_{2}\frac{1}{P(x = a_{i})} $$ We will see that the entropy is a weighted average of the information, so the expected information content in a distribution. Kolmogorov complexity è un modo diverso per definire la complessità. Legato è Neural Networks#Kullback-Leibler Divergence. ...

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

Indexes Trattiamo qui di alcuni metodi che sono utilizzati per costruire indici Introduction to indexes Gli indici sono una struttura di dati aggiuntiva che ci permette di ricercare più in fretta alcuni valori per le queries. In questa sezione proviamo ad approfondire in che modo possono essere costruite e gestite. Search keys Sono in breve la cosa che vogliamo andare a cercare. Solitamente sono nella forma <key, label>, che ci permette di trovare in fretta il label, che si potrebbe intendere come il valore che noi stiamo provando a cercare. ...