Corso di

Complementi di Informatica Generale

Formazione all'Insegnamento Matematico Scientifico (FISM)

Salvatore Spinella

spinella@di.unito.it

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

Tutoraggio del Corso

Eva Sciacca

sciacca@di.unito.it

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

Esame

Programmazione?? + Orale

Calendario

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)

Graficamente....

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

Un immagine esplicativa!

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'

Esercizio

Scrivete il programma per

V ← 0

Che azzera una variabile

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

Tabulazione funzione accoppiamento

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?

Troppo bello per essere vero...

Non è computabile. Non esiste un programma che la calcola.