Appunti · InformaticaIT · Maturità

Algoritmi, problem solving e pseudocodifica

Un algoritmo è una sequenza finita e non ambigua di passi che, a partire da dati di ingresso, produce in un numero finito di operazioni la soluzione di un problema. Questo appunto guida dall'analisi del problema alla sua formalizzazione, presentando le proprietà fondamentali degli algoritmi, le strategie di problem solving (analisi, scomposizione top-down, raffinamenti successivi), le tre strutture di controllo della programmazione strutturata (sequenza, selezione, iterazione) garantite dal teorema di Böhm-Jacopini, e i due linguaggi di descrizione — pseudocodice e diagrammi di flusso. Si chiude con i primi cenni a correttezza ed efficienza, valutata contando le operazioni eseguite.

5sezionica. 18min di lettura3competenzeLivelloBase 1 · Standard 3 · Approfondimento 1Verificato · 06/2026

T·0111 / 14

Profilo d’esame

Affrontare e risolvere problemi elaborando opportune strategie algoritmiche e formalizzandole con pseudocodice e diagrammi di flussoComprendere il ruolo dell'informatica come strumento di modellizzazione e risoluzione di problemiCogliere il rapporto tra il problema, il modello individuato e la sua soluzione algoritmica, valutandone correttezza ed efficienza

Operatori:analizzaspiegadescrivideterminaclassificaconfrontaillustragiustificainterpretatraduci

livello base

È richiesto saper analizzare un problema, scomporlo e descriverne la soluzione con le tre strutture di controllo, in pseudocodice o con un diagramma di flusso corretto.

livello avanzato

Nell'opzione Scienze Applicate si aggiungono la dimostrazione informale di correttezza (invarianti, casi limite) e la valutazione dell'efficienza tramite il conteggio delle operazioni e il confronto fra algoritmi alternativi.

Profondità

Schrift

Inhalt · 5 sezioni

Algoritmi, problem solving e pseudocodifica

Dal problema all'algoritmo: analisi e modellizzazione#

BasisOSA-informatica-fondamenti-algoritmi — strategie di problem solving: analisi del problema, dati di ingresso/uscita, scomposizione (top-down) e raffinamenti successivi

Il processo di problem solving: dal problema all'algoritmo

Risolvere un problema con il calcolatore significa, prima ancora di scrivere una sola istruzione, comprenderlo a fondo e descriverne la soluzione come procedimento meccanizzabile: questa è l'attività di problem solving, di cui l'algoritmo è il prodotto finale. Il punto di partenza non è il codice, ma l'analisi del problema, cioè la chiara distinzione fra ciò che si conosce e ciò che si vuole ottenere.

L'analisi individua anzitutto i dati di ingresso (input) — le informazioni note o fornite — e i dati di uscita (output) — i risultati attesi — collegandoli attraverso le relazioni che governano il problema. Definire con precisione input e output significa già delimitare il problema: una specifica ambigua porta inevitabilmente a un algoritmo sbagliato, perché la macchina esegue alla lettera ciò che le si dice, non ciò che si intendeva dire.

I problemi complessi si affrontano con la strategia top-down: si parte dal problema nel suo insieme e lo si scompone in sottoproblemi più semplici, ciascuno dei quali può essere affrontato e risolto separatamente. Questo procedimento di raffinamenti successivi (stepwise refinement) prosegue finché ogni sottoproblema è così elementare da tradursi direttamente in poche istruzioni; la composizione delle soluzioni parziali ricostruisce la soluzione complessiva.

Il prodotto dell'analisi è il modello del problema: una rappresentazione astratta che trascura i dettagli irrilevanti e conserva solo ciò che serve a calcolare la soluzione. Solo dopo aver costruito il modello e progettato l'algoritmo ha senso passare alla pseudocodifica e, infine, alla codifica in un linguaggio di programmazione. Saltare l'analisi per scrivere subito codice è l'errore più frequente e più costoso.

Esempio svolto

Analisi e scomposizione di un problema

Analizza il problema «calcolare la media aritmetica dei voti di uno studente»: individua i dati di ingresso e di uscita, esprimi la relazione che li lega e scomponi il problema in sottoproblemi elementari.

