Concetti AI Artificial Intelligence

AI – ARTIFICIAL INTELLIGENCE A.A. 18/19 ~ Piffari Michele Pre requisiti ▪ Teoria della complessità computazionale Vedi anche qui. Si tratta di andare a studiare qual è il numero di risorse di calcolo minime (tempo di calcolo e memoria) per andare a risolvere un certo problema. In base a quella che è la complessità e/o l’efficienza dell’algoritmo migliore che riesce a risolvere una certa classe di problemi, si tende a classificare tali algoritmi in differenti classi di complessità. Le classi più “note” sono: o P: nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità. Contiene tutti i problemi decisionali che possono essere risolti da una macchina di Turing deterministica usando una quantità polinomiale di tempo di computazione, o tempo polinomiale. o NP: la classe di problemi NP comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale. La classe NP prende il suo nome dall'abbreviazione di Nondeterministic Polynomial Time. Si tratta quindi di problemi per cui un algoritmo può ipotizzare una soluzione, e poi può verificare questa ipotesi (verifica la correttezza della soluzione, non è che la computa) in un tempo polinomiale. o Big-O notation: la notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il comportamento di una funzione per argomenti elevati in modo semplice ma rigoroso, al fine di poter confrontare il comportamento di più funzioni fra loro. Più precisamente, è usata per descrivere un limite asintotico superiore per la magnitudine di una funzione rispetto ad un'altra, che solitamente ha una forma più semplice. Ha due aree principali di applicazione: in matematica, è solitamente usata per caratterizzare il resto del troncamento di una serie infinita, in particolare di una serie asintotica, mentre in informatica risulta utile nell'analisi della complessità degli algoritmi. La complessità temporale di un algoritmo è espressa comunemente usando la notazione Ogrande, che esclude i coefficienti e i termini di ordine inferiore. Quando è espressa in questo modo, si dice che la complessità temporale è descritta asintoticamente, ossia, quando la dimensione degli input va a infinito. Ad esempio, se il tempo richiesto da un algoritmo su tutti gli input di dimensione n è al massimo 5n3 + 3n, la complessità temporale asintotica è O(n3). Piffari Michele – AI – 18/19 1 Tempo polinomiale Si dice che un algoritmo è in tempo polinomiale se il suo tempo di esecuzione è limitato superiormente da un'espressione polinomiale nella dimensione dell'input per l'algoritmo, cioè, T(n) = O(nk) per una qualche costante k. I problemi per i quali esiste un algoritmo deterministico in tempo polinomiale appartengono alla classe di complessità