Glossario Algoritmi e Strutture dati

Albero binario di ricerca auto-bilanciato che, dopo ogni inserimento o rimozione, si riequilibra con rotazioni. Garantisce operazioni in tempo logaritmico mantenendo l'altezza controllata.

Albero binario di ricerca auto-bilanciato che usa una colorazione dei nodi per limitare lo sbilanciamento. Offre un buon compromesso tra velocità di bilanciamento e di modifica, usato in molte librerie standard.

Algoritmo di ricerca del cammino minimo che guida l'esplorazione con una stima euristica della distanza dall'obiettivo. Combinando costo reale e stima, trova percorsi ottimali in modo efficiente, molto usato nei videogiochi.

Algoritmo che trova i cammini minimi da un nodo a tutti gli altri in un grafo con pesi non negativi. Espande progressivamente il nodo più vicino non ancora fissato, ed è centrale nel calcolo di percorsi ottimali.

Strategia che a ogni passo compie la scelta localmente migliore, sperando di ottenere una soluzione complessivamente ottima. È semplice e veloce, ma non garantisce l'ottimo per tutti i problemi.

Struttura ad albero bilanciato con nodi capaci di contenere molte chiavi e figli, progettata per minimizzare gli accessi a memoria secondaria. Mantiene i dati ordinati garantendo operazioni logaritmiche, ed è alla base di indici di database e file system.

Tecnica che costruisce una soluzione per tentativi, tornando indietro appena una scelta si rivela senza uscita. È usata per problemi combinatori come rompicapi, percorsi e configurazioni valide.

Algoritmo per i cammini minimi da una sorgente che, a differenza di Dijkstra, gestisce anche archi con peso negativo. Rileva inoltre la presenza di cicli negativi, a costo di una complessità maggiore.

Struttura dati probabilistica che verifica in modo molto compatto se un elemento appartiene a un insieme. Può dare falsi positivi ma mai falsi negativi, utile per filtrare rapidamente prima di controlli costosi.

Tecnica per problemi di ottimizzazione che esplora le soluzioni ad albero, scartando interi rami che non possono migliorare il risultato. Riduce lo spazio da esaminare grazie a stime dei limiti.

Algoritmo di visita che esplora un grafo per livelli, partendo dalla sorgente e allargandosi ai vicini via via più lontani. Trova il cammino con meno archi ed è la base di molti algoritmi su grafi non pesati.

Algoritmo di ordinamento elementare che scorre ripetutamente la lista scambiando gli elementi adiacenti fuori posto. È semplice ma inefficiente sui grandi insiemi, con complessità quadratica; utile soprattutto a fini didattici.

Struttura dati a dimensione fissa in cui la fine si ricongiunge all'inizio, riutilizzando lo spazio in modo ciclico. È usata per flussi continui, code di eventi e comunicazione tra produttori e consumatori.

Insieme dei problemi decisionali risolvibili in tempo polinomiale rispetto alla dimensione dell'input. Rappresenta, in modo semplificato, i problemi considerati trattabili in modo efficiente.

Struttura dati in cui ogni elemento ha una priorità e viene estratto sempre quello più prioritario, non il più vecchio. È usata in scheduling, algoritmi su grafi e ovunque serva servire prima gli elementi più importanti.

Costo medio di un'operazione valutato su una lunga sequenza, anche quando singole operazioni sono occasionalmente costose. Spiega perché strutture come gli array dinamici restano efficienti nel complesso.

Misura di quanta memoria aggiuntiva un algoritmo richiede in funzione della dimensione dell'input. È spesso in compromesso con la complessità temporale: risparmiare tempo può costare spazio e viceversa.

Misura di come il tempo di esecuzione di un algoritmo cresce al crescere della dimensione dell'input. Espressa in notazione asintotica, permette di confrontare gli algoritmi indipendentemente dall'hardware.

Algoritmo che ordina contando le occorrenze di ciascun valore, adatto quando i dati appartengono a un intervallo ristretto di interi. Evita i confronti e raggiunge complessità lineare in quelle condizioni.

Grafo diretto privo di cicli, in cui non esiste alcun percorso che riporti a un nodo di partenza seguendo il verso degli archi. La sua struttura consente un ordinamento topologico ed è usata per modellare dipendenze, pianificazioni e flussi di elaborazione.

Algoritmo di visita di grafi e alberi che esplora un ramo fino in fondo prima di tornare indietro e proseguire. È usato per attraversamenti, rilevamento di cicli e ordinamenti topologici.

Coda a doppia estremità che consente di inserire e rimuovere elementi sia in testa sia in coda in modo efficiente. Generalizza pila e coda, adattandosi a molti schemi di elaborazione dei dati.

Tecnica che scompone un problema in sottoproblemi più piccoli dello stesso tipo, li risolve e ne combina le soluzioni. È alla base di algoritmi efficienti come il merge sort e la ricerca binaria.

Tecnica che usa due indici che scorrono una struttura, spesso da estremi opposti o a velocità diverse, per risolvere problemi in modo efficiente. È comune su array e liste ordinate.

Struttura dati compatta, detta anche albero indicizzato binario, che calcola somme cumulative e aggiornamenti in tempo logaritmico. È più semplice e leggera di un segment tree per le somme su prefissi.

