Fondamenti di Informatica II: prima verifica

3 maggio 1999

Domande di teoria (15 punti):

1. si definisca il concetto di complessità computazionale asintotica e si dia la definizione di $\Theta(n)$ (4 punti);
2. si dimostri che un algoritmo avente complessità computazionale pari ad un polinomio di grado $m$ è di classe $O(n^m)$, ovvero:
   
   $$a_mn^m+a_{m-1}n^{m-1}+\ldots+a_1n+a_0=\sum_{j=0}^{m}a_jn^j\in O(n^m)$$
   
   
   (4 punti)
3. si descrivano i possibili metodi di memorizzazione tramite rappresentazioni concatenate e se ne sintetizzino le caratteristiche (7 punti)

Esercizio di programmazione da svolgere al computer (15 punti):

Si sviluppi un programma che iterativamente chieda il nome di un file ASCII contenente riga per riga il nome di una materia di esame e, sulla successiva, il relativo voto, stampi il contenuto del file ordinandolo a partire dal voto più alto e stampi anche la media risultante dei voti calcolata non considerando i due voti più bassi.

Nello sviluppare il programma si consideri che:

• i voti sono tutti numeri interi da 18 a 30;
• la lunghezza massima dei nomi delle materie è 50 caratteri;
• il numero massimo degli esami non è definito, mentre il numero minimo è 3;

Esempio di file di input:

Il programma sviluppato sarà giudicato in funzione dei seguenti parametri:

• efficacia ed efficienza (3 punti);
• aderenza allo standard ANSI C (3 punti);
• commenti (3 punti);
• struttura (2 punti);
• adeguatezza delle strutture dati scelte (4 punti);

Le prime righe del programma devono contenere i dati anagrafici del candidato, ben evidenziati. Generare il file di input mediante un comune editor. Al termine della prova salvare il programma nel direttorio radice dell'unità disco F:; i primi 8 caratteri del nome del candidato rappresenteranno il nome del programma (estensione .C).