Dom 18 Agosto, 06:52:57 - 2019

Autore Topic: Testo esame 7 Febbraio 2011  (Letto 7350 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Numa Pompilio

  • Guru
  • Direttore di Dipartimento
  • *****
  • Post: 2750
  • FeedBack: +120/-168
    • Mostra profilo
    • New Guernica
Testo esame 7 Febbraio 2011
« il: Mar 08 Febbraio, 19:22:55 - 2011 »
Qualcuno di voi ha il testo/i dell'esame?
Yawn è un guru in queste cose

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #1 il: Mar 08 Febbraio, 19:26:33 - 2011 »
Io pensando di non passarlo, mi sono presta tutti i testi possibili immaginabili  :asd: ora ringraziando il cielo non ne ho più bisogno! Però non ho lo scanner quindi le soluzioni sono 2: o ve lo scrivo, o provo a fotografarlo sperando si veda decentemente..! Ora vedo..
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline Numa Pompilio

  • Guru
  • Direttore di Dipartimento
  • *****
  • Post: 2750
  • FeedBack: +120/-168
    • Mostra profilo
    • New Guernica
Re: Testo esame 7 Febbraio 2011
« Risposta #2 il: Mar 08 Febbraio, 19:27:03 - 2011 »
Io pensando di non passarlo, mi sono presta tutti i testi possibili immaginabili  :asd: ora ringraziando il cielo non ne ho più bisogno! Però non ho lo scanner quindi le soluzioni sono 2: o ve lo scrivo, o provo a fotografarlo sperando si veda decentemente..! Ora vedo..

foto, foto ;)
Yawn è un guru in queste cose

Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #3 il: Mar 08 Febbraio, 19:28:46 - 2011 »
Io pensando di non passarlo, mi sono presta tutti i testi possibili immaginabili  :asd: ora ringraziando il cielo non ne ho più bisogno! Però non ho lo scanner quindi le soluzioni sono 2: o ve lo scrivo, o provo a fotografarlo sperando si veda decentemente..! Ora vedo..


L'esame come ti è sembrato?Difficile rispetto allo scorso anno?

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #4 il: Mar 08 Febbraio, 19:38:42 - 2011 »

L'esame come ti è sembrato?Difficile rispetto allo scorso anno?

Allora..difficile era quello degli anni scorsi..io l'ho trovato atroce..oh boh, avrò studiato poco, ma la parte di linguaggi secondo me era inaccessibile..boh..è uscito il teorema della deduzione con tanto di esempio di applicazione..cioè bah io non lo sapevo O.o e altre dimostrazioni che bohhh! Algoritmi l'ho trovato più facile (rispetto a linguaggi)..solo che ho sentito che molti hanno trovato difficoltà nel primo esercizio..chiedeva di scrivere 2 versioni del codice che aveva dato il prof con delle modifiche..e hanno trovato difficoltà a capire proprio cosa faceva l'algoritmo del prof..figurati riscriverlo XD Io personalmente ho trovato più difficoltà nel terzo esercizio..implementazione della chiusura transitiva..floyd..non me l'ero proprio visto, pensando fosse assurdo che uscisse..e invece..ed ho sentito la prof lamentarsi che non aveva corretto nessuna chiusura transitiva perchè quasi nessuno l'aveva fatta..(nessuno delle..20 persone che eravamo?! asd)

Comunque pessima notizia..le foto non si vedono..mi metto al lavoro per scrivervelo qua XD

Citazione
Parte Modelli

Premessa: tempo a disposizione 90 minuti. Ognuna delle domande vale 10 punti, 5 per la teoria (parte a) e 5 per l'esercizio (parte b). Per avere la sufficienza è necessario ottenere almeno 18 punti totalizzando 9 punti sulle domande di tipo a) e 9 sulle domande di tipo b)

Compito A