Tecnica che mantiene una finestra mobile su una sequenza, aggiornandola in modo incrementale invece di ricalcolare da capo. Risolve efficientemente problemi su sottosequenze contigue.

Algoritmo che calcola i cammini minimi tra tutte le coppie di nodi di un grafo pesato. Procede considerando via via nodi intermedi ed è adatto a grafi densi di dimensioni contenute.

Tecnica che trasforma una chiave in un indice tramite una funzione hash, per accedere ai dati quasi in tempo costante. È il fondamento delle tabelle hash e richiede di gestire le collisioni tra chiavi.

Struttura dati ad albero binario quasi completo in cui ogni nodo rispetta un ordine rispetto ai figli. Permette di ottenere in tempo logaritmico il minimo o il massimo, ed è la base delle code di priorità.

Algoritmo di ordinamento che sfrutta la struttura heap per estrarre ripetutamente l'elemento massimo o minimo. Garantisce complessità n log n e ordina sul posto, senza bisogno di memoria aggiuntiva significativa.

Algoritmo che costruisce la sequenza ordinata inserendo un elemento alla volta nella posizione corretta. È efficiente su insiemi piccoli o quasi ordinati, ma diventa lento al crescere dei dati.

Rappresentazione di un grafo in cui ogni nodo mantiene l'elenco dei nodi a cui è collegato. È efficiente in memoria per i grafi sparsi ed è la forma più comune per attraversarli.

Rappresentazione di un grafo tramite una matrice in cui ogni cella indica se due nodi sono collegati. Consente di verificare un collegamento in tempo costante, ma occupa molto spazio sui grafi sparsi.

Algoritmo di ordinamento che divide ricorsivamente la sequenza a metà, ordina le parti e le fonde ordinatamente. Ha complessità garantita di n log n ed è stabile, ma richiede memoria aggiuntiva per la fusione.

Notazione asintotica che descrive un limite inferiore alla crescita di un algoritmo, ossia il suo comportamento nel caso migliore o come minimo garantito. Complementa la più nota notazione O.

Notazione asintotica che descrive un limite stretto alla crescita di un algoritmo, valido sia come inferiore sia come superiore. Indica il tasso di crescita esatto quando i due limiti coincidono.

Proprietà dei problemi più difficili della classe NP, a cui ogni altro problema di NP può essere ricondotto. Trovare per uno solo di essi un algoritmo efficiente risolverebbe l'intera classe.

Categoria di problemi almeno tanto difficili quanto i più ardui della classe NP, senza dover appartenere a NP stessi. Per essi non si conoscono algoritmi efficienti, e spesso ci si accontenta di soluzioni approssimate.

Tecnica che risolve problemi complessi scomponendoli in sottoproblemi sovrapposti, memorizzandone i risultati per evitare ricalcoli. Applicabile quando vale il principio di ottimalità, trasforma soluzioni esponenziali in polinomiali, come nel calcolo di distanze fra stringhe.

Algoritmo di ordinamento basato sul divide et impera che sceglie un elemento pivot e partiziona l'array in valori minori e maggiori, ordinando ricorsivamente le parti. In media molto efficiente e in place, può degradare a prestazioni quadratiche con scelte sfortunate del pivot.

Algoritmo che ordina i numeri cifra per cifra, dalla meno alla più significativa, senza confronti diretti. Può superare i limiti degli algoritmi comparativi quando le chiavi hanno lunghezza limitata e nota.

Algoritmo che individua un elemento in una sequenza ordinata dimezzando ripetutamente l'intervallo di ricerca in base al confronto con l'elemento centrale. Raggiunge un costo logaritmico, molto inferiore alla scansione lineare, a patto che i dati siano già ordinati.

Algoritmo che cerca un elemento scorrendo la collezione dall'inizio finché non lo trova o la esaurisce. È semplice e non richiede dati ordinati, ma nel caso peggiore deve esaminare tutti gli elementi.

Struttura ad albero che consente interrogazioni e aggiornamenti efficienti su intervalli di un array, come somme o minimi. È usata dove servono molte query su porzioni di una sequenza che cambia nel tempo.

Algoritmo che seleziona ripetutamente l'elemento minimo dalla parte non ordinata e lo pone in coda a quella ordinata. Semplice e con pochi scambi, ha però sempre complessità quadratica indipendentemente dai dati.

Variante dell'insertion sort che confronta elementi distanti tra loro, riducendo progressivamente la distanza. Migliora le prestazioni rispetto all'inserimento semplice, con un comportamento dipendente dalla sequenza di distanze scelta.

Struttura dati ordinata che sovrappone più liste concatenate con collegamenti che saltano elementi, accelerando la ricerca. Offre prestazioni simili agli alberi bilanciati con un'implementazione più semplice.

Algoritmo di ordinamento ibrido che combina merge sort e insertion sort, ottimizzato per dati reali con parti già ordinate. È l'algoritmo predefinito in linguaggi come Python e Java per gli array di oggetti.

Struttura dati ad albero che organizza stringhe condividendo i prefissi comuni lungo i rami. Consente ricerche, inserimenti e completamenti di parole molto efficienti, usata ad esempio nei suggerimenti di testo.

Struttura dati che gestisce insiemi disgiunti, permettendo di unirli e di verificare rapidamente se due elementi appartengono allo stesso insieme. È chiave in algoritmi su grafi come la costruzione di alberi minimi.