Dal problema al programma

Dal problema al programma
Unità di apprendimento
Tratte da moduli presentati dalle prof.sse Piera De Maio e Maria Cantone – PNFI TIC
Scopo
Conoscere alcuni concetti fondamentali dell’informatica:
algoritmo, automa a programma, 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
UA.1 Problemi e algoritmi
1.1 introduzione intuitiva del concetto di problema
1.2 cenni sulle strategie per la risoluzione dei problemi
– soluzione di un problema: fase di analisi e algoritmi
1.2a Diagrammi a blocchi
1.2b Linguaggio di progetto
Esempi ed esercizi
UA.2 Automi esecutori
2.1 Automi esecutori
2.2 Caratteristiche di un automa
2.2a Concetto di sistema
2.2b Concetto di modello
2.3 Automi e classi di problemi
Esercitazioni
UA.3 Linguaggi
3.1 Sintassi e semantica dei linguaggi
3.1a Linguaggi nella comunicazione uomo-macchina
3.2 Linguaggi e automi
3.3 Linguaggi di programmazione con esempio
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
Un problema è incertezza cioè mancanza di informazioni
Problema è quando non sappiamo affrontare “normalmente” la vita; di solito il nostro comportamento è
meccanico, le nostre azioni sono frutto di abitudine ma nasce il problema quando un fatto imprevisto ci
causa dubbio, disagio perché ci impone una scelta con esigenza di riflettere cioè ragionare analizzando
dettagliatamente il pro e il contro delle decisioni al fine di sciogliere quel dubbio (analysis = “scioglimento,
risoluzione”).
Problemi e algoritmi
Un problema consta dei seguenti elementi
•Dati iniziali: ossia ciò che è noto (misura reale) e che indichiamo col
termine input
•Risultati o dati finali: gli elementi incogniti che si devono determinare e
che indicheremo con output
•Condizioni: le limitazioni o vincoli cui devono soggiacere i risultati
Il “che cosa” e il “come”:
•
il problema descrive “che cosa” si deve calcolare
•
l’algoritmo descrive “come” effettuare un calcolo
Problemi e algoritmi
Tipi di
problemi
Problemi di
decisione
Problemi di
ricerca
Problemi di
ottimizzazione
1.2 Strategie per la
risoluzione dei problemi
Problema
Verifica dei risultati
Interpretazione
Esecuzione
Modello
Procedimento risolutivo
(algoritmo)
1.2 Strategie per la
risoluzione dei problemi
Interpretazione
TOP
DOWN
GRAFICO
Suddivide il problema in tanti
sotto-problemi fino ad operazioni
elementari
Utilizza uno schema
grafico a segmenti
Esempio di Problema
Individuare il percorso più breve per andare a scuola (scomponendo
in sotto-problemi)
1.2 Strategie per la
risoluzione dei problemi
Algoritmo
Insieme dei comandi che definiscono una sequenza
finita di operazioni da eseguire mediante le quali si
risolve il problema
Deve essere :
finito
(numero limitato di passi: i comandi sono in numero finito
e vengono eseguiti un numero finito di volte);
definito
(ogni istruzione deve consentire un’interpretazione
univoca – non ambigua e precisa);
eseguibile
(la sua esecuzione deve essere possibile con gli
strumenti a disposizione);
deterministico
(ad ogni passo deve essere definita una ed una
sola operazione successiva).
Passo
Azione elementare che deve essere intrapresa per procedere nell’esecuzione
dell’algoritmo.
Questo concetto richiede di stabilire l’insieme delle azioni che l’esecutore dell’algoritmo (persona
o la macchina) è in grado di svolgere.
In altre parole, chi definisce un algoritmo deve accordarsi con chi lo dovrà eseguire circa le
istruzioni da utilizzare per descrivere l’algoritmo stesso.
Supponiamo ad esempio di dover
descrivere la ricetta per la preparazione
di una frittata: l’istruzione “mettere
quattro uova in una padella “ può essere
utilizzata solo se si è sicuri che la
persona che eseguirà la ricetta è
abbastanza esperta da capire che nella
padella deve essere versato il contenuto
delle uova che devono quindi venire rotte
in modo da eliminare i gusci.
Esempi di algoritmo
Preparazione di una torta
Ricetta: descrizione precisa di un procedimento “meccanico”
Esempi di algoritmo
Prelevamento col Bancomat
Una dettagliata sequenza di azioni/operazioni che devono essere
eseguite per risolvere una classe di problemi. Il nome deriva dal
matematico Uzbeko-Iraniano Al-Khawarizmi ‫( الخوارزم ي‬vissuto
intorno all'anno 800)
Esempio di algoritmo (continua)
L'algoritmo "va' dal salotto alla cucina" si compone in realtà delle seguenti
istruzioni:
– esci dal salotto
– curva a sinistra
– prosegui per il corridoio fino all'ultima porta sulla sinistra
– attraversa la porta a sinistra
L'algoritmo "attraversa la porta a sinistra" si compone di:
– controlla se la porta è aperta
– nel caso che la porta sia aperta salta il passo seguente
– apri la porta (cioè protendi braccio, afferra maniglia ….)
– avanza di un metro
Esempio di algoritmo
Un modo dettagliato di rappresentare l'algoritmo "attraversa la porta a sinistra"
specificando le sequenze sotto-algoritmiche è allora il seguente:
– controlla se la porta è aperta
– nel caso che la porta sia aperta salta il passo seguente
– apri la porta
─ protendi il braccio
─ afferra la maniglia
─ rotea la mano di 30 gradi in direzione antioraria
─ applica una pressione alla maniglia diretta di fronte a te
─ ...
– avanza di un metro
Esercizi
Spedire una lettera all’amico Giorgio che abita a Roma:
1 - Ordinare le seguenti operazioni:
- metto il foglio nella busta
- attacco il francobollo
- prendo una busta
- esco di casa
- imbuco la lettera nella cassetta
- aggiungo il c.a.p. di Roma
- prendo il francobollo
- vado all’ufficio postale
- scrivo sulla busta l’indirizzo di Giorgio
- chiudo la busta
- cerco il numero del c.a.p di Roma
- cerco l’indirizzo di Giorgio nella rubrica.
2 - Specificarne le sequenze sotto-algoritmiche
Esercizi
Considerando i seguenti concetti come il percorso che va dal problema al
programma, collegare con parole o frasi significative ogni parola alla
successiva e a quanti più concetti è possibile:
PROBLEMA, ALGORITMO, DIAGRAMMA A BLOCCHI, LIGUAGGIO DI
PROGETTO, AUTOMA, SISTEMA, MODELLO, LINGUAGGI DI
PROGRAMMAZIONE, PROGRAMMA
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
1.2a 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 e/o output, calcolo e/o di elaborazione, condizioni ed
individua un inizio ed una fine.
INPUT
ISTRUZIONI
CONDIZIONI
fine
1.2a Esempio di diagramma
a blocchi
inizio
Somma S di una
sequenza di N
numeri di valore
A variabile
N
S=
A
S= S+A
N=N-1
SI
N>
NO
S
fine
1.2b Linguaggio di progetto
Linguaggio di progetto o pseudo-codifica
È un linguaggio formale (linguaggio di progetto), con regole prive di ambiguità ed eccezioni che esprimono i vari
tipi di istruzioni. Viene definito pseudo-codifica o notazione lineare strutturata.
Generalmente utilizzato nella soluzione informatizzata di problemi più complessi.
inizio
leggi N
S

fai
leggi A
S
S+A
N
N-1
mentre ( N >  )
stampa S
fine
In modo più efficiente, al
posto di inizio/fine si
possono usare le parentesi
graffe
Algoritmo: media aritmetica
Diagramma a blocchi o flow-chart
Calcolo della media aritmetica di una sequenza di valori numerici
Algoritmo: media aritmetica
Linguaggio di progetto o pseudo-codifica
inizio
N
S 
fai
leggi V
SS+V
N  N +1
mentre (V > )
N  N-1
M
scrivi M
fine
Tecnica descrittiva
di più semplice
lettura/comprensione
2.1 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
2.2 Caratteristiche di un automa
Automi
Sono macchine 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 (condizione di funzionamento) 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
2.2a Concetto di sistema
Si dice sistema un insieme di elementi che interagiscono tra loro in modo
da formare una nuova entità (con un determinato scopo o funzionalità) che,
al verificarsi di un dato evento (azione) proveniente dall’ambiente esterno,
produce una risposta definita.
Un sistema non è un oggetto ma la definizione di un ambito (limiti di analisi): si sceglie cosa
nascondere (come in una scatola nera) e cosa evidenziare, interessati all’uso.
Rappresentazione sistemica (paradigma ingresso-uscita): descrizione a blocchi funzionali cioè
una rappresentazione grafica che distingue tra variabili in ingresso (grandezze su cui possiamo
agire per introdurre modifiche) e in uscita (risposte cioè grandezze che risultano influenzate e che
possiamo osservare per studiare sperimentalmente l’andamento) individuando gli eventuali
parametri costanti :
Per una classificazione rigorosa dei sistemi:
http://professoressa.altervista.org/Dispense_III/Classificazione%20sistemi.pdf
2.2b Concetto di modello
Modello
E’ uno schema teorico (una descrizione semplificata) 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’obiettivo
da raggiungere)
Modelli simbolici o matematici (danno una rappresentazione astratta mediante un
insieme di equazioni che legano le grandezze)
Modelli iconici (danno una rappresentazione fedele della realtà in scala ridotta)
Modello per trascurare gli aspetti superflui alla soluzione di problemi
Per una motivazione all’uso della modellizzazione ed una classificazione rigorosa dei modelli:
http://professoressa.altervista.org/Dispense_III/Apprendimento_Modelli.pdf
2.3 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, computer (automa a programma)
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.
Problemi e algoritmi
ESERCITAZIONI
Testo dei problemi on-line
http://utenti.multimania.it/pbiasotti/Dispense_III/Esercizi_da_problema_ad_algoritmo.p
df
Introduzione alla logica delle proposizioni: quesiti on-line
http://professoressa.altervista.org/Dispense_III/Cavalieri_furfanti.pdf
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
Problemi e algoritmi
Soluzione all’ ESERCITAZIONE (spazio degli stati)
Un bambino ha costruito sul tavolo una torre di tre
blocchi colorati, così disposti dall’alto in basso:
ROSSO-GIALLO-VERDE. Vuole capovolgerla, in
modo da avere VERDE-GIALLO-ROSSO e si serve
di una sola mano per spostare non più di un
blocchetto alla volta sul tavolo.
Il percorso ottenuto componendo in
successione le 4 transizioni elementari (nella
figura) conduce alla soluzione: una volta
arrivato alla configurazione in cui tutti i blocchi
poggiano sul tavolo, può completare in
sequenza la torre seguendo diverse alternative
(ne è illustrata una delle possibili)
Per approfondire: La Torre di Hanoi
3
Linguaggi
Il linguaggio è un sistema
codificato
di
segni
che
consente la comunicazione,
intesa
come
scambio
di
informazioni
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 (sistema
di segni) che devono essere conosciuti sia dalla
sorgente emittente che dal destinatario, altrimenti la
comunicazione non ha effetto
?
?
?
?
sorgente
destinatario
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
+ significato
Il gruppo dei suoni o di
lettere g/a/t/t/o
Nella storia si sono usate diverse forme di comunicazione
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 (di posizione)
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 tutte le regole che servono
per generare le forme di un linguaggio
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 in linguaggio comprensibile al calcolatore mediante le
quali si può risolvere il problema.
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
3.2 Linguaggi e automi
Programmi
general purpose
Sistema operativo
I principali software
Office Automation
•Word processor
Software di base,
controlla tutte le
risorse del computer,
necessita di un
linguaggio più vicino
al linguaggio
macchina
•Foglio di calcolo
(Assembler)
•Editor di suoni
•Sistemi di gestione base dati
•Programmi per la realizzazione di
presentazioni multimediali
•Programmi di grafica computerizzata
•Editor di pagine web
3.3 Linguaggi di
programmazione
Problema
Algoritmo
Programma
sorgente
Risultati
Dalla
formulazione del
problema alla
sua soluzione
Programma
traduttore
Elaborazione
Programma
oggetto
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
3.3 Linguaggi di programmazione
Fortran
Cobol
Algol
Basic
PHP
Principali linguaggi
Logo
PL1
Lisp
Pascal
C /C++
Java
Esempio: da problema a programma
Calcolo dell’interesse composto generalizzato: dall'analisi
all'implementazione, con richiami a concetti pregressi on-line
http://professoressa.altervista.org/Dispense_I/Analisi_Modellizza
zione_Es_Interessi.pdf (linguaggio C/C++)
Giocando con la torre di Hanoi on-line
http://professoressa.altervista.org/Dispense_III/La%20torre%20di
%20Hanoi_3D.pdf (linguaggio C/C++ o JavaScript)