Fondamenti Teorici

(1)

Fondamenti Teorici

Antonio Pescapè e Marcello Esposito Parte Prima

v1.0

(2)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 2

Agenda

• Presentazione del Corso

• Concetto di Elaborazione

• Concetto di Algoritmo

• Concetto di Esecutore

• Concetto di Automa

• Esempi di Automi

(3)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 3

Presentazione del Corso

• Teoria dell’Informatica

• Architettura di un elaboratore

• Programmazione

Argomenti e struttura del corso

(4)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 4

Presentazione del Corso

Materiale Didattico

Libro di testo

u B. Fadini, C. Savy, Fondamenti di Informatica I, Liguori Editore

Materiale distribuito durante il corso u Manuale di C++

u Ambiente di sviluppo

u Dispense ed esercizi

(5)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 5

X è l’insieme dei dati di Ingresso Y è l’insieme dei dati di Uscita

F è una trasformazione che fa corrispondere Y ad X

F è una somma di due interi, F è la risoluzione di una equazione, F è l’ordinamento di una lista di nomi.

Concetto di Elaborazione

Y=F(X)

(6)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 6

• F non necessariamente risolve il suo compito in un solo passo

• F fornisce l’astrazione di una funzionalità: si

aspetta di ricevere dati ben definiti e fornisce dati ben definiti

• La generica F elabora un insieme di

informazioni di ingresso e restituisce un altro insieme di informazioni di uscita

Concetto di Elaborazione

F per svolgere il suo compito, opera un ALGORITMO

(7)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 7

Concetto di ALGORITMO

Un ALGORITMO è una sequenza finita di passi che risolve automaticamente un problema

n Il concetto di Algoritmo è un concetto astratto ed è indipendente da chi lo esegue e da come esso è descritto

n Esso è una sequenza di passi

n La sequenza è finita

n E’ deterministico

n E’ progettato per risolvere automaticamente un problema

Chi esegue un algoritmo ?

(8)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 8

Concetto di ESECUTORE

L’ESECUTORE di un algoritmo è l’entità che deve realizzare il compito attuando la sequenza di passi

che compongono l’algoritmo

n Un esecutore può far fronte al suo compito se e solo se è in grado di eseguire tutti i passi della sequenza.

In altri termini l’algoritmo dipende dal compito che si vuole realizzare.

Un esempio di esecutore: il pallottoliere

(9)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 9

Un ESECUTORE: il pallottoliere

Disponendo di un esecutore in grado di contare e spostare le palline di un pallottoliere si effettui la

somma tra due numeri interi

(10)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 10

Algoritmo per la somma utilizzando il pallottoliere

a) Si inizializzi il pallottoliere: si spostino sulla sinistra della prima riga un numero di palline pari al primo addendo, si spostino sulla sinistra della seconda riga un numero di palline pari al secondo addendo, si spostino tutte le palline della terza riga a destra

b) Passo 1: si sposti una pallina dalla sinistra alla destra della prima riga e contestualmente se ne sposti una dalla destra alla sinistra della terza riga

c) Si ripeta il passo 1 finché non di è svuotata la parte sinistra della prima riga

d) Passo 2: si sposti una pallina dalla sinistra alla destra della seconda riga e contestualmente se ne sposti una dalla destra alla sinistra della terza riga

e) Si ripeta l’operazione precedente finché non si è svuotata la parte sinistra della seconda riga

f) Lettura del risultato: il numero di palline che si viene a trovare alla

sinistra della terza riga al termine delle operazioni è il risultato

(11)

Elementi di Informatica – Fondamenti Teorici, A. Pescapè e M. Esposito 11

Sequenza statica e sequenza dinamica

In un algoritmo è possibile individuare due tipi di sequenze. Il primo tipo, detto sequenza statica, è la sequenza con cui i passi sono elencati nella formulazione dell’algoritmo stesso.

Se ora assumiamo di voler effettuare la somma 2+3=5 con questo algoritmo è facile verificare che l’esecutore, seguendo l’algoritmo, eseguirà la sequenza dinamica di passi 12 passi:

(a) (b) (c) (b) (c) (d) (e) (d) (e) (d) (e) (f)

Se invece effettuassimo la somma 3+2=5 con l’esecutore eseguirà la sequenza dinamica:

(a) (b) (c) (b) (c) (b) (c) (d) (e) (d) (e) (f) che pur avento ancora 12 passi è diversa dalla precedente.

La sequenza dinamica è quindi la sequenza di passi effettivamente eseguita

dall’esecutore in una particolare esecuzione dell’algoritmo. essa dipende dalla sequenza

statica, ma in generale non coincide con essa. Inoltre, mentre esiste un’unica sequenza

statica, esistono in generale molte sequenze dinamiche diverse, ciascuna associata a

particolari valori dei dati di ingresso (gli operandi della somma nell’esempio

precedente).

(12)

Considerazioni

• L’algoritmo fa riferimento a dati (o informazioni) di ingresso, a dati (o informazioni) intermedi e a dati (o informazioni) di uscita

• L’algoritmo calcola i dati di uscita a partire dai dati