Individuazione dell'output
Il risultato richiesto è un solo valore: la media aritmetica dei voti, un numero reale.
Individuazione dell'input
Servono i voti dello studente, cioè una sequenza di n valori numerici, e implicitamente la loro quantità n.
Relazione tra input e output
La media è la somma dei voti divisa per il loro numero.
Scomposizione top-down
Sottoproblema 1: leggere i voti e contarli (determinare n). Sottoproblema 2: calcolare la somma S dei voti. Sottoproblema 3: dividere S per n e restituire il risultato (con la condizione n > 0 per evitare la divisione per zero).

Risultato: Output: media M; input: i voli v_1, ..., v_n e il loro numero n; relazione M = S/n; il problema si scompone in «leggi e conta», «somma», «dividi e restituisci».

Errori frequenti

Iniziare a scrivere l'algoritmo senza aver prima identificato input e output: si finisce per «inseguire» il problema invece di risolverlo, producendo soluzioni incomplete o incoerenti.
Confondere il problema (la specifica «che cosa») con l'algoritmo (la procedura «come»): possono esistere molti algoritmi diversi per lo stesso problema, e descriverne uno non equivale a definire il problema.

Ripasso attivo

Dato il problema «calcolare la media aritmetica dei voti di uno studente», svolgi l'analisi: indica i dati di ingresso e di uscita, scrivi la relazione che li lega e scomponi il problema top-down in almeno tre sottoproblemi elementari.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Proprietà degli algoritmi e formalismi di rappresentazione#

StandardOSA-informatica-fondamenti-algoritmi — concetto di algoritmo: proprietà (finitezza, determinismo, generalità, eseguibilità) e formalismi di rappresentazione

Le quattro proprietà fondamentali di un algoritmo

Non ogni elenco di istruzioni è un algoritmo: perché lo sia, deve soddisfare alcune proprietà fondamentali. La finitezza richiede che l'algoritmo termini dopo un numero finito di passi; il determinismo (o non ambiguità) impone che ogni passo sia definito in modo univoco, così che la stessa sequenza di passi a partire dagli stessi dati produca sempre lo stesso risultato.

La generalità richiede che l'algoritmo risolva non un singolo caso, ma un'intera classe di problemi dello stesso tipo: l'algoritmo della media deve funzionare per qualunque insieme di voti, non solo per uno specifico. L'eseguibilità (o realizzabilità) impone infine che ogni passo sia un'operazione effettivamente compibile dall'esecutore, con le risorse a sua disposizione.

A queste si affianca la richiesta che i dati di ingresso e di uscita siano ben definiti: un algoritmo riceve zero o più input e produce almeno un output. Un procedimento che non termina (un ciclo infinito), che contiene un passo ambiguo, o che richiede un'operazione impossibile, non è un algoritmo corretto, anche se a prima vista «sembra» risolvere il problema.

Lo stesso algoritmo può essere descritto con formalismi diversi: il linguaggio naturale (chiaro ma ambiguo), il diagramma di flusso (rappresentazione grafica), lo pseudocodice (a metà fra linguaggio naturale e linguaggio di programmazione) e infine un linguaggio di programmazione (eseguibile dalla macchina). I formalismi intermedi — pseudocodice e diagrammi di flusso — servono a progettare e comunicare l'algoritmo senza vincolarsi alla sintassi di uno specifico linguaggio.

Esempio svolto

Verifica delle proprietà su un procedimento dato

È dato il seguente procedimento: «parti da x = 1; finché x è diverso da 0, aumenta x di 1; quando x = 0 stampa x». Stabilisci se è un algoritmo, verificando le quattro proprietà fondamentali.

Eseguibilità
Ogni passo (assegnazione, confronto, incremento, stampa) è un'operazione elementare effettivamente compibile: la proprietà è soddisfatta.
Determinismo
Ogni passo è definito in modo univoco, senza ambiguità: la proprietà è soddisfatta.
Finitezza
Partendo da x = 1 e incrementando, x assume i valori 2, 3, 4, ... e non vale mai 0: la condizione di uscita non si verifica mai e il ciclo non termina.
Conclusione
Poiché la finitezza è violata (ciclo infinito), il procedimento NON è un algoritmo, pur sembrando ben definito.

Risultato: Non è un algoritmo: viola la proprietà di finitezza perché la condizione di terminazione non è mai raggiunta.

Errori frequenti

Confondere il determinismo con la generalità: il primo riguarda l'univocità di ogni passo, la seconda l'applicabilità a un'intera classe di casi.
Ritenere algoritmo un procedimento che non garantisce la terminazione: senza la proprietà di finitezza non si ha un algoritmo, ma solo una procedura potenzialmente infinita.

