1.
Applicazioni, algoritmi e loro relazione
Un’applicazione, o programma applicativo, è un software che può essere
eseguito da un computer ed è composto da una serie di istruzioni progettate
per risolvere uno specifico problema o svolgere un compito determinato. Può
operare direttamente a beneficio dell’utente finale, come nel caso di un
elaboratore di testi o di un’app di navigazione, oppure fornire servizi ad altre
applicazioni. Un programma applicativo non lavora da solo, ma utilizza i
servizi messi a disposizione dal sistema operativo per accedere alle risorse
hardware, come CPU, memoria e dispositivi di input/output. Per questa
ragione, in genere, i programmi sono sviluppati con riferimento a uno
specifico sistema operativo.
Dietro ogni applicazione vi è almeno un algoritmo, cioè una procedura ben
definita che descrive come passare dai dati in ingresso al risultato
desiderato. Ad esempio, un programma può implementare un algoritmo per
trovare il percorso più breve tra due punti su una mappa, un algoritmo per
convertire un numero intero in binario o esadecimale, oppure un algoritmo
per filtrare in una rubrica tutti gli indirizzi email che terminano con una certa
stringa. L’applicazione, nel suo complesso, è dunque un insieme ordinato di
algoritmi che cooperano per fornire le funzionalità richieste.
2. Definizione e proprietà fondamentali di un algoritmo
Un algoritmo può essere definito come una sequenza finita di operazioni non
ambigue, eseguibili passo dopo passo, progettate per risolvere uno specifico
problema. Ogni algoritmo riceve alcuni dati in ingresso e produce alcuni dati
in uscita, che rappresentano la soluzione del problema in esame. Le istruzioni
che compongono l’algoritmo devono poter essere eseguite dall’esecutore
previsto, che può essere un essere umano o una macchina, e ciascun passo
deve essere completato in un tempo finito in modo deterministico.
Esistono tre criteri fondamentali che ogni algoritmo deve soddisfare. In primo
luogo, l’eseguibilità: ogni azione descritta deve essere concretamente
realizzabile dall’esecutore, senza richiedere capacità non specificate. In
secondo luogo, la non ambiguità: ogni istruzione deve avere un significato
univoco, così che esecutori diversi la interpretino allo stesso modo. In terzo
luogo, la finitezza: per ogni insieme valido di dati in ingresso, l’algoritmo
deve terminare dopo un numero finito di passi, anche quando la risposta
corretta è “nessuna soluzione”.
Vi sono poi altri requisiti auspicabili. La generalità richiede che l’algoritmo sia
applicabile a tutti i dati appartenenti al dominio per cui è stato definito, non
solo a pochi casi particolari. Il determinismo implica che le regole siano tali
da produrre sempre lo stesso risultato a partire dagli stessi dati iniziali.
L’efficienza, infine, riguarda l’uso parsimonioso delle risorse, in termini di
tempo di esecuzione e di memoria, risultato cruciale nell’implementazione su
calcolatore.
Un esempio intuitivo di algoritmo è una ricetta di cucina, come quella di una
torta di mele: essa elenca ingredienti (dati in ingresso) e una successione di
passi da compiere per ottenere il dolce (uscita). Se gli ingredienti sono
corretti e i passi sono seguiti nell’ordine giusto, si ottiene il risultato atteso;
ingredienti sbagliati o istruzioni errate portano a un esito diverso. Algoritmi
diversi possono portare allo stesso risultato finale, così come ricette differenti
possono produrre torte di mele simili, purché rispettino le condizioni
essenziali.
3. Algoritmi, funzioni e costrutti di base
In ambito informatico, un algoritmo viene spesso rappresentato come una
funzione: prende in ingresso uno o più parametri, esegue una serie di
operazioni e restituisce un risultato. Questa visione è analoga a quella delle
funzioni matematiche, in cui a un valore di input x corrisponde un valore di
output y secondo una certa regola. Nei programmi reali, le funzioni
implementano algoritmi specifici, ad esempio una libreria grafica può
contenere diverse funzioni che applicano filtri differenti a un’immagine.
Due algoritmi si dicono equivalenti se hanno lo stesso dominio di ingresso e
di uscita e, per ogni possibile valore di ingresso, producono lo stesso
risultato. Da un punto di vista astratto, ogni algoritmo può essere visto come
una funzione che trasforma opportunamente un insieme di dati in un altro
insieme di dati. Il compito del programmatore non è solo quello di trovare un
algoritmo corretto, ma anche di sceglierne o progettarne uno efficiente, ossia
che utilizzi il minor numero possibile di passi e di risorse.
La teoria della programmazione strutturata ha individuato tre costrutti di
base sufficienti a realizzare qualsiasi algoritmo: sequenze, decisioni e cicli. Le
sequenze rappresentano una lista ordinata di istruzioni da eseguire una dopo
l’altra. Le decisioni (o selezioni) consentono di scegliere traiettorie diverse a
seconda che una condizione sia vera o falsa: se la condizione risulta vera, si
segue una certa sequenza; se è falsa, se ne segue un’altra. I cicli (o
iterazioni) permettono di ripetere una stessa sequenza di operazioni finché
una determinata condizione rimane soddisfatta. È stato dimostrato che
questi tre costrutti sono sufficienti a esprimere qualsiasi algoritmo, senza
bisogno di strutture aggiuntive.
4. Algoritmi iterativi e ricorsivi: esempio del fattoriale
Gli algoritmi possono essere implementati seguendo due approcci principali:
iterativo o ricorsivo. Un algoritmo è detto iterativo quando la sua definizione
non prevede il richiamo di sé stesso; la ripetizione di operazioni avviene
tramite cicli espliciti, come i classici loop “for” o “while”. Un algoritmo è
invece ricorsivo quando, nella sua definizione, compare un richiamo
all’algoritmo stesso, di solito applicato a un caso più semplice del problema
iniziale, con una o più condizioni di terminazione che impediscono una
regressione infinita.
Un esempio classico è il calcolo del fattoriale di un numero naturale n,
indicato con n!, definito come il prodotto di tutti i numeri interi positivi minori
o uguali a n. In forma iterativa, si può inizializzare una variabile risultato a 1
e poi moltiplicarla ciclicamente per 2, 3, fino a n. In forma ricorsiva, invece, si
può definire n! come n·(n−1)!, con la condizione di base che 0! = 1. In
questo secondo caso, l’algoritmo chiama sé stesso con un argomento ridotto
a ogni passo, finché raggiunge il caso base.
Se implementati correttamente, gli algoritmi iterativi e ricorsivi sono
equivalenti dal punto di vista del risultato. La scelta fra i due approcci può
dipendere da considerazioni di chiarezza, semplicità o efficienza: alcuni
problemi si prestano a una formulazione ricorsiva più naturale, mentre altri
sono più facilmente trattabili con cicli iterativi. I programmatori spesso
devono bilanciare eleganza e prestazioni, eventualmente ottimizzando
versioni esistenti degli algoritmi per adattarle a nuove esigenze.
5. Programma e fasi della programmazione
Un programma è la formulazione testuale, in un linguaggio di
programmazione, di uno o più algoritmi. I linguaggi di programmazione di
alto livello cercano di avvicinare la forma del codice al linguaggio umano,
mantenendo al tempo stesso la precisione necessaria per essere tradotti
automaticamente nel linguaggio macchina, ossia in codice binario
comprensibile dalla CPU. Tale traduzione è affidata a strumenti come
compilatori, interpreti e linker.
Le fasi della programmazione, in senso stretto, includono innanzitutto
l’analisi del problema per identificare in modo chiaro e univoco quali siano i
dati in ingresso e i risultati attesi in uscita. Segue la progettazione
dell’algoritmo, che deve rispettare i criteri sopra descritti. Infine, l’algoritmo
viene tradotto in un linguaggio di programmazione scelto in base alla natura
del problema, alla piattaforma di destinazione e ad altri vincoli tecnici.
Nel contesto più ampio dello sviluppo di un’applicazione, il processo prevede
diverse fasi specializzate. L’analisi dei requisiti (requirements analysis)
riguarda la definizione dettagliata degli obiettivi del programma, del suo
comportamento atteso e dei vincoli. Il design si concentra sulla struttura del
software, decomponendo il compito complessivo in sottofunzioni gestibili e
definendo le interfacce tra i moduli. L’implementazione è la fase in cui i
programmatori scrivono il codice sorgente seguendo le specifiche
progettuali.
A queste fasi seguono il testing, durante il quale team dedicati verificano che
il programma funzioni secondo le specifiche e che non presenti
malfunzionamenti evidenti, e il deployment, cioè la distribuzione del software
agli utenti finali. La documentazione descrive come il programma funziona e
come deve essere utilizzato. Infine, la manutenzione comprende sia la
correzione di errori sia l’aggiunta di nuove funzionalità nel corso del ciclo di
vita del prodotto. Poiché nella pratica molti problemi sono inizialmente mal
definiti, la raccolta e il chiarimento dei requisiti sono passaggi cruciali: una
comprensione incompleta o errata del problema porta quasi inevitabilmente
a programmi inadeguati.
6. Algebra booleana: concetti di base e operatori
L’algebra booleana, introdotta da George Boole a metà dell’Ottocento, è un
sistema matematico che si occupa di valori logici e operazioni su di essi.
Essa è alla base della logica, della teoria degli insiemi, della progettazione di
circuiti elettronici e della programmazione, in particolare per la definizione di
condizioni nei costrutti decisionali e nei cicli. In questo contesto, esistono
solo due costanti: vero (true) e falso (false), che in ambito informatico
corrispondono spesso alle cifre binarie 1 e 0, agli stati acceso/spento di uno
switch o a livelli di voltaggio distinti.
Le variabili booleane possono assumere solo i valori vero o falso e su di esse
si definiscono tre operatori fondamentali: AND, OR e NOT. L’operatore AND
restituisce vero solo se entrambe le espressioni coinvolte sono vere;
altrimenti restituisce falso. L’operatore OR restituisce vero se almeno una
delle espressioni è vera e falso solo se entrambe sono false. L’operatore
NOT, infine, è unario e inverte il valore della variabile o dell’espressione a cui
si applica: se l’espressione è vera, NOT la rende falsa e viceversa. In
notazione algebrica, AND viene spesso rappresentato come una
moltiplicazione (AB), OR come una somma (A+B), mentre NOT viene indicato
con una barra sopra la variabile ((\bar{A})).
7. Tavole di verità ed espressioni booleane
Il comportamento degli operatori booleani può essere riassunto attraverso le
tavole di verità, che mostrano i risultati delle operazioni per tutte le possibili
combinazioni di valori delle variabili in ingresso. Per l’operatore AND tra due
variabili A e B, la tavola di verità indica che soltanto quando A = 1 e B = 1 il
risultato è 1; in tutti gli altri casi è 0. Per l’operatore OR, il risultato è 1 in tutti
i casi tranne quando sia A sia B sono pari a 0. Per l’operatore NOT, la tavola
di verità mostra la semplice inversione: se A = 0, (\bar{A} = 1), e se A = 1,
(\bar{A} = 0).
Un’espressione booleana è ben formata quando è costruita utilizzando
costanti e variabili booleane, operatori AND, OR, NOT e parentesi per definire
chiaramente la precedenza. La precedenza standard prevede che vengano
valutate prima le espressioni tra parentesi, poi le negazioni,
successivamente i prodotti logici (AND) e infine le somme logiche (OR), in
analogia con l’aritmetica. Ad esempio, l’espressione A + BC non ha lo stesso
significato di (A + B)C, proprio come avviene per la somma e la
moltiplicazione tra numeri.
Per N variabili booleane esistono (2^N) possibili combinazioni di valori,
quindi la tavola di verità corrispondente avrà (2^N) righe. Costruire la tavola,
come negli esempi forniti, permette di determinare il valore dell’espressione
per ogni combinazione di ingressi e di verificare proprietà o equivalenze tra
espressioni diverse.
8. Proprietà dell’algebra booleana
L’algebra booleana soddisfa una serie di proprietà che ricordano, in parte,
quelle dell’algebra ordinaria, pur avendo significato logico. Le leggi di
identità affermano che x AND 1 = x e x OR 0 = x, cioè che l’operazione AND
con vero e quella OR con falso non alterano il valore di x. Le leggi di
dominazione dicono che x AND (NOT x) = 0 e x OR (NOT x) = 1: una variabile
e la sua negazione non possono essere entrambe vere, ma almeno una delle
due è sempre vera.
Le leggi associative consentono di raggruppare liberamente le espressioni
senza modificare il risultato: (x AND y) AND z = x AND (y AND z) e
analogamente per OR. Le leggi commutative stabiliscono che x AND y = y
AND x e x OR y = y OR x, quindi l’ordine degli operandi non influisce sul
risultato. Le leggi distributive, infine, mostrano la relazione tra AND e OR: x
AND (y OR z) = (x AND y) OR (x AND z) e, in forma duale, x OR (y AND z) =
(x OR y) AND (x OR z). Queste proprietà sono fondamentali per semplificare
espressioni booleane, ottimizzare circuiti logici e ragionare sulle condizioni in
programmi complessi.
2. Scaletta sintetica per il ripasso
1. Applicazioni e algoritmi
1.1 Definizione di applicazione
1.2 Relazione con il sistema operativo
1.3 Esempi di problemi risolti da applicazioni
1.4 Applicazione come insieme di algoritmi
2. Definizione di algoritmo
2.1 Sequenza finita di operazioni non ambigue
2.2 Dati in ingresso e in uscita
2.3 Criteri fondamentali: eseguibilità, non ambiguità, finitezza
2.4 Requisiti auspicabili: generalità, determinismo, efficienza
2.5 Esempio della ricetta come algoritmo
3. Algoritmi come funzioni
3.1 Equivalenza di algoritmi
3.2 Algoritmi come trasformazioni di dati
3.3 Funzioni nelle librerie di programmi
3.4 Necessità di efficienza
4. Costrutti di base e approcci di implementazione
4.1 Programmazione strutturata: sequenze, decisioni, cicli
4.2 Sufficienza dei tre costrutti
4.3 Approcci iterativo e ricorsivo
4.4 Esempio del fattoriale (iterativo/ricorsivo)
5. Programma e fasi della programmazione
5.1 Programma come formulazione testuale di un algoritmo
5.2 Linguaggi di alto livello e traduzione in linguaggio macchina
5.3 Fasi: analisi dei dati in ingresso e uscita, progettazione algoritmo,
codifica
5.4 Processo di sviluppo software: analisi requisiti, design,
implementazione, testing, deployment, documentazione,
manutenzione
5.5 Importanza dei requisiti
6. Algebra booleana: concetti base
6.1 True/false, corrispondenza con bit 1/0
6.2 Variabili booleane
6.3 Operatori AND, OR, NOT
7. Tavole di verità ed espressioni booleane
7.1 Tavole di verità per AND, OR, NOT
7.2 Espressioni booleane ben formate
7.3 Precedenza degli operatori e uso delle parentesi
7.4 Numero di righe in funzione del numero di variabili
8. Proprietà dell’algebra booleana
8.1 Leggi di identità e dominazione
8.2 Leggi associative e commutative
8.3 Leggi distributive
8.4 Uso delle proprietà per semplificare espressioni e progettare circuiti
3. Otto domande aperte con spunti di risposta
1. Definisci che cosa si intende per “applicazione” in informatica
e spiega in che modo essa si appoggia al sistema operativo per
svolgere i propri compiti.
Spunti: definire applicazione come programma che esegue compiti
specifici; sottolineare che usa i servizi del sistema operativo per
accedere a CPU, memoria e periferiche; spiegare che, senza l’OS,
l’applicazione dovrebbe gestire direttamente l’hardware; fornire uno o
due esempi concreti (ad es. editor di testo, app di navigazione).
2. Che cos’è un algoritmo? Illustra i tre criteri fondamentali che
deve soddisfare e commenta il ruolo della finitezza.
Spunti: dare la definizione di algoritmo come sequenza finita di passi
non ambigui; descrivere eseguibilità, non ambiguità e finitezza;
discutere perché la finitezza è essenziale per garantire che l’algoritmo
termini sempre, anche quando la risposta è che non esiste una
soluzione; se utile, usare l’analogia con una ricetta di cucina.
3. Spiega che cosa significa che due algoritmi sono equivalenti e
discuti perché, in pratica, i programmatori sono interessati non
solo alla correttezza ma anche all’efficienza.
Spunti: definire equivalenza come stessa mappatura da ingressi a
uscite; chiarire che algoritmi diversi possono dare gli stessi risultati con
percorsi diversi; sottolineare che l’efficienza in termini di tempo e
memoria è cruciale, specie per grandi quantità di dati o sistemi con
risorse limitate; menzionare la necessità di migliorare algoritmi
esistenti durante l’evoluzione del software.
4. Descrivi i tre costrutti base della programmazione strutturata
(sequenze, decisioni, cicli) e spiega perché sono sufficienti per
implementare qualunque algoritmo.
Spunti: definire sequenza come lista di istruzioni eseguite in ordine;
descrivere decisioni (if/else) come scelte di percorso basate su
condizioni; spiegare i cicli (while, for) come ripetizioni controllate;
ricordare che la teoria di programmazione strutturata dimostra la
sufficienza di questi tre costrutti per rappresentare qualsiasi procedura
computabile.
5. Confronta un algoritmo iterativo e uno ricorsivo a partire
dall’esempio del calcolo del fattoriale di un numero naturale.
Spunti: descrivere la versione iterativa come ciclo che moltiplica
progressivamente i numeri da 1 a n; descrivere la versione ricorsiva
come definizione n! = n·(n−1)! con caso base 0! = 1; evidenziare che
entrambi producono lo stesso risultato; discutere vantaggi e svantaggi
in termini di chiarezza, semplicità della definizione e potenziali
differenze di prestazioni (ad esempio overhead di chiamata ricorsiva).
6. Illustra le principali fasi del processo di sviluppo di
un’applicazione, spiegando perché la fase di analisi dei
requisiti è particolarmente critica.
Spunti: elencare analysis, design, implementation, testing,
deployment, documentation, maintenance; per ognuna indicare
brevemente lo scopo; sottolineare che i problemi nel mondo reale sono
spesso mal definiti; spiegare che requisiti incompleti o errati portano a
software che non soddisfa i bisogni dell’utente, rendendo costosa la
correzione in fasi successive.
7. Presenta i concetti fondamentali dell’algebra booleana,
descrivendo le costanti, le variabili e i tre operatori principali
con le relative tavole di verità.
Spunti: definire vero/falso, 1/0 e la corrispondenza con stati fisici
(on/off); introdurre variabili booleane; descrivere AND (vero solo se
entrambi veri), OR (vero se almeno uno vero), NOT (inversione del
valore); riportare in forma sintetica le tavole di verità; commentare il
ruolo di queste operazioni nella programmazione (condizioni di if e
while) e nella logica dei circuiti.
8. Spiega alcune delle principali proprietà dell’algebra booleana
(identità, dominazione, associatività, commutatività,
distributività) e discuti come possono essere utili per
semplificare un’espressione logica.
Spunti: enunciare, ad esempio, x AND 1 = x, x OR 0 = x, x AND (NOT x)
= 0, x OR (NOT x) = 1; ricordare che l’associatività e la commutatività
permettono di riordinare e raggruppare termini; spiegare le leggi
distributive e il loro parallelismo con l’algebra ordinaria; mostrare come
queste proprietà permettono di ridurre il numero di termini in
un’espressione o di trasformarla in una forma più adatta
all’implementazione in codice o in circuiti.