Mer 21 Agosto, 10:14:38 - 2019

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

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

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 #45 il: Mer 16 Febbraio, 17:19:50 - 2011 »
Non sono..io sono quasi sicura di aver scritto O(n) e la motivazione che ho dato è che la chiamata viene fatta su ogni intero nella lista..quindi al più ho n chiamate..e la prof mi ha sottolineato che in realtà c'è anche la get che ha costo O(n) e che quindi potevo dedurlo da li..fine..
Boh che ti devo dire..forse ricordo male io..
--> "...ma che matrimonio io voglio sperperare un patrimonio, morire in manicomio, andare all’inferno e far impazzire il demonio...!" <-- (Articolo <3)


Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #46 il: Mer 16 Febbraio, 20:21:35 - 2011 »
Si ricordo. Nel mio compito c'era l'iteratore ecco perché in quel caso mi veniva lineare. Parasca te avevi l'altro compito, e sono ormai convinto al 100% che il costo era quadratico  ;D

Offline spin

  • Ricercatore
  • ****
  • Post: 274
  • FeedBack: +3/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #47 il: Mer 23 Febbraio, 16:38:38 - 2011 »

ragazzi voi come lo fareste l'algoritmo per calcolare la chiusura transitiva di un grafo basato su matrice di adiacenza? qualcuno è riuscito a farlo?  ???

Offline dAmore

  • Prof
  • Studente di Dottorato
  • ******
  • Post: 153
  • FeedBack: +44/-11
  • Leggo/scrivo nel forum saltuariamente.
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #48 il: Gio 24 Febbraio, 23:12:56 - 2011 »
ragazzi voi come lo fareste l'algoritmo per calcolare la chiusura transitiva di un grafo basato su matrice di adiacenza? qualcuno è riuscito a farlo?  ???
Basato su liste di adiacenza o su matrice di adiacenza, un algoritmo non cambia (cambia l'implementazione ovviamente). E può cambiare il costo di alcune operazioni.

Offline Wes90

  • Studente di Dottorato
  • ***
  • Post: 200
  • FeedBack: +17/-46
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #49 il: Sab 26 Febbraio, 21:05:35 - 2011 »


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



Qui, perchè è insertion sort? Perchè ad ogni inserimento della priority queue bisogna fare un solo confronto?
Quindi come funziona l'ordinamento nella coda di priorità con lista ordinata, che confronta l'elemento inserito con l'ultimo in lista e se è minore fa uno scambio e così via con l'elemento successivo finchè la lista non è ordinata?
« Ultima modifica: Sab 26 Febbraio, 21:07:20 - 2011 da Wes90 »

Offline psyko

  • Ricercatore
  • ****
  • Post: 285
  • FeedBack: +13/-9
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #50 il: Gio 03 Marzo, 11:22:16 - 2011 »
Qui, perchè è insertion sort? Perchè ad ogni inserimento della priority queue bisogna fare un solo confronto?
Quindi come funziona l'ordinamento nella coda di priorità con lista ordinata, che confronta l'elemento inserito con l'ultimo in lista e se è minore fa uno scambio e così via con l'elemento successivo finchè la lista non è ordinata?
quoto... perchè è insertion sort??

e poi un'altra domanda...
2b) Dimostrare che se il problema PL (0,1) appartenesse a P anche il problema ‘vertex- cover’ (VC) apparterrebbe a P.
per caso si risolve dicendo:
dato che SAT<=p PL{0,1} e SAT<=p VC allora se PL{0,1} appartenesse a P anche SAT apparterrebbe a P e di conseguenza anche VC appartiene a P.

ho detto una cazzata?

Offline nana

  • Studente
  • *
  • Post: 12
  • FeedBack: +4/-0
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #51 il: Gio 03 Marzo, 11:35:35 - 2011 »
1) E' insertion sort perchè nel caso di vettore già ordinato di n elementi, l'algoritmo fa solo gli n confronti ma non modifica nulla perchè il vettore è gia ordinato, quindi in questo caso (che è il caso migliore) insertion sort richiede O(n).

2) anche io farei cosi.

P.S. Le aule 15 e 16 dell'esame di domani sono quelle di via scarpa?

Offline psyko

  • Ricercatore
  • ****
  • Post: 285
  • FeedBack: +13/-9
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #52 il: Gio 03 Marzo, 11:38:29 - 2011 »
"P.S. Le aule 15 e 16 dell'esame di domani sono quelle di via scarpa?" si via scarpa...

grazie per la rapidità :D
invece un altra domanda:
Dare una traccia della dimostrazione che i linguaggi semidecidibili sono tutti e soli i linguaggi di tipo 0.
dove posso trovare la risposta a questa domanda... sto cercando su slide e libro ma non la trovo  :-\
Grazie

Offline nana

  • Studente
  • *
  • Post: 12
  • FeedBack: +4/-0
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #53 il: Gio 03 Marzo, 11:43:48 - 2011 »
C'è nelle slide delle MT alla slide 60

12.3.3 LINGUAGGI DI TIPO 0 E MT
Teorema. Un linguaggio L è semidecidibile se e solo se è un linguaggio di Tipo 0

anche se nel programma dettagliato è scritto che non era necessario saperla....

Offline psyko

  • Ricercatore
  • ****
  • Post: 285
  • FeedBack: +13/-9
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #54 il: Gio 03 Marzo, 11:45:14 - 2011 »
Bella roba -.-"
cmq grazie ancora

Offline nana

  • Studente
  • *
  • Post: 12
  • FeedBack: +4/-0
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #55 il: Gio 03 Marzo, 11:52:30 - 2011 »
Di nulla, figurati  :D

Offline psyko

  • Ricercatore
  • ****
  • Post: 285
  • FeedBack: +13/-9
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #56 il: Gio 03 Marzo, 18:44:09 - 2011 »
mmm un'altra domandina perche mi sa che ho sbagliato a prendere gli appunti... mi confermate che la completezza dell'operatore NOR si dimostra così:

 !(A v B) = A NOR B
 !A = A NOR A
 A v B = (A NOR B) NOR (A NOR B)

e NAND:

 !A = A NAND A
 A v A = !(!A ^ !B) = (A NAND A) NAND (B NAND B)
 A ^ B = (A NAND B) NAND (A NAND B)

??
grazie