Domanda 1
1a) Definire le grammatiche di tipo 3. Mostrare un esempio di grammatica di tipo 3 che genere un linguaggio infinito e per tale esempio mostrare 3 stringhe che appartengono al linguaggio da essa generato e 3 stringhe che non appartengono al linguaggio da essa generata. Dare traccia della dimostrazione che ogni linguaggio generato da una grammatica di tipo 3 può essere riconosciuto da un automa a stati finiti deterministico.
1b) Sia L = {wwR | w € {a,b}+ } . Fornire la grammatica che genera il linguaggio L*.

Domanda 2
2a) Definire i linguaggi decidibili ed i linguaggi semidecidibili. Definire un linguaggio che è semidecidibile ma non decidibile (dare almeno una traccia della dimostrazione)
2b) Dimostrare che se il problema PL(0,1) appartenesse a P anche il problema della soddisfacibilità (SAT) apparterrebbe a P.

Domanda 3
3a) Illustrare i metodi Convert1 e Convert2 per mettere in forma normale congiuntiva una formula booleana. Perchè sono stati proposti due diversi metodi?
3b) Dimostrare (spiegando il procedimento seguito) che in base alle premesse:
A -> B, A and B -> C, B and C -> D  posso concludere !A v D


Compito B


Domanda 1
1a) Definire le espressioni regolari. Mostrare un esempio di espressione regolare e per tale esempio mostrare 3 stringhe appartenenti al linguaggio da essa definito e 3 stringhe non appartenenti. Dare una traccia della dimostrazione che ogni linguaggio definito da un'espressione regolare può essere generato da una grammatica di tipo 3.
1b) Sia L = {an,bn | n>= 1 }. Fornire la grammatica che genera il linguaggio L*.

Domanda 2
2a) Definire i linguaggi decidibili e i linguaggi semidecidibili. Dare una traccia della dimostrazione che i linguaggi semidecidibili sono tutti e soli i linguaggi di tipo 0.
2b) Dimostrare che se il problema PL(0,1) appartenesse a P anche il problema vertex-cover (VC) apparterrebbe a P.

Domanda 3
3a) Enunciare il "Teorema di Deduzione", spiegarne il significato e mostrarne una applicazione.
3b) Dimostrare (spiegando il procedimento seguito) che in base alle premesse:
A -> B, A and B -> C, A  posso concludere B and C
« Ultima modifica: Mar 08 Febbraio, 19:58:36 - 2011 da Parasca »
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline Numa Pompilio

  • Guru
  • Direttore di Dipartimento
  • *****
  • Post: 2750
  • FeedBack: +120/-168
    • Mostra profilo
    • New Guernica
Re: Testo esame 7 Febbraio 2011
« Risposta #5 il: Mar 08 Febbraio, 20:04:49 - 2011 »
grande
Yawn è un guru in queste cose

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #6 il: Mar 08 Febbraio, 20:57:14 - 2011 »
Citazione
Parte Algoritmi

10 punti a problema.

Compito B

Problema 1

Si consideri il metodo incrementa(LinkedList<Integer> cifre) che, data una lista che contiene le cifre di un generico numero intero (da quella meno significativa a quella più significativa), incrementa di una unità il valore (facendo side-effect sulla lista stessa).

Codice: [Seleziona]
public static void incrementa(LinkedList<Integer> cifre) {
 incrementaRic(cifre, 0);
}
private static void incrementaRic(LinkedList<Integer> cifre, int index) {
 if (index >= cifre.size()) {
  cifre.add(1);
  } else {
        Integer val = cifre.get(index);
        if (val < 9) {
            cifre.set(index, val + 1);
         } else {
              cifre.set(index, 0);
              incrementaRic(cifre, index + 1);
            }
      }
  }

Si richiede quanto segue:

a) Determinare giustificando opportunatamente, il costo computazionale del metodo incrementa in funzione della dimensione dell'input.

b) Scrivere il metodo statico java decrementa(LinkedList<Integer> cifre) che decrementa di una unità il valore rappresentato dall'iteratore (secondo le medesime convensioni del metodo incrementa(...)). Assumere che il valore passato come parametro sia strettamente positivo. Determinare, giustificando oppurtanamente, il costo del metodo.

