Corso di
Complementi di Informatica Generale
Formazione all'Insegnamento Matematico Scientifico (FISM)
Salvatore Spinella
www.di.unito.it/~spinella/fism
Chi siamo?? (secondo la facoltà)
● Scienze Biologiche 509 1 cfu debito INF● Scienze Biologiche 270 2 cfu di debito INF● Fisica 3 cfu.● Scienze Generali 270 3 cfu di INF (primi
laureati ad ottobre)● Scienze Generali 509 5 cfu di INF ● Scienze Naturali 509 6 cfu debito INF● Scienze Naturali 270 6 cfu di debito INF (un
solo laureato in estate 2011)
Calendario?! (48 ore)
● aula Monod, diaprtimento di Matematica via carlo alberto 10
● 19-set-2011 dalle 14,00 alle 18,00
● 20-set-2011 dalle 9,00 alle 13,00
● 21-set-2011 dalle 14,00 alle 18,00
● 22-set-2011 dalle 14,00 alle 18,00
● 23-set-2011 dalle 14,00 alle 18,00
● AULA 2, DIPARTIMENTO BIOLOGIA ANIMALE E UOMO VIA ACCADEMIA ALBERTINA 13
● 26-set-2011 dalle 14,00 alle 18,00
● 27-set-2011 dalle 14,00 alle 18,00
● 28-set-2011 dalle 14,00 alle 18,00
● 29-set-2011 dalle 14,00 alle 18,00
● 30-set-2011 dalle 14,00 alle 18,00
● ????????
● 2-ott-2011 dalle 14,00 alle 18,00
● 3-ott-2011 dalle 14,00 alle 18,00
Libri di Riferimento
● Console, Ribaudo, Avalle, Introduzione all'informatica, UTET
● JC Brookshear, Informatica, una panoramica generale, Pearson
● Materiale online (in lingua inglese?)
Piano del corso in 6 CFU (1/2)
● Principi Teorici (1 CFU) 8 ore● Teoria dell'informazione● Modelli computazionali
● Algoritmi (1 CFU) 8 ore● Introduzione● Ordinamento● Strutture dati?● Ricorsione?Ø Esercitazione : Diagrammi di flusso e
Pseudocodice
Piano del corso in 6 CFU (2/2)● Linguaggi di programmazione (2 CFU) 16 ore
● Tipi predefiniti● Programmazione strutturata● Laboratorio linguaggio Python● Esercitazione
● Sistemi e Reti (2 CFU) 16 ore● Architettura di un SOv Esercitazione : Unix e Shell● Architetture di Rete
Teoria dell'informazione
Che cosa è l'informazione?
Ciò che disambigua lo stato di un sistema
La teoria?
Studia, mediante la teoria della probabilità, i problemi di trasferimento dei messaggi da una
sorgente emettitrice a un ricevitore
Storia
Claude Shannon 1916-2001.
Nel 1948 con la pubblicazione di “Una teoria matematica della comunicazione”, Shannon caratterizzerò un canale di comunicazione con un unico parametro: la capacità. Dimostrò inoltre che è possibile trasmettere informazioni al di sotto della capacità del canale con una probabilità di errore arbitrariamente piccola.
Diagramma schematico un sistema generale di comunicazione
http://www.research.att.com/~njas/doc/shannon1948.pdf
Canali discreti
In generale, per canale discreto si intende un sistema in cui è possibile comporre una sequenza a partire da un insieme finito di simboli elementari
e trasmetterla da un punto all'altro.
Ciascun simbolo si abbia una certa durata di tempo di trasmissione in secondi (non necessariamente la stessa per diversi simboli, ad esempio, i punti e linee in telegrafia).
S1,…,Sn
σ1,σ2,… ,σn
Capacità di un canale
C=log (numero di simboli che è permesso in un tempo T )T
“per T grande”!!
C=log(Numero di caratteri permessi in un tempo T )
T
Sorgenti discrete di informazione (1/2)
To give a visual idea of how this series of processes approaches a language, typical sequences in the approximations to English have been constructed and are given below. In all cases we have assumed a 27-symbol “alphabet,” the 26 letters and a space.
1. Zero-order approximation (symbols independent and equiprobable).
XFOML RXKHRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD QPAAMKBZAACIBZLHJQD.
2. First-order approximation (symbols independent but with frequencies of English text).
OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL.
3. Second-order approximation (digram structure as in English).
ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIN D ILONASIVE TUCOOWE AT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.
Sorgenti discrete di informazione (2/2)
4. Third-order approximation (trigram structure as in English).
IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.
5. First-order word approximation. Rather than continue with tetragram,..., n-gram structure it is easier and better to jump at this point to word units. Here words are chosen independently but with their appropriate frequencies.
REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.
6. Second-order word approximation. The word transition probabilities are correct but no further struc
ture is included.
THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.
Scelta, Incertezza, Entropia
Si supponga di avere un insieme di eventi con probabilità
Queste probabilità sono note, ma non conosciamo altro.
E' possibile definire una misura di quanta “scelta” è coinvolta nella selezione di un evento o quanta incertezza abbiamo del risultato? (parole di Shannon)
p1,p2,…,pn
p1 , p2 , p2 ,… , pn
Misura d'informazione H
Quali proprietà dovrebbe avere una misura di informazione?
1. H deve essere continua rispetto alle probabilità p
2. Se tutte le n probabilità p sono uguali, rispetto a n tale misura H dovrebbe essere monotona
3. Se una scelta è suddivisa in due scelte successive, l'H originale dovrebbe essere la somma pesata dei valori individuali di H.
Significato della 3
A sinistra abbiamo 3 possibilità. A destra prima si sceglie tra 2 e poi ancora tra 2.
H(12,13,16)=H(12,12)+12H(23,16)
Deve essere
H (12,13
,16 )=H ( 1
2,12 )+1
2H ( 1
3,16 )
Teorema
La sola funzione H che soddisfa le tre assunzioni ha la forma:
H=−k∑i=1npilog (pi)
La quantità misurata da questa formula viene detta anche entropia.Esempio: l'entropia binaria
Hb=plog (p)+(1−p)log (1−p)
H ( p1,…, pn)=−K∑i=1
n
p i log( pi)
H ( p ,1−p)=p log p−(1−p) log(1−p)
Proprietà di HLa quantità H ha una serie di interessanti proprietà che ne compravano ulteriormente la selezione come misura ragionevole di scelta o informazioni.
1. H = 0 se e solo se tutti i p tranne uno sono pari a zero, questo ha il valore 1. Quindi solo quando siamo certi del risultato H si annulla. Altrimenti H è positivo.
2. Per un dato n, H è massimo e pari a log(n) quando tutti i p sono uguali. Questa è anche intuitivamente la situazione più incerta.
3.
H(x,y)⩽H(x)+H(y)
H ( x , y )⩽H (x)+H ( y )
Computazione e Programmi
● La computazione non ha una definizione formale perché è un concetto primitivo.
● Per studiarlo si fa riferimento a modelli ideali ad esempio la famosa Macchina di Turing.
● Noi utilizzeremo i programmi (perchè ci risulterà utile in seguito!)
Macchina di Turing (1/2)
Diamole solo un'occhiata...
Un insieme di quadruple che ne costituiscono la “logica”, ad esempio:● (q1 B) → (R q2)● (q2 1) → (R q2)● (q2 B) → (1 q3)● (q3 1) → (R q3).... ecc
Un nastro a “quadretti” e un strumento di scrittura per stamparci sopra.
Macchina di Turing (2/2)
q1 q2 q3 sono degli stati.
1 B sono dei simboli
R L sono dei movimenti dello strumento di scrittura a destra o a sinistra
L'azione della macchina è quello di seguire la logica delle quadruple accoppiando ed eseguendo la transizione
Modelli computazionali
Sono stati immaginati diversi modelli computazionali, ma analizzandone le possibilità di calcolo sono risultati tutti equivalenti.
In particolare, ogni modello di calcolo equivale ad un uomo che esegue calcoli assegnati con “carta e penna”.
Ovviamente le potenze di calcolo dei vari modelli differiscono enormemente.
I programmi: linguaggio S
Tralasciamo l'oggetto che eseguirà il programma e concentriamoci su quest'ultimo.
Definiamo con
Un insieme di variabili di input che assumono valori nell'insieme dei numeri naturali.
X1 , X2 , X3 ,…
Linguaggio S
Definiamo con
Un insieme di variabili di output
E con
Un insieme di variabili ausiliarie.
Per convezione queste variabili valgono inizialmente zero.
Y 1 , Y 2 , Y 3 ,…
Z1, Z2 ,Z3 ,…
Le istruzioni
● V ← V – 1● V ← V + 1
● IF V ≠ 0 GOTO L
Solo queste!! I programmi saranno sequenze finite di istruzioni del tipo
[L] istruzione
con L etichetta di riferimento
esempio
[A] X ← X – 1
Y ← Y + 1
IF X ≠ 0 GOTO A
Cosa fa questo programma?
Restituisce in Y il valore di X se questo è diverso 0 altrimenti restituisce 1
Raffiniamo il linguaggio
Raffiniamo il linguaggio aggiungendo delle nuove istruzione costruite a partire da quelle iniziali. Questo renderà tutto più comodo e “abbellirà” il linguaggio. Per sempio
Z ← Z + 1
IF Z ≠ 0 GOTO L
Può essere sinteticamente utilizzato come
GOTO L
[A] IF X ≠ 0 GOTO B
GOTO C
[B] X ← X – 1
Y ← Y + 1
Z ← Z + 1
GOTO A
[C] IF Z ≠ 0 GOTO D
GOTO E
[D] Z ← Z – 1
X ← X + 1
GOTO C
Continuiamo ad arricchire...
Per convenzione il GOTO ad una etichetta insistente corrisponde alla terminazione.
Cosa fa? Una assegnazione del tipo
V ← V'
Un piccolo passo per un programma...
Y ← X1
Z ← X2
[B] if Z ≠ 0 GOTO A
GOTO E
[A] Z ← Z – 1
Y ← Y + 1
GOTO B
Cosa computa?
Y ← X1 + X2
Abbiamo la somma!
Ancora
Z2 ← X2
[B] IF Z2 ≠ 0 GOTO A
GOTO E
[A] Z2 ← Z2 – 1
Z1 ← X1 + Y
Y ← Z1
GOTO B
Cosa fa?
Y ← X1 * X2
Esercizio
Scrivere il programma che calcola
Y ← X1 – X2
Se X1 è minore o uguale a X2 restituire zero
I programmi calcolano funzioni
I programmi calcolano funzioni delle variabili X1, X2, X3... E Y è il valore calcolato rispetto a tali variabili.
Sinteticamente possiamo scrivere che la funzione calcolata dal programma P è
ψP(m )( x1 , x2 ,… , xm)
Domanda
Se ad ogni programma corrisponde ad una funzione matematica è vero anche il contrario?
Cioè.
Ad ogni funzione matematica definibile è possibile associare il programma che la calcola?
C'è un lungo ragionamento da fare per rispondere a questa domanda...
Si noti che esistono molti programmi la cui fine è indefinita (loop!!).
Una speciale codifica dei programmi
Funzione accoppiamento
Numero di Godel
Le p rappresentano la sequenza dei numeri primi a partire da 2.
⟨ x , y ⟩=2x (2y+1)−1
[a1 , a2 ,… , an ]=∏ p iai
Ad ogni istruzione un numero
Riordiniamo le variabili così:
Y, X1, Z1, X2, Z2,...
E le eticchette
A1, B1, C1, D1, E1, A2, B2,...
In questo modo è possibile numerare le sequenze. Esempio la variabile di posizione 0 è Y, quella di posizione 1 è X1...
Ad ogni programma un numero
Associamo quindi alle istruzioni base un numero in maniera biunivoca #(I)=<a, <b, c> >
a è il numero di sequenza dell'etichetta, b è il numero della variabile coinvolta c (0, 1 o 2) identifica quale delle tre istruzioni viene codificata.
La codifica di un programma può essere effettuata come
#(P)=[#(I1),#(I2),#(I3),..,#(In)]-1
La funzione di fermata
Definiamo la seguente funzione.● HALT(x,y) restituisce 1 se il programma di
numero x si ferma e restituisce il risultato sull'input y
● HALT(x,y) restituisce 0 se il programma di numero x su input y ha una fine indefinita.
Una funzione così definita ha un programma che la calcola?