Corso di Informatica
per Giurisprudenza
Matteo Cristani
Dipartimento di Informatica
Facoltà di Scienze MM. FF. NN.
Università degli Studi di Verona
http://www.sci.univr.it/~cristani
1
Agenda
Concetto di algoritmo:
Algoritmi e programmi
Macchina a stati
Linguaggi e calcolabilità
Linguaggi di Programmazione
Semantica operazionale
Funzioni e denotazione
Equivalenza funzionale e computazionale
Codifica dei dati
Tipi elementari
Strutture di dato
2
Macchina a stati (1)
Formalizzazione del concetto di calcolo
Operazioni base di una macchina a stati:
Lettura
dell’input
Scrittura dell’output
Transizione di stato
Memorizzazione dati
3
Macchina a stati (2)
Calcolo:
Stato
iniziale
Sequenza di caratteri di input
Sequenza di stati ed azioni di trasformazione
dell’input
Sequenza di scritture dell’output
Stati finali
4
Rappresentazione a grafo
Read x
Write g(x) on the memory
Write f(x) on the output
5
Esempio di macchina a stati (1)
Un apparecchio telefonico può essere riguardato
come una macchina a stati
Stato iniziale: segnale assente
Stati intermedi: segn. di linea
segn. di libero
segn. di occupato
segn. di assenza
di linea
Stato finale:
conversazione
conclusa
(s0)
(s1)
(s2)
(s3)
(s4)
(s5)
Linguaggio riconosciuto: Attivazione di una
conversazione telefonica
6
Esempio di macchina a stati (2)
Modello di funzionamento
Stato
iniziale:
Sequenza:
segnale assente
Accesso
Se linea Componi
Se libero Conversazione
se occupato Concludi
(a);
(c);
(p) altrimenti
(e)
7
Esempio di macchina a stati (3)
p
c
s2
e
a
s5
s1
c
s3
e
s0
a
s4
e
8
Il concetto di linguaggio (1)
Alfabeto
Un
insieme finito e non vuoto i cui elementi
sono detti SIMBOLI
Stringa
Una
sequenza di lunghezza qualsiasi di simboli
di un alfabeto
Stringa vuota
La
sequenza di lunghezza zero su un qualsiasi
alfabeto (è denotata con )
9
Il concetto di linguaggio (2)
Sia un alfabeto,
*
denota l’insieme delle stringhe su
+ denota l’insieme delle stringhe su tranne la
stringa vuota
+ = * - {}
Linguaggio
Sottoinsieme
L
delle stringhe su di un alfabeto
*
10
Un esempio
= {a,b,c}
* = {, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb,
cc, aaa, aab, aac, …}
Un linguaggio
L=
{a, aa, aaa, aaaa, aaaaa, …}
11
Grammatiche (1)
Dato un alfabeto VT detto alfabeto terminale,
un alfabeto VN detto alfabeto nonterminale,
un elemento s dell’alfabeto nonterminale detto
simbolo distinto,
un insieme P di regole di produzione che
trasformano stringhe di (VT ∪ VN)* in stringhe
nonvuote su VT ∪ VN,
la quadrupla < VT,VN,s,P> è detta una grammatica
12
Grammatiche (2)
Date due stringhe e di (VT ∪ VN)*
diremo che deriva ( ⇒ )se e solo se
scrivesi
= xy;
= xy
Con x, y, , in (VT ∪ VN)*
C’è una regola di produzione →
13
Grammatiche (3)
Una stringa è derivata indirettamente da un’altra
quando si può compiere una sequenza di passi di
derivazione che conduce dalla prima alla seconda
stringa
Il linguaggio generato da una grammatica è
costituito dalle stringhe terminali derivate
indirettamente dal simbolo distinto
Ogni stringa del linguaggio generato da una
grammatica si dice sinttaticamente corretta per la
grammatica stessa
14
Grammatiche (4)
Un linguaggio generato da una grammatica
si dice grammaticale
IMPORTANTISSIMO:
Un linguaggio è grammaticale se e solo se è
riconoscibile da una macchina a stati
15
Osservazioni (1)
Nonostante gli alfabeti siano insiemi finiti i
linguaggi possono essere infiniti
La stringa vuota è uguale per qualsiasi
alfabeto
16
Osservazioni (2)
Le lettere dell’Italiano sono simboli di un alfabeto
Possiamo vedere come linguaggio:
Il lessico (radici e desinenze delle parole)
Il vocabolario (l’insieme delle parole italiane)
Le strutture frasali (sintagmi) italiane:
“Il giovane biologo veronese”;
“L’arguto giurista in erba scaligero”;
“L’interessante corso di Informatica”
Le frasi ed i periodi Italiani:
“La lezione si fece stimolante”;
“La pausa per il caffè era peraltro cogente”
17
Problemi (1)
Chiamiamo
PROBLEMA DI RICONOSCIMENTO
di un linguaggio L su di un alfabeto , il
problema di stabilire se una data stringa
in * sia in L o no
Ogni stringa si dice una istanza del
problema
18
Generalità sulle funzioni (1)
Siano A e B due insiemi, diciamo
Prodotto Cartesiano A╳B
l’insieme delle coppie ordinate di elementi
di A e B
Chiamiamo relazione tra A e B un sottoinsieme del
prodotto cartesiano di A e B
Per una relazione r definita tra A e B definiamo A
il dominio di r, e B il codominio di r
19
Generalità sulle funzioni (2)
Una funzione è una relazione univoca, cioè
una relazione che ad ogni elemento del
dominio associa al più un elemento del
codominio
Una funzione che associa sempre ad un
elemento del dominio un elemento del
codominio si dice totale
20
Generalità sulle funzioni (3)
Dato un elemento x del dominio l’elemento
in relazione f con x nel codominio si indica
con f(x) e si dice l’immagine di x
Dato un elemento y nel codominio, se vale
y = f(x), allora si dice che x è la
controimmagine di y secondo f
21
Generalità sulle funzioni (4)
Una funzione f si dice iniettiva se ad elementi
distinti del dominio associa elementi distinti del
codominio:
x ≠ y → f(x) ≠ f(y)
Una funzione si dice suriettiva se ogni elemento
del codominio ha controimmagine
∀y∃x[y = f(x)]
Una funzione sia iniettiva che suriettiva si dice
biiettiva o biunivoca
22
Esempi (1)
A={0,1}; B={a,b}
A╳B = {(0,a);(0,b);(1,a);(1,b)}
Relazione determinata da 1 va con b
R={(0,a);(0,b);(1,b)}
23
Esempi (2)
Sia A=naturali (ℕ) e B=naturali
Funzione f(n)=n2
Proprietà:
Iniettiva
Non suriettiva
Funzione f(n) = maxdiv(n) [che trova il massimo
divisore di n strettamente minore di n]
Proprietà:
Non iniettiva
Suriettiva
24
Problemi (2)
Sia f una funzione dai numeri naturali in se
stessi (f: ℕ ℕ)
Dato un numero naturale n chiamiamo
PROBLEMA DI CALCOLO
Trovare
f(n)
Dati due numeri naturali m ed n chiamiamo
PROBLEMA DI DECISIONE
Stabilire
se vale f(n) = m
25
Concetto di calcolabilità
Una funzione f si dice calcolabile se e solo
se esiste una macchina a stati che è in grado
di leggere n in input e scrivere f(n) in output
in un tempo finito
Una funzione f totale e calcolabile si dice
totalmente calcolabile
26
Equivalenza (1)
Ogni problema di decisione può essere
risolto se so risolvere il corrispondente
problema di calcolo
Per
decidere se m=f(n) calcolo f(n) e stabilisco
se vale l’uguaglianza
Meno ovviamente vale anche il contrario
Se
so stabilire quando m=f(n) per calcolare f(n)
enumero da 1 in avanti e risolvo 1=f(n),
2=f(n),… fino a quando il risultato è vero. Il
valore stabilito è f(n)
27
Equivalenza (2)
Ogni problema di decisione corrisponde ad un
problema di riconoscimento e viceversa
Per stabilire che questo è vero è sufficiente
ricordare che l’insieme * è ovviamente
numerabile (anche detto di cardinalità ℵ0) ovvero
corrispondente biunivocamente ad ℕ tramite una
funzione h
Una volta enumerato * il problema di
riconoscimento per una stringa corrisponde a
stabilire se vale per una funzione f(h())=1 (inteso
come codifica per il vero)
28
Equivalenza (2) - continua
Per un problema di decisione ogni istanza del
problema può definirsi come una istanza di un
problema di riconoscimento
Enumeriamo ℕ2. Enumeriamo * per un dato alfabeto
e costruiamo la corrispondenza biunivoca composta
da * all’enumerazione di ℕ2.
Ogni coppia di ℕ corrisponde ora ad una stringa in *.
Sia L il linguaggio delle stringhe che corrispondono ad
una coppia (m,n) tale che f(n)=m. Riconoscere L
corrisponde a risolvere il problema di decisione per f
29
Problemi paradigmatici
Date le equivalenze sopradette, i problemi
paradigmatici sono quelli di riconoscimento
La calcolabilità è definita mediante
macchine a stati
Quindi: l’obiettivo dell’informatica teorica
è definire tecniche per risolvere problemi di
riconoscimento mediante macchine a stati
30
Linguaggi di programmazione
Un linguaggio di programmazione è un linguaggio
grammaticale il cui scopo è descrivere tecniche di
risoluzione di problemi in modo che attraverso un
meccanismo automatico si possa fare applicare tali
tecniche su di una macchina a stati
I token di un linguaggio di programmazione
(simboli dell’alfabeto su cui è costruito) si
chiamano istruzioni
31
Linguaggi di programmazione
Una stringa sintatticamente corretta di un
linguaggio di programmazione si dice un
programma
La semantica operazionale di un linguaggio di
programmazione corrisponde ad un insieme di
regole che trasformano programmi in macchine a
stati
La semantica denotazionale di un linguaggio di
programmazione corrisponde ad un insieme di
regole che trasformano un programma nella
funzione da esso calcolata
32
Tipi di linguaggio (1)
Se le istruzioni di un linguaggio di
programmazione vengono tradotte in
comandi eseguibili dalla macchina
(istruzioni macchina) una per volta il
linguaggio di programmazione si dice
interpretato
Il programma che effettua la traduzione si
dice interprete
33
Tipi di linguaggio (2)
Se ogni programma di un linguaggio di
programmazione viene tradotto in una
sequenza di istruzioni macchina (codice
eseguibile) il linguaggio di programmazione
si dice compilato
Il programma che effettua la traduzione si
dice compilatore
34
Tipi di linguaggio (3)
Ogni programma eseguibile può essere in realtà
strutturato in comandi eseguibili direttamente dalla
macchina ma anche in comandi eseguibili da
macchine virtuali
Una macchina virtuale è un programma che
conosce un codice intermedio tra quello ad alto
livello del linguaggio di programmazione e quello
della macchina fisica
Tale codice prende il nome di p-code
35
Architettura dei linguaggi
Sintassi del linguaggio e sua analisi
PARSER
Semantica del linguaggio
INTERPRETE
COMPILATORE
Esecuzione di programmi
Run-Time
Support
36
Paradigmi di programmazione (1)
Un paradigma di programmazione è un
modo di vedere la macchina che esegue i
programmi
Esecuzione di p-code come semantica
operazionale
37
Paradigmi di programmazione (2)
Linguaggi imperativi
La
computazione è modellata come
l’esecuzione di ordini da parte di un “servo”
Linguaggi dichiarativi
La computazione è modellata come un calcolo
strutturato di
Funzioni
Condizioni logiche
(paradigma funzionale)
(paradigma logico)
38
Equivalenza di programmi
Due programmi che computano la stessa
funzione possono farlo in modo
profondamente diverso
Se due programmi computano la stessa
funzione si dice che sono funzionalmente
equivalenti
Se due programmi che computano la stessa
funzione lo fanno nello stesso modo si dice
che sono algoritmicamente equivalenti
39
Algoritmo
Perciò:
Necessità:
Algoritmo è la forma astratta di un programma, essendo
due programmi implementazioni dello stesso algoritmo
se computano la stessa funzione nello stesso modo
Un modo semplice e generale di descrivere gli algoritmi
Pseudolinguaggio
Una forma non implementata di linguaggio di
programmazione che contenga le strutture base dei
linguaggi di programmazione (imperativi)
40
Strutture fondamentali
Funzioni base
Controllo
di flusso
Lettura di dati
Scrittura di dati
Assegnamento di valori a variabili
41
Controllo di flusso: sequenza
Struttura di controllo
per fare eseguire due
istruzioni una dopo
l’altra
La rappresentazione
normalmente adottata
è di utilizzare un
separatore di linea
esplicito /il punto e
virgola) o implicito (a
capo)
Istruzione 1
Istruzione 2
42
Controllo di flusso: selezione
Struttura di controllo
per fare eseguire una
istruzione se vale una
condizione ed un’altra
altrimenti
La struttura
generalmente si
rappresenta mediante la
codifica
se condizione
allora
istr. 1
altrimenti istr. 2
condizione
vero
Istr. 1
falso
Istr. 2
43
Controllo di flusso: ciclo
Struttura di controllo
per fare eseguire
ripetutamente una
istruzione se vale una
condizione
La struttura
generalmente si
rappresenta mediante la
codifica
fintantoché condizione
istruzione
condizione
vero
falso
Istr. 1
Istr. 2
44
Nozione di variabile
Variabile
Nome
Tipo
Valore
Un nome di variabile è valido, generalmente se è
alfanumerico con limiti all’impiego di operatori
aritmetici e se inizia con una lettera
Occorrono costrutti per
Definire tipi
Attribuire tipi alle variabili
45
Altre istruzioni
Assegnamento
←v
Sottocaso: incremento
x
x←x+1
Lettura
read(x)
Scrittura
write(x)
46
Tipi di dati
Tipi elementari/strutturati
Tipi predefiniti/utente
Costrutti di definizione di tipo
Costrutti di binding (assegnamento di tipo
alle variabili)
Regole di compatibilità tra tipi
47
Tipi elementari
Tipi elementari predefiniti
Interi
Short/long
Range
Reali
(numeri relativi)
(numeri con la virgola)
Float/Double
Range e precisione
Carattere
Stringhe
Logico
(caratteri alfanumerici)
(sequenze di caratteri alfanumerici)
(vero o falso)
48
Tipi enumerativi
I tipi enumerativi sono tipi utente
elementari costituiti da un elenco di tutti e
soli i possibili valori del tipo
Esempio: colori dell’arcobaleno
{rosso, arancione, giallo, verde, blu, indaco, violetto}
49
Tipi strutturati
Strutture statiche
Array
Record
Strutture dinamiche
Liste
Alberi
File
50
Accesso agli elementi
Strutture ad accesso diretto o casuale sono
quelle che permettono di leggere e scrivere
elementi della struttura senza aver prima
scandito altri elementi
Strutture ad accesso sequenziale sono quelle
che invece richiedono che la lettura di un
elemento segua la lettura di altri elementi
che precedono l’elemento detto nell’ordine
di scansione della struttura
51
Array
Un array è un oggetto formato da un insieme
accessibile direttamente di oggetti tutti dello stesso
tipo
Gli indici di accesso sono un tipo enumerativo
ovvero numeri interi
Un array è definito dalla sua dimensione
strutturale (un array di dimensioni strutturale 1è
un vettore, uno di dimensione strutturale 2 è una
matrice) e dalle dimensioni relative (un vettore di
dieci elementi è di dimensione relative 10)
52
Array
Esempio:
Array di dimensione strutturale 1 e dimensione relativa
7 di numeri interi
[4,5,2,3,5,11,2]
Array
di dimensione strutturale 2 e dimensioni
relative 2 e 4
2
3
44
4
11
21
3
121
53
Record
Un record è un oggetto formato da un
insieme accessibile direttamente di oggetti
di tipi diversi
Gli indici di accesso sono nomi validi di
variabili
54
Liste
Una lista si costruisce aggiungendo un
elemento in coda ad una lista esistente, che
può essere vuota
Per leggere una lista abbiamo due operatori:
Uno
per ritornare il valore della posizione
corrente
Uno per spostare la posizione corrente in avanti
55
Grafi
Un grafo (diretto) è una coppia <V,E> in cui E è
un insieme di coppie di V, gli elementi di V si
chiamano vertici, gli elementi di E archi
Una sequenza di vertici di un grafo è un percorso
se e solo se ogni coppia di vertici in sequenza è un
arco
Un grafo si dice aciclico se e solo se non contiene
percorsi circolari (cioè che iniziano e terminano
con lo stesso vertice)
56
Alberi
Un albero è
Un
grafo diretto aciclico dove
Ogni vertice è puntato da al più un altro vertice
L’insieme dei vertici non puntati è un singoletto
Una lista è un albero i cui elementi puntano
al più un altro elemento
57
File
I file sono sequenze accessibili anche
mediante indici
Si differenziano dalle liste per avere
potenzialmente molti punti d’accesso
58
Scarica
