Verifiche Didattiche On-line (VeDO)
Vista HTML soluzione compito
|
|
Compito: Dicembre
|
|
Domande con soluzione
|
Dichiarare l'equivalenza (ossia, l'uguaglianza dell'insieme delle frasi) dei seguenti gruppi di espressioni regolari (considerare come alfabeto i simboli 0 e 1):
 {{0}{1}}, {0|1} sono equivalenti fra loro
 {{0}0{1}1}, {0|1} sono equivalenti fra loro
{0{12}}, {0|12} sono equivalenti fra loro
{0{12}}, [0{0|12}] sono equivalenti fra loro
|
Si consideri la grammatica sull'alfabeto costituito dal solo simbolo 0, e le cui frasi sono tutte e sole le stringhe che hanno almeno 100 zeri. Allora il linguaggio di tale grammatica:
è di tipo 3
è riconoscibile da un automa a stati finiti
è riconoscibile da un automa a stati finiti con meno di 50 stati
è riconoscibile da una macchina di Turing
|
E' possibile costruire una macchina di Turing che:
non termina la computazione con qualunque input
se l'input è una sequenza di 2 allora non termina, e in tutti gli altri casi termina lasciando tale sequenza inalterata
con 10'000 stati
che preso in ingresso un numero n (positivo) espresso in binario, calcola e scrive sul nastro l'n-esimo numero della serie di Fibonacci
|
Si consideri la codifica di numeri interi in complemento a 2 (con soli 4 bit), allora:
il più grande numero codificabile è 8
il più piccolo numero codificabile è -8
il numero -4 si codifica in 1100
applicando il complemento a 2 al numero -8 si riottiene il numero -8
|
L'algoritmo di ricerca dicotomica (o binaria):
E' applicabile solo ad array ordinati
Ha complessita' in tempo logaritmica
Ha complessità in tempo peggiore di quella quadratica
E' mediamente più veloce della ricerca sequenziale
|
Si consideri il tipo List per le liste visto a lezione, realizzato in C con una struct con campi head (di tipo int) e tail (di tipo List*). Si consideri anche una funzione con prototipo 'List *cons(int,List*)', che prende una testa e una coda, e alloca nello heap la struct List corrispondente e la ritorna in uscita. Allora, dopo l'esecuzione di queste due istruzioni: List *l1=cons(10,NULL); l1->tail=l1; si ha che:
int i=l1->tail->head; associa ad i il valore 0
int i=l1->tail->head; associa ad i il valore 10
int i=l1->tail->head; causa un Segmentation Fault
int i=l1->tail->tail->tail->head; causa un Segmentation Fault
|
La funzione malloc del C:
E' definita nella libreria stdio
Torna in uscita un puntatore
Alloca spazio nella memoria stack
Prende in ingresso il numero di bit della memoria da allocare
|
Considerando un ordine di valutazione standard (post-order sull'Abstract Syntax Tree), il * meno prioritario del -, il - associativo a destra, il * associativo a sinistra, allora l'espressione 1-3*4-5-4*3*2:
quando valutata, valuta gli operatori nell'ordine -,-,-,*,*,*
quando valutata, valuta gli operatori nell'ordine -,*,-,-,*,*,*
quando valutata, ritorna -36
quando valutata, ritorna -12
|
Considerando le varie tipologie di memoria disponibile nell'architettura di un calcolatore:
i registri della CPU hanno meno capienza rispetto alla memoria centrale (RAM)
la memoria centrale (RAM) ha un tempo d'accesso più alto rispetto ai dischi magnetici (ad esempio rispetto ad un hard disk)
alcuni dati possono essere trasferiti dalla memoria centrale (RAM) alla memoria secondaria per effetto di Swapping
alcuni dati possono essere trasferiti dalla memoria centrale (RAM) alla cache della CPU per effetto di Caching
|