Analisi e Progettazione di Algoritmi - Vocabolario

Flashcard di vocabolario basate sulle note del corso di Analisi e Progettazione di Algoritmi, per il ripasso dei concetti fondamentali relativi ad analisi della complessità, programmazione dinamica, algoritmi golosi, algoritmi su grafi e teoria della NP-completezza.

Notazione $O(f(n))$

Insieme delle funzioni $g(n)$ per cui esistono due costanti $c > 0$ e $n_0 \ge 0$ tali che $g(n) \le c \cdot f(n)$ per ogni $n \ge n_0$.

Notazione $\Omega(f(n))$

Insieme delle funzioni $g(n)$ per cui esistono due costanti $c > 0$ e $n_0 \ge 0$ tali che $g(n) \ge c \cdot f(n)$ per ogni $n \ge n_0$.

Notazione $\Theta(f(n))$

Insieme delle funzioni $g(n)$ per cui esistono tre costanti $c_1, c_2 > 0$ e $n_0 \ge 0$ tali che $c_1 \cdot f(n) \le g(n) \le c_2 \cdot f(n)$ per ogni $n \ge n_0$.

Analisi Ammortizzata

Tecnica di analisi che misura il costo medio per operazione su una sequenza di operazioni nel caso peggiore, distribuendo il costo di operazioni rare e costose su molte operazioni economiche.

Master Method

Teorema per risolvere relazioni di ricorrenza della forma $T(n) = a \cdot T(\lceil n/b \rceil) + t(n)$ per $a \ge 1$ e $b > 1$, determinando la complessità in base al confronto tra $t(n)$ e $n^c$ con $c = \log_b a$.

Invariante di Ciclo

Condizione logica che deve valere all'inizio del ciclo e rimanere vera dopo ogni iterazione del corpo del ciclo, utilizzata per dimostrare la correttezza formale degli algoritmi iterativi.

Programmazione Dinamica

Tecnica di progettazione di algoritmi bottom-up che risolve i problemi combinando le soluzioni di sottoproblemi più piccoli, memorizzandole in una struttura dati per evitare di ricalcolare sottoproblemi ripetuti.

Triangolo di Pascal-Tartaglia

Rappresentazione tabellare usata nella programmazione dinamica per calcolare i coefficienti binomiali con complessità temporale $O(n^2)$.

Tabella di Programmazione Dinamica per LCS

Matrice di dimensione $(m+1) \times (n+1)$ usata per memorizzare le lunghezze delle più lunghe sottosequenze comuni di prefissi e ricostruire la soluzione ottima risalendo i riferimenti memorizzati.

Sottostruttura Ottima

Proprietà di un problema di ottimizzazione per cui la soluzione ottima globale contiene al suo interno le soluzioni ottime dei sottoproblemi che la compongono.

Algoritmo Goloso (Greedy)

Tecnica di progettazione di algoritmi che costruisce la soluzione in modo incrementale compiendo a ogni passo la scelta localmente ottima.

Codice Prefisso

Insieme di codici binari a lunghezza variabile in cui nessun codice è il prefisso di un altro, garantendo la decodificabilità univoca e immediata.

Albero del Codice di Huffman

Albero binario costruito con approccio goloso bottom-up che rappresenta un codice prefisso ottimale a lunghezza variabile basato sulle frequenze dei simboli.

Guscio Convesso (Convex Hull)

Il più piccolo poligono convesso che racchiude un insieme finito $P$ di $n$ punti nel piano.

Algoritmo di Jarvis (Gift Wrapping)

Algoritmo goloso per il calcolo del guscio convesso che seleziona sequenzialmente i vertici del poligono con complessità temporale output-sensitive $O(n \cdot k)$, dove $k$ è il numero di vertici del guscio.

Grafo Orientato Aciclico (DAG)

Grafo orientato privo di cicli orientati, nel quale la relazione di raggiungibilità definisce un ordine parziale sui vertici.

Ordinamento Topologico

Ordinamento totale $<$ dei vertici di un grafo orientato aciclico (DAG) tale che per ogni arco $(u, v)$ si abbia $u < v$.

Componente Fortemente Connessa

Sottografo massimale di un grafo orientato in cui ogni coppia di vertici $u$ e $v$ è mutuamente raggiungibile.

Albero di Ricoprimento Minimo (MST)

Sottografo connesso e aciclico di un grafo non orientato e pesato che contiene tutti i nodi del grafo e minimizza la somma dei pesi degli archi.

Algoritmo di Prim

Algoritmo goloso che costruisce un albero di ricoprimento minimo espandendo un singolo albero a partire da un nodo radice, aggiungendo a ogni passo l'arco di costo minimo connesso alla frontiera.

Algoritmo di Kruskal

Algoritmo goloso per il calcolo dell'albero di ricoprimento minimo che esamina tutti gli archi in ordine crescente di peso e li aggiunge alla soluzione se uniscono due alberi distinti di una foresta.

Struttura Dati Union-Find

Struttura dati che gestisce una collezione di insiemi disgiunti mediante l'uso di alberi, supportando le operazioni makeSet, union e find ottimizzate da euritiche come union-by-size, union-by-rank e path compression.

Algoritmo di Dijkstra

Algoritmo goloso per la ricerca dei cammini minimi da una sorgente singola in un grafo pesato con pesi non negativi, basato sull'uso di una coda di priorità.

Algoritmo di Floyd-Warshall

Algoritmo di programmazione dinamica che calcola le distanze dei cammini minimi tra tutte le coppie di nodi in un grafo orientato pesato privo di cicli di costo negativo, con complessità temporale $O(n^3)$.

Classe P

Classe dei problemi di decisione che possono essere risolti da un algoritmo deterministico in tempo polinomiale $O(n^k)$ per una costante $k$.

Classe NP

Classe dei problemi di decisione verificabili in tempo polinomiale da un algoritmo deterministico di verifica dato un opportuno certificato di dimensione polinomiale.

Riduzione Polinomiale ($P_1 \le_P P_2$)

Funzione $f$ calcolabile in tempo polinomiale che trasforma ogni istanza $x$ di $P_1$ in un'istanza $f(x)$ di $P_2$ tale che $x \in P_1$ se e solo se $f(x) \in P_2$.

Problema NP-Completo

Problema $P$ appartenente alla classe NP che risulta anche NP-arduo, ovvero a cui ogni altro problema in NP è riducibile in tempo polinomiale.