Lun 18 Marzo, 18:33:08 - 2019

Autore Topic: Modelli  (Letto 522 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Modelli
« il: Mar 13 Giugno, 18:53:18 - 2017 »
ciao a tutti,
ho provato a svolgere un testo di esame degli anni passati. Ho avuto difficoltà a risolvere il problema 2 nel senso che non riesco proprio a capire cosa chieda il testo. Inoltre ho avuto anche difficoltà su problema 4 nello spiegare perchè si dice tesi e no teorema. E infine sul problema 5. Ora posto le mie personali soluzioni di cui non sono per niente sicuro, magari confrontandoci può essere di aiuto.

PROBLEMA 1

(a) Definire formalmente il concetto di espressione regolare.
    
   Dato un alfabeto Σ U {+, °, ,*, (, ) } , chiamiamo espressione regolare la stringa r Є Σ tale che:
   
      1. r=ø oppure
      2. r Є Σ oppure
      3. r=s+t oppure r=s°t oppure r = s*  dove s e t sono anche esse espressioni regolari
      
(b) Definire formalmente il concetto di linguaggio rappresentato da una espressione regolare

        Il linguaggio L(e) rappresentato da un espressione regolare è induttivamente definito come segue:
        e                    L(e)

        Ø                     Λ
        a                    {a}  (per ogni simbolo a ∈ Σ)
       (s+t),              L(s) ∪ L(t)
       (s°t),               L(s) °  L(t)
     s*                       L(s)*

   
PROBLEMA 2
Definire una grammatica non ambigua per le espressioni regolari sull’ alfabeto {a, b}.
[Per grammatica ambigua spetterà fino al 60% del punteggio]   

PROBLEMA 3
Costruire l’ASFD che riconosce il complemento del linguaggio rappresentato dall' espressione regolare
(a + ab)+.
Gli automi dell'esercizio sono quelli allegati. Il primo allegato riconosce (a + ab)+. Il secondo allegato è l'automa deterministico che riconosce (a + ab)+. Infine il terzo è la complementazione   

PROBLEMA 4
Illustrare e motivare la tesi di Church-Turing, chiarendo anche perché si parli di “tesi” e non di “teorema”.

Afferma che un problema se è intuitivamente calcolabile, allora esisterà una MdT in grado di risolverlo.


PROBLEMA 5
Descrivere la riduzione polinomiale 3SAT  <p PL{0,1] e mostrare due istanze di esempio, una positiva e
l’altra negativa.

PROBLEMA 6
Definire un algoritmo per verificare la soddifacibilità di una formula in forma normale disgiuntiva e
tracciare la sua esecuzione sulla formula di esempio

        ( a ᴧ (NOT)b ᴧ c) v ((NOT)a ᴧ (NOT)c) v (a ᴧ b ᴧ c ᴧ (NOTd)) v ((NOT)b ᴧ (NOT)c) v (a ᴧ (NOT b) ᴧ c ᴧ d)
   
L'algoritmo usato è DPLL seguente   
   function DPLL( Formula F)
    if F is empty
             then return true;
         if F contains an empty clause
             then return false;
         for every unit clause l in F
             F = unit-propagate(l, F);
         for every literal l that occurs pure in F
             F = pure-literal-assign(l, F);
         l := choose-literal(F);
         return DPLL(F Union {l}) OR DPLL(F Union {NOT l});   
      
   La traccia di esecuzione nel caso specifico
   
   DPLL( F Union {a} ) = ( a ᴧ (NOT)b ᴧ c) v ((NOT)a ᴧ (NOT)c) v (a ᴧ b ᴧ c ᴧ (NOTd)) v ((NOT)b ᴧ (NOT)c) v (a ᴧ (NOT b) ᴧ c ᴧ d) v (NOT)a
   F = unite-propagate(a, F) = (NOT)c v ((NOT)b ᴧ (NOT)c)
   F = unite-propagate((NOT)c, F) = formula vuota, quindi soddisfacibile
   
« Ultima modifica: Mar 13 Giugno, 19:46:26 - 2017 da scheggia89 »

Offline Zepone

  • Ricercatore
  • ****
  • Post: 360
  • FeedBack: +21/-5
    • Mostra profilo
Re:Modelli
« Risposta #1 il: Mer 26 Luglio, 10:36:43 - 2017 »
Partiamo da due presupposti:

  • leggo solo ora, quindi non so se risponderti può essere ancora utile per la tua personale situazione
  • ho dato gli esami di informatica teorica parecchi anni fa, quindi sono leggermente arruginito

premesso ciò, vediamo di aiutarti (e di aiutare chi leggerà in futuro avendo il tuo stesso problema).

Relativamente al punto 2, la domanda può essere vista così: è dato un certo alfabeto, in questo caso quello costituito dai caratteri a e b. Dato un alfabeto, è possibile costruire una grammatica ad esso associata; tuttavia (e se farete linguaggi per il web lo vedrete per bene), una grammatica può essere sia ambigua che NON ambigua.
Bene, si definisca allora una grammatica, per l'alfabeto dato che NON sia ambigua, ossia una grammatica che non sia definita come descritto nel seguente link:

https://it.wikipedia.org/wiki/Grammatica_ambigua

Dovendo tu stesso costruire la grammatica e quindi le regole che la compongono, l'accortezza che dovrai adoperare è far si che queste non permettano di ottenere, come dice il link qui sopra, stringhe prodotte con derivazioni sinistre diverse.

Sulla domanda della tesi, trovi una risposta chiara qui:

https://www.riflessioni.it/forum/filosofia/10782-tesi-di-church-goedel-e-intelligenza-artificiale.html

il cui passo principale riporto qui per brevità:

"Questo non è un teorema matematico, ma è una tesi, nel senso che non può essere dimostrata matematicamente. Questo perché "intuitivamente calcolabile" è un concetto del linguaggio naturale, quindi vago e non perfettamente definito (come richiederebbe una dimostrazione matematica)."

Infine, per la domanda 5, trovi una buona spiegazione in queste slides del prof Ausiello:

http://www.dis.uniroma1.it/~ausiello/InfoTeoRM/7.NP-COMP-07.pdf

a partire dalla fine della pagina 16; li troverai definizione, dimostrazione ed un esempio della riduzione richiesta.

Spero che la mia risposta possa essere di aiuto.
« Ultima modifica: Gio 27 Luglio, 11:31:12 - 2017 da Zepone »
Un giorno, qualcuno mi sconfiggerà. Ma non sarà oggi e non sarai tu.