11/03/2025

F O N DA M E N T I
D I I N F O R M AT I C A
E B A S I D I DAT I
I N G EG N E R I A
GESTIONALE
PROF. ROBERTO GENNA
A.A. 2024-2025

PROBLEM
SOLVING
COME DISCIPLINA

1
 11/03/2025

IL PROBLEM SOLVING

• Con il termine problem solving si identifica la

disciplina che si occupa di trovare procedimenti
generali per risolvere problemi.
• Quando si fa riferimento all’informatica, si occupa
di trovare algoritmi risolutivi e di descriverli in
modo adeguato mediante un agente di computo
(esecutore)

IL PROBLEM SOLVING

• Si possono identificare due ruoli fondamentali:

• Istruttore (soggetto umano):
– Analizza il problema, ne trova un metodo risolutivo che traduce
in un algoritmo
• Esecutore:
– Attua e realizza l’algoritmo, una volta che è stato (in
programma) in modo da essere interpretato opportunamente,
sulla base delle descrizione fornita dall’istruttore

2
 11/03/2025

IL PROBLEM SOLVING

Problema istruttore

Metodo
ANALISI
risolutivo

esecutore
DESCRIZIONE ALGORITMO

Descrizione
INTERPRETAZIONE interpretata
(codice)

ESECUZIONE Soluzione

METODO RISOLUTIVO

• Il modello di soluzione del problema è definito ad un alto livello

di astrazione. E’ composto da:
– Descrizione dell’insieme dei possibili input ammissibili
• Quali sono gli input?
• Quali valori devono assumere?
– Descrizione dell’output (soluzione) atteso
• Qual è l’output?
• Qual è la soluzione, dato un certo input?

– Inoltre occorre identificare le relazioni che intercorrono tra input e

output
• Come modificare e agire sull’input per ottenere l’output?

3
 11/03/2025

COME “RISOLVERE” UN
PROBLEMA?
• Analizzare il problema
– Identificare gli input
• Individuare gli obiettivi da raggiungere
– Descrivere le relazioni tra gli input e l’output
– Identificare altri “elementi” intermedi per ottenere dall’input l’output
• Descrivere
– le regole da rispettare
– i vincoli e le relazioni tra i dati i dati espliciti ed impliciti
– Eliminare i dettagli inutili ed ambigui
– Descrivere i passi da realizzare

ALGORITMO
7

ESECUTORE
• Ogni calcolatore è un esecutore.
– L’algoritmo è tradotto in un linguaggio comprensibile
dall’esecutore --> programma
– L’esecutore esegue una successione di azioni elementari
associate alle istruzioni (in un tempo finito e in modo
deterministico)
Metodo Risolutivo
(algoritmo)

ESECUTORE
DATI RISULTATI

4
 11/03/2025

PROBLEM
SOLVING
GLI APPROCCI

APPROCCI AL PROBLEM
SOLVING
• La metodologia e le tecniche per arrivare alla
descrizione di procedimenti risolutivi di problemi
complessi varia a seconda dell’approccio
considerato.
Nota. Si suppone che i problemi primitivi siano quelli
più semplici, direttamente risolvibili dall’esecutore (e
dall’istruttore)

10

5
 11/03/2025

APPROCCI AL PROBLEM
SOLVING
• Ci sono due approcci fondamentali per progettare
algoritmi:
– top-down
– bottom-up
• Sono logicamente opposti...
• ...ma in pratica si combinano insieme (anche nella
programmazione):
– ibrido o misto

11

APPROCCI AL PROBLEM
SOLVING
• Approccio top-down
– parte dai requisiti della specifica
– li decompone in sotto-requisiti
– procede per decomposizione, in modo gerarchico
– termina quando tutti i sotto-requisiti sono compiti elementari
• Approccio bottom-up
– parte dai compiti elementari (che si sanno già svolgere)
– li combina per crearne di (più) complessi
– … ottenendo strumenti generici, librerie, utility, soluzioni riutilizzabili
– assembla strumenti, utility, ecc. e compiti costruendo una soluzione ad
un compito più complesso
– termina quando il compito risolto coincide con la specifica

12

6
 11/03/2025

APPROCCIO TOP-DOWN
• Il metodo top down consiste nello scomporre il problema iniziale in due o
più problemi più semplici, risolti i quali (ipotesi) sappiamo ottenere la
soluzione al problema dato.
• Questo processo si dice scomposizione del problema (iniziale) in
sottoproblemi.
• I sottoproblemi individuati possono a loro volta essere ridotti a problemi
più semplici: il processo di scomposizione viene iterato, fino a
raggiungere problemi primitivi (la cui soluzione è nota all’esecutore)
• I problemi primitivi sono anche detti problemi elementari.
• Il programma è rappresentato dalla descrizione finale delle
scomposizioni.

