Dom 18 Agosto, 07:21:13 - 2019

Autore Topic: Esame Linguaggi Modelli e Complessità  (Letto 8879 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Ntonigà

  • Professore Associato
  • *
  • Post: 542
  • FeedBack: +56/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #30 il: Dom 10 Gennaio, 19:37:08 - 2010 »
No aspe eccolo il problema.
Se gli stati finali sono più d'uno che si fa? E' impossibile :sisi:

Lo stato iniziale diventa finale.
Ammazzi gli stati finali ti crei un nuovo stato iniziale che leggerà l'unione dei caratteri previsti per gli ex stati finali avendo come archi gli archi previsti per gli ex stati finali che si attaccheranno ai nodi giusti.
Tutto trasposto ovviamente.
"Il software è come il sesso, è migliore quando è libero."

Offline Tom89

  • Professore Ordinario
  • **
  • Post: 703
  • FeedBack: +145/-79
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #31 il: Dom 10 Gennaio, 20:08:26 - 2010 »
Uhm ok.
Ma c'è da leggersi da qualche parte? Il prof Schaerf lo aveva accennato ma non ho controllato...

Offline lucaskywalker

  • Studente di Dottorato
  • ***
  • Post: 176
  • FeedBack: +35/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #32 il: Mar 12 Gennaio, 20:42:06 - 2010 »
Ho un problema con questo esercizio del compito di luglio:
2b) Definire il problema decisionale VERTEX COVER (ricoprimento degli archi di un
grafo mediante nodi). Mostrare una istanza positiva e una negativa con almeno 5 nodi e 8
archi. Dimostrare che VERTEX COVER appartiene ad NP.

definire il problema VC e dimostrare che appartiene ad NP li ho fatti,ma il fatto delle istanze con nodi e archi non riesco a risolverlo.qualcuno sa come si fà??

Offline andrea89

  • Author
  • Professore Ordinario
  • **
  • Post: 733
  • FeedBack: +76/-17
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #33 il: Mar 12 Gennaio, 22:14:41 - 2010 »
come fai a dimostrare che è NP?ancora questo non l'ho capito!in teoria ci sono su tutto,ma le dimostrazioni mi fregano!
ll computer non è una macchina intelligente che aiuta le persone
stupide, anzi è una macchina stupida che funziona solo nelle mani delle persone intelligenti (Umberto Eco).

Offline lucaskywalker

  • Studente di Dottorato
  • ***
  • Post: 176
  • FeedBack: +35/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #34 il: Mar 12 Gennaio, 22:26:01 - 2010 »
la dimostrazione dovrebbe stare sulle slide..

Offline Tom89

  • Professore Ordinario
  • **
  • Post: 703
  • FeedBack: +145/-79
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #35 il: Mar 12 Gennaio, 22:49:55 - 2010 »
Domanda di servizio: ma dove e quando è l'esame dopodomani?
Ancora non si sa niente?  ???

Offline lucaskywalker

  • Studente di Dottorato
  • ***
  • Post: 176
  • FeedBack: +35/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #36 il: Mar 12 Gennaio, 22:56:48 - 2010 »
su infostud c'è scritto:    Aule 3, 14 e 15 Via Scarpa. Ore 9:00

spero che ci dicano qualcosa di più preciso perchè l' aula 3 rispetto alla 14 e alla 15 non sta vicinissimo..

Offline Feanoer

  • Ricercatore
  • ****
  • Post: 313
  • FeedBack: +9/-6
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #37 il: Mar 12 Gennaio, 23:58:21 - 2010 »
spero usciranno entro dmn

