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 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 espresso come Q(n2).
Per il significato della notazione Q 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..
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;
}