Dal problema al programma
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
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
Problemi e algoritmi
Tipi di
problemi
Problemi di
decisione
Problemi di
ricerca
Problemi di
ottimizzazione
Strategie per la risoluzione
dei problemi
Problema
Interpretazione
Modello
Verifica dei risultati
Esecuzione
Procedimento
risolutivo (algoritmo)
Strategie per la risoluzione
dei problemi
Interpretazione
TOP
DOWN
GRAFICO
Suddivide il problema in tanti
piccoli sottoproblemi
Utilizza uno schema
grafico a segmenti
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 ).
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
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
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
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
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
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
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)
Linguaggi
Il linguaggio è un sistema
codificato
di
segni
che
consente la comunicazione,
intesa
come
scambio
di
informazioni
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
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
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
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.
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
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
Linguaggi di
programmazione
Problema
Algoritmo
Programma
sorgente
Risultati
Dalla
formulazione del
problema alla
sua soluzione
Programma
traduttore
Elaborazione
Programma
oggetto
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
Linguaggi di programmazione
Fortran
Cobol
Algol
Basic
PHP
Principali linguaggi
Logo
PL1
Lisp
Pascal
C /C++
Java
Cosa e' la programmazione?
•
•
•
•
•
•
La programmazione e' l'attivita' di sviluppare programmi per un calcolatore.
Lo scopo della scrittura di un programma e' la risoluzione di un problema.
Per risolvere un problema bisogna:
Formulare il problema (specifica dei requisiti) in modo più o meno formale
Capire il problema e scomporlo in parti gestibili (analisi del problema)
Progettare una soluzione (algoritmo)
Implementare la soluzione (scrittura del codice)
Testare la soluzione e correggere eventuali errori (verifica del programma,
testing e debugging)
Tenere sempre aggiornato il programma (manutenzione)
L’ALGORITMO
I DATI
LE ISTRUZIONI
LE STRUTTURE FONDAMENTALI
Informalmente, un algoritmo è una procedura ben definita che
serve per risolvere un dato problema
E’ una sequenza di passi che prende dei valori come input e
produce altri valori come output
Più precisamente, un algoritmo è un procedimento di calcolo ,
descrivibile con un numero finito di operazioni che conducono al
risultato
IL PROGRAMMA
Gli algoritmi sono astratti e per controllarne il funzionamento devono essere
realizzati con un qualche strumento concreto
• Ad esempio la descrizione di una ricetta di cucina è un algoritmo ma la preparazione della pietanza
è la realizzazione della ricetta.
E’ solo allora che si vede se la ricetta “funziona”
• Altro esempio può essere rappresentato da una qualsiasi formula matematica, che rappresenta,
nel linguaggio matematico un procedimento. Ma la bontà di tale regola può essere verificata solo
con dei veri e propri calcoli, sostituendo alle variabili dei veri numeri.
In ambito informatico, un algoritmo viene descritto tramite un programma, ossia un
testo scritto in uno specifico linguaggio detto linguaggio di programmazione per
essere eseguito da calcolatori elettronici
30
L’algoritmo e il programma
Ogni linguaggio di programmazione ha una sua sintassi ed una propria
rappresentazioni dei dati, e utilizza le proprie operazioni di manipolazione dei dati
Invece:
Le proprietà degli algoritmi sono talmente fondamentali, generali e robuste, da essere
indipendenti dalle caratteristiche di specifici linguaggi di programmazione o di particolari
calcolatori elettronici
Quindi:
PER RISOLVERE UN PROBLEMA E’ ASSOLUTAMENTE NECESSARIO TROVARE
UN PROCEDIMENTO RISOLUTIVO DESCRIVIBILE CON UN ALGORITMO, E
SOLO DOPO SI PUO’ PASSARE A SCRIVERE IL PROGRAMMA
32
PROGRAMMA = ISTRUZIONI + DATI
Un programma può essere visto come un manipolatore di dati:
a fronte di dati in ingresso che descrivono il problema producono dati in uscita come
risultato del problema
INPUT
(dati)
OUTPUT
PROCESSO
(istruzioni)
(dati)
Le operazioni sui dati sono le istruzioni.
I dati sono gli oggetti su cui vengono eseguite le istruzioni.
Tutti i linguaggi di programmazione prevedono un insieme di
dati e istruzioni
che il programmatore può utilizzare nella realizzazione dei propri programmi.
34
I DATI
I dati possono essere distinti in base a :
INPUT
• Utilizzo all’interno del processo
OUTPUT
LAVORO
INTERO
• Formato
NUMERICO
DECIMALE
ALFANUMERICO
• Valore assunto durante il processo
VARIABILE
COSTANTE
Questi aspetti dei dati devono essere definiti già nell’algoritmo,
in modo da poterli poi “tradurre” con la sintassi propria del linguaggio di
programmazione
35
LE ISTRUZIONI
Anche le istruzioni devono essere scritte rispettando la sintassi propria del
linguaggio di programmazione
Ogni linguaggio di programmazione ha le proprie istruzioni, ma tutti i linguaggi devono
possedere alcune istruzioni per compiere le azioni fondamentali
 Acquisire i dati su cui attivare il processo di elaborazione
input
• Comunicare all’esterno i risultati ottenuti
output
 Azioni di tipo aritmetico
- assegnare un valore ad una variabile
- utilizzare gli operatori aritmetici (+, -, /, *, %)
 Azioni di tipo logico
- Utilizzare gli operatori di relazione( =, <, >, <=, >=, <>) per
confrontare il contenuto di due variabili
- Utilizzare gli operatori logici (and, or, not)
assegnazione
confronto
36