ADS2 è un modello costruttivo-generativo dell’Algoritmo di Stirling. Il suo scopo è determinare il numero totale di partizioni di un insieme.
Un insieme è una collezione definita di elementi distinti. Non sono ammessi duplicati. Un insieme può contenere sottoinsiemi, cioè sotto-collezioni di elementi appartenenti all’insieme originale.
Una partizione è una collezione di sottoinsiemi (blocchi) che coprono l’insieme originale senza sovrapposizioni e senza duplicati tra i blocchi.
Il numero totale di partizioni di un insieme di n elementi è dato dal numero di Bell
ADS2 non utilizza formule ricorsive o programmazione dinamica. Il calcolo avviene tramite enumerazione completa dello spazio delle partizioni mediante backtracking.
Nel corso dell’anno scolastico 2025/2026 ho implementato ADS2 nel linguaggio C. Il programma include una CLI per l’interazione con l’utente.
Il programma è composto dalle seguenti procedure:
- INIT: inizializza la sintassi dell'input, ovvero gli operatori con cui l'utente comunica l'insieme da elaborare
- ASGN: assegnazione/acquisizione e elaborazione/interpretazione della stringa, inserita dall’utente, che rappresenta l'insieme
- CRD: calcolo della cardinalità dell’insieme
- BCKTR: generazione delle partizioni tramite backtracking
- BLL: restituzione del numero di Bell
- ESC: procedura tecnica di deallocazione della memoria (nel caso del C) e gestione della terminazione del programma o dell’avvio di una nuova computazione Dopo INIT, il programma continua l’esecuzione a meno che l’utente non interrompa il flusso durante ASGN o ESC.
Ogni fase usa funzioni di supporto per compiti specifici. In particolare:
leggi_char: legge un singolo carattere dall'utente in modo sicuro.gia_usato: verifica se un carattere è stato già inserito durante la personalizzazione degli operatori, da poter evitare casi come OPS = [=, =, =, =]controllare: controlla la presenza dei tre operatori principali(corresponsore, terminatore aperto, terminatore chiuso) e il loro ordineestrarre: funzione di parsing ovvero di tokenizzazione manuale, con eliminazione degli spazi all'inizio e alla fine della sottostringa estratta
La CLI guida l'utente durante l'esecuzione del programma. Le funzionalita principali sono:
- configurare gli operatori;
- leggere l'insieme da elaborare;
- validare l'input;
- mostrare i risultati;
- decidere se eseguire un'altra computazione.
La sintassi adottata da ADS2 per la rappresentazione degli insiemi è composta da quattro operatori:
- corresponsore: separa il denominatore(nome dell'insieme) dal contenuto dell'insieme
- terminatore aperto: identifica l'inizio dell'elenco degli elementi
- terminatore chiuso: identifica la fine dell'elenco degli elementi
- separatore: distingue un elemento dal successivo
Nella configurazione predefinita tali operatori corrispondono rispettivamente ai simboli: = { } , e consentono di rappresentare un insieme nella forma: A = {a1, a2, ... aN} dove A rappresenta il denominatore dell'insieme e a1, a2 .. aN rappresentano i suoi elementi. ADS2 consente all'utente di personalizzare ciascun operatore durante la fase di inizializzazione, mantenendo invariata la struttura logica dell'input Esempio: A > [a1; a2; ... aN]
Durante l'esecuzione, ADS2 utilizza un sistema di conferma basato sulle risposte s/n (sì/no) per le operazioni che richiedono una scelta da parte dell'utente:
- accettazione degli operatori predefiniti
- avvio di una nuova computazione
- terminazione del programma In caso di risposta non valida, il sistema richiede nuovamente l'inserimento senza interrompere l'esecuzione. Gli input non conformi vengono rifiutati e non vengono inoltrati alle procedure di elaborazione. Per consentire l'interruzione immediata dell'applicazione, ADS2 riconosce inoltre il comando 'exit' digitabile durante la fase di acquisizione dell'insieme.
Prima dell'acquisizione dell'insieme, l'utente può scegliere tra due modalità:
- elementi costituiti da singoli caratteri alfanumerici;
- elementi costituiti da stringhe alfanumeriche di lunghezza arbitraria.
Dopo la fase di acquisizione, il programma mostra l'insieme normalizzato senza duplicati e con la sintassi corretta. Vengono inoltre visualizzate:
- cardinalità effettiva dell'insieme
- degenerazione dell'insieme (numero di duplicati rimossi)
- numero totale delle partizioni possibili
L'elemento centrale di ADS2 è la funzione backtrack, responsabile della generazione esplicita di tutte le partizioni possibili dell'insieme. A differenza di ADS1, che calcola il numero di Bell attraverso i numeri di Stirling di seconda specie, ADS2 costruisce direttamente ogni possibile partizione e ne conta il numero totale.
Per rappresentare i blocchi della partizione il programma utilizza una codifica basata su bitmask.
Ad ogni elemento dell'insieme viene associato un indice compreso tra 0 e N−1 e il valore:
La funzione di backtracking procede elemento per elemento. Per ogni elemento corrente vengono esplorate due possibilità:
- inserimento in uno dei blocchi già esistenti;
- creazione di un nuovo blocco. Quando tutti gli elementi sono stati assegnati, viene raggiunto uno stato terminale della ricorsione e il contatore delle partizioni viene incrementato. Il valore finale del contatore corrisponde al numero di Bell dell'insieme.
ADS2 genera esplicitamente tutte le partizioni possibili. Poiché il numero di partizioni di un insieme di cardinalità N è il numero di Bell B(N), il tempo di esecuzione cresce proporzionalmente al numero di configurazioni generate.
La complessità temporale può essere espressa come:
- chiamate ricorsive;
- assegnazioni ai blocchi;
- operazioni bitwise;
- aggiornamento del contatore delle partizioni.
Il tipo numerico utilizzato per il conteggio è
long long.
Il programma segue questo flusso: INIT -> ASGN -> CRD -> BCKTR -> BLL -> ESC Ogni procedura ha un lavoro preciso e passa il risultato alla fase successiva. La quasi totalità del lavoro computazionale è concentrata nella procedura BCKTR.
La generazione completa delle partizioni comporta una crescita estremamente rapida del tempo di esecuzione. Per questo motivo il programma suggerisce una cardinalità massima consigliata pari a circa 15 elementi.
La memoria è utilizzata principalmente da:
- vettore degli elementi dell'insieme;
- stato corrente della partizione;
- stack della ricorsione. La profondità massima della ricorsione è N.
Il programma è single-threaded e CPU-bound. Non utilizza parallelismo né sincronizzazione.
- Apri una shell o un terminale
- Entra nella cartella che contiene
main.c. - Usa il compilatore GCC per generare l'eseguibile:
gcc main.c -o ads2 - Se la compilazione ha successo, avvia il programma con:
./ads2
- Apri il "Developer Command Prompt for Visual Studio".
- Entra nella cartella che contiene
main.c. - Compila con il comando:
cl main.c /Fe:ads2.exe - Se la compilazione ha successo, esegui il programma con:
ads2.exe