La materia della Calcolabilità e Complessità basa il suo studio su tre aree princinpali: gli automi, la computabilità e la complessità. La teoria della complessità concentra i suoi studi nella comprensione di cosa rende alcuni problemi più difficili a livello computazionale rispetto ad altri. Per affrontare un problema computazionalmente difficile, possono essere seguite diverse strade. In alcuni casi si cerca di comprendere la natura della difficoltà e si cerca di modificare il problema in modo da renderlo risolvibile in maniera più semplice. Altre volte, invece, ci si accontenta di una soluzione non esatta. Altre volte ancora un problema può risultare di difficile risoluzione solo nel caso peggiore, mentre risulta di facile risoluzione negli altri casi. La complessità computazionale è interessata specialmente nel campo della crittografia, all'interno del quale si preferisce un problema di complessità difficile a uno facile.
La materia della Calcolabilità e Complessità basa il suo studio su tre aree princinpali: gli automi, la computabilità e la complessità. La teoria della complessità concentra i suoi studi nella comprensione di cosa rende alcuni problemi più difficili a livello computazionale rispetto ad altri. Per affrontare un problema computazionalmente difficile, possono essere seguite diverse strade. In alcuni casi si cerca di comprendere la natura della difficoltà e si cerca di modificare il problema in modo da renderlo risolvibile in maniera più semplice. Altre volte, invece, ci si accontenta di una soluzione non esatta. Altre volte ancora un problema può risultare di difficile risoluzione solo nel caso peggiore, mentre risulta di facile risoluzione negli altri casi. La complessità computazionale è interessata specialmente nel campo della crittografia, all'interno del quale si preferisce un problema di complessità difficile a uno facile.
Lo studio di queste teoria comporta conoscere alcune notazioni e terminologie a livello matematico. Iniziamo così dando una definizione di insieme, definito come un gruppo di oggetti rappresentati in maniera unitaria. Gli oggetti possono essere di qualsiasi tipo, inclusi numeri e simboli, e prendono il nome di elementi. Per descrivere un insieme si può procedere in diversi modi, il più semplice è quello di elencare i vari elementi. Per indicare l'appartenenza o la non appartenenza di un elemento all'interno di un insieme si utilizzano rispettivamente i simboli e . Gli insiemi vengono indicati con delle lettere maiuscole, inoltre quando ogni elemento di un insieme A appartiene anche ad un altro insieme B, si dice che l'insieme A è un sottoinsieme dell'insieme B, indicandolo con la seguente annotazione . Un insieme privo di elementi si indica con .
Un concetto simile a quello di un insieme è il concetto di tupla, la quale rappresenta una lista ordinata di oggetti. Una sequenza finita prende il nome di tupla. Generalmente si pospone il numero di elementi della tupla difronte al nome, definendo la notazione k-tupla. Definiamo inoltre il prodotto cartesiano come il prodotto di due insiemi, costituito da tutte le coppie il cui primo elemento appartiene all'insieme A e il secondo elemento all'insieme B. Un prodotto cartesiano, o prodotto vettoriale, viene denotato con la seguente terminologia .
Tra due o più insiemi vengono definite delle relazioni che prendono il nome di funzioni, attraverso le quali si definiscono relazioni di input e output. Una funzione ha il compito di prendere in input e di produrre un output. Una proprietà fondamentale è che a fronte dello stesso input, la funzione deve produrre lo stesso output. L'insieme degli input prende il nome di dominio, mentre l'insieme degli output prende il nome di codominio. Una rappresentazione di una funzione attraverso una tabella prende il nome di mappa.
Un altro elemento importante, che merita quindi di essere trattato, sono i grafi. Un grafo non orientato, è un insieme di punti e di linee che connettono dei punti, definiti come nodi o vertici. I nodi sono collegati tra di loro da archi. Inoltre si definisce il grado di un nodo come il numero di archi di un particolare nodo. Per comodità i nodi e gli archi vengono etichettati, il grafo risultante viene definito grafo etichettato. All'interno dello studio della complessità e calcolabilità, i grafi di maggiore rilevanza sono i grafi orientati, nei quali gli archi posseggono una direzione dettata da una freccia. Ogni nodo quindi avrà degli archi in entrata e degli archi in uscita.
Gli elementi più utilizzati all'interno delle varie teorie sono le stringhe, i linguaggi e la logica booleana. Le stringhe sono composte da sequenze di caratteri appartenenti ad un alfabeto. Un alfabeto viene definito come un insieme non vuoto di simboli. Una stringa su di alfabeto è una sequenza finita di simboli dell'alfabeto, senza nessuna separazione. Se definiamo con w una stringa su un alfabeto , definiamo lunghezza di w il numero di simboli che contiene, indicando questo valore con il simbolo . Una stringa con cardinalità pari a 0 prende il nome di stringa vuota e viene rappresentata con il simbolo di o . Inoltre un insieme di stringhe prende il nome di linguaggio.
La logica booleana è un sistema matematico costituito da operazioni che agiscono principalmente su due valori: vero o falso, i quali prendono il nome di valori booleani. Le operazioni all'interno di questo linguaggio vengono definite operazioni booleane e sono: la negazione, la disgiunzione e la congiunzione. Attraverso questi elementi possiamo intraprendere lo studio della calcolabilità e della complessità nei prossimi articoli.
Top comments (0)