c) Scrive il metodo statico java LinkedList<Integer> differenza(LinkedList<Integer> a, LinkedList<Integer> b) che, utilizzando i metodi incrementa(...) e/o decrementa(...) definiti in precedenza, calcoli e restituisca il valore a-b (assumendo a>=b ). Determinare, giustificando opportunatamente, il costo del metodo.


Problema 2
Con riferimento al tipo astratto Coda di Priorità si richiede quanto segue:

a) Definire il tipo astratto Coda di Priorità realizzando una possibile interfaccia java PQ che lo descrive.

b) Realizzare la classe astratta java PQListaNonOrdinata che implementa l'interfaccia PQ e che rappresenta una coda di priorità realizzata mediante lista non ordinata contenente chiavi di tipo intero. La classe deve contenere tutte le variabili di istanza e le firme dei metodi fondamentali oltre alla implementazione del metodo di rimozione del valore minimo. Di ogni metodo deve infine essere indicato (e motivato) il costo computazionale.

c) Definire il metodo static void PQsort(int[] array) che ordina il vettore array mediante una coda di priorità PQListaOrdinata. Indicarne poi, motivandolo adeguatamente, il costo computazionale.


Problema 3
Con riferimento ai grafi orientati si richiede quanto segue:

a) Definire il concetto di chiusura transitiva di un grafo.

b) Definire una possibile rappresentazione per un grafo basata su matrice di adiacenza realizzando una classe astratta java Graph contenente tutte le variabili di istanza e le firme di tutti i metodi pubblici che si ritiene fondamentali per risolvere il problema successivo.

c) Realizzare un metodo di istanza della classe Graph la cui firma è Graph chiusuraTransitiva() che calcola la chiusura transitiva del grafo this. Descrivere poi il costo computazionale dell'algoritmo, motivandolo opportunatamente.
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #7 il: Mar 08 Febbraio, 21:05:46 - 2011 »
Citazione
Parte Algoritmi

10 punti a problema.

Compito A

Problema 1

Si consideri il metodo incrementa(ListIterator<Integer> cifre) che, data una lista che contiene le cifre di un generico numero intero (da quella meno significativa a quella più significativa), incrementa di una unità il valore (facendo side-effect sulla lista stessa).

Codice: [Seleziona]
public static void incrementa(ListIterator<Integer> cifre) {
 if (!cifre.hasNext()) {
  cifre.add(1);
  } else {
        Integer val = cifre.next();
        if (val < 9) {
            cifre.set(val + 1); //Costo costante
         } else {
              cifre.set(0);  //costo costante
              incrementa(cifre);
            }
      }
  }

Si richiede quanto segue:

a) Determinare giustificando opportunatamente, il costo computazionale del metodo incrementa in funzione della dimensione dell'input.

b) Scrivere il metodo statico java decrementa(ListIterator<Integer> cifre) che decrementa di una unità il valore rappresentato dall'iteratore (secondo le medesime convensioni del metodo incrementa(...)). Assumere che il valore passato come parametro sia strettamente positivo. Determinare, giustificando oppurtanamente, il costo del metodo.

c) Scrive il metodo statico java ListIterator<Integer> differenza(ListIterator<Integer> a, ListIterator<Integer> b) che, utilizzando i metodi incrementa(...) e/o decrementa(...) definiti in precedenza, calcoli e restituisca il valore a-b (assumendo a>=b ). Determinare, giustificando opportunatamente, il costo del metodo.


Problema 2
Con riferimento al tipo astratto Coda di Priorità si richiede quanto segue:

a) Definire il tipo astratto Coda di Priorità realizzando una possibile interfaccia java PQ che lo descrive.

b) Realizzare la classe astratta java PQListaOrdinata che implementa l'interfaccia PQ e che rappresenta una coda di priorità realizzata mediante lista ordinata contenente chiavi di tipo intero. La classe deve contenere tutte le variabili di istanza e le firme dei metodi fondamentali oltre alla implementazione del metodo di inserimento di un nuovo elemento. Di ogni metodo deve infine essere indicato (e motivato) il costo computazionale.

c) Definire il metodo static void PQsort(int[] array) che ordina il vettore array mediante una coda di priorità PQListaOrdinata. Indicarne poi, motivandolo adeguatamente, il costo computazionale.


