Gli Algoritmi

IL PROBLEMA

Chiamiamo problema una qualsiasi situazione per  cui è necessario  elaborare una strategia per identificare una sua soluzione, ovvero una serie di azioni da compiere per raggiungere il risultato.

Ad esempio sono problemi le seguenti situazioni:

• Preparare una torta, risolvere un cruciverba, sommare 10 numeri, ordinare alfabeticamente dei nomi, prelevare contanti con il Bancomat, disporre una lista di nomi in ordine alfabetico, calcolare l’area di un rettangolo conoscendone le dimensioni, etc., sono alcuni esempi di problemi.

Si osservi che:

• Non necessariamente esiste un’unica soluzione per un problema.
• Non tutti i problemi sono risolvibili.
• Prima di identificare una strategia è necessario distinguere i dati conosciuti (INPUT) dalle incognite che bisogna determinare (risultati: OUTPUT).

 

RISOLUZIONE PROBLEMA

Per risolvere un problema occorre individuare questi elementi:

• Dati dello stato iniziale (input), quelli forniti dall’esterno per poter risolvere il problema.
• Risultati dello stato finale (output), ovvero quelli da comunicare all’esterno.
• Metodo risolutivo, che fornisce la soluzione al problema.

 

ESEMPIO – Copia di un file dal DVD-ROM all’unità di massa.

• DATI IN: DVD-ROM da inserire, file da copiare.
• DATI OUT: memorizzazione del file in una determinata cartella del PC

 

PROCEDURA RISOLUTIVA

Apri lo slot del driver dvd-rom.

Inserisci il dvd-rom.

Chiudi lo slot del driver dvd-rom.

Apri Esplora Risorse.

Doppio Clic sulla Unità nella quale è stato inserito il dvd-rom.

Doppio clic sulla cartella contenete il file desiderato.

Selezionare il file desiderato.

Clic sul menu Modifica.

Clic sulla voce Copia.

Doppio clic sulla Unità C corrispondete all’unità di massa.

Doppio clic sulla cartella nella quale si vuole copiare il file.

Clic sul menu Modifica.

Clic sulla voce Incolla.

 

DEFINIZIONE DI ALGORITMO

L’algoritmo è un procedimento di calcolo.

Informalmente, un algoritmo è una procedura ben definita che serve per risolvere un dato problema.

Un algoritmo, costituito da una sequenza di passi, prende dei valori come input e produce altri valori come output.

Diamo una definizione formale:

L’algoritmo è una SEQUENZA ORDINATA e FINITA di AZIONI ELEMENTARI NON AMBIGUE (cioè definite con precisione e chiaramente comprensibili per l’esecutore), eseguibili direttamente dall’ESECUTORE (UOMO O MACCHINA) per risolvere un PROBLEMA (e arrivare a un risultato UNIVOCO utile) in un TEMPO FINITO.

 

OSSERVA

• CALCOLABILITA’: un problema è calcolabile quando è risolvibile attraverso un algoritmo.
• PROGRAMMAZIONE: il problema viene risolto con un algoritmo e successivamente codificato, attraverso un linguaggio di programmazione, in un programma eseguibile dalla macchina. Successivamente viene eseguito un testing per verificare se rispetta le ipotesi fatte.
• Il procedimento è una sequenza finita di istruzioni elementari.
• L’esecutore può essere l’uomo o la macchina, cioè l’ente che esegue la procedura risolutiva, il procedimento.
• Un’azione elementare eseguita da un esecutore umano è detta operazione.
• Un’azione elementare eseguita da una macchina è detta istruzione.

 

CARATTERISTICHE DI UN ALGORITMO

• Finito: la sequenza di istruzioni deve essere finita (con un inizio e una fine).
• Eseguibile: ogni istruzione deve essere eseguita dall’esecutore in un tempo finito.
• Non ambiguo: le istruzioni devono poter essere interpretate da tutti allo stesso modo senza lasciare dubbi nella sua interpretazione.
• Generale: deve essere valido non solo per un particolare problema, ma per una classe di problemi.
• Deterministico: Ogni istruzione deve produrre il medesimo effetto a partire dalle stesse condizioni iniziali, indipendentemente dall’esecutore.
• Completo: deve contemplare tutti i casi che si possono verificare durante l’esecuzione.
• Sequenzialità: le operazioni vengono eseguite una dopo l’altra.
• Ogni istruzione deve produrre un risultato osservabile.
• Le istruzioni devono essere elementari, cioè non ulteriormente scomponibili.

 

ETIMOLOGIA DEL TERMINE ALGORITMO

Il termine algoritmo deriva dal termine latino medievale algorismus, che a sua volta deriva dal nome del matematico arabo (persiano) Abū Jaʿfar Muhammad ibn Mūsā al-Khwārizmī vissuto nell’800 d.C., ritenuto l’ideatore della procedura risolutiva per il calcolo della moltiplicazione tra due numeri mediante l’incolonnamento delle cifre (quella che usiamo ancora oggi).

 

STESURA DI UN ALGORITMO

• RIGA DI INTESTAZIONE: nome dell’algoritmo
• SEZIONE DICHIARATIVA: elenco dei dati (variabili in/out e costanti/variabili di lavoro) che utilizza l’algoritmo.
• SEZIONE ESECUTIVA: compresa fra le parole INIZIO e FINE ed elenca le operazioni/istruzioni (dichiarazione, immissione, assegnazione, controllo, scrittura) che l’esecutore deve compiere.

 

ESEMPIO Calcolare il prezzo di un prodotto sul quale è praticato uno sconto

  DATI INPUT: il prezzo del prodotto (Prezzo), la percentuale di sconto (Percentuale). La´percentuale di sconto può essere considerata una costante (es 20%).

  DATI OUTPUT: lo sconto (Sconto), e il prezzo scontato (PrezzoScontato).

  RISOLUZIONE:

  INIZIO

Acquisisco il Prezzo del prodotto

Acquisisco la Percentuale di sconto

Calcolo lo Sconto: Prezzo * Percentuale /100

Calcolo il prezzo scontato: Prezzo – Sconto

Comunico il valore calcolato

FINE

 

ESERCIZIO

Descrivere attraverso il processo risolutivo le azioni che svolgete per venire a scuola (Sento la sveglia, mi alzo, etc…, prendo il pulman, etc.). Ricordatevi quali sono le ipotesi da rispettare affinchè la procedura possa essere considerata un algoritmo.