C.d.L. in SCIENZE AMBIENTALI
Teoria e Applicazioni delle Macchine Calcolatrici
Prova scritta del 19/3/'98

1)	Descrivere, mediante diagramma di flusso, un algoritmo che legge da standard input un testo qualsiasi (sequenza di caratteri) terminato da ‘..’, lo memorizza in un vettore T, e quindi conta quante volte la parola ‘cioe`’ è presente nel testo dando poi il risultato ottenuto su standard output.
2)	Descrivere mediante diagramma sintattico la grammatica di un linguaggio sull’alfabeto {1} costituito da tutte e sole le sequenze di 1 di lunghezza dispari.
3)	Con riferimento all’esercizio (1), realizzare in Pascal (a) una funzione CONTA che, presi come parametri di ingresso un testo A e la sua dimensione n, restituisce come risultato il numero p delle occorrenze della parola ‘cioe`’ in A; (b) il programma principale (completo) che legge da standard input il testo T  (dimensione max. 5000 caratteri), richiama CONTA su T, e ne stampa il risultato su standard output.
4)	Scrivere un sottoprogramma Pascal (iterativo e/o ricorsivo) che realizza la seguente funzione: f(n) = Isu(i = 1,n,i2).
5)	Si consideri la seguente procedura (ricorsiva) di visita di un albero T, scritta in linguaggio Pascal-like (si supponga che T1, T2,...,Tn siano sottoalberi di T, e che figli(N) sia una funzione che restituisce l’insieme dei sottoalberi che hanno N come nodo padre):
		procedure VISITAxx({T1,T2,...,Tn});
			esamina la radice R1 di T1;
			esamina la radice R2 di T2;
			...
			esamina la radice Rn di Tn;
			VISITAxx(figli(R1) » figli(R2) » ... » figli(Rn));
Qual’e’ l’ordine di visita dei nodi di un generico albero T a seguito della chiamata VISITAxx({T})? Giustificare la risposta e fornire un esempio.
6)	Considerando la rappresentazione dei numeri reali <mantissa,esponente>, con mantissa numero frazionario in modulo e segno ed esponente intero in complemento a 2, dire a quale numero corrisponde il seguente numerale: <110100000,111101> (n.b., bit più a sinistra = bit del segno).
7)	(a) Quanti caratteri puo' contenere una memoria principale di 2Megabyte di dimensione? (b) E un disco magnetico di 1.5Gigabyte? (c) Quanti numeri interi in complemento a 2 possono essere memorizzati in un dischetto da 1400Kbyte? (indicare esplicitamente quali ipotesi si fanno sull'occupazione di memoria di un carattere e di un numero intero).
8)	Dire cosa è, come funziona, ed a cosa serve l’Interfaccia Utente-Sistema Operativo (max. 1 pagina, min. 20 righe).
9) Qual’è l’ordine di grandezza della complessità computazionale dell’algoritmo realizzato al punto (4)?
10) Illustrare mediante disegno l'effetto prodotto dall'esecuzione delle seguenti istruzioni Pascal:
		new(X);
		X^.PUNT1 := X;
		X^.PUNT2 := X^.PUNT1;
assumendo che siano date le seguenti dichiarazioni:
		type ELEM =	record
			INFO: char;
			PUNT1, PUNT2: ^ELEM
			end;
		var X: ^ELEM;