L’IA si basa pesantemente su algoritmi per l’elaborazione dei dati, l’apprendimento, la presa di decisione e la risoluzione di problemi complessi.
Complessità Algoritmica e dei Problemi
Complessità Algoritmica:
Si riferisce alla quantità di risorse computazionali (principalmente tempo e spazio di memoria) necessarie per eseguire un algoritmo in funzione della dimensione dell’input. Viene espressa utilizzando la notazione asintotica (O grande) che descrive il comportamento dell’algoritmo al crescere della dimensione dell’input. Un algoritmo con complessità O(n) (lineare) scala meglio rispetto a uno con complessità O(n2) (quadratica) o O(2n) (esponenziale) all’aumentare della quantità di dati. Nell’IA, dove spesso si lavora con enormi dataset (pensiamo al machine learning o all’elaborazione del linguaggio naturale), la scelta di algoritmi con bassa complessità è vitale per garantire tempi di esecuzione ragionevoli.
“scala meglio” (scales better) significa che l’algoritmo mantiene prestazioni ragionevoli (in termini di tempo o spazio) anche quando la dimensione dell’input diventa molto grande. Un algoritmo che scala meglio vede la sua richiesta di risorse crescere più lentamente all’aumentare dell’input.
La “scalabilità peggiore” è visualizzata da una funzione il cui grafico cresce molto rapidamente sull’asse del tempo di esecuzione (y) all’aumentare della dimensione dell’input sull’asse orizzontale (x).
-
Funzione Lineare (): Il grafico è una linea retta con una pendenza costante. L’angolo di questa retta indica la costante moltiplicativa. Una pendenza maggiore significa che per ogni aumento unitario della dimensione dell’input, il tempo di esecuzione aumenta di una quantità maggiore (ma sempre in modo lineare). Tuttavia, la natura della crescita è lineare.
-
Funzione Quadratica (): Il grafico è una curva. La sua pendenza aumenta man mano che cresce. Questo riflette il fatto che il tasso di crescita del tempo di esecuzione sta accelerando.
Complessità dei Problemi:
Non si riferisce a un algoritmo specifico, ma alla difficoltà intrinseca di risolvere un determinato problema computazionale. Un problema può essere intrinsecamente difficile anche se si utilizza l’algoritmo più efficiente possibile. I problemi vengono classificati in diverse classi di complessità, come P (risolvibili in tempo polinomiale da una macchina di Turing deterministica) e NP (verificabili in tempo polinomiale da una macchina di Turing deterministica).
Tempo Polinomiale: Un problema si dice risolvibile in tempo polinomiale se esiste un algoritmo che può risolverlo e il cui tempo di esecuzione è limitato superiormente da una funzione polinomiale della dimensione dell’input. Quindi, un problema è in tempo polinomiale se esiste un algoritmo per risolverlo tale che il suo tempo di esecuzione nel caso peggiore è per qualche costante (indipendente da ).
Funzione Polinomiale : Una funzione polinomiale è una singola espressione che può contenere più termini (che sono singoli “monomi” o “potenze di con coefficienti”)
Macchina di Turing Deterministica (MTD):È un modello computazionale teorico in cui, dato uno stato e un simbolo letto, la prossima azione è univocamente determinata. È il modello di calcolo di riferimento per definire la classe di complessità P
Molti problemi importanti in IA, come la pianificazione ottima, la soddisfazione di vincoli complessi e alcuni problemi di apprendimento, sono noti per essere NP-completi o NP-hard, il che suggerisce che non si conoscono algoritmi efficienti (in tempo polinomiale) per risolverli in generale.
Risolvere in Tempo Polinomiale (Classe P):
-
Significato: Un problema decisionale (un problema la cui risposta è “sì” o “no”) appartiene alla classe P se esiste un algoritmo eseguito da una Macchina di Turing Deterministica (MTD) che è in grado di trovare la soluzione (cioè, di determinare se la risposta al problema è “sì” o “no”) in un tempo che è limitato superiormente da una funzione polinomiale della dimensione dell’input.
-
Esempio: Considera il problema di determinare se un numero intero è pari. Possiamo scrivere un semplice algoritmo (una MTD) che controlla l’ultima cifra del numero. Il tempo di esecuzione di questo algoritmo è lineare rispetto al numero di cifre (la dimensione dell’input). Quindi, il problema di verificare la parità è in P.
-
Implicazione: Se un problema è in P, significa che possiamo trovare una soluzione efficiente (in termini di tempo, almeno in teoria per grandi input) utilizzando un algoritmo “standard” (deterministico).
Verificare in Tempo Polinomiale (Classe NP):
-
Significato: Un problema decisionale appartiene alla classe NP se, data una potenziale soluzione per un’istanza del problema la cui risposta è “sì”, possiamo verificare (controllare) in tempo polinomiale (usando una MTD) se quella soluzione è effettivamente una soluzione valida.
-
Il Ruolo della soluzione : La chiave qui è la “soluzione”. Se qualcuno ci fornisce una potenziale soluzione a un problema in NP (per un’istanza la cui risposta è “sì”), possiamo usare un algoritmo deterministico (una MTD) per controllare rapidamente (in tempo polinomiale) se questa soluzione è corretta. Non abbiamo bisogno di trovare la soluzione da soli in tempo polinomiale.
-
Esempio: Considera il problema del commesso viaggiatore (TSP) nella sua versione decisionale: “Dato un insieme di città, le distanze tra loro e un certo valore , esiste un percorso che visita tutte le città esattamente una volta e ha una lunghezza totale minore o uguale a ?”.
- Verificare: Se qualcuno ci fornisce un percorso specifico (l’ordine in cui visitare le città), possiamo facilmente calcolare la lunghezza totale del percorso e verificare in tempo polinomiale (lineare rispetto al numero di città) se questa lunghezza è minore o uguale a . Questo significa che il TSP (decisionale) è in NP.
- Risolvere: Trovare il percorso più breve in assoluto sembra essere molto più difficile e tutti gli algoritmi conosciuti nel caso peggiore hanno una complessità super-polinomiale (si congettura che non esista un algoritmo polinomiale per risolverlo). Quindi, anche se possiamo verificare una soluzione velocemente, trovarla è difficile.
- Implicazione: Se un problema è in NP, significa che se qualcuno ci dà la risposta (“sì” e una prova di ciò, il certificato), possiamo facilmente convincerci che la risposta è corretta. Tuttavia, trovare quella risposta e la sua prova da soli potrebbe essere molto difficile.
La Differenza Fondamentale:
- Classe P: Possiamo trovare la soluzione in modo efficiente (tempo polinomiale).
- Classe NP: Possiamo verificare se una soluzione proposta è corretta in modo efficiente (tempo polinomiale), ma trovare la soluzione originale potrebbe essere difficile.
Implicazioni per l’IA: La consapevolezza della complessità aiuta i ricercatori e gli sviluppatori di IA a:
- Scegliere algoritmi scalabili per grandi volumi di dati.
- Comprendere i limiti teorici di ciò che può essere efficientemente calcolato.
- Concentrarsi su approcci approssimati o euristici per problemi intrinsecamente difficili.