Ripasso attivo

Per ciascuna delle quattro proprietà fondamentali (finitezza, determinismo, generalità, eseguibilità), proponi un esempio di procedimento che la viola e spiega perché, di conseguenza, non può essere considerato un algoritmo.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Le strutture di controllo: sequenza, selezione, iterazione#

StandardOSA-informatica-fondamenti-algoritmi — strutture di controllo fondamentali: sequenza, selezione, iterazione (teorema di Böhm-Jacopini)

Le tre strutture di controllo: sequenza, selezione, iterazione

Il teorema di Böhm-Jacopini (1966) stabilisce un risultato fondante: qualunque algoritmo può essere espresso utilizzando soltanto tre strutture di controllo elementari — la sequenza, la selezione e l'iterazione — combinate fra loro. È il fondamento teorico della programmazione strutturata, la metodologia, promossa anche da Edsger Dijkstra, che bandisce il salto incondizionato (goto) a favore di un flusso del controllo ordinato e leggibile.

La sequenza è la struttura più semplice: le istruzioni vengono eseguite una dopo l'altra, nell'ordine in cui sono scritte. La selezione (o struttura condizionale) sceglie quale blocco di istruzioni eseguire in base al valore di una condizione: nella forma a due rami (se condizione allora A altrimenti B) si esegue A se la condizione è vera, B se è falsa; esiste anche la forma a un ramo solo (senza altrimenti).

L'iterazione (o ciclo) ripete un blocco di istruzioni finché una condizione resta verificata. Si distinguono il ciclo a condizione iniziale (mentre condizione esegui blocco), che controlla la condizione prima di ogni ripetizione e può quindi non eseguire mai il blocco, e il ciclo a condizione finale (ripeti blocco finché condizione), che esegue il blocco almeno una volta. Quando il numero di ripetizioni è noto in anticipo si usa il ciclo enumerativo (per i da 1 a n).

Ogni ciclo deve garantire la terminazione: deve esistere una grandezza (il contatore o la condizione) che evolve a ogni iterazione fino a far cessare la ripetizione. Un ciclo il cui corpo non modifica mai le variabili della condizione di controllo è un ciclo infinito e viola la finitezza. La corretta combinazione di queste tre strutture — eventualmente annidate l'una nell'altra — è sufficiente a esprimere qualunque procedimento calcolabile.

S = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}

Somma dei primi n interi

La somma accumulata dal ciclo enumerativo coincide con la formula chiusa di Gauss: un utile controllo di correttezza del risultato dell'iterazione.

Esempio svolto

Somma dei primi n interi con un ciclo enumerativo

Scrivi in pseudocodice un algoritmo che, dato un intero n > 0, calcoli e stampi la somma 1 + 2 + ... + n usando un ciclo enumerativo, e indica la grandezza che garantisce la terminazione.

Inizializzazione
Si pone una variabile accumulatore S a 0 prima del ciclo.
Ciclo enumerativo
Per i da 1 a n: S <- S + i. Il contatore i parte da 1 e cresce a ogni iterazione fino a n.
Terminazione
La grandezza che garantisce la terminazione è il contatore i: poiché aumenta di 1 a ogni passo e n è finito, dopo esattamente n iterazioni si ha i > n e il ciclo termina.
Verifica con la formula di Gauss
Per n = 5 il ciclo accumula 1+2+3+4+5 = 15; la formula chiusa conferma 5*6/2 = 15.

Risultato: leggi n; S <- 0; per i da 1 a n esegui S <- S + i; stampa S. Per n = 5 il risultato è 15, in accordo con n(n+1)/2.

Errori frequenti

Dimenticare di aggiornare, all'interno del corpo del ciclo, la variabile che compare nella condizione: il ciclo non termina mai (ciclo infinito).
Confondere il ciclo a condizione iniziale (mentre) con quello a condizione finale (ripeti...finché): il secondo esegue il corpo sempre almeno una volta, il primo può non eseguirlo affatto.

Ripasso attivo

Scrivi in pseudocodice un algoritmo che, dato un intero n > 0, calcoli e stampi la somma 1 + 2 + ... + n utilizzando un ciclo enumerativo; indica esplicitamente quale grandezza garantisce la terminazione.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Pseudocodice e diagrammi di flusso#

StandardOSA-informatica-fondamenti-algoritmi — pseudocodifica e diagrammi di flusso (flowchart); variabili, costanti, espressioni

