Informatica
Linguaggi formali
Che cos’è un linguaggio formale, un alfabeto e una parola. I concetti di base della teoria dei linguaggi formali, spiegati confrontandoli con il linguaggio comune e con esempi.
Automi a stati finiti
L’automa a stati finiti come modello di calcolo con stati e transizioni. Definizione, diagramma degli stati, formalizzazione del calcolo ed esempi di parole accettate.
Minimizzazione degli automi
Gli stati irraggiungibili di un automa a stati finiti, cioè quelli in cui non si può arrivare dallo stato iniziale. La definizione e come eliminarli in modo sicuro dall’automa.
Proprietà di chiusura dei linguaggi regolari
I linguaggi regolari sono chiusi rispetto a unione, intersezione, concatenazione e chiusura di Kleene. Cosa significa chiusura rispetto a un’operazione e perché vale per i linguaggi regolari.
Espressioni regolari
Che cos’è un’espressione regolare e come descrive un insieme di parole. Definizione, confronto con le espressioni aritmetiche e legame con gli automi a stati finiti.
Stima del numero di valori distinti
Linear counting: come stimare il numero di valori distinti in grandi quantità di dati. Funzioni di hash, bitmap e perché l’approccio ingenuo non basta.
Filtro di Bloom: un elemento appartiene all’insieme?
Il filtro di Bloom è una struttura dati probabilistica che risponde rapidamente se un elemento appartiene a un insieme. Principio di funzionamento, funzioni di hash e usi pratici.
Cifrario di Cesare
Come funziona il cifrario di Cesare, uno dei più antichi metodi per cifrare un testo. Il principio dello scorrimento delle lettere, la generalizzazione del cifrario e uno strumento online.
Cifrario di Vigenère
Il cifrario di Vigenère usa più alfabeti e per questo resiste all’analisi delle frequenze. Come funziona la cifratura, il quadrato di Vigenère, la scelta della chiave e uno strumento online.
