🗄Algorithms-and-Data-Structures

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

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

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

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