Diagramma di flusso: numero pari o dispari

Per descrivere un algoritmo in modo preciso ma indipendente da uno specifico linguaggio di programmazione si usano due formalismi complementari. Lo pseudocodice è una notazione testuale che combina la chiarezza del linguaggio naturale con la struttura del codice: usa parole chiave fisse (leggi, scrivi, se...allora...altrimenti, mentre, per) e l'indentazione per evidenziare i blocchi, ma non è vincolato a una sintassi rigida.

Il diagramma di flusso (flowchart) è la rappresentazione grafica dell'algoritmo: ogni tipo di azione ha un simbolo convenzionale. L'ovale (o cerchio) indica inizio e fine; il parallelogramma le operazioni di ingresso/uscita (leggi, scrivi); il rettangolo le elaborazioni (assegnazioni, calcoli); il rombo le decisioni, da cui escono due rami etichettati Vero e Falso. Le frecce indicano il flusso del controllo, cioè l'ordine di esecuzione.

In entrambi i formalismi compaiono gli elementi base dell'elaborazione: le variabili, contenitori con un nome che custodiscono un valore modificabile; le costanti, valori fissi; e le espressioni, combinazioni di variabili, costanti e operatori (aritmetici, relazionali, logici) che producono un valore. L'assegnazione (di solito indicata con la freccia <-) attribuisce a una variabile il valore di un'espressione: x <- x + 1 calcola prima x + 1 e poi lo memorizza in x.

Pseudocodice e diagramma di flusso descrivono lo stesso algoritmo a livelli diversi: il flowchart è più immediato e visivo, utile per coglierne la struttura logica; lo pseudocodice è più compatto e si traduce quasi direttamente in un linguaggio di programmazione. Entrambi devono rispettare la programmazione strutturata, impiegando solo le tre strutture di controllo e mantenendo un unico punto di ingresso e un unico punto di uscita per ogni blocco.

Esempio svolto

Pseudocodice di un algoritmo con selezione

Scrivi lo pseudocodice di un algoritmo che legge un intero n e stampa «pari» se n è divisibile per 2, «dispari» altrimenti, coerente con il diagramma di flusso della Fig. 4.

Ingresso
leggi n (il dato di ingresso è un numero intero).
Condizione di selezione
Si calcola il resto della divisione intera di n per 2 con l'operatore modulo: la condizione è n mod 2 = 0.
Rami della selezione
se n mod 2 = 0 allora scrivi «pari» altrimenti scrivi «dispari».
Verifica su un caso
Per n = 7: 7 mod 2 = 1, diverso da 0, quindi si esegue il ramo altrimenti e si stampa «dispari» (corretto).

Risultato: leggi n; se n mod 2 = 0 allora scrivi «pari» altrimenti scrivi «dispari». Per n = 7 stampa «dispari».

Errori frequenti

Usare il simbolo sbagliato nel flowchart: per esempio un rettangolo (elaborazione) per una decisione, che invece richiede il rombo con due rami etichettati.
Interpretare l'assegnazione come un'uguaglianza matematica: x <- x + 1 non è un'equazione impossibile, ma l'istruzione «aumenta x di 1»; confondere = (confronto) con <- (assegnazione) è un errore tipico.

Ripasso attivo

Disegna il diagramma di flusso e scrivi lo pseudocodice di un algoritmo che legge un numero intero e stampa la parola «pari» se è divisibile per 2, «dispari» altrimenti.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Cenni a correttezza ed efficienza#

VertiefungOSA-informatica-fondamenti-algoritmi — cenni alla complessità e all'efficienza di un algoritmo (correttezza, numero di operazioni)

Crescita del numero di confronti: ricerca lineare (~n) e ricerca binaria (~log2 n)

Un algoritmo non basta che termini: deve essere corretto, cioè produrre l'output giusto per ogni input ammissibile, in accordo con la specifica del problema. La correttezza si argomenta verificando che l'algoritmo si comporti bene nei casi tipici e, soprattutto, nei casi limite (input vuoto, valore nullo, valore minimo o massimo): è proprio sui casi limite che gli algoritmi apparentemente giusti falliscono più spesso.

Accertata la correttezza, ci si chiede quanto l'algoritmo sia efficiente, cioè quante risorse consumi. L'efficienza si valuta principalmente in termini di tempo (numero di operazioni elementari eseguite) e di spazio (memoria occupata). Per non dipendere dalla velocità della macchina, si conta il numero di operazioni fondamentali in funzione della dimensione n dell'input, ottenendo una stima indipendente dall'hardware.

