Figure e strutture ricorsive e autoreferenziali

“Ma come ti è venuto in mente?” è la domanda che mi è stata posta più di

frequente nei mesi in cui ho sviluppato questa tesina, la risposta non è così semplice ma

cercherò brevemente di chiarirlo in questa premessa.

La scelta dell’argomento in questione risale a questa estate quando

inaspettatamente mi sono reso conto che alcuni degli interessi scaturiti dai miei studi,

apparentemente lontani ed eterogenei tra loro, si trovavano in realtà strettamente legati

e avvicinati da una teoria, che fino ad allora avevo considerato esclusivamente

informatica. Ciò che ha ispirato questa tesina sono un film, ExistenZ di Cronenberg, un

libro, Sei personaggi in cerca d’autore di Pirandello, e un paio di progetti informatici sui

quali stavo lavorando, un programma per il calcolo del determinante di una matrice

quadrata e un programma per il disegno del frattale di Mandelbrot. A questo dovrei forse

aggiungere il profondo interesse che da sempre nutro per tutto ciò che è complesso,

articolato e che spesso sfugge all’immediata comprensione.

Ma come si legano tra loro questi diversi spunti? Per spiegarlo proverò a

ricostruire brevemente come il nucleo della tesina si sia formato inizialmente nella mia

mente. Dovrebbe essere andata all’incirca così: “Bello quel film dell’altra sera! Ma c’è

qualcosa che non riesco a cogliere, nel film quei ragazzi iniziavano a giocare ad un

videogioco e nel videogioco iniziavano un altro videogioco e così via…, mi sembra di aver

già sentito qualcosa di simile ma non riesco a ricordarlo… Ecco, aspetta... Ma sì sicuro

Pirandello! Sei personaggi in cerca d’autore! Il teatro nel teatro, ecco cos’era, il teatro che

al suo interno richiama se stesso. Bello, detto così sembra quasi una funzione di

informatica, ricordi?, una funzione che al suo interno richiama se stessa si definisce

ricorsiva. L’avevo usata in quel programma per il calcolo del determinante e adesso di

nuovo nel programma per disegnare il frattale di Mandelbrot… e se si ingrandisce il

frattale si trova nuovamente una struttura simile a quella di partenza, una figura nella

figura… come nel film!... Come nel libro!...”

Delineato il nucleo principale ho ampliato la tesina documentandomi su internet

e consultando diversi libri primo tra i quali Gödel, Escher, Bach: un’Eterna Ghirlanda

Brillante, un volume di Hofstadter che mi ha guidato nello sviluppo della parte

riguardante l’autoreferenza permettendo un ampliamento delle tematiche trattate.

Nel percorso da me seguito è risultato inoltre fondamentale l’interesse personale

per una materia studiata nei primi quattro anni di liceo e abbandonata in quest’ultimo,

disegno tecnico, che mi ha permesso di conoscere e approfondire le litografie

“matematiche” di Escher e i paradossi in esse rappresentati. Essi spesso rientrano

perfettamente nelle tematiche da me qui trattate e proprio per questo sono state scelte

e da me unite nella copertina della tesina.

In conclusione questo lavoro rispecchia perfettamente tutti gli stimoli culturali

che questo indirizzo di studi è stato in grado di offrirmi in cinque anni e che mi è piaciuto

accogliere e trasformare in interessi personali. 3

Durante una giornata ci si trova spesso di fronte a problemi logici da risolvere

o fenomeni da analizzare con attenzione e quello che si tende il più delle volte a fare

è di costruire un procedimento lineare da seguire che, come una retta, partendo da

un punto iniziale giunga ad una conclusione o ad un risultato finale.

Esistono però dei casi particolari in cui questo percorso lineare non può

sussistere ma deve forzatamente deviare piegandosi o ramificarsi in

sottoprocedure. Per quanto riguarda il primo caso può accadere che, deviando, un

procedimento si ripieghi su se stesso portando inizio e fine a coincidere in uno

stesso punto. Cercando così di utilizzare tale procedura nella risoluzione di un

problema ci si troverebbe in un dato istante del tutto inaspettatamente di fronte

al problema di partenza rendendo evidente il fatto che la procedura o il problema

stesso contengano un richiamo più o meno esplicito verso il proprio inizio,

essendo dunque autoreferenziali.

Anche se ci si trovasse di fronte ad un procedimento ramificato ,che si

suddivide cioè in sottoprocedure di ordini gerarchici via via inferiori, potrebbe