Offline Apollonius

  • Studente di Dottorato
  • ***
  • Post: 195
  • FeedBack: +15/-6
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #38 il: Gio 28 Gennaio, 13:34:51 - 2010 »
Qualcuno puo aiutarmi con questo esercizio?Definire le classi P, NP, PSPACE. Si consideri il problema della soddisfacibilità di
formule Booleane in forma normale congiuntiva (CNF) con esattamente tre letterali
per clausola (3-SAT).
• Mostrare un’istanza positiva e un’istanza negativa del problema 3-SAT.
• Dimostrare che il problema 3-SAT appartiene a NP.
• Mostrare come si trasforma l’istanza di SAT:
w = (p ∨ q) ∧ (¬p ∨¬q ∨ r ∨ s)
in una istanza di 3-SAT w’ applicando la riduzione da SAT a 3-SAT
• Mostrare tutti i modelli dell’istanza originale w e dell’istanza trasformata w’
• Che conseguenze avremmo sul problema P verso NP se si dimostrasse che,
facendo riferimento a macchine di Turing deterministiche, la complessità del
problema 3-SAT è O (n^ 2).
Allora le definizioni sono P= Uk DTIME(n^k) NP=Uk NTIME(n^k) e PSPACE=Uk DSPACE(n^k) dove cn Uk si intende, ad esempio per P, DTIME(1) unione DTIME(n) unione ... unione DTIME(n^k) e cosi anche per le altre.(Credo sia fatto bene).
Un istanza positiva di 3-SAT può essere (a ∨ b ∨ c )  ∧ (¬a ∨ b ∨ c ) mentre una negativa  (a ∨ b ∨ c )  ∧ (¬a ∨ b ∨ c ) ∧ (a ∨¬ b ∨ c ) ∧ (a ∨ b ∨¬ c ) ∧ (¬a ∨¬ b ∨ c ) ∧ (¬a ∨ b ∨¬ c ) ∧ (a ∨¬ b ∨ ¬c ) ∧ (¬a ∨¬ b ∨ ¬c ) poichè è insoddisfacibile.(e anche questo credo sia fatto bene).
 Per dimostrare che 3-SAT appartiene a NP procedo così : 1) dimostro che SAT appartiene a NP, con la dimostrazione che si trova sulle slide; 2) dico che SAT può essere ridotto a 3-SAT ,  infatti se abbiamo ( a ∨ b ) in 3-SAT diventa (a ∨ b ∨ c )  ∧ (a ∨ b ∨ ¬c ).(e anche questo credo sia fatto bene).
w = (p ∨ q) ∧ (¬p ∨¬q ∨ r ∨ s) diventa in 3-SAT  (p ∨ q ∨ c ) ∧ (p ∨ q ∨ ¬c ) ∧ (¬p ∨ ¬q ∨ c ) ∧ (¬c ∨ r∨ s ) (non sono sicuro che si possa usare sempre lo stesso letterale sia per trasformare la clausola da 2 letterali in quella da 3 sia per trasformare la clausola da 4 letterali in una da 3, in questo caso ho usato c).
Per i modelli di w è facile per i moodelli di w traformata sono troppe le possibili sequenze di assegnazioni per 5 letterali (2^5=32 possibili assegnazioni e il lavoro di verificare se sono accettate è lunghissimo!!) quindi chiedo se qualcuno ha un idea migliore anke perchè usando il mio metodo ci si mette una buona mezz'ora!!
Per l'ultimo punto nn ho neanche idea di quello che mi chiede.
Se qualcuno sa risolvere questi 2 punti che nn so fare glie ne sarei grato.Inoltre spero possa far comodo la soluzione degli altri punti (sperando siano fatti bene) a chi nn sapeva fare neanche quelli. Comunque il compito da cui ho preso l'esercizio è quello del 15/01/09 esercizio 3.
Grazie in anticipo ;)

Offline Feanoer

  • Ricercatore
  • ****
  • Post: 313
  • FeedBack: +9/-6
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #39 il: Gio 28 Gennaio, 14:19:40 - 2010 »
guarda per la prima non saprei...anche io ragionerei come te...e quindi ci vuole tanto tempo. Per l'altra leggi le ultimissime cose scritte in questo topic
http://solo.dis.uniroma1.it/index.php?option=com_smf&Itemid=6&topic=6660.15
JackDuluoz  lo ha spiegato molto bene ;)

Offline giozh

  • Author
  • Direttore di Dipartimento
  • **
  • Post: 2146
  • FeedBack: +148/-108
  • antagonista e me ne compiaccio
    • Mostra profilo
    • sites