Lo stesso problema può ammettere algoritmi con efficienza molto diversa. Cercare un elemento in una sequenza di n dati con la ricerca lineare richiede, nel caso peggiore, n confronti: il costo cresce proporzionalmente a n (costo lineare). Se i dati sono ordinati, la ricerca binaria dimezza a ogni passo lo spazio di ricerca e richiede circa log2(n) confronti (costo logaritmico), molto più conveniente per n grande.

Per confrontare gli algoritmi si distingue il caso migliore, il caso peggiore e il caso medio, e ci si concentra di norma sul caso peggiore, che garantisce un limite superiore al costo. L'ordine di grandezza del numero di operazioni (costante, logaritmico, lineare, quadratico, esponenziale...) descrive come il costo cresce all'aumentare di n e costituisce il criterio principale per scegliere, fra più algoritmi corretti, quello da preferire.

C_{\text{lin}}^{\text{peggiore}} = n

Ricerca lineare (caso peggiore)

Nel caso peggiore (elemento assente o in ultima posizione) la ricerca lineare confronta x con tutti gli n elementi: il costo cresce linearmente con n.

C_{\text{bin}} \approx \lfloor \log_2 n \rfloor + 1

Ricerca binaria (dati ordinati)

Dimezzando a ogni passo lo spazio di ricerca, il numero di confronti cresce come il logaritmo in base 2 di n: per n = 1000 sono circa 10 confronti contro i 1000 della ricerca lineare.

Esempio svolto

Costo della ricerca lineare e confronto con la binaria

Scrivi la ricerca lineare di un valore x in una sequenza di n elementi, determina il numero di confronti nel caso peggiore e confrontalo con la ricerca binaria su dati ordinati per n = 1000.

Algoritmo (pseudocodice)
trovato <- falso; per i da 1 a n esegui: se A[i] = x allora trovato <- vero. Si scorre l'intera sequenza confrontando ogni elemento con x.
Caso peggiore della ricerca lineare
Se x non è presente (o è l'ultimo elemento), si eseguono n confronti: il costo è proporzionale a n.
Costo della ricerca binaria
Su dati ordinati la ricerca binaria dimezza lo spazio a ogni passo: il numero di confronti è circa il logaritmo in base 2 di n.
Confronto numerico per n = 1000
Lineare: fino a 1000 confronti. Binaria: log2(1000) ~ 9.97, quindi circa 10 confronti. La binaria è circa cento volte più conveniente, ma richiede dati ordinati.

Risultato: La ricerca lineare costa fino a n = 1000 confronti nel caso peggiore; la ricerca binaria ne richiede circa 10 (~log2 1000), risultando nettamente più efficiente sui dati ordinati.

Errori frequenti

Misurare l'efficienza con il tempo in secondi misurato su una macchina specifica: tale valore dipende dall'hardware e non confronta gli algoritmi; va contato invece il numero di operazioni in funzione di n.
Trascurare i casi limite (sequenza vuota, n = 0, elemento assente) nel valutare la correttezza: un algoritmo corretto sui casi «normali» può fallire proprio lì.

Ripasso attivo

Per una sequenza di n elementi, scrivi lo pseudocodice della ricerca lineare di un valore x, conta il numero di confronti nel caso peggiore e confrontalo con il costo della ricerca binaria su dati ordinati per n = 1000.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Riferimenti e fonti

Fonti

Ministero dell'Istruzione e del Merito (MIM)

Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) — Obiettivi Specifici di Apprendimento

Algoritmi, problem solving e pseudocodifica

Punti chiave

Analisi e scomposizione di un problema

Punti chiave

Verifica delle proprietà su un procedimento dato

Punti chiave

Somma dei primi n interi con un ciclo enumerativo

Punti chiave

Pseudocodice di un algoritmo con selezione

Punti chiave

Costo della ricerca lineare e confronto con la binaria

Fonti

Algoritmi, problem solving e pseudocodifica

Punti chiave

Analisi e scomposizione di un problema

Punti chiave

Verifica delle proprietà su un procedimento dato

Punti chiave

Somma dei primi n interi con un ciclo enumerativo

Punti chiave

Pseudocodice di un algoritmo con selezione

Punti chiave

Costo della ricerca lineare e confronto con la binaria

Fonti