Prova finale di algoritmi e principi dell'informatica per l'anno accademico 2022-2023.
Docente: Martineghi Davide
Valutazione: 24/30
Realizzare un programma in C per la ricerca del percorso ottimo tra stazioni di servizio di un'autostrada.
Il programma non solo deve produrre un output corretto, ma deve rispettare dei vincoli di memoria e tempo CPU come in tabella:
| Valutazione | Memoria | Tempo | Esito |
|---|---|---|---|
| 18 | 128 MiB | 19 s | ✅ |
| 21 | 118 MiB | 15 s | ✅ |
| 24 | 108 MiB | 10 s | ✅ |
| 27 | 98 MiB | 6 s | ❌ |
| 30 | 88 MiB | 4 s | ❌ |
| 30L | 78 MiB | 1 s | ❌ |
Il mio progetto prendendo i dati dal verificatore ha i seguenti utilizzi di memoria e tempo:
- Memoria: ~6,1 MiB
- Tempo: ~6,3 s
Questi risultati possono variare a seconda della potenza di calcolo della macchina.
La specifica completa del progetto è disponibile qui.
I test sono disponibili qui.
La struttura dati che rappresenta l'autostrada è una lista doppiamente concatenata; questa soluzione è stata scelta per semplicità implementativa e per il minor uso di memoria rispetto ad altre strutture dati.
Al fine di rispettare i limiti di tempo è stato necessario creare una cache contenente i puntatori alle ultime stazioni modificate o accedute. Il grafico seguente rappresenta il tempo di esecuzione del programma con input il file open_111.txt al variare della grandezza della cache:
Note
I tempi di esecuzione sono molto alti siccome il programma è stato eseguito in una macchina virtuale per questo test.
| Descrizione | Strumento |
|---|---|
| IDE | CLion |
| Compilatore | gcc |
| Misurazione memoria | Valgrind - Massif |
| Sistema operativo | Windows 10 e Debian 11 |
Il progetto è distribuito sotto licenza GPL v2, si applicano le limitazioni descritte in tale licenza.