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…
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…
Introduzione # L’importanza del topic # Gli algoritmi di ordinamento sono molto di base per la comprensione dell'ampio raggio degli algoritmi. Utilizzano l'analisi, introducono tecniche di risoluzione dei problemi computazionali come greedy, divide et impera e simile. Permettono…
1.1 Il cammino minimo # 1.1.1 Definizione e caratteristiche # 1.1.2 Costi negativi # Sono cose molto brutte 1.1.3 Cammino minimo semplice # Costruzione di cammini minimi # 1.2 Vertici # 1.2.1 definizione distanza fra due vertici # Costo del cammino minimo che li connette…
Rappresentazione e terminologia # Operazioni importanti Definizione di grafo # È un insieme di nodi e di archi. (prendili da insiemi corretti) Metodi di rappresentazione # Liste di incidenza # In pratica numero tutti gli archi e storo il valore dell'arco incidente per ogni nodo.…
In questa nota andiamo a parlare in modo sommario (si impara probabilmente molto meglio con la pratica) di generali tipologie di approcci che esistono per affrontare problemi di tipo algoritmico. Divide et impera # Introduzione # Abbiamo già visto L'utilizzo di questa tecnica…
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…
Introduzione alla notazione asintotica # Cercare di definire il tempo impiegato da una funzione per essere eseguita in termini di DIMENSIONE dell'input . **(il numero di bit a livello basso basso) Ma abbiamo il problema di misura, in quanto dobbiamo considerare delle variabili…
0 Introduzione # 0.1 L’algoritmo # Vogliamo cercare di creare algoritmi, ovvero soluzioni a problemi computazionali che non dipendono dal linguaggio di programmazione. 0.1.1 Definizione # Procedura per risolvere un problema in un numero finito di passi (quindi un algoritmo deve…
Iterazione # Questo metodo semplicemente consiste di calcolare tutte le operazioni e scriverlo con una notazione asintotica. slide Sostituzione (induzione) # slide Analisi della relazione di ricorrenza di fibonacci Si può dimostrare utilizzando l'induzione che una relazione di…