Re: Esame Linguaggi Modelli e Complessità
« Risposta #40 il: Gio 28 Gennaio, 15:25:41 - 2010 »
Citazione
(non sono sicuro che si possa usare sempre lo stesso letterale sia per trasformare la clausola da 2 letterali in quella da 3
ogni volta che spezzi la  formula devi aggiungere un nuovo letterale, quindi il c lo puoi usare solo una volta (ovviamente in una metà negato e in un'altra no)
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/CM/E/IT d- s: a-- C++ UL>++++ P L++ !E W++>+++ !N !o K-? !w--- !O- !M- !V PS+ !PE !Y PGP !t 5? !X !R tv+ b++ DI !D G e h r+++ y+++*
------END GEEK CODE BLOCK------

http://inviaggionelpiatto.blogspot.com

Offline Apollonius

  • Studente di Dottorato
  • ***
  • Post: 195
  • FeedBack: +15/-6
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #41 il: Gio 28 Gennaio, 15:26:02 - 2010 »
grazie Feanoer e grazie anche a JackDuluoz ;)
Quindi per quanto riguarda il calcolo dei modelli avremmo 2^6 possibili assegnazioni e il problema di trovare i modelli diventa incredibilmente grosso!!
Qualcuno ha un idea migliore per risolverlo??
« Ultima modifica: Gio 28 Gennaio, 15:27:38 - 2010 da Apollonius »

Offline Feanoer

  • Ricercatore
  • ****
  • Post: 313
  • FeedBack: +9/-6
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #42 il: Gio 28 Gennaio, 16:57:13 - 2010 »
di niente :D

Offline giozh

  • Author
  • Direttore di Dipartimento
  • **
  • Post: 2146
  • FeedBack: +148/-108
  • antagonista e me ne compiaccio
    • Mostra profilo
    • sites
Re: Esame Linguaggi Modelli e Complessità
« Risposta #43 il: Ven 29 Gennaio, 10:24:06 - 2010 »
Citazione
grazie Feanoer e grazie anche a JackDuluoz Wink
Quindi per quanto riguarda il calcolo dei modelli avremmo 2^6 possibili assegnazioni e il problema di trovare i modelli diventa incredibilmente grosso!!
Qualcuno ha un idea migliore per risolverlo??
purtroppo i modelli sono quelli, e che io sappia un metodo "piu veloce" per scrivere tutti i modelli e vedere quali soddisfano la formula o meno e semplicemente avere pazienza. mi ricordo che a lezione schaerf per un 3sat si è scritto tutti i possibili modelli e se li è provati uno per uno (anche se a volte alcuni modelli che non soddisfano la formula li vedi ad occhio)
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/CM/E/IT d- s: a-- C++ UL>++++ P L++ !E W++>+++ !N !o K-? !w--- !O- !M- !V PS+ !PE !Y PGP !t 5? !X !R tv+ b++ DI !D G e h r+++ y+++*
------END GEEK CODE BLOCK------

http://inviaggionelpiatto.blogspot.com

Offline Feanoer

  • Ricercatore
  • ****
  • Post: 313
  • FeedBack: +9/-6
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #44 il: Ven 29 Gennaio, 12:03:49 - 2010 »
Ragà ho due dubbi...
Citazione
2b) Definire il problema decisionale PL-{0,1} (programmazione lineare con variabili in
{0,1}) Mostrare una istanza positiva e una negativa con almeno 4 variabili e 6
equazioni.Dimostrare che PL-{0,1} appartiene ad NP.
Qui,volevo scrivere le istanze positive e negative in modo SAT e poi essendo SAT<=PPL lo trasformavo...lasciando x se è positiva e mettendo 1-x se x è negativa.
Lui mi chiede almeno 4 variabilI e 6 equazioni...quindi io dovrei scrivere sei clausole e fino qui ok. La domanda è..ma ogni clausola deve contenere 4 letterali? O non necessariamente tutte le clasuole devono averle 4...basta che in generale le 6 clasuole hanno in totale 4 letterali?

Secondo dubbio
Citazione
1a) Fornire una traccia della dimostrazione che ogni linguaggio di tipo 2 è riconoscibile
con un automa a pila non deterministico.
Sul libro quale dimostrazione è?