Sequenze, sottosequenze e programmazione dinamica

In questo post parleremo di sequenze numeriche, sottosequenze e programmazione dinamica.
Iniziamo a dare qualche definizione:
Una sequenza numerica è semplicemente una lista di numeri interi.


Esempio:[15,6,12,18,9,8,10,20,8,4,7]
Possiamo definire lunghezza di una sequenza o di una sottosequenza il numero dei suoi elementi.
Quella dell’esempio di partenza è quindi lunga 11 (sono 11 i numeri presenti nella lista).
Una sottosequenza è una lista che contiene una parte degli elementi della sequenza di partenza, posti nello stesso ordine. Semplicemente alcuni elementi vengono eliminati dalla lista di partenza ma, attenzione, tutti gli altri restano nella stessa posizione di partenza!
Alcuni esempi di sottosequenze della lista precedente:
[15,6,12,18,7], [9,8,10, 8,4,7]
Non è invece una sottosequenza della lista precedente la seguente:
[15,18,12,9,8,20,10,4]
perché gli elementi non compaiono nello stesso ordine di quella di partenza (es. 18 e 12 oppure 20 e 10).
Data una sequenza, è poi interessante determinare le sue sottosequenze che hanno proprietà particolari. Quelle comunemente più rilevanti sono le seguenti:

MASSIMA SOTTOSEQUENZA CRESCENTE/DECRESCENTE ovvero la sottosequenza più lunga (strettamente) crescente/decrescente.
'strettamente' significa che non ci sono elementi ripetuti
Di queste sottosequenze possono essercene anche più di una!
NB come già detto, gli elementi devono mantenere lo stesso ordine di quella di partenza! Non dobbiamo riordinarli noi!

Per una sequenza di n elementi esiste un numero di distinte sottosequenze pari all'n-ma potenza di 2. L'algoritmo che permette di risolvere problemi con sequenze e sottosequenze ha una complessità esponenziale.

In informatica la programmazione dinamica è una tecnica di progettazione di algoritmi basata sulla divisione del problema in sottoproblemi e sull'utilizzo di sottostrutture ottimali (es. grafo, matrice…).
Il processo di risoluzione prevede 3 passi:
1. suddividere il problema in sottoproblemi più piccoli;
2. risolvere questi problemi in modo ottimale, utilizzando in modo ricorsivo questo processo a tre passi;
3. usare queste soluzioni ottimali per costruire una soluzione ottimale al problema originale.
La programmazione dinamica si usa quindi nei casi in cui esista una definizione ricorsiva del problema.
L’algoritmo che ne deriva genera un programma di complessità esponenziale a causa del calcolo ripetuto sugli stessi sottoinsiemi di dati da parte delle diverse chiamate ricorsive.

A questo punto sorgono spontanee le seguenti domande: cosa significa algoritmo? E cosa significa ricorsione?
Un algoritmo è un procedimento o programma che risolve un determinato problema attraverso un numero finito di istruzioni elementari, chiare e non ambigue.
Un algoritmo ricorsivo è un algoritmo espresso in termini di se stesso (es. una funzione che richiama se stessa più volte nella sua implementazione).

Questo tipo di argomento non è semplicissimo ma sono sicura che sulle sequenze e sottosequenze numeriche tutti gli amanti della matematica, anche i più piccini, possano sbizzarrirsi nella risoluzione di problemi.

Spero invece di aver stimolato la curiosità dei più grandi con i concetti di algoritmo, ricorsione e programmazione dinamica!

Date un'occhiata al mio video su youtube:

https://youtu.be/ihmiazuRmC4