Corso di Programmazione

Esempi di programmi - a.a. 2025-26

Qui di seguito è raccolto il codice dei principali esempi discussi in classe nel corso degli ultimi anni. Selezionando l'icona (Racket/DrScheme o DrJava), o il testo corrispondente a destra dell'icona, è possibile visualizzare ciascun esempio. In alcuni casi, selezionando il testo in evidenziato in colore diverso (sempre a destra dell'icona) si accede ad eventuali documenti illustrativi. Inoltre, i TeachPack possono essere scaricati e utilizzati come supporto alla realizzazione dei programmi che operano su immagini; opportune indicazioni sono riportate per gli esempi che richiedono TeachPack.

I parte: Astrazione procedurale (linguaggio Scheme)

	Procedure basate su semplici espressioni appunti: struttura delle espressioni e notazione in Scheme
	Semplici procedure ricorsive
	Procedure ricorsive per l'elaborazione di stringhe appunti: ricorsione come "delega"
	Rappresentazione posizionale degli interi non negativi
	Rappresentazione dei numeri interi nel sistema ternario bilanciato nota storica nota: intervallo di interi rappresentabili
	Ricorsione generale "ad albero" appunti: percorsi di Manhattan nota: conferenza di A. Policriti "Bioinformatica, DNA e Algoritmi" appunti: sottosequenza comune più lunga (LCS) nota storica sulla sequenza di Fibonacci
	Introduzione di parametri aggiuntivi nota storica in relazione alle operazioni primitive sulle liste
	Ricorsione di coda appunti: ricorsione generale e ricorsione di coda (processo di elaborazione) nota storica sull'algoritmo di Euclide
	Procedure con parametri o valori procedurali: Codice di Giulio Cesare nota storica sul codice di Giulio Cesare

	Esempi a.a. 2024-25
	Annotazioni sulle dimostrazioni di correttezza per induzione il ruolo delle dimostrazioni formali di correttezza nella visione di Lamport (2003)

II e III parte: Astrazione sui dati e astrazione sullo stato (linguaggio Java)

	Introduzione a Java: Esempi di "traduzione" da Scheme a Java
	Introduzione a Java: Esempi di programmi iterativi
	Definizione di classi in Java: Liste di interi nello stile di Scheme
	Programma in Java che utilizza oggetti di tipo IntSList
	Esempio di astrazione sui dati: classe RoundTable (Conta ispirata a un racconto di Giuseppe Flavio)
	Applicazione del modello (RoundTable): alla risoluzione del problema di Giuseppe Flavio nota storica e appunti
	Classe RoundTable: Revisione della rappresentazione al fine di migliorare le prestazioni
	Programma per risolvere il rompicapo delle n regine: numero di soluzioni e lista delle soluzioni appunti: ricerca delle soluzioni
	Esempio di astrazione sui dati: classe Board per rappresentare la scacchiera del rompicapo delle n regine appunti: caselle della scacchiera minacciate
	Argomento avanzato: Astrazione relativa al tipo Liste di elementi di tipo T (Generics) esempi: SList<Integer>, SList<String>
	Concetto di stato: memoization e programmazione dinamica appunti: percorsi di manhattan attraverso la programmazione dinamica
	Memoization e programmazione dinamica: sottosequenza comune più lunga appunti: LCS e LLCS attraverso la programmazione dinamica
	Oggetti che evolvono in Java: Risoluzione del problema ispirato da Giuseppe Flavio
	Astrazione (sullo stato) basata sul concetto di oggetto: "Tavola rotonda" per il problema ispirato da Giuseppe Flavio
	Problema delle n regine: Scacchiera come oggetto che evolve
	Problema delle n regine in Java: Algoritmo risolutivo nel caso di stato che evolve
	Strumenti di supporto per il progetto sulla codifica di Huffman (package huffman_toolkit): Accesso in lettura e scrittura a file di testo documentazione del package appunti: tecnica di codifica di Huffman
	Codifica di Huffman: Classe "Node" per rappresentare l'albero di Huffman appunti
	Codifica di Huffman: strumenti per la compressione e decompressione di documenti (file di testo); esempio articolato di programma, in parte orientata agli oggetti appunti: tecnica di codifica di Huffman
	Ricorsione e iterazione: Rieleaborazione iterativa con stack dei metodi ricorsivi di "Huffman"
	Analisi dei programmi iterativi: Asserzioni, invarianti e verifica della correttezza appunti

	Esempi a.a. 2010-24
	Realizzazione alternativa della classe RoundTable utilizzando un array per rappresentare lo stato interno
	Definizione di classi in Java: Numeri complessi
	Rappresentazione alternativa della "Tavola rotonda" basata su un array
	"Crivello di Eratostene" per la generazione di numeri primi: Analisi della logica tramite asserzioni e invarianti appunti: sviluppo del programma per raffinamenti successivi e applicazioni
	Versione del "Crivello di Eratostene" che introduce alcuni raffinamenti
	Programma per il calcolo dell'IRPEF: programma "per casi" con parziale separazione di logica algoritmica e dati appunti
	Programma per il calcolo dell'IRPEF: programma ricorsivo con completa separazione di logica algoritmica e dati
	Esempio di astrazione sui dati: Conta ispirata a un racconto di Giuseppe Flavio nota storica e appunti
	Conta ispirata a un racconto di Giuseppe Flavio: Revisione della rappresentazione
	Astrazione sui dati: Scacchiera e problema delle n regine appunti
	Esempio di utilizzo di oggetti in Java (applicazione di classi predefinite)
	Creazione e utilizzo di oggetti in Java: Risoluzione del problema ispirato da Giuseppe Flavio
	Astrazione (sullo stato) basata sul concetto di oggetto: "Tavola rotonda" per il problema ispirato da Giuseppe Flavio
	Rappresentazione alternativa della "Tavola rotonda" basata su un array nota a margine: bytecode della classe Josephus
	Problema delle n regine in Java: Rappresentazione della scacchiera
	Problema delle n regine in Java: Algoritmo risolutivo
	Procedure ricorsive per l'elaborazione grafica: ripetizione bidimensionale di un motivo grafico utilizzando il teachpack "drawings"
	approfondimenti sulla correttezza (documento PDF)
	Alcuni spunti di riflessione...
	Altri esempi di elaborazione di stringhe: Shortest Superstring Problem appunti: conferenza di A. Policriti "Bioinformatica, DNA e Algoritmi"
	Liste di liste: Costruzione di Steinhaus
	Ulteriori esempi di programmi ricorsivi: Moltiplicazione Egizia e variazioni sulla Torre di Hanoi
	Applicazione di liste per rappresentare dati strutturati: Schemi di ordinamento
	Astrazione sui dati: Rappresentazione alternativa della scacchiera
	Esempi di applicazione del comando iterativo "while"
	Rappresentazione Ternaria Bilanciata (BTR): Versione iterativa dei programmi per interpretazione e codifica
	Schema di ordinamento "Merge Sort": Approccio iterativo bottom-up
	Concetti di classe e oggetto nella programmazione orientata agli oggetti: 1. Disco del rompicapo della "Torre di Hanoi"
	Concetti di classe e oggetto nella programmazione orientata agli oggetti: 2. Torre del rompicapo della "Torre di Hanoi"
	Concetti di classe e oggetto nella programmazione orientata agli oggetti: 3. Configurazione del rompicapo della "Torre di Hanoi"
	Concetti di classe e oggetto nella programmazione orientata agli oggetti: 4. Programma per risolvere il rompicapo della "Torre di Hanoi"
	Ricorsione e iterazione: Rielaborazione iterativa degli algoritmi per il rompicapo delle n regine (I)
	Ricorsione e iterazione: Rielaborazione iterativa degli algoritmi per il rompicapo delle n regine (II)
	Ricorsione generale e iterazione: Soluzione iterativa del problema della "Torre di Hanoi"

Problemi proposti su astrazione procedurale e astrazione sui dati
(per installare i teachpack è necessario controllare la versione di DrScheme/DrRacket nella sezione dedicata)

	Procedure con argomenti e valori di tipo immagine: "Quilting" - Concrete Abstractions, capp. 1, 2 (quilting.scm); per questo esempio serve anche il TeachPack fungraph.ss
	Parametri e valori procedurali: ulteriore esempio per visualizzare grafici di funzioni reali (plot.scm); per questo esempio serve anche il TeachPack fungraph.ss
	Definizioni di "forme" e procedure per risolvere un rompicapo in Scheme (puzzle.scm); per questo esempio serve il TeachPack tassellation.ss
	Alcune indicazioni di massima per generare fiocchi di neve con le curve frattali (snowflake.scm) come in questa immagine ; il criterio è illustrato da questo schema ; è inoltre necessario il TeachPack fungraph.ss
	Codice per generare una figura frattale basata sulla decomposizione di un esagono figura risultante in questa immagine ; la regola ricorsiva è suggerita da questo schema ; è inoltre necessario il TeachPack fungraph.ss
	Definizioni di "forme" e procedure per risolvere un problema di tassellazione in Scheme (tiles.scm): coprire con piastrelle a forma di L il pavimento illustrato qui ; per questo esempio serve il TeachPack tassellation.ss
	Definizioni di "icone" e procedure per risolvere problema delle torri di Hanoi ... con delle immagini (towers.scm); per questo esempio serve il TeachPack hanoi.ss
	Definizioni di procedure per visualizzare le soluzioni del problema delle n regine (chessboard.scm); per questo esempio serve il TeachPack tassellation.ss
	Rompicapo del quindici: semplice interfaccia grafica Esercizio: realizzazione del rompicapo basata sull'interazione con una semplice GUI. descrizione sintetica del package "puzzleboard"
	Problema delle "n regine" e problema del "giro del cavallo": semplice interfaccia grafica Esercizio: visualizzazione delle soluzioni per mezzo di una semplice GUI. descrizione sintetica del package "chessboard"
	Produzione di suoni (MIDI): semplice "pianoforte sintetico" Esercizio: costruzione di un canone sul tema "Fra' Martino" a partire dalla melodia FrereJacques descrizione del package "music"

Esempi degli anni accademici precedenti: 2003-2011

	Tipi numerici e non numerici: Conversioni di base
	Ricorsione e induzione appunti
	Funzioni di ordine superiore
	Algoritmo di Karatsuba per la moltiplicazione (schema di principio)
	Altri esempi di elaborazione di liste: Sequenze di nucleotidi nel DNA
	Dati strutturati: Stack ed elaborazione di espressioni
	Dati strutturati: Alberi binari
	Astrazione sui dati: Scacchiera e problema del giro del cavallo
	Altri esempi sull'astrazione sui dati: Vettori del piano (non svolto in classe)
	Astrazione sullo stato: Stack rivisitato e valutazione RPN
	Esempi di elaborazione di liste: Rappresentazione binaria
	Altre soluzioni del problema delle n regine
	Astrazione sui dati: Code con priorità
	Astrazione sui dati: Codifica di Huffman per la compressione di documenti appunti
	Memoization: sottosequenze comuni più lunghe rappresentate da percorsi su matrici
	Astrazione basata sul concetto di oggetto: "Tavoletta" del rompicapo del quindici
	Rompicapo del quindici: esempio di utilizzo
	Asserzioni e invarianti: Rappresentazione binaria
	Invarianti di classe: Code limitate
	Invarianti di classe: Code con priorità
	Code con priorità: esempio di utilizzo
	Asserzioni e invarianti: MCD esteso (ulteriore esempio)
	Invarianti di classe: Scacchiera e regine
	Invarianti di classe: tavoletta e rompicapo
	Concetto di stato e paradigma imperativo: Problema delle n regine
	Esercizio sulle tecniche di memoization e programmazione dinamica: Numeri di Stirling del II tipo
	Asserzioni e invarianti di semplici programmi Java
	Asserzioni e invarianti: Ricerca binaria
	Invarianti di classe: gioco del Sudoku
	Gioco del Sudoku: esempio di utilizzo
	Astrazione basata sul concetto di oggetto: "Frame" per rappresentare obiettivi da perseguire
	Astrazione basata sul concetto di oggetto: "Stack" per registrare gli obiettivi (ancora) da perseguire
	Dall'iterazione alla ricorsione: "BinaryString" (ed esercizio)
	Utilizzo di oggetti: Valutazione basata su uno stack di espressioni RPN
	Astrazione basata sul concetto di oggetto: "Stack" per registrare dati e risultati parziali
	Esempio più complesso di programmazione orientata agli oggetti: Modello della tavoletta del "Rompicapo del 15" (generalizzato)
	Esempio più complesso di programmazione orientata agli oggetti: Rappresentazione di una mossa del "Rompicapo del 15"
	Esempio più complesso di programmazione orientata agli oggetti: Applicazione dell'algoritmo A* per risolvere il "Rompicapo del 15"

TeachPack DrScheme

Per poter utilizzare i TeachPack proposti è necessario scegliere il linguaggio HTDP "intermediate with lambda" (oppure PLT - Graphical nelle versioni obsolete) disponibili con DrRacket / DrScheme (menù: Language > Choose Language...). Un teachpack può quindi essere caricato con il comando "Add Teachpack" (menù: Language > Add Teachpack).

Il teachpack "drawings" estende le funzionalità dei due successivi e dovrebbe essere compatibile con tutte le versioni di DrRacket. Negli altri casi occorre verificare la versione di DrRacket/DrScheme.

	drawings.ss
	fungraph.ss
	tassellation.ss
	hanoi.ss

TeachPack per DrRacket a partire dalla versione 6.1 (Agosto 2014):

	fungraph.ss
	tassellation.ss

TeachPack per la versione 1.0.3 di DrScheme:

	fungraph.ss
	tassellation.ss
	hanoi.ss

Package Java

	console.jar emulatore di terminale per l'input/output testuale (materiale didattico reso disponibile da David Eck); vedi anche la nota esplicativa e un semplice esempio di applicazione
	Semplice interfaccia grafica per il rompicapo del 15 e generalizzazioni descrizione sintetica del package "puzzleboard"
	Semplice interfaccia grafica per i problemi delle n regine e del giro del cavallo descrizione sintetica del package "chessboard"
	Semplice strumento MIDI (pianoforte sintetico) per la programmazione dell'esecuzione di canoni descrizione sintetica del package "music"