Fondamenti di informatica (SSE e Statistica)
Prova scritta del 4 giugno 2001

Domanda 1
Scrivere un programma C che legge da tastiera 20 interi, e li stampa ordinati in senso non 
decrescente usando l'algoritmo insertion-sort.  Calcolare la complessità asintotica del programma 
proposto, nel caso peggiore. Spiegare il significato delle notazioni usate per esprimere la 
complessità asintotica.

Soluzione
#include <stdio.h>
#include <conio.h>
#define NMAX 20

void insertion_sort(int *v)
{	int i, j, new_el;

	for(i=1; i<NMAX; i++) {
		new_el=v[i];
		for(j=i; (j>0) && (v[j-1]>new_el); j--) {
			v[j] = v[j-1];
		}
		if (j!=i)
v[j]=new_el;
	}
}

void leggi_vettore(int *vett)
{	int i;

	for (i=0;i<NMAX;i++) {
		printf("v[%d] = ",i);
		scanf("%d",&vett[i]);
	}
}

void stampa_vettore(int *vett)
{	int i;

	printf("\n\n");
	for (i=0;i<NMAX;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}

main()
{     int v[NMAX];

	clrscr();
	leggi_vettore(v);
	insertion_sort(v);
	stampa_vettore(v);
	getch();
	return 0;
}

L'algoritmo di insertion sort, nel caso peggiore, esegue una serie di scansioni dell'array di 
lunghezza crescente da 1 a n-1, dove n è il numero totale di elementi. Quindi la sua complessità nel 
caso peggiore è data dalla somma 1+2+3+...+(n-2)+(n-1), che in notazione asintotica può essere 
espressa come ?(n2).
Per il significato della notazione ? si veda il testo di Cormen, Leicerson e Rivest, 
Introduzione agli Algoritmi, vol. 1, pagg. 21 e seguenti.

Domanda 3
Descrivere l'utilità e il funzionamento dello strato del sistema operativo che si occupa della 
gestione dei processi.

Soluzione
Si veda il testo di Bellini, Guidi, pagg. 268 e seguenti..



Domanda 2
Scrivere un funzione C di nome max_subseq che, dati come parametri un array di interi V e 
il numero di elementi in esso contenuti, restituisce la lunghezza massima di una sottosequenza di 
elementi adiacenti tutti strettamente maggiori della media degli elementi in V.
Esempio:
se alla funzione venissero passati i seguenti parametri

vettore 4 5 6 5 7 9 8 4 3 2 6 7    e lunghezza  12

essendo la media degli elementi uguale a 5.5, la funzione dovrebbe restituire il valore 3 
(infatti, tra le sottosequenze sotto evidenziate, la più lunga contiene tre elementi)

4 5 6 5 7 9 8 4 3 2 6 7

Soluzione
La funzione proposta utilizza una funzione ausiliaria per il calcolo della media degli elementi 
nell'array.
Una volta calcolata la media, si può utilizzare una variabile maxlung che mantiene la 
lunghezza massima delle sottosequenze incontrate, ed un'altra variabile lung che invece misura la 
lunghezza della sottosequenza in esame.
Si procede con la scansione dell'array: quando si incontra un elemento maggiore della media 
si incrementa il contatore lung, quando invece si incontra un elemento non maggiore della media 
allora si interrompe la sottosequenza, e si confronta la lunghezza raggiunta con il valore di 
maxlung, eventualmente aggiornandolo.
Alla fine della scansione, si dovrà verificare se l'ultima sottosequenza (per la quale non è stato 
incontrato un elemento di "chiusura" minore o uguale alla media) è quella di lunghezza massima.


float mediavett(int *v, int n)
{
int i;
float somma;

somma=0;
for(i=0; i<n; i++){
		somma += v[i];
}
return somma/n;

}




int max_subseq(int *v, int n)
{
int i, lung, maxlung;
float media;

lung=0;   /* lung rappresenta la lunghezza della sottosequenza corrente */
maxlung=0;  /* maxlung rappresenta la lunghezza massima incontrata */
media=mediavett(v,n);

for(i=0; i<n; i++){
		if(v[i]>media)  /* in questo caso la sottosequenza continua */
			lung++;
		else {          /* altrimenti termina */
			if (lung>maxlung)
/* confronto la lunghezza della s.seq. appena terminata con maxlung */
				maxlung=lung;    /* ed eventualmente aggiorno */
			lung=0;
/* in ogni caso la sottosequenza e' terminata, e lung riparte da 0 */
		}
}
	if (lung>maxlung)      /* confronto la lunghezza dell'ultima s.seq. */
		maxlung=lung;
return maxlung;
}