di ingresso, eventualmente utilizzando altri dati già

presenti nella formulazione dell’algoritmo (costanti)

o già noti all’esecutore

(13)

Concetto di AUTOMA

Uno dei concetti matematici introdotti per

formalizzare una macchina che esegue algoritmi è l’ AUTOMA a STATI FINITI

n L’automa è anche detto Macchina Sequenziale

n Automa di Mealy e di Moore

(14)

Definizione di AUTOMA

Un automa è una quintupla:

(I, U, Q, t, w)

• I è l’insieme finito di ingressi, i : i ∈ ∈ ^I

• U è l’insieme finito delle uscite, u : u ∈ ∈ ^U

• Q è l’insieme finito degli stati, q : q ∈ ∈ ^Q

• t è la funzione di transizione di stato, t : Q x I -> I

• w è la funzione d’uscita, w : Q x I -> U

Questa è la definizione secondo Mealy; s e c o n d o M o o r e la funzione d’uscita è tale che:

w : Q -> U

(15)

Esempi di AUTOMA

• Un automa per contare la parità/disparità delle

occorrenze di un simbolo all’interno di una stringa di simboli

• Un automa contatore m o d M: si contino, modulo M, le occorrenze di un dato simbolo

• Un automa che controlla il funzionamento di un frullatore

• Un automa che controlla il funzionamento di una porta elettrica

• Un automa riconoscitore di sequenze

(16)

Ancora sul Concetto di AUTOMA

• L’automa introduce il concetto di stato

• Lo stato viene anche detto stato interno

• Lo stato abilita l’automa a rispondere in maniera diversa a identiche sollecitazioni

• Il comportamento di un automa dipende, attraverso lo stato, dalla sua storia passata

• L’automa risolve un problema preciso, per risolvere un problema diverso bisogna riprogettarne un altro

• Ma allora il nostro PC, che risolve una vasta gamma

di problemi, non è un automa ?

(17)

• Lo stato, nella pratica, viene memorizzato in organi di memoria detti REGISTRI

• Un REGISTRO si dice k -stabile se può memorizzare k stati distinti e mantiene inalterate le informazioni in esso

“registrate” fino a che non le si vogliano alterare

STATI e REGISTRI

1 2 3

E’ 1000-stabile, assumendo cioè 1000 possibili stati diversi. Gli stati possono, convenzionalmente, essere associati ai primi 1000 numeri naturali.

1 0 1

Esempi: Un registro che memorizza 3 cifre decimali (10 simboli):

E un registro che memorizza 3 cifre binarie ?

(18)

Prendendo come esempio un registro che memorizza 3 cifre decimali (10 simboli) come è possibile memorizzare un numero negativo ?

REGISTRI e Rappresentazioni

Anche se non è possibile memorizzare il “segno”

basterà assumere convenzionalmente che il numero negativo sia associato ad un numero naturale

rappresentabile.

Un elaboratore opera sulle RAPPRESENTAZIONI dei numeri e non sui numeri; alle rappresentazioni sono convenzionalmente associate delle informazioni.

Per la rappresentazione di un dato di cardinalità N

occorrono pertanto registri ad almeno N stati stabili,

ciascuno dei quali atto ad individuare uno dei possibili

valori del dato.

(19)

Una elaborazione è un procedimento che da alcuni dati di partenza, secondo un algoritmo, produce dei dati di arrivo detti risultati

Il modello penna e carta

Se si lascia un compito ad una persona, senza aver

formalizzato correttamente il tutto ed aver valutato tutte le possibilità non si è fornito un algoritmo

Una accurata formulazione della procedura ed una accurata descrizione di TUTTE le azioni da

intraprendere in TUTTE le possibili condizioni di

funzionamento che possono verificarsi è un algoritmo

Esempio : V A I A C O M P R A R E I L L A T T E

(20)

C’è una persona che non sa assolutamente nulla di algebra

La persona possiede una calcolatrice ed è capace di effettuare le operazioni elementari e i confronti logici

La persona possiede penna e carta e appositi tabulati per prendere nota di dati iniziali, risultati intermedi e risultati finali

La persona è in grado di interpretare semplici istruzioni operative

Sotto queste ipotesi, è possibile fornire a questa

persona una procedura da seguire scrupolosamente per risolvere, ad esempio, una equazione di II grado

Il modello penna e carta: esempio

(21)

Il modello penna e carta: esempio

E D C B

c b

a A

5 4

3 2

1 a

c a b

x b

⋅

−

±

= −

2 2 4

2 , 1

Soluzione di una equazione di secondo grado

(22)

Il modello penna e carta: esempio

1) A2 * A2 à B 1 2) A1 * 4 à B2 3) B2 * A3 à B2 4) B1 – B2 à B3

5) Se (if) B3 < 0 allora (then) scrivi in A5 “Compl ” e termina 6) A2 * -1 à C1

7) A1 * 2 à C2

8) Se (if) B3 == 0 allora (then):

1) Scivi in A5 “ Coinc”

2) C1 / C2 à B5 e termina

...

E D C B

c b