verificarsi un altro fenomeno altrettanto particolare. Potrebbe infatti accadere

che le sottoprocedure siano esatte copie della procedura di partenza dalla quale si

ramificano generando così quel fenomeno definito come ricorsività. Utilizzando

tale procedura ricorsiva nella risoluzione di un problema ci si ritrova più volte di

fronte a sottoproblemi del tutto identici al problema di partenza ma in esso

contenuti.

I due fenomeni appena presentati risultano a mio parere strettamente legati da una

caratteristica comune: sia un procedimento autoreferenziale che uno ricorsivo presentano infatti

un richiamo verso se stessi. Attraverso l’autoreferenza il richiamo si genera su uno stesso livello

gerarchico mentre con la ricorsività il richiamo è effettuato su più livelli gerarchici.

Ho deciso di caratterizzare ciascuna parte con una figura che ne evidenziasse l’essenza: il

nastro di Möbius per l’autoreferenza e il triangolo di Sierpinski per la ricorsività.

Processi chimico – biologici

autoreferenziali Processi e algoritmi

ricorsivi

Figure e strutture

autoreferenziali

Autoreferenza Ricorsività Frattali

Autoreferenza

nel pensiero

Procedure

autoreferenziali Figure e strutture

ricorsive 4

Calcolo fattoriale (Programma Java)

Calcolo matriciale (Programma VB)

Processi e algoritmi ricorsivi Programmazione ricorsiva Frattale di Mandelbrot (Programma VB)

Triangolo di Sierpinski

Frattali non biomorfi

Sei personaggi in cerca d’autore

Il fu Mattia Pascal

Pirandello Ricorsività Frattali

Shakespeare - Hamlet

Beckett - Waiting for Godot

Strutture ricorsive in letteratura Frattali biomorfi

Strutture ricorsive presenti in natura

Figure e strutture ricorsive Ricorsione nell’arte Alberi

Montagne

Effetto Droste Nuvole

M.C. Escher

Metabolismo DNA - proteine

Meccanismi di autoregolazione

Metabolismi cellulari Autoreferenza nell’arte

Figure e strutture

Processi chimico – biologici autoreferenziali

autoreferenziali Strutture autoreferenziali in letteratura

Pavese - Feria d’agosto

Beckett - Waiting for Godot

Autoreferenza

Nietzsche - Filosofia dell’eterno ritorno x

Schopenhauer - Autoreferenza della volontà Derivazione e

Procedure matematiche

Pensiero filosofico Procedure autoreferenziali

Autoreferenza nel pensiero Procedure logiche

Paradosso di Epimenide 5

Magritte - L’uso della parola I

Wittgenstein Processi e algoritmi

Automatizzazione procedure di calcolo ricorsivi

matematiche con funzioni ricorsive Programmazione ricorsiva

Calcolo del determinante di una matrice quadrata Richiamo ricorsivo alla funzione per il

calcolo del determinante

Inizio

F V

Calcolo determinante della matrice Calcolo dei complementi algebrici di

Dimensione

di 2° ordine una riga della matrice

matrice > 2 Scomposizione in matrici di 1

ordine inferiore

Calcolo determinante delle

matrici di ordine inferiore

Somma dei prodotti degli elementi

della riga scelta per i rispettivi

complementi algebrici

Calcolo del fattoriale di un numero n Richiamo ricorsivo alla funzione per il

calcolo del fattoriale

Inizio

F V Il Fattoriale di N è uguale a N per il

Il Fattoriale di 0 è uguale a 1 N <> 0 fattoriale di N-1

Disegno del frattale di Mandelbrot Inizio

Selezione di un punto P del piano

0

Traslazione del punto P in Z

0 Richiamo ricorsivo alla funzione per la

traslazione del punto (Z viene passato

N = N+ 1 alla funzione come P )

|OP | > 2 0

0

OR

N > 100

Selezione del colore di P in base a N 6

0 Processi e algoritmi

Automatizzazione di procedure matematiche ricorsivi

tramite funzioni ricorsive

Avendo definito brevemente nell’introduzione il concetto di Programmazione ricorsiva

ricorsività vediamo ora come esso possa essere applicato efficacemente

nell’automatizzazione di procedure di calcolo nell’ambito della

programmazione.

Dato un problema risulta essere abbastanza naturale cercarne

una rappresentazione astratta, cioè cercare di assimilare il problema

specifico ad una categoria più generale di problemi che, una volta

