Dal problema al programma
Unità di apprendimento
Tratte da moduli presentati dalle prof.sse Piera De Maio e Maria Cantone – PNFI TIC
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; 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
Strategie per la risoluzione
dei problemi
Problema
Verifica dei risultati
Interpretazione
Esecuzione
Modello
Procedimento risolutivo
(algoritmo)
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)
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.
• bisogna accordarsi con chi lo dovrà eseguire stabilendo l’insieme delle
azioni che l’esecutore dell’algoritmo è in grado di svolgere
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)
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 e/o output, calcolo e/o di elaborazione, condizioni ed
individua un inizio ed una fine.
INPUT
ISTRUZIONI
CONDIZIONI
fine
Esempio di diagramma a blocchi
inizio
Somma S di una
sequenza di N
addendi di valore
A variabile
N
S=
A
S= S+A
N=N-1
SI
N>
NO
S
fine
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
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 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
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
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
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.