Dal Problema al Programma

Piano Nazionale di Formazione degli Insegnanti
sulle Tecnologie dell’informazione e della
Comunicazione
Dal problema al programma
Modulo 8
A cura della prof.ssa Piera De Maio
Scopo del modulo
Conoscere alcuni concetti fondamentali
dell’informatica:algoritmo, automa, linguaggio formale
Essere in grado di cogliere l’intreccio tra alcuni risultati
della matematica e della logica dei primi decenni del
secolo scorso ed i successivi sviluppi e applicazioni che
questi hanno avuto in campo informatico
Indice
8.1 Problemi e algoritmi
8.1.1 introduzione intuitiva del concetto di problema
8.1.2 cenni sulle strategie per la risoluzione dei problemi
8.1.3 soluzione di un problema
8.1.4 gli algoritmi
8.1.4a Diagrammi a blocchi
8.1.4b Linguaggio di progetto
8.2 Automi esecutori
8.2. Automi esecutori
8.2.1 Caratteriatiche di un automa
8.2.1bConcetto di modello
8.2.1cConcetto di automa
8.2.1b 8.2.2 Automi e classi di problemi
Esercitazioni
8.3 Linguaggi
8.3.1 Sintassi e semantica dei linguaggi
8.3.1a Linguaggi nella comunicazione uomo-macchina
8.2.2 Linguaggi e automi
8.3.3 Linguaggi di programmazione
8.1.1 Introduzione intuitiva al
concetto di problema
Il problema è una situazione che pone delle
domande alle quali si devono dare delle risposte.
Risolvere il problema vuol dire uscire dalla
situazione
8.1 Problemi e algoritmi
Un problema consta dei seguenti elementi
•Dati: ossia ciò che è noto e che indichiamo
col termine input
•Risultati: gli elementi incogniti che si
devono determinare e che indicheremo con
output
•Condizioni: le limitazioni
soggiacere i risultati
cui
devono
8 .1 Problemi e algoritmi
Tipi di
problemi
Problemi di
decisione
Problemi di
ricerca
Problemi di
ottimizzazione
8.1.2 Strategie per la
risoluzione dei problemi
Problema
Interpretazione
Modello
Verifica dei risultati
Esecuzione
Procedimento
risolutivo (algoritmo)
8.1.2b Concetto di modello
Modello
E’ uno schema teorico elaborato per rappresentare elementi
fondamentali di fenomeni o enti
Modelli descrittivi (riproducono in modo semplice la realtà , senza presupporre l’uso
che ne verrà fatto)
Modelli predittivi
(danno gli elementi di una situazione per prevederne l’evoluzione)
Modelli prescrittivi (impongono un particolare comportamento in previsione dell’obiet
tivo da raggiungere)
Modelli simbolici o matematici (danno una rappresentazione astratta mediante un
insieme di equazioni che legano le grandezze)
Modelli analogici ( danno una rappresentazione fedele della realtà in scala ridotta )
8.1.2 Strategie per la
risoluzione dei problemi
Interpretazione
TOP
DOWN
GRAFICO
Suddivide il problema in tanti
piccoli sottoproblemi
Utilizza uno schema
grafico a segmenti
8.1.2 Strategie per la
risoluzione dei problemi
Algoritmo
Insieme delle istruzioni che definiscono una
sequenza di operazioni mediante le quali si
risolve il problema
Deve essere :
finito
(numero limitato di passi );
definito
(ogni istruzione deve consentire un’interpretazione
univoca);
eseguibile
( la sua esecuzione deve essere eseguibile con gli
strumenti a disposizione);
deterministico
( ad ogni passo deve essere definita una
operazione successiva ).
8.1.2 Strategie per risoluzione
dei problemi
Rappresentazioni grafiche e
formalizzate di un algoritmo
La descrizione delle fasi esecutive del problema può
avvenire mediante la formalizzazione dei passi elementari
da effettuare che può essere realizzata con:
Diagramma a blocchi
o flow-chart
e/o
Pseudocodifica
8.1.4a Diagrammi a blocchi
Diagramma a blocchi o flow-chart
Ha il pregio di evidenziare visivamente l’avanzamento in
sequenza e le varie strutture che compongono l’algoritmo,
presenta istruzioni di input, calcolo e/o di elaborazione,
condizioni e output.
INPUT
ISTRUZIONI
CONDIZIONI
OUTPUT
8.1.4a Esempio di diagramma
a blocchi
inizio
Somma di una
sequenza di
numeri
N
S=
A
S= S+A
N=N-1
NO
N= 
SI
S
FINE
8.1.4b Linguaggio di progetto
Linguaggio di progetto o pseudocodifica
E un linguaggio formale, ( linguaggio di progetto) con regole prive di ambiguità ed eccezioni che
esprimono i vari tipi di istruzioni. Viene definito pseudocodifica o notazione lineare strutturata.
Generalmente utilizzato dai programmatori di elaboratori.
begin
ESEMPIO IN PASCAL
Input N