a A

5 4

3 2

1 b

²

4ac 4 a

-b 2 a

b

²

- 4ac C1/C2

Compl

Coinc

(23)

Il modello penna e carta: esempio

…

Altrimenti (else) 1) √ ^B3 à C3 2) C1 + C3 à D1 3) C1 – C3 à D 2 4) D1 / C2 à B4 5) D2 / C2 à C4

6) Scrivi in A5 “ Dist” e termina

E D C B

c b

a A

5 4

3 2

1 b

²

4ac 4 a

-b 2 a

b

²

- 4ac

Dist

√ (b

²

- 4ac)

-b + √ ^(b

²

^{- 4ac)} ^{-b -} √ ^(b

²

^{- 4ac)}

x

₂

x

₁

(24)

Analogie (1)

La persona è il calcolatore

La persona attraverso la sequenza di semplici

operazioni può realizzare operazioni anche molto complesse

La persona, come il calcolatore, NON ha coscienza

del problema che sta risolvendo, NON entra nella

semantica dei dati iniziali e dei risultati. Per lui

sono solo numeri.

(25)

Analogie (2)

Il procedimento descritto è un algoritmo. Esso non lascia niente al caso

La tabella sulla carta e le istruzioni date alla persona sono assimilabili alla memoria del calcolatore. Da essa vengono prelevati i dati

iniziali, vengono riposti i dati intermedi e i risultati finali

E’ compito dell’utente interpretare correttamente lo stato della tabella dopo il termine del

procedimento.

(26)

Esercizio 1

T e s t o:

Progettare, utilizzando il modello di automa a stati finiti, un controllore di un'ascensore di una palazzina di 2 piani. Si utilizzino le seguenti convenzioni:

- l'insieme I degli ingressi è costituito dalla pulsantiera dell'ascensore e cioè I = {T, 1, 2}

- l'insieme U delle uscite è costituito dalla

direzione di spostamento dell'ascensore stesso

e cioè U = { F e r m o, Su, Giù}.

(27)

Esercizio 1

S o l u z i o n e:

I = {T, 1, 2};

U = { F e r m o, s u, giù};

(28)

Esercizio 2

T e s t o:

Progettare il sistema di controllo e gestione della parità

all'ingresso del Parlamento Italiano. Il funzionamento deve essere il seguente: fatta l'ipotesi che all'ingresso si presentino solo due tipi di parlamentari, di tipo D (parlamentari del

centro-destra) e di tipo S (parlamentari del centro-sinistra), si considerino sequenze di S e D delimitate dal carattere '*'. Una sequenza di ingresso, ad e s e m p i o, potrebbe essere:

* S S S S D S S S D D D S S D S D S S S D S D S S D S D D D S *

Progettare u n automa che accetti in ingresso questo tipo di

s e q u e n z e e restituisca uscita PariS s e il numero di S della

s e q u e n z a è pari, uscita DispariS s e esso è dispari.

(29)

Esercizio 2

S o l u z i o n e:

I = {'*', 's', 'd'};

U = {-, PariS, DispariS};

(30)

Esercizio 3

Testo:

Progettare un automa a stati finiti (di Mealy o di Moore) che accetta in ingresso i caratteri

dell'alfabeto e riconosce la sequenza di ingresso

costituita dalla parola 'aba'.

(31)

Esercizio 3

S o l u z i o n e:

I = {'a', 'b', ..., 'z'};

U = {-, 1};

Lo stato arbitrariamente

denominato 'a' corrisponde alla situazione "una 'a' riconosciuta'.

Quello denominato 'ab' corrisponde alla situazione

"sequenza 'ab' riconosciuta".

La transizione tratteggiata in grigio si riferisce ad un funzionamento alternativo dell'automa secondo il quale esso si riposiziona

nuovamente nello stato 'a' subito dopo aver riconosciuto la

sequenza. In questo caso, alla

sequenza 'ababa' la macchina

risponde con due uscite alte in

corrispondenza della seconda e

della terza 'a'.

(32)

Esercizio 4

Una segnale luminoso è collegato ad una porta dotata di una serratura elettronica. Il segnale resta sempre rosso, a meno che la serratura e la porta n o n risultino entrambe aperte, nel qual caso il colore del segnale diventa verde. Progettare l’automa a stati finiti (di Mealy o di Moore) che controlli il colore del segnale.

L’insieme degli ingressi è costituito da:

- CS: Chiudi Serratura - AS: Apri Serratura - CP: Chiudi Porta - AP: Apri Porta

L’insieme delle uscite è costituito da:

- LV: Luce Verde - LR: Luce Rossa

Lo stato iniziale è così caratterizzato:

- S0 = Porta Chiusa e Serratura Chiusa

(33)

Esercizio 5

U n frullatore elettrico per poter funzionare correttamente necessita di essere acceso e della presenza del tappo sul bicchiere. Progettare u n automa a stati finiti (di Mealy o di Moore) per controllare il funzionamento del frullatore. Il s e g n a l e d’uscita resta basso, a m e n o che il frullatore n o n sia acceso e non sia presente il tappo.