🗄Algorithms-and-Data-Structures

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 che siano indipendenti rispetto alla macchina. Caratteristiche della notazione Vogliamo considerare una notazione asintotica (che guarda quanto fa il comportamento verso l’infinito) ### Accesso di memoria Ogni operazione in un processore moderno ha in generale un numero di accessi in memoria constante (solitamente abbiamo sempre un numero fissato di operandi possibile, questo significa che se un certo algoritmo ha una certa complessità, resta di questa complessità anche tenendo in considerazione le operazioni di accesso di memoria). Questo discorso non tiene più se teniamo in considerazione numeri a precisione infinita, che possono avere un numero arbitrario di accessi in memoria per poter essere computato. ...

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

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

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

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. Diventa una tabella con una parte i nodi e l’altra gli archi. Avrò dei valori -1 e 1 che marcano partenza e arrivo. La cosa carina di questo metodo è che può essere generalizzata anche per Ipergrafi, in cui gli archi possono avere più di una partenza o arrivo. Solitamente è memorizzato come una lista, quindi esattamente nodo partenza e arrivo per ogni edge. ...

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 per quick e merge sort in Algoritmi di ordinamento Questa tecnica si focalizza in tre passi fondamentali: Dividere il problema in sotto-problemi Risolvere il sotto-problema Mergiare le soluzioni di questi sotto-problemi. Questa è più una tecnica che si impara di più con la pratica, andremo a fare un problema che utilizza questa tecnica ...

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 caratteristica principale dell’albero di ricerca è una condizione sulle chiavi (che hanno i figli). Infatti questo albero binario di ricerca si può vedere come una implementazione della struttura astratta del dizionario. (che ricordiamo, è un struttura in cui a ogni nodo sono presenti due valori, una chiave (tute differenti) e un dato, e sono definite tre operazioni principali, possiamo vederla come interfaccia). ...

6.1 Introduzione 6.1.1 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 un primo uso di astrazioni e l’analisi di sottoproblemi. 6.1.2 Il problema Il problema è trovare una permutazione di un insieme di numeri iniziali tale per cui tale insieme di numeri si ordinato: ...

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 Condizione di bellman Albero dei cammini minimi Rilassamento Definizione Si va a vedere dove non funziona la disuguaglianza triangolare, se localmente non funziona ovvero se per esempio succede $D_{xu} + \omega(u,y) < D_{xy}$ per qualche vertice all’interno del grafo, so di per certo che la distanza $D_{xy}$ non è una distanza, quindi possiamo riassegnarla in modo che verifichi la disuguaglianza ...