Problema 3
Con riferimento ai grafi orientati si richiede quanto segue:

a) Definire il concetto di chiusura transitiva di un grafo.

b) Definire una possibile rappresentazione per un grafo basata su liste di adiacenza realizzando una classe astratta java Graph contenente tutte le variabili di istanza e le firme di tutti i metodi pubblici che si ritiene fondamentali per risolvere il problema successivo.

c) Realizzare un metodo di istanza della classe Graph la cui firma è Graph chiusuraTransitiva() che calcola la chiusura transitiva del grafo this. Descrivere poi il costo computazionale dell'algoritmo, motivandolo opportunatamente.

--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #8 il: Mar 08 Febbraio, 22:24:46 - 2011 »

Grazie per i testi!Meno male che non sono venuto!

Mi ha fatto ridere la domanda di modelli "Perchè sono state 2 modelli di Convert?"

E che ne so!Non c'è risposta da nessuna parte  :asd:


Invece le domande pre-test?

Offline Mordicchio

  • Studente di Dottorato
  • ***
  • Post: 149
  • FeedBack: +27/-5
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #9 il: Mar 08 Febbraio, 23:15:55 - 2011 »
Invece le domande pre-test?

In confronto ai compiti di algoritmi e modelli erano delle vere e proprie passeggiate di salute (eppure c'è stato più di qualcuno che non è riuscito a passare nemmeno il pre-test)... erano 12 domande a risposta multipla, cerco di riepilogare quelle che mi ricordo: tautologia, automa a stati finiti, macchine a registri, numero minimo di albero con n-nodi, qual è l'algoritmo di ordinamento più efficiente da usare con un array già ordinato, definizione di classe di complessità temporale, ecc.
« Ultima modifica: Mar 08 Febbraio, 23:17:59 - 2011 da Mordicchio »
Pessuno è nerfetto

Offline DFirmani

  • Prof
  • Studente
  • ******
  • Post: 29
  • FeedBack: +13/-2
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #10 il: Mar 08 Febbraio, 23:54:55 - 2011 »
..implementazione della chiusura transitiva..floyd..non me l'ero proprio visto, pensando fosse assurdo che uscisse..e invece..ed ho sentito la prof lamentarsi che non aveva corretto nessuna chiusura transitiva perchè quasi nessuno l'aveva fatta..(nessuno delle..20 persone che eravamo?! asd)

C'è anche da dire che non ho corretto nessuna chiusura transitiva... sui 5 esami che ho corretto... non sul totale.
Esagerate sempre... :-P

Offline Wash_88

  • Studente di Dottorato
  • ***
  • Post: 239
  • FeedBack: +27/-3
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #11 il: Mer 09 Febbraio, 00:45:33 - 2011 »
Invece le domande pre-test?

1. Un algoritmo O(n logn) è sicuramente...

  • O(n)
  • \Omega(n2)
  • \Omega(n)
  • O(n2)

2. Una classe di complessità temporale contiene:

  • tutti i linguaggi riconoscibili entro una quantità di tempo fissata
  • tutti i linguaggi non trattabili con macchine di Turing
  • tutti i linguaggi non decidibili con macchine di Turing
  • tutti i linguaggi non riconoscibili entro una quantità di tempo fissata

3. Se il problema P ammette lower bound \Omega(n2)

  • nessun algoritmo lo risolve in tempo O(n)
  • nessun algoritmo lo risolve in tempo \Omega(n2)
  • sicuramente esiste un algoritmo che lo risolve in tempo O(n2)
  • tutti gli algoritmi che lo risolvono, lo risolvono in tempo O(n2)

4. Un automa a stati finiti è

  • un dispositivo formale per il riconoscimenti di linguaggi regolari
  • un dispositivo formale per il riconoscimenti di linguaggi context-free
  • un dispositivo formale per il riconoscimenti di linguaggi trattabili
  • un dispositivo formale per il riconoscimenti di linguaggi naturali

5. Il problema della terminazione:

  • dipende dal fatto che le MT sono meno potenti dei normali calcolatori
  • è un tipico esempio di problema non trattabile
  • è un tipico esempio di problema non decidibile
  • può essere risolto da macchine di Turing non deterministiche

6. L'altezza minima di un albero di n nodi è

  • n/2
  • log n
  • 1
  • n

7. Se l'algoritmo A calcola la funzione a(x) in tempo O(fA(|x|)) (avendo indicato con |x| il numero di bit necessari e sufficienti a rappresentare x) e l'algoritmo B calcola la funzione b(x) in tempo O(fB(|x|)), allora esiste un algoritmo C che calcola la funzione a(b(x)) in tempo

  • fB(|x|) + fA(|b(x)|)
  • |fA(b(|x|))|
  • fA(b(|x|)
  • fB(|x|) + fA(|x|)

8. Una tautologia è:

  • una formula proposizionale che ha almeno un modello che la soddisfa
  • una regola di inferenza del sistema di deduzione hilbertiano
  • una formula proposizionale che è soddisfatta da tutti i modelli
  • una formula proposizionale che ha almeno la metà dei modelli che la soddisfano

9. In un grafo semplice e non orientato di n nodi il massimo numero di spigoli è

  • n(n-1)/2
  • n(n-1)
  • n2/2
  • n

10. Il linguaggio {anbn | n>=1} è

  • un classico esempio di linguaggio decidibile ma non context-sensitive
  • un classico esempio di linguaggio regolare
  • un classico esempio di linguaggio context-free ma non regolare
  • un classico esempio di linguaggio context-sensitive ma non context-free

11. Le macchine a registri

  • sono in grado di calcolare funzioni non calcolabili con macchine di Turing
  • sono in grado di calcolare solo funzioni crescenti
  • sono in grado di calcolare le stesse funzioni calcolabili con macchine di Turing
  • possono calcolare solo somme e prodotti

12. Nel caso di array già ordinato, qual'è il più conveniente fra i seguenti algoritmi di ordinamento?

  • Selection-sort
  • Merge-sort
  • Insertion-sort
  • Heap-sort

Soglia di ammissione: 9 risposte corrette.
« Si dice che il minimo battito d’ali di una farfalla sia in grado di provocare un uragano dall’altra parte del mondo »

Offline Wash_88

  • Studente di Dottorato
  • ***
  • Post: 239
  • FeedBack: +27/-3
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #12 il: Mer 09 Febbraio, 01:10:57 - 2011 »
Per quanto mi riguarda, l'esame era fattibile, ma la parte di algoritmi era veramente lunga: non sono nemmeno riuscito a iniziare i punti b) e c) del terzo esercizio. La parte di modelli, invece, se si aveva studiato, si poteva fare senza tanti problemi.

Mi ha fatto ridere la domanda di modelli "Perchè sono state 2 modelli di Convert?"

E che ne so!Non c'è risposta da nessuna parte  :asd:

La risposta a questa domanda c'è sulle slide: sta a pagina 5 e 6 delle slide 8.3 Logica.  ;)
« Si dice che il minimo battito d’ali di una farfalla sia in grado di provocare un uragano dall’altra parte del mondo »

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #13 il: Mer 09 Febbraio, 09:39:05 - 2011 »
Mi tocca rifare la parte di linguaggi a marzo. E pure il pre-test anche se non è molto logico che rifaccia il pre-test xD
Che voi sappiate, per rifare solo una parte, ci si riprenota normalmente?

Offline Parasca

  • Direttore di Dipartimento
  • ***
  • Post: 1909
  • FeedBack: +267/-229
  • Una scrivania ordinata è sintomo di mente malata!
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #14 il: Mer 09 Febbraio, 10:45:51 - 2011 »
Grazie per i testi!Meno male che non sono venuto!

Mi ha fatto ridere la domanda di modelli "Perchè sono state 2 modelli di Convert?"

E che ne so!Non c'è risposta da nessuna parte  :asd:


Invece le domande pre-test?

Se non ricordo male vennero create due convert perchè con la convert1 si rischiava di arrivare a millemila clausole..mentre la convert2 accorciava un po'..
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)