|
Il progetto consiste nel realizzare una struttura dati o un algoritmo correlati con i temi discussi a lezione. Di seguito vengono elencati alcuni progetti fra quelli possibili. La lista non è eaustiva e lo studente può suggerire altri temi su cui svolgere il progetto.
I progetti possono essere svolti anche a gruppi di 2-3 persone. In tal caso, si suggerisce di scegliere un progetto un pò più impegnativo. Nel seguito si indicano anche dei possibili modi per "complicare" i progetti. In generale per complicare un progetto si può costuire un'interfaccia grafica, oppure una qualche forma di estensione. Progetti più consistenti sono anche quelli che prevedono di realizzare algoritmi o strutture dati non spiegati a lezione. La scelta di studiare qualcosa non visto a lezione è considerata positiva di per sé e non si richiede di implementare algoritmi complicati.
Per chiarimenti o per concordare un progetto occorre contattare il docente.
- Algoritmi di visita su grafi
Realizzare un programma che visita il grafo usando gli argoritmi di vista presentati a lezione. Occorre specificare un formato con cui si definiscono dei grafi: ad esempio
2: 1,3, 4
5: 3
....
dove 2:1,3,4 specifica che il nodo 2 ha figli 1,3,4. Oppure una rappresentazione basata sulla matrice di adiacenza del grafo.
Il programma leggerà un file che definisce un grafo e stamperà i nodi in ordine anticipato, posticipato, etc.. La presenza di un'interfaccia grafica non è richiesta, ma può servire a rendere il progetto più consistente.
- Algoritmo dei cammini minimi
Realizzare un programma che dato un grafo calcola l'albero dei cammini minimi. Occorre specificare un formato con cui si definiscono dei grafi (vedi progetto precedente). Quindi si studia l'algoritmi per il calcolo dei cammini minimi (Dijkstra) descritto sul libro di testo "iintroduzione agli algoritmi". Infine si implementa un programma che legge in ingresso un gtrafo e calcola l'albero dei cammini minimi. Un problema simile è quello che calcola la matrice delle distanze minime fra i nodi (Floyd-Warshall).
- Strutture dati: Heap, tabella hash
Si tratta di realizzare un Heap o una tabella hash con le operazioni di insermento, ricerca e cancellazione. Il programma dovrà interagire con l'utente che potrà inserire, ricercare o rimuovere dalla struttura dati (ad esempio, stringhe o interi). La presenza di un'interfaccia grafica non è richiesta, ma può servire a rendere il progetto più consistente.
- Strutture dati: B-Alberi e altre strutture ordinate
Si tratta di una struttura dati che mantiene ordinati gli elementi del vettore. Oltre agli Heap visti a lezione ci sono altre strutture dati con questa proprietà: ad esempio i B-Alberi. Occorre studiare tali strutture sul libro di testo "introduzione agli algoritmi". Il programma dovrà interagire con l'utente che potrà inserire, ricercare o rimuovere dalla struttura dati (ad esempio, stringhe o interi).
- Lex e Yacc
Usando Lex e Yacc, realizzare un analizzatore sintattico per un semplice linguaggio . Si tratta di definire un linguaggio di programmazione molto semplice: ad esempio, un linguaggio che contiene WHILE, IF, assegnamento, interi e variabili. Poi si realizzerà un prgramma che legge un file in ingresso e decide se il file è corretto o meno. Una versione più complessa di questo progetto prevede che il programma produca in uscita l'albero sintattico. Infine, una versione assai complicata di questo progetto produrrà in uscita del codice C che implemta il linguaggio in ingresso.
- Interprete TAC
Costruire un inteprete per il linguaggio TAC descritto a lezione. Occorre definire una semplice rappresentazione per i programmi TAC. L'intepreta prenderà in ingresso un programma contenuto in un file e lo eseguirà. La presenza di un'interfaccia grafica non è richiesta, ma può servire a rendere il progetto più consistente.
- Altre strutture dati o algoritmi
E' possibile scegliere un algoritmo descritto nel libro di testo "introduzione agli algoritmi" o in altri testi e implementarlo. Si può scegliere algoritmi/strutture dati non discusse a lezione. Si suggerisce di scegliere algoritmi semplici, descritti nel libro in poche pagine.
|