S
repeat
input A
S
S+A
N
N-1
until N=
output S
end
8.2 Automi esecutori
La risoluzione di un problema è un processo di manipolazione di
informazioni per generare nuove informazioni .
Per risolvere un problema ci sono due tipi di attività :
“intelligenti”di elaborazione
“routinarie” di esecuzione
8.2.1 Caratteristiche di un automa
Automi
Sono macchina che compiono attività complesse in cui sono
riconoscibili elementi propri delle attività
superiori del
comportamento umano. Possono essere programmate per svolgere
diverse mansioni e per modificare le proprie azioni in relazione ai
mutamenti ambientali. (Es: lavatrici, sistemi di controlli ascensori,
bancomat…computer)
Un automa è un sistema :
Dinamico Passa da uno stato all’altro secondo gli input che riceve
Invariante Se le condizioni iniziali sono le stesse il comportamento
del sistema è invariato
Discreto Le variabili, d’ingresso, di stato e d’uscita possono
assumere solo valori discreti
8.2.1 Il concetto di automa
Grafi e tabelle di transizione
Servono a rappresentare il comportamento logico-funzionale di un automa
Es. tabella e grafo di un automa a stati finiti di un ascensore
S\i
T
1
2
pt
Pt/ fermo
1p/ su
2p/ su
1p
Pt/ giù
1p/ fermo
2p/ su
2p
Pt/ giù
1p/ giù
2p/ fermo
1/ su
1/fermo
T / fermo
T/giù
PT
2/ fermo
2/su
1P
1/ giù
2P
2/su
8.2.2 Automi e classi di problemi
Un sistema automatico o automa è un sistema nel
quale la componente umana è completamente
eliminata nell’ambito dei processi, che sono ben
determinati e prevedibili:
Lavatrice, lavastoviglie,
programma)
computer
Un sistema umano, al contrario, presenta un carattere
probabilistico, poiché l’uomo può assolvere a funzioni
impreviste , utilizzando il ragionamento, la creatività e
l’intuito.
(automa
a
Problemi e algoritmi
ESERCITAZIONI
Un bambino ha costruito una torre di tre blocchi colorati così disposti dall’alto in basso:
ROSSO-GIALLO-VERDE. IL bambino vuole capovolgerla in modo da avere VERDEGIALLO-ROSSO.Può spostare solo un blocchetto alla volta. Individuare il numero
minimo di stati per i quali si arriva alla configurazione desiderata.
Cercare una chiave in un mazzo di 100 chiavi con il minor numero di prove
(diagramma di flusso)
8.3
Linguaggi
Il linguaggio è un sistema
codificato
di
segni
che
consente la comunicazione,
intesa
come
scambio
di
informazioni
8.3.1 Sintassi e semantica dei
linguaggi
Un’informazione può :
Essere acquisita direttamente tramite rilevamento di un evento
reale attraverso percezione sensoriale.
Essere trasmessa (messaggio) intenzionalmente da un emittente
ad un ricevente per mezzo di un canale
La comunicazione
Il messaggio presuppone l’utilizzo di un codice (
sistema di regole) e di un linguaggio che devono
essere conosciuti sia dal emittente che dal
destinatario, altrimenti la comunicazione non ha
effetto
?
?
?
?
emittente
destinatario
8.3.1 Sintassi e semantica dei
linguaggi
La funzione del linguaggio è quella di sostituire ad oggetti
o concetti dei segni/simboli per trasmettere un messaggio.
Il segno è l’associazione di qualcosa di materiale e
sensibile
(immagine, suono…) che chiamiamo
significante con qualcosa di puramente concettuale che
chiamiamo significato
Il codice ci consente l’interpretazione dei segni
Segno
gatto
= significante
Il gruppo dei suoni o di
lettere g/a/t/t/o
+ significato
8.3.1 Sintassi e semantica dei
linguaggi
ELEMENTI DI UN LINGUAGGIO
Alfabeto insieme finito e non vuoto di simboli convenzionali
espressi con segni tipografici detti caratteri
Ortografia insieme finito e non vuoto di regole per la scrittura dei
suoni
Sintassi insieme finito e non vuoto delle regole mediante le quali si
formano le stringhe o le frasi di un linguaggio
Semantica insieme finito e non vuoto di significati da attribuire alle
stringhe
Morfologia insieme finito e non vuoto di tuttele regole che servono
per generare le forme di un linguaggio
8.3.1.a Linguaggi nella
comunicazione uomo - macchina
L’uomo per comunicare all’ automa le strategie risolutive di
un problema ha bisogno di un linguaggio formale che gli
consenta di passare dall’ algoritmo al programma , cioè ad
una sequenza di istruzioni mediante le quali si può risolvere
il problema.
8.3.2 Linguaggi e automi
Linguaggi non evoluti
Linguaggio macchina, linguaggio
assemblativo (Assembler).
Vicino alla logica della macchina
Linguaggi evoluti
Linguaggi non orientati alla
macchina , ma alla soluzione dei
problemi.
Vicino alla logica dell’uomo
8.3.2 Linguaggi e automi
I principali software
Sistema operativo
Office Automation
•Word processor
Software di base ,
controlla tutte le
risorse del
computer, necessita
di un linguaggio più
vicino al linguaggio
macchina
(Assembler)
•Foglio di calcolo
•Sistemi di gestione base dati
•Programmi per la realizzazione di
presentazioni multimediali
•Programmi di grafica computerizzata
•Editor di suoni
•Editor di pagine web
8.3.3 Linguaggi di
programmazione
Problema
Algoritmo
Programma
sorgente
Risultati
Dalla
formulazione del
problema alla
sua soluzione
Programma
traduttore
Elaborazione
Programma
oggetto
8.3.3 Linguaggi di
programmazione
Programma sorgente
Istruzioni di
dichiarazione
Descrivono dati
e variabili
utilizzati dal
programma,
definendone tipo
e struttura
L’algoritmo risolutivo
viene trasformato in un
programma attraverso
un linguaggio di
programmazione che
può contenere:
Istruzioni di
assegnazione
Istruzioni di
controllo
Consentono di
assegnare alla
variabile un valore
dello stesso tipo
della variabile
Sono istruzioni
che richiedono
salti di sequenza
nell’esecuzione
del programma
Istruzioni di
input e output
Richiedono
l’ingresso o l’uscita
di un’informazione
da una periferica
alla memoria
centrale e viceversa
8.3.3 Linguaggi di programmazione
Fortran
Cobol
Algol
Basic
PHP
Principali linguaggi
Logo
PL1
Lisp
Pascal
C /C++
Java