🗄Algorithms-and-Data-Structures

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

3.1 Introduzione 3.1.1 Cosa sono Le strutture di dati si interessano solamente di come memorizzare i dati, non necessariamente va a memorizzare un tipo di dato concreto. Quindi + sul come - sul cosa. 3.1.2 Prototipo e implementazione Avevamo introdotto la differenza fra algoritmo e programma all’inizio del corso, andiamo ora a definire la differenza fra prototipo e implementazione: Prototipo: va a fare una descrizione dei metodi che deve avere una determinata struttura di dati....

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

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

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