Problema e algoritmo

Dal problema all'algoritmo

Problema: situazione da risolvere per ottenere un certo risultato.
Cosa prevede la risoluzione di un problema?

a) comprensione dati iniziali a disposizione (Input);
b) ciò’ che si vuole ottenere (Output).

Questa è l’analisi dei dati, ossia individuare i passi, o meglio, le operazioni che bisogna compiere (procedura) per ottenere il risultato atteso.

Analisi ---> Procedura ---> Risultato

La procedura da seguire per risolvere il dato problema è in informatica universalmente nota con il termine algoritmo.
Algoritmo: è un insieme di regole (istruzioni) aventi le seguenti caratteristiche:

1. finitezza: un A. è composto da un numero finito di istruzioni (passi elementari);
2. determinatezza: deve essere definito e preciso (le istruzioni non devono essere ambigue);
3. terminazione: dopo l’esecuzione di un numero finito di passi, l’algoritmo deve terminare;
4. effettività: l’azione specificata in ogni passo dell’algoritmo deve essere effettivamente eseguibile dall’esecutore (*) preposto per l’esecuzione dell’algoritmo stesso; non avrebbe senso infatti prevedere in un algoritmo azioni che l’esecutore designato non è in grado di compiere;
5. generalità: un algoritmo dovrebbe essere progettato per risolvere non tanto uno specifico problema, quanto una classe di problemi simili.

*esecutore: “chi” è preposto all’esecuzione dei singoli passi specificati in un algoritmo.

In genere si usa classificare gli esecutori in esecutori intelligenti, che risolvono i problemi applicando le conoscenze acquisite nel corso della propria attività, ed esecutori automatici, che risolvono in problemi eseguendo meccanicamente i passi di un algoritmo senza acquisire nuove conoscenze.
In generale si può dire che non esiste un algoritmo univoco per risolvere un determinato problema.
Nel mondo della programmazione individuare un algoritmo adatto a risolvere un dato problema non è, in generale, cosa semplice. La questione non riguarda solo l’efficacia, cioè il fatto che l’ A. risolva il problema in esame. Un altro elemento critico è l’efficienza, ovvero quanto costa, in termini di risorse, l’esecuzione del nostro algoritmo (es, eccessiva occupazione della memoria).
Rappresentazione grafica degli algoritmi: flow – chart

Teorema di Jacopini –Bohm (1966):
“Un qualsiasi algoritmo può essere espresso usando esclusivamente le strutture di sequenza, di selezione e di iterazione”.

1. Sequenza: una o più azioni elementari sono eseguite una di seguito all'altra nell'ordine in cui sono scritte.
2. Selezione: l’esecutore sceglie tra l’eseguire una o più operazioni in alternativa ad altre in funzione del verificarsi o meno di una certa condizione logica, selezionando il “percorso” da seguire in dipendenza da quanto eseguito in precedenza nell'avanzamento del procedimento di soluzione.
3. Ripetizione o iterazione: l’esecutore ripete più volte una o più operazioni in funzione del verificarsi o meno di una condizione logica che controlla il numero di volte per cui tali istruzioni devono essere ripetute (ciclo).

• ciclo determinato: in questo caso si conosce precisamente il momento in cui la ripetizione avrà termine, ossia si conosce a priori il numero delle volte che il ciclo verrà ripetuto;
• ciclo indeterminato: il numero dei cicli ripetuti dipende dal verificarsi o meno della condizione che ne controlla l’arresto. La condizione può essere espressa in testa o in coda al ciclo: nel primo caso il ciclo potrebbe anche non essere mai eseguito (se la condizione è inizialmente falsa), mentre nel secondo caso il ciclo sarà eseguito almeno una volta.