• test (verifica)

13

APPROCCIO BOTTOM-UP
• Il metodo bottom up consiste nel partire dalla conoscenza
dei problemi primitivi che l’esecutore sa risolvere e
identificare composizioni e/o sequenze di tali soluzioni per
ottenere un problema risolvibile che va verso la soluzione
del problema dato.
• test (verifica) della soluzione al problema risolvibile.
• Se ciò non è sufficiente si deve trovare (per aggregazioni e
giustapposizioni successive) una sequenza appropriata di
problemi primitivi e problemi risolvibili, la cui soluzione
equivale alla soluzione del problema dato.
• test (verifica) della soluzione al problema dato.
• il programma finale sarà rappresentato dalla descrizione
della sequenza di problemi primitivi da risolvere.

14

7
 11/03/2025

ESEMPIO: AREA DI UNA

CAMPANA (TOP-DOWN)
Scomposizione del problema in
tre sottoproblemi Sottoproblema 1
Problema
r soluzione elementare:
s = ½ π r2

Sottoproblema 2
h2 soluzione elementare:
b
s = b h2

Sottoproblema 3
soluzione elementare:
s = ?? soluzione elementare:
s = ??

15

ESEMPIO: AREA DI UNA

CAMPANA (TOP-DOWN)
Scomposizione del sottoproblema 3 in tre
b ulteriori sottoproblemi

h1
B

Sottoproblema 3
h1
soluzione effettiva: h1 h1
b
s = ½ (½(B–b) h1) +
b h1 + ½ (B–b) ½ (B–b)
Sottoproblema 3.3
½ (½(B–b) h1) Sottoproblema 3.1 Sottoproblema 3.2
soluzione elementare: soluzione elementare:
soluzione elementare:
s = b h1 s =½ (½(B–b) h1)
s =½ (½(B–b) h1)

Composizione delle soluzioni dei tre

sottoproblemi 3.1, 3.2 e 3.3 per risolvere il
sottoproblema 3

16

8
 11/03/2025

ESEMPIO: AREA DI UNA

CAMPANA (TOP-DOWN)
Sottoproblema 1
Problema r soluzione elementare:
s = ½ π r2
r=b/2 Composizione delle
soluzioni dei tre
sottoproblemi 1, 2 e 3 Sottoproblema 2
h2 per risolvere il problema
b h2 soluzione elementare:
originario b
s = b h2
h1
B

soluzione effettiva: Sottoproblema 3

h1
soluzione effettiva:
s = ½ π r2 + B
b h2 + s = ½ (½(B–b) h1) +
½ (½(B–b) h1) + b h1 +
b h1 + ½ (½(B–b) h1)
½ (½(B–b) h1)

17

ESEMPIO: RICONOSCERE UN
NUMERO PRIMO (BOTTOM-UP)
Un numero n è primo se e solo se:
n è divisibile solo per sé stesso e per il numero 1

OPERAZIONE ELEMENTARE:
• divisione (resto)

CONCETTO NECESSARIO:
• divisibilità

18

9
 11/03/2025

ESEMPIO: RICONOSCERE UN
NUMERO PRIMO (BOTTOM-UP)
COMPITO:
• Un numero n è divisibile per un numero d se e
solo se il resto della divisione n/d è ZERO
OPERAZIONE (nuova funzione/funzionalità):
• F ( n , d ) = divisibile ( n , d )
• input: n,d numeri naturali
• output: VERO o FALSO (tipo logico)
• algoritmo: SE resto di n/d vale 0
ALLORA risultato è VERO
ALTRIMENTI risultato è FALSO
19

ESEMPIO: RICONOSCERE UN
NUMERO PRIMO (BOTTOM-UP)
Un numero n è primo se e solo se:
n è divisibile solo per sé stesso e per il numero 1

A partire dalla (soluzione della) nuova operazione:

• divisibile(n,d)
riscrivo il problema iniziale:
• non esiste un numero d’ tale che
divisibile(n,d’) valga VERO

20

10
 11/03/2025

ESEMPIO: RICONOSCERE UN
NUMERO PRIMO (BOTTOM-UP)
Un numero n è primo se e solo se:
• non esiste un numero d’ tale che divisibile(n,d’)=VERO

Riformulo il problema:
• per ogni numero d diverso da n e da 1, risulta
divisibile(n,d) = FALSO

Ma allora non esiste un algoritmo?!

• «per ogni» significa provare tutti i numeri
naturali d diversi da n e da 1 (infiniti casi)

21

