Operatori regolari

Posted by On Filed under Calcolabilità e linguaggi formali

Union: A ∪ B = {x|x∈A or x∈B}

Concatenation: A ○ B = {xy | x∈A and y∈B}

Star: A* = {x1, x2, x3,...xk | k ≥ 0 and each xi∈A }

 

Inoltre si definisce per prassi ε stringa vuota (in maniera simile a quello che in SQL è NULL)

 

La prova dell'unione di A con B è data dalle seguenti cinque considerazioni:

  1. Gli stati possibili sono dati dal prodotto cartesiano degli stati A × B: Q = {(r1, r2) | r1∈A and r2∈B}
  2. Σ per ora lo consideriamo un unico dizionario per entrambe le macchine
  3. δ è una funzione definita su una coppia di stati alla volta: δ((r1, r2), a) = (δ(r1, a), δ(r2, a)). Ovviamente lo stato restituito è un elemento di Q, che a sua volta è costituito da "coppie".
  4. q0 = (q1, q2)
  5. Il risultato è un F = (F1 × Q2) ∪ (F2 × Q1)

Nota: il risultato NON è F1 × F2, perché questo rappresenterebbe l'intersezione dei due automi, e non l'unione, perché entrambi gli stati di uscita dovrebbero essere validi.

Automi finiti

Posted by On Filed under Calcolabilità e linguaggi formali
Symbol Meaning Example
Q finite set called the States sciacquo, carico, centrifuga, scarico, lavaggio
Σ finite state called Alphabet on, off, error
δ:QxΣ→Q transition function carico x on → lavaggio
q0∈Q start state scarico
F⊆Q Set of accepted states scarico finale

Un automa a stati finiti può accettare o non accettare una serie ordinata di valori del dizionario.
Dato un entrypoint (quello definito come q0), se al termine della serie di valori sono arrivato a un elemento Q appartenente a F, allora la serie è valida ed è accettata dall'algoritmo, altrimenti no.

Per esempio, questo:

è un automa descrivibile come: ({q1, q2}, {0,1}, δ, q1, q2})

dove δ è definito come

0 1
q1 q1 q2
q2 q1 q2

in questo automa, la sequenza 100 non è valida, perché termina su un elemento che non è uno stato accettato (cioè non appartiene a F).

1101 invece termina in q2, che appartiene a F. Quindi 1101 è una sequenza accettata.

Il significato dell'automa - non sempre così facile da comprendere - è che le uniche stringhe accettate sono quelle che terminano con 1.

L(M) = {w | w ends in a 1}

Operatori di logica booleana (e codifica HTML)

Posted by On Filed under Calcolabilità e linguaggi formali

I simboli principali sono:

Simbolo Codice html Significato
⇒ ⇒ Implica. Se la parte sinistra è vera, allora è vera anche la parte destra
⇔
↔		 ⇔
↔		 Se e solo se (SSe). Se la parte sinistra è vera, allora è vera anche la parte destra e viceversa.

a b a∧b
V V V
V F F
F V F
F F V
¬ ¬ Negazione (operatore unario)
∧ ∧ And: la proposizione è vera solo se sono veri entrambi i termini

a b a∧b
V V V
V F F
F V F
F F F
∨ ∨ Or: la proposizione è vera se è vero almeno uno dei termini

a b a∧b
V V V
V F V
F V V
F F F
⊕ ⊕ Or esclusivo: la proposizione è vera se i due termini sono differenti. è complementare a SSe

a b a∧b
V V F
V F V
F V V
F F F

Le doverose premesse

Posted by On Filed under Calcolabilità e linguaggi formali

Lo studio della "teoria della computazione", o come viene chiamata all'UniVe, Calcolabilità e Linguaggi Formali, riguarda tre argomenti:

  • Complessità
  • Calcolabilità
  • Automi

La complessità indaga i costi di esecuzione degli algoritmi, in particolare li suddivide in classi, le cui principali sono polinomiale ed esponenziale.

La calcolabilità riguarda quali problemi siano risolvibili da un computer: per esempio, se risolvi un problema la risposta è che si può, ma se per ora non riesci non puoi sapere se il motivo è che non hai elaborato abbastanza oppure se è proprio interminabile.

Gli automi definiscono quali sono le caratteristiche di una macchina in grado di calcolare.

 

Punti di attenzione per l'esame

Posted by On Filed under Probabilità & statistica, R

Apici di R

Come caratteri di markdown, R usa gli apici "storti", che si ottengono con alt+96 oppure facendo copia e incolla da qui:

```{r}
```

Installazione pacchetti

A causa di un "bug" tra R e antivirus, il timeout di R per l'installazione di pacchetti nella cartella temporanea non è sufficiente.
Per questo, va eseguita la seguente istruzione:

trace(utils:::unpackPkgZip, quote(Sys.sleep(2)), at = which(grepl("Sys.sleep", body(utils:::unpackPkgZip), fixed = TRUE)))

Il testo completo del suggerimento.

I found that the problem indeed is the antivirus "real time file system protection". I do the following to fix the problem:
trace(utils:::unpackPkgZip, edit=TRUE)
I edit line 140 (line 142 in R 3.4.4):
Sys.sleep(0.5)
to:
Sys.sleep(2)
I seems like the antivirus stalls the creation of the package tmp dir. After changing it to 2 seconds the error is gone.
EDIT: to do this programmatically execute
trace(utils:::unpackPkgZip, quote(Sys.sleep(2)), at = which(grepl("Sys.sleep", body(utils:::unpackPkgZip), fixed = TRUE)))
(credits @DavidArenburg)

Librerie usate

Le librerie usate sono sei, e si possono installare e includere con le seguenti istruzioni:

install.packages(c("tigerstats", "MASS", "labstatR", "matrixcalc", "mvtnorm", "mnormt"))
library(tigerstats)
library(mnormt)
library(mvtnorm)
library(matrixcalc)
library(labstatR)
library(MASS)

Markov

In due compiti su tre ha dato come primo esercizio una catena di Markov. La so, quindi se la trovo devo puntare su quella per ottenere tutti e 10 i punti.

Controllare se c'è una catena di Markov e iniziare da lì.

Gli esercizi chiedono di:

  1. costruire una matrice di probabilità
  2. tramite l'operatore %*% si possono calcolare le matrici dei passi successivi
  3. simulare una catena (ciclo while e vettore di risultati, uso di sample per probabilità specificate esplicitamente)
  4. plot della catena
  5. simulazione di n traiettorie per determinare media, varianza... (non serve il vettore). Il valore iniziale deve essere incluso dentro al for esterno

Esercizi obbligatori

Da questa sessione sono marcati come obbligatori alcuni esercizi. INIZIA DA QUELLI!!!

Normale

  1. ATTENZIONE: nel testo può essere specificata la Scarto Quadratico Medio (SD, Standard Deviation) oppure la Varianza. Molta attenzione, perché ai comandi dnorm, pnorm, qnorm e rnorm va passato lo Scarto Quadratico Medio, mentre se il dato è la varianza ne va passata la radice quadrata:
    SD = SQM/SD oppure Sqrt(Var)
  2. Se si chiede di reiterare la normale su più di un caso (es. presi 5 elementi con distribuzione normale...), la SD va divisa per la radice quadrata del numero di elementi.
  3. Se si chiede, dati una media, un valore a campione e il suo percentile, di trovare la SD, si fa la differenza tra la media e il valore e si divide per qnorm(percentile). Se chiede la Varianza, elevare questo valore al quadrato

Variabili

Quando nel primo punto di un esercizio chiede di calcolare una variabile, probabilmente la userà nei punti successivi, quindi vale la pena di salvarla.

Attenzione che in qualche caso NON usa gli stessi parametri in tutto l'esercizio (es. cambia la SD).

Esercizi con distribuzioni diverse

Può dare esercizi in cui sono presenti due elementi con distribuzioni diverse, per esempio uno normale con probabilità 55% e uno poisson con probabilità 45%.

Chiede sempre:

  1. Un esempio di distribuzione A
  2. Un esempio di distribuzione B
  3. Un esempio di distribuzione congiunta (es. A*0.55 + B*0.45)
  4. Dato un evento con una certa probabilità (punto 3), determinare quale probabilità c'è che sia di A. In questo caso la probabilità P(A|cong) = A*0.55 / cong

Vettori (R)

Posted by On Filed under R

Per creare un vettore in R si può:

  1. definire un intervallo numerico, per esempio 
    1:5

    rappresenta un vettore di numeri da 1 a 5

  2. usare c(), con questo comando è possibile creare vettori di oggetti di qualunque tipo. Per esempio, 
    c("Marco", "Franco", "Gino")
  3. usare seq(). il vantaggio è che è possibile determinare l'intervallo tra i numeri. Per esempio, 
    seq(1, 3, 0.1)

    crea un vettore di 30 numeri 1.0, 1.1, 1.2,..., 2.9, 3.0

  4. usare rep(). Rep permette di ripetere tante volte i numeri o i caratteri passati come primo argomento. Per esempio, 
    rep(1:3, 4)

    restituisce i numeri da 1 a 3 ripetuti per 4 volte: 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3

Per concatenare dei vettori è possibile usare di nuovo il comando c(). Per esempio

a <- c(1, 2, 3)
b <- c(4, 5, 6)
c(a, b)
[1] 1, 2, 3, 4, 5, 6

Per filtrare il contenuto di un array, è possibile usare una condizione tra parentesi quadre:

c <- c(a, b)
c[c < 3]
[1] 1, 2, 1, 2, 1, 2, 1, 2

Per raggruppare gli elementi di un vettore, è possibile usare cut(). Questo è comodo soprattutto se si vuole rappresentare la densità di numeri reali:

cut(rnorm(1000), breaks = 20)

Questo comando suddivide i 1000 numeri casuali (basati su una distribuzione normale) in 20 blocchi calcolati automaticamente in base al valore minimo e al massimo.
Il numero è sostituito con un'etichetta che indica a quale dei 20 gruppi appartiene.
È usato spesso con table(), che restituisce un doppio vettore (un vettore di dimensione 2x20, in questo caso) con le etichette e il conteggio degli elementi.

plot(table(cut(rnorm(1000), breaks = 20)), type="s")

Per creare una matrice è possibile usare il comando matrix(), a cui vanno passati un vettore e il numero di righe e di colonne. Se gli elementi sono passati in ordine di lettura, è possibile specificare l'opzione byrow = TRUE.

matrix(c(-5:5, dnorm(-5:5)), 2, 11, byrow = TRUE)

Questo comando crea una matrice 2x11 con i numeri interi da -5 a +5 e i corrispondenti valori di una distribuzione normale standard.

Lo stesso risultato si poteva ottenere con rbind(), che prende due vettori della stessa dimensione - pena un alert - e ne fa un vettore bidimensionale.

rbind(-5:5, dnorm(-5:5))

Se avessi desiderato una matrice con due colonne e 11 righe, avrei dovuto usare

matrix(c(-5:5, dnorm(-5:5)), 11, 2)

oppure

cbind(-5:5, dnorm(-5:5))

cbind al posto di rbind