Corso di Programmazione

Esempi di programmi - a.a. 2024-25

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
	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 e correttezza dei programmi ricorsivi appunti: ricorsive generale e ricorsione di coda (processo di elaborazione) nota storica sull'algoritmo di Euclide annotazioni sulle dimostrazioni di correttezza per induzione il ruolo delle dimostrazioni formali di correttezza nella visione di Lamport (2003)
	Procedure con parametri o valori procedurali: Codice di Giulio Cesare nota storica sul codice di Giulio Cesare

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

	Esempi a.a. 2023-24
	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"