ESEMPIO: RICONOSCERE UN
NUMERO PRIMO (BOTTOM-UP)
CONOSCENZA (dalla matematica):
• Per ogni numero d’ > n divisibile(n,d’)=FALSO
Riformulo il problema:
• per ogni numero d’ < n diverso da n e da 1, …
• ∀ numero naturale d’ ∈ [ 2 ; n [, risulta
divisibile(n,d’) = FALSO

Ma allora esiste un algoritmo!

• verifico i numeri da 2 a n-1 (numero finito di casi)
22

11
 11/03/2025

ESEMPIO: RICONOSCERE UN
NUMERO PRIMO (BOTTOM-UP)

Algoritmo (idea):
• verifico i numeri d da 2 a n-1;
• se risulta divisibile(n,d) = VERO
allora termino (output: n non è un numero primo)
• quando ho finito tutte le verifiche da 2 a n-1
allora termino (output: n è un numero primo)

23

ESEMPIO: RICONOSCERE UN
NUMERO PRIMO (BOTTOM-UP)
ALGORITMO (bozza):
1. provo d = 2
2. calcolo divisibile(n,d)
3. se risulta divisibile(n,d) = VERO
3.1 allora termino
(output: n non è un numero primo)
3.2 altrimenti provo d successivo e vado al
passo 2
4. (se sono arrivato qui…) termino
(output: n è un numero primo)

24

12
 11/03/2025

FO R M A LI ZZA ZI O NE
D I A LG O R I T M I
D A L L’ A L G O R I T M O A L P R O G R A M M A

25

RAPPRESENTAZIONE DEGLI
ALGORITMI
algoritmo

• Linguaggio naturale
• Diagramma a blocchi
• Pseudo codice
• Linguaggio di programmazione

programma

26

13
 11/03/2025

LINGUAGGIO NATURALE

• Nella risoluzione di un problema, il primo passo verso la modellazione

di un algoritmo è cercare di descrivere le azioni da fare in linguaggio
naturale
• Es. Trovare il massimo tra due numeri
• Passi:
– Prendo i due numeri
– Faccio la differenza
– Se il risultato è maggiore di 0 allora il primo numero è il massimo
– …

27

DIAGRAMMA A BLOCCHI
(FLOW-CHART)
• Consente la modellazione grafica Inizio

di un algoritmo
Leggi
• A volta fornisce una alternativa allo xey P1 e P2

pseudo-codice.
d←x–y
P3
• E’ molto immediato: esso consente di
descrivere un algoritmo concentrandosi Sì No
d>0?
principalmente sulla sequenza delle P4

operazioni di cui si compone. Scrivi Scrivi

“max è x” “max è y”
P5 P6

Fine
P7

28

14
 11/03/2025

PSEUDO-CODICE
• La rappresentazione dell’algoritmo in forma testuale.
• Spesso i costrutti di controllo sono descritti con la forma
e le parole chiave corrispondenti a quelle dei linguaggi di
programmazione, mentre le operazioni possono essere
descritte in modo informale e sintetico.
• La somiglianza strutturale con i
programmi definitivi rende le
leggi alfa, beta
descrizioni degli algoritmi con prod = 0
pseudo-codice molto adatte while alfa ≠ 0
prod = prod + beta;
alle fasi di sviluppo dei programmi alfa = alfa – 1;
stessi. stampa prod;

29

INFINE..
IL LINGUAGGIO DI
PROGRAMMAZIONE
• Passare dallo pseudocodice al • Si tratta di convertire le
linguaggio di programmazione istruzioni (in pseudocodice) in
desiderato, diventa immediato effettive istruzioni secondo la
sintassi del linguaggio di
from math import sqrt programmazione
x = float(input("x: "))
y = float(input("y: "))
segment1L = float(input("Length of 1st segment: "))
segment1Sp = float(input("Speed along 1st segment: "))
segment2Sp = float(input("Speed along 2nd segment: "))

segment1T = segment1L / segment1Sp

segment2L = sqrt((x - segment1L) ** 2 + y ** 2)
segment2T = segment2L / segment2Sp

print("Total travel time: ")

print(segment1T + segment2T)

30

15
 11/03/2025

DIAGRAMMA RIASSUNTIVO
Linguaggio:
Sequenza statica metodo per descrivere
un algoritmo
Algoritmo:
sequenza di passi
per la realizzazione
di un compito Esecutore:
Sequenza dinamica entità che comprende
il linguaggio ed
esegue i passi

Specifica: Casi di test:

Dati di ingresso esempi concreti di
descrizione di un problema
dati di ingresso e e dati di uscita dati di ingresso e
dati di uscita corrispondenti uscite attese

31

16