4         Note di teoria

4.1        Linguaggi

4.1.1            Espressioni regolari

Le espressioni regolari sono un modo di descrivere particolari stringhe di caratteri, per la precisione quelle stringhe di caratteri che sono riconoscibili da automi a stati finiti.

In genere il risultato dei raggruppamenti vanno in variabili ($1 ... in Perl)                                                      

4.1.2            Con una sola istruzione

La macchina virtuale con una sola istruzione è formata da celle contigue, nelle prime celle sono contenuti:

§         PC il Program Counter

§         R0, R1 celle di lavoro o registri

§         Input buffer dei dati di input

§         Output buffer dei dati di output

§         Uno la costante 1

§         A, B,… celle di lavoro

Seguono le istruzioni della macchina, ognuna è di tre celle C₁, C₂, C₃, l'esecuzione del programma è:

C₁ = C₁ – C₂

PC = PC – C₃ se C₁  < 0 altrimenti PC = PC + 3

4.2        Statistica

4.2.1            Test del Chi quadro (χ²)

Il test χ² è utilizzato per stimare l'affidabilità di certe ipotesi su campioni statistici. Nell'esempio di codice Fortran (v. par. 2.28 ), lo si è utilizzato per stimare la bontà di un semplice generatore di numeri pseudocasuali[1]. Nell'esempio sono stati simulati dei lanci di dado, la formula che fornisce il valore del test χ² è:

dove r è il numero dei risultati possibili, 6 nell'esempio del lancio dei dadi; n è il numero totale di lanci, n_i è il numero di volte in cui è comparsa la faccia i del dado con p_i la probabilità teorica, nel nostro caso 1/6. Esistono delle tabelle che contengono i valori limite relativi alla probabilità che le ipotesi non siano corrette; queste tabelle sono in funzione dei gradi di libertà dei risultati, nel nostro caso i gradi di libertà sono r – 1 = 5 perché, conoscendo il numero di lanci totale e i risultati relativi a 5 valori ottenuti, il sesto valore lo si può ricavare. Il valore limite del test χ² per 5 gradi di libertà, con probabilità di errore < 0,05 è 11,1.

4.3        Trattamento dei dati

4.3.1            Codici di Hamming

L'idea di base della codifica di Hamming[2], è di avere m bit di informazione più altri k bit, ognuno dei quali è la parità di un'opportuno sottoinsieme degli m bit di informazione. Per individuare se è presente un errore si calcola un numero di controllo (checking number) c a partire da k, e precisamente per ogni bit di k, se esso verifica la parità (quindi non c'e' un errore), il corrispondente bit di c vale 0, altrimenti vale 1. Se c vale 0, non ci sono errori, altrimenti c contiene un valore che, per come sono stati scelti i sottoinsiemi di bit per il calcolo della parità, indica quale bit è errato. Quindi la dimensione di k deve essere tale da contenere i numeri da 1 a m + k[3].

La determinazione dei k sottoinsiemi è immediata: il sottoinsieme β_i contiene tutti i bit nel cui numero binario la posizione i-esima è 1, ad esempio β₁ = {b₁,b₃,…,b_2n+1…} in quanto nei numeri dispari il primo bit vale sempre 1.

La tabella sottostante, relativa a 7 bit, di cui 3 di parità, esemplifica la scelta dei sottonsiemi:

Figura 38

Si supponga che un errore nei dati, sia rilevato dagli insiemi β₁ e β₃, quindi il checking number è (101)₂ = (5)₁₀, che indica nel bit b₅ il bit errato.

L'ultimo problema è quello di scegliere la posizione dei k bit di parità: si sceglieranno le posizioni il cui numero contiene un solo bit 1, cioè 1, 2, 4, …2ⁿ, … , in tal modo tutti i bit di controllo saranno indipendenti fra di loro.

Il sistema descritto permette di scoprire e correggere un errore; se ci sono due errori, il sistema corregge in modo errato (vedere nell'esempio se, per ipotesi, sono errati b₄ e b₅). Per correggere un errore o individuare la presenza di due errori, occorre aggiungere un ulteriore bit di parità su tutti i bit (parità generale). Trascurando il caso di tre o più errori, evento con probabilità molto bassa, si possono avere tre casi:

·         nessun errore: tutte le parità sono soddisfatte,

·         un solo errore: la parità generale non è soddisfatta, se il checking number è zero, l'errore è sulla parità generale, altrimenti è sul bit indicato dal checking number,

·         due errori: la parità generale è soddisfatta, il checking number è diverso da zero.

Una scelta accettabile, che bilancia ridondanza e maneggevolezza è l'utilizzo di 16 bit (due bytes), in cui 11 sono di informazione, 4 di controllo ed 1 di parità generale.

4.3.2            Crittografia con doppia chiave

Questo è un semplice sistema per criptare informazioni, lo schema di funzionamento è il seguente:

sia A il mittente e B il ricevente

1. A applica al testo una funzione, conosciuta solamente da A
2. A invio il testo criptato a B
3. B trasforma il testo con una funzione conosciuta solo da B
4. B invio il testo ad A
5. A "toglie" la sua criptazione dal testo
6. A spedisce il testo a B
7. B "toglie" la sua criptazione

La funzione da applicare deve essere facilmente invertibile, ad esempio si può rimescolare il testo secondo la formula: j = i*p mod q dove i è la posizione attuale del carattere e j la posizione che esso assumerà, p e q sono due numeri primi maggiori della lunghezza del testo, con q, per motivi pratici, pari al primo numero primo maggiore o uguale alla lunghezza del testo. Qui la chiave segreta è essenzialmente il numero p.

4.4        Logica

4.4.1            Deduzione

Nella logica la deduzione è l’operazione per cui da un insieme di premesse vere si ottiene, una conclusione vera applicando opportune regole. Si è visto che certe proposizioni, i Teoremi o Tautologie, sono sempre vere; esistono degli insiemi di teoremi, detti base assiomatica, che, con le regole di deduzione, permettono di dedurre tutti e soli i teoremi. Una delle regole di deduzione si basa sull’operatore implica: la formula (α > β) può essere letta: se (è vero) α allora (è vero) β. La frase, comprese le parti fra parentesi, rappresenta il modo comune di intendere l’operatore implica; in realtà nella logica la formula risulta vera anche quando α è falso e β indifferentemente vero o falso. Di fatto questi due casi non hanno quasi importanza pratica[4].

La seconda regola permette di sostituire in una formula tutte le occorrenze di una variabile proposizionale con un teorema. Per essere più formali sarà indicato come sistema PM[5] l'insieme di assiomi e regole che permettono la deduzione:

Base assiomatica

A1.                                             (p v p) > p

A2.                                             p > (p v q)

A3.                                             (p v q) > (q v p)

A4.                                             (q > r) > ((p v q) > (p v r))

Regole

TR1.     Regola di sostituzione: é possibile sostituire in una formula tutte le occorrenze di una variabile proposizionale con un teorema.

TR2.     Modus ponens (MP) o separazione: se α è vera e (α > β) è vera, allora β è vera.

Dato un insieme di formule e variabili proposizionali Φ ={α₁,α₂,…a₁,a₂,… }, in cui ogni componente di Φ è vera per ipotesi[6], diciamo che β è una deduzione, se β  è deducibile da Φ perché o è una formula o è una variabile proposizionale appartenente a Φ, o è ricavabile applicando le regole.

Un semplice esempio è:

Φ = {"piove" , "piove > strada bagnata"}

β = "strada bagnata" 

Un esempio un po' più complesso è il seguente, in cui occorre verificare se la variabile proposizionale b è derivabile dall'insieme Φ:

1.       a > b

2.       c > b

3.       a v c

I passi successivi mostrano la deduzione di b, con l'indicazione, a destra, dell'assioma o delle formule implicate nel Modus Ponens:

4.       (a > b) > ((c v a) > (c v b)                   A4

5.       ((c v a) > (c v b)                                 MP 1, 4

6.       (c v b)                                                 MP 3, 5

7.       (c v b) > b                                           A1

8.       b                                                         MP 6, 7

La procedura di deduzione può essere automatizzata, ma al crescere delle formule coinvolte, il tempo necessario a trovare la soluzione cresce rapidamente. La procedura può essere migliorata con accorgimenti euristici, analoghi a quelli utilizzati da un uomo che voglia ottenere la soluzione. Una procedura, facilmente implementabile su calcolatore, è quella che realizza il metodo reductio. Il metodo sostanzialmente verifica che la negazione di β falsifica almeno una delle formule appartenente a Φ, in questo caso β è deducibile, poichè per ipotesi tutte le formule appartenenti a Φ sono vere; se la negazione di β non falsifica Φ, β non è deducibile da Φ. Per una realizzazione del metodo reductio occorre:

1.    trasformare Φ e β in forma normale congiuntiva, cioè in and di or: Φ = φ₁ ● φ₂ ● … ● φ_j …,  e β = β₁ ● β₂ ● … ● β_i …

2.   per ogni β_i appartenente a β occorre verificare se β_i è deducibile da Φ; ciò viene provato se, supposta falsa β_i, almeno una φ_j risulta falsa, contraddicendo le ipotesi. β_i è falsa imponendo opportunamente il valore Vero o Falso (V o F) ad ogni sua variabile.

3.    I valori assegnati alle variabili in β_i sono assegnati anche, alle stesse variabili in Φ.

4.         Ogni φ_j può essere:

4.1     Falsa poiché tutte le variabili presenti sono valorizzate a falso, β_i può essere deducibile da Φ.

4.2     Vera, se almeno una variabile presente ha valore vero, in tal caso occorre esaminare φ_j+1.

4.3     Indefinita, se ci sono ancora variabili non valorizzate (oltre ad eventuali variabili con valore falso). In questo caso occorre valorizzare le variabili in modo che rendano vera la formula: se le variabili in φ_j sono n, occorrono 2ⁿ-1 valorizzazioni. I valori assegnati alle variabili in φ_j vengono assegnati alle stesse varibili presenti nelle formule φ_k successive (k > j).

4.3.1    La verifica prosegue sulle formule successive a φ_j. Se per ogni assegnazione non si trova un φ_k falso, β non è deducibile.

Dall'esempio precedente:

1           Φ = (¬a v b) ● (¬c v b) ● (a v c);   β = b

2           Affinchè β sia falso b deve valere F.

3           Φ = (¬a v F) ● (¬c v F) ● (a v c)

4           φ₁ = ¬a v F è indefinito

4.3  Alla variabile a viene imposto il valore F, perché ¬a; le formule successive diventano: (¬c v F) ● (F v c)

4     φ₂ = ¬c v F è indefinito

4.3  Alla variabile c viene imposto il valore F, perché ¬c; la formula successiva diventa: (F v F)

4     φ₃ = F v F φ₃, contro le ipotesi, risulta falso, quindi β è derivabile da Φ.

Se Φ è inconsistente, perchè ad esempio contiene una formula e la sua negazione, sia β che ¬β sono derivabili.

4.6        Geometria e analisi

4.6.1            Cerchio ed Ellisse

Le equazioni di un’ellisse centrata ortogonale, di assi a e b, in funzione dell’angolo formato dall’asse x e dalla retta che contiene l’origine ed un punto generico (x,y) dell’ellisse, sono (equazioni parametriche):

x = a*cos(φ), y = b*sen(φ)

Se a = b la figura geometrica è un cerchio. La relazione fra le coordinate di un’ellisse generica con assi ortogonali che si incontrano nel punto (xc, yc), inclinata di in angolo α e la stessa con gli assi coincidenti con gli assi cartesiani è:

X = xc + x*cos(α) – y*sen(α)

Y = yc + x*sen(α) + y*cos(α)

Valore di pi greco

3,141592653589793238462643383279502884197169399375105820974944592307816...

pi greco = 4(1/1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13 - 1/15...)

pi greco circa 355/113 3.141592(92035398)