individuata una procedura di risoluzione adeguata e funzionale, possano

portare alla risoluzione, per analogia, di tutti i casi specifici. In secondo

luogo nel creare un algoritmo risolutivo si tenderà il più delle volte a

modularizzare il problema di partenza, si cercherà cioè di suddividere il

problema in sottoproblemi via via più semplici per i quali si possono

individuare o già si conoscono delle soluzioni facilmente calcolabili.

Scomponendo il problema può capitare in taluni casi che i

sottoproblemi siano esatte copie del problema di partenza (come è stato

spiegato nell’introduzione), ciò permette di esprimere un dato problema

in funzione di se stesso rendendo possibile lo sviluppo di un algoritmo

ricorsivo per la sua risoluzione.

Un esempio di un problema che può essere chiaramente

espresso in funzione di se stesso è quello della valutazione della mossa

migliore nel gioco degli scacchi, infatti la mossa migliore per un giocatore

è quella che lascia l’avversario nella situazione più difficile. Per valutare la

bontà di una mossa allora si può pensare di eseguire la mossa e poi di

valutare la situazione dal punto di vista dell’avversario che cercherà di

capire quale è la sua mossa migliore generando un richiamo ricorsivo alla

procedura.

In matematica sono molti i problemi e le procedure che possono

essere espressi in maniera ricorsiva e quelli da me presi in esame in

questo percorso sono solo alcuni esempi che mi sono divertito a realizzare

nel corso di questi ultimi due anni di liceo. La prima volta che mi sono

imbattuto in una procedura matematica ricorsiva stavo realizzando un

programma in VisualBasic che fosse in grado di calcolare il determinante di

una qualsiasi matrice quadrata.

Analizziamo ora brevemente il problema:

 

a a

•  

 1

,

1 1

, 2

data una matrice di 2° ordine: A  

a a

 

2 ,

1 2 , 2 a a

    

1

,

1 1

, 2

il suo determinante si calcola: det A a a a a

1

,

1 2 , 2 1

, 2 2 ,

1

a a

2 ,

1 2 , 2  

a a a

 

1

,

1 1

, 2 1

, 3



•  

data una matrice di ordine superiore (es. 3° ordine): A a a a

2 ,

1 2 , 2 2 , 3

 

a a a

 

3 ,

1 3 , 2 3 , 3

a a a

1

,

1 1

, 2 1

, 3 a a a a a a

      

2 , 2 2 , 3 2 ,

1 2 , 3 2 ,

1 2 , 2

Il suo determinante si calcola: det A a a a a a a

2 ,

1 2 , 2 2 , 3 1

,

1 1

, 2 1

, 3

a a a a a a

3 , 2 3 , 3 3 ,

1 3 , 3 3 ,

1 3 , 2

a a a

3 ,

1 3 , 2 3 , 3 7

Dall’analisi del problema si può facilmente dedurre che per Processi e algoritmi

risolvere il determinante di una matrice di ordine superiore a 2 sarà ricorsivi

necessario richiamare ricorsivamente la funzione per il calcolo del

determinante stesso. Infatti nello sviluppo ogni elemento della prima riga

viene moltiplicato con il suo minore complementare, ovvero il

determinante della matrice di un ordine inferiore ottenuta eliminando la Programmazione ricorsiva

prima riga e una delle colonne.

Nel programma da me creato in VisualBasic questa procedura è

rappresenta dalla seguente funzione:

Public Function Determinante(ByVal matrixA, dimensioneA,) As Long

If (dimensioneA > 2) Then 'risoluzione di matrici di ordini superiori a 2

Dim MatrixB() As Long 'matrice temporanea di 1 ordine inferiore a quella data

Dim dimensioneB As Long 'ordine della matrice temporanea

Dim ma As Long ‘complemento algebrico

Dim pos As Long 'posizione dell'elemento di sviluppo

Dim mtot As Long ‘somma dei prodotti del complemento algebrico per il minore complementare

dimensioneB = dimensioneA - 1

ReDim MatrixB(1 To dimensioneB, 1 To dimensioneB) As Long

Dim rB As Long 'contatore righe della matrice temporanea

Dim cB As Long 'contatore colonne della matrice temporanea

For i = 1 To dimensioneA 'per ogni elemento della 1a riga della matrice data

cB = 1

rB = 1

For ra = 1 To dimensioneA 'per ogni elemento riga della matrice data

For cA = 1 To dimensioneA 'per ogni colonna della matrice data