INTRODUZIONE ALLA PROGRAMMAZIONE CON IL CALCOLATORE ANTROPOMORFO

IL CALCOLATORE ANTROPOMORFO

Il calcolatore antropomorfo consiste di un omino racchiuso in una cabina che riceve istruzioni e dati attraverso due strisce di carta continue illimitate che entrano ed escono dalla cabina attraverso due feritoie (dette input ed output).

L'omino può fare solamente le seguenti cose (cioè queste sono le sue istruzioni):

leggere e scrivere su foglietti di carta, a tali foglietti può essere assegnato un nome (non ci sono limiti sul numero e sulla grandezza dei foglietti che possono essere usati dall'omino);
leggere sulla striscia di input;
scrivere sulla striscia di output;
eseguire una lista di istruzioni una dopo l'altra;
ripetere in dipendenza da una condizione un'istruzione;
scegliere tra due istruzioni in dipendenza da una condizione.

IL PROBLEMA

Costruire un itinerario che colleghi due città su una rete stradale.

L'ALGORITMO (IL PROGRAMMA)

Input/output

INPUT (cosa dare al programma): città di partenza
città di arrivo
rete stradale
OUTPUT (cosa ritornerà il programma): elenco delle città che costituiscono l'itinerario, se un itinerario esiste, niente altrimenti

Rappresentazione dell'informazione

CITTÀ: sequenza di caratteri
ITINERARIO: sequenza di città
RETE STRADALE: sequenza delle coppie di città tra cui esiste un tronco autostradale

Algoritmo 1

Idea: costruire man mano itinerari sempre più lunghi che partono dalla città di partenza, controllando ogni volta se ne esiste uno che che arriva nella meta.

leggere sulla striscia di input la città di partenza e copiarla sul foglietto A

leggere sulla striscia di input la città di arrivo e copiarla sul foglietto B

leggere sulla striscia di input la rete stradale tronco dopo tronco 
e copiarla sul foglietto RETE
 
scrivere sul foglietto ITINERARI gli itinerari di lunghezza 1 che partono 
da A

mentre su ITINERARI non c'è scritto un itinerario che finisce in B fare
    ( prendere un foglietto bianco e chiamarlo AUSILIARE
      per ogni itinerario  c1, ...cn  scritto su ITINERARI
          prendere un foglietto bianco e chiamarlo CITTA 
          scrivere su CITTA tutte le città raggiungibili da cn
          per ogni città c scritta su CITTA
               scrivere su AUSILIARE  c1,...,cn,c 
      cancellare ITINERARI
      ricopiare AUSILIARE su ITINERARI
     )
scrivere sulla striscia di output il primo itinerario in ITINERARI 
che finisce in B

Controllare se è un algoritmo (per esercizio dettagliare tutte le parti descritte grossolanamente, come scrivere sul foglietto ITINERARI gli itinerari di lunghezza 1 che partono da A).
Elencare i foglietti utilizzati. Notare che sapere quali foglietti utilizzare è importante per poter eseguire in modo efficiente l'algoritmo (l'omino se li deve preparare prima per essere pronto ad usarli).
Se eliminiamo l'ipotesi che non vi siano limiti sul numero e la lunghezza di tali foglietti, queste informazioni potrebbero essere utilizzate per decidere se è possibile o meno eseguire il programma.
Problema: discutere se sono chiare le parti di istruzioni come "che partono da A" e "che finisce in B" ?
Per essere precisi occorrebbe scrivere "che partono dalla città scritta su A" e "che finisce nella città scritta su B" ?
Notare che A, B, CITTA, ... sono i nomi dei foglietti e non di quello che c'è scritto su tali foglietti, quindi nel dare l'algoritmo è importante distinguere quando ci si riferisce al foglietto (come in "scrivere su AUSILIARE") e quando ci si riferisce a quanto scritto sul foglietto (come in "per ogni città c scritta su CITTA").
Chiedersi se l'algoritmo è corretto ? cioè ci darà la risposta che aspettiamo.
Se non esiste un itinerario (per esempio tra Torino e Palermo) e ci sono dei cicli nella rete stradale, non otterremo mai una risposta. Corregerlo !
Questione fondamentale: esisterà un algoritmo per questo problema ? In questo caso la risposta è si; esiste una teoria matematica (Calcolabilità) che permette di rispondere a questo tipo di domande.

Algoritmo 2

Idea: non costruire itinerari che contengono cicli; il nuovo algoritmo e presentato di seguito, in rosso le correzioni.

leggere sulla striscia di input la città di partenza e copiarla sul foglietto A

leggere sulla striscia di input la città di arrivo e copiarla sul foglietto B

leggere sulla striscia di input la rete stradale tronco dopo tronco 
e copiarla sul foglietto RETE
 
scrivere sul foglietto ITINERARI gli itinerari di lunghezza 1 che partono 
da A (non ci saranno cicli)

mentre su ITINERARI non c'è scritto un itinerario che finisce in B fare
    ( prendere un foglietto bianco e chiamarlo AUSILIARE
      per ogni itinerario  c1, ...cn  scritto su ITINERARI
          prendere un foglietto bianco e chiamarlo CITTA 
          scrivere su CITTA tutte le città raggiungibili da  cn
          che sono differenti da  c1, ..., cn
          per ogni città  c  scritta su CITTA
               scrivere su AUSILIARE  c1,...,cn,c 
      se c'è scritto qualcosa su AUSILIARE,  allora
          ( cancellare ITINERARI
            ricopiare AUSILIARE su ITINERARI
          )
      altrimenti scrivere sull'ouput "non ci sono itinerari"
     )
scrivere sulla striscia di output il primo itinerario in ITINERARI 
che finisce in B

ESERCIZI

Scrivere un programma per il calcolatore antropomorfo per trovare tutti gli itinerari esistenti tra due città.
Scrivere un programma per il calcolatore antropomorfo per trovare l'itinerario più corto tra due città si assuma che la rete stradale sia corredata dalle lunghezze dei tronchi.