Esame di Algoritmi e Strutture Dati

Progetto individuale:

Consiste nella realizzazione di un programma o di una libreria ANSI C seguendo la metodologia di sviluppo software "in the small", nella valutazione della complessità computazionale asintotica del software sviluppato e nella verifica della correttezza di una sua parte.

Il progetto deve essere sviluppato individualmente. I progetti che esibiscano praticamente il medesimo software verranno tutti annullati e i relativi sviluppatori non verranno ammessi alla prova scritta.

Il progetto, comprensivo di relazione in formato PDF, sorgenti ANSI C e makefile, deve essere consegnato al docente per posta elettronica (indicare come oggetto "consegna progetto Algoritmi e Strutture Dati") almeno sette giorni prima della prova scritta (vedi date consegna progetto) mediante un allegato in formato .tar.gz oppure .zip. Il docente comunicherà per posta elettronica la valutazione del progetto due giorni prima della prova scritta.

La relazione deve essere in formato PDF, deve essere scritta in corretta lingua italiana o inglese, deve iniziare con una pagina di copertina riportante almeno il nominativo dello studente e deve contenere le seguenti sette sezioni (ciascuna con inizio su una nuova pagina):

1. Specifica del problema. Riportare fedelmente l'enunciato del problema assegnato.
   
   
2. Analisi del problema. Descrivere in modo schematico gli input e gli output del problema e le principali relazioni intercorrenti tra di essi, da sfruttare ai fini della soluzione del problema.
   
   
3. Progettazione dell'algoritmo. Inquadrare lo sviluppo dell'algoritmo nel contesto del problema assegnato e della sua analisi, indicare le principali scelte di progetto che sono state compiute e le eventuali tecniche algoritmiche e strutture dati che sono state adottate con le relative motivazioni (p.e. scelta di determinate strutture dati oppure scelta di uno schema di soluzione ricorsivo oppure adozione di una specifica tecnica algoritmica), e descrivere in modo schematico i passi principali -- con eventuali raffinamenti -- dell'algoritmo ideato per risolvere il problema astraendo dallo specifico linguaggio di programmazione impiegato nell'implementazione (i passi dell'algoritmo non debbono assolutamente essere scritti in linguaggio ANSI C).
   
   
4. Implementazione dell'algoritmo. Completare e tradurre l'algoritmo nel linguaggio ANSI C, includendo nella relazione tutti i file .c e .h sviluppati come pure il makefile.
   
   
5. Testing del programma. Effettuare diversi test significativi dell'esecuzione del programma per ciascuna classe di input del problema, riportando fedelmente per ciascun test sia i dati di input introdotti da tastiera/file che i risultati prodotti su video/file.
   
   
6. Valutazione della complessità del programma. Riportare l'impostazione e il calcolo del tempo d'esecuzione -- espresso come numero di passi base -- di ciascuna funzione del programma in rapporto alla dimensione dei dati di ingresso, ricavandone poi l'ordine di grandezza (se diversamente specificato, procedere per via sperimentale descrivendo come gli esperimenti sono stati impostati e riportando graficamente i risultati degli esperimenti).

Il software sviluppato (quarta sezione della relazione) deve essere come segue:

• Leggibile:
  • Privo di scelte di progetto non descritte o non motivate nella terza sezione della relazione.
  • Privo di identificatori non evocativi di ciò che rappresentano.
  • Privo di variabili globali
  • Ben indentato (evitare linee troppo lunghe che vanno a capo nella relazione).
  • Dotato di appropriate spaziature per funzioni e operatori.
  • Dotato di opportuni commenti che richiamano la progettazione dell'algoritmo.
• Articolato in funzioni.
• Coerente coi principii della programmazione strutturata:
  • Privo di istruzioni goto.
  • Privo di istruzioni exit.
  • Privo di istruzioni continue.
  • Privo di istruzioni break che non si trovano alla fine di un case di uno switch.
  • Privo di istruzioni return che non si trovano alla fine del corpo di una funzione.
• Compilabile tramite gcc con opzioni -Wall (rilevazione di tutti i warning) e -ansi (conformità allo standard ANSI) senza che vengano segnalati errori o warning.
• Funzionante correttamente rispetto al problema assegnato senza introdurre alcuna limitazione e comprensivo della validazione degli input.
• Efficiente in termini di tempo d'esecuzione impiegato e spazio di memoria occupato.

Ogni inosservanza di quanto stabilito sopra a proposito della consegna del progetto, della preparazione della relazione e dello sviluppo del software determina una riduzione del voto del progetto. Non sono ammessi ritardi nella consegna del progetto.

Prova scritta:

Consiste in una serie di domande relative al programma del corso. Il tempo a disposizione è di 60 minuti. Non è ammessa la consultazione di testi, dispense o appunti in formato cartaceo o elettronico. L'ammissione alla prova scritta è subordinata all'ottenimento di un voto di almeno 18/30 nel progetto. È obbligatorio presentarsi alla prova scritta muniti di libretto universitario.

Prova orale:

Consiste in una serie di domande relative al programma del corso più l'eventuale discussione del progetto e della prova scritta. L'ammissione alla prova orale è subordinata all'ottenimento di un voto di almeno 18/30 in ambedue le prove precedenti. È obbligatorio presentarsi alla prova orale muniti di libretto universitario.

Valutazione:

È determinato dalla media del voto del progetto e del voto della prova scritta, con un aggiustamento compreso tra -5/30 e 5/30 derivante dalla prova orale. Nel caso in cui il progetto sia giudicato sufficiente ma la prova scritta o la prova orale non venga superata, il progetto viene mantenuto valido per tutti i successivi appelli d'esame dello stesso anno accademico. Qualora il progetto venga rifatto e riconsegnato in un appello successivo, il voto del progetto precedentemente consegnato viene annullato. Se la riconsegna avviene nella medesima sessione, al voto del nuovo progetto consegnato viene applicata una penale di 5/30.