Domande Orale Degano

2»

Comments

  • MindFlyerMindFlyer Posts: 436
    edited May 2017
    andreRondo wrote: »
    @MindFlyer In fondo a pagina 42 delle dispense, dice che la condizione (*) nella definizione di funzione u-ricorsiva può essere rimossa, a patto che la funzione phi(x1,x2,....,xn,y) sia essa stessa una funzione ricorsiva primitiva. E' giusto rispondere che se essa è ricorsiva primitiva (e quindi totale), allora calcola sicuramente un valore e quindi converge, per cui non c'è bisogno di dire che per tutti gli z minori di y, phi(x1,....xn,z) deve convergere?

    E' giusto dire quello che hai detto, ma secondo me in quel punto della dispensa voleva intendere qualcosa di più profondo. Alla luce del teorema di forma normale 1.9.3, puoi direttamente modificare quella regola VI e dire: se phi è ricorsiva primitiva, allora la funzione psi(x1, x2, ..., xn) = mu.y[ phi(x1, x2, ..., xn, y)=0 ] è in R.

    Cioè, si toglie la regola VI generale e si mette solo questa regola più debole. Il teorema di forma normale dice che la classe di funzioni R che viene fuori da queste nuove regole è la stessa di prima.

    P.S., fai un nuovo thread se hai nuove domande. Non siamo su facebook, thx.
  • andreRondoandreRondo Posts: 24
    edited May 2017
    Fatto orale ieri mattina di ECC, le domande che mi ha fatto sono le seguenti:
    - Data la funzione phi(x) dire se è calcolabile:

    phi(x) = { k se phi_x = phi_k con x < k AND per ogni i,j . i < x,k AND phi_ j diverso da phi_i
    3 altrimenti
    }
    Lo ha inventato sul momento, per cui preparatevi anche a questi tipi di esercizi "diversi" da quelli che avete sempre visto qua sul forum (di riduzioni varie).
    Non so neanche io come ne sono uscito.. sono sincero :')
    - Dimostrare che un insieme qualunque chiamato K3, è R-Completo. (e fare esempio)
    - Teorema di enumerazione, dimostrazione intuitiva (spiegare cosa si intende con macchina universale, poche righe sotto la dimostrazione formale nelle dispense) e dimostrazione formale (quella delle dispense)
    - La soddisfacibilità di un'espressione booleana in forma disgiuntiva quanto costa? (tempo polinomiale, a volte lineare) E di una in forma congiuntiva? (tempo esponenziale)
    Il problema SAT com'è? (NP-Completo)
    Quindi se esprimessimo SAT in forma disgiuntiva,avremmo trovato un modo per dire che SAT non è più NP, perchè verrebbe a costare tempo polinomiale, quindi apparterrebbe a P... E' vero o non è vero? (No perchè per passare da forma congiuntiva a disgiuntiva impiego tempo esponenziale)
    - Dimostrare che SAT è NP-completo.

  • La risposta è che ogni insieme ricorsivo che non sia vuoto e non sia N è completo per REC. Se vuoi un esempio (siccome si chiedeva di trovarne uno, e non di parafrasare la domanda), prendi l'insieme dei numeri pari.[/quote]

    Perdona il ritardo nella risposta. L'insieme dei numeri pari e' stato il primo che presi in considerazione all'orale, e il prof mi disse che la risposta non gli andava bene. Nello scrivere il post da te citato ho letteralmente riportato cio' che mi ha detto il professore. Detto questo, spero possa essere di aiuto a chi deve ancora sostenere l'orale, visto che a me e' stato utile tutto cio' che ho trovato qui sopra, e in particolare i tuoi interventi @MindFlyer (e di questo ti ringrazio :) ).
  • LorenzoLorenzo Posts: 2
    edited November 2017
    Un po' di domande a caso da orali che ho visto:

    - Dato un problema A, NP completo per riduzioni polinomiali o logaritmiche in spazio
    · Trovare un problema che non si riduce ad A
    · Trovare un problema a cui A non si riduce
    - Teorema di gerarchia
    - Teorema di enumerazione
    - Esempi di insiemi non ricorsivamente enumerabili
    - Definire l'insieme degli indici delle funzioni estendibili, e dimostrare non sia ricorsivo
    - Teorema di Rice (dimostrazione)
    - Funzione non estendibile
    - Teorema di accelerazione lineare e teorema di accelerazione di Blum
    - Definizione di funzione appropriata
    - Dati gli insiemi I_n: {x tale che x è maggiore di n e minore di 2n e phi_x = phi_n}
    - Sono ricorsivi? Ricorsivamente enumerabili?
    - La loro unione è ricorsiva? Ricorsivamente enumerabile?
    - Teorema di enumerazione (di nuovo, lo chiede spesso)
    - Teorema di forma normale
    - Legami tra vincoli di tempo e vincoli di spazio, dimostrazione logspace <= P
    - Definizione di insieme di indici che rispettano funzioni
    - co-NP (insieme dei problemi il cui complemento è in P) è uguale a P? Dimostrarlo
    - co-NP è uguale a NP? Se lo fosse si potrebbe dire qualcosa su P = NP?
    - Dimostrare che K non è un insieme di indici che rispettano delle funzioni (Credo che la dimostrazione che preferisce parte dal definire una funzione che vale 1 sul proprio indice e non sia definita in nessun altro punto, e poi in qualche modo usare il teorema del parametro e del punto fisso per dimostrare che è calcolabile)
    - Enunciare e dimostrare il teorema del punto fisso (NB, per l'ultimo passaggio della dimostrazione nelle dispense è importante dire che la funzione usata grazie al teorema del parametro è iniettiva)
  • kenzokenzo Posts: 1
    Posto anche io le domande che ha fatto ieri, sperando possano essere utili!

    Dimostrare che K < FIN
    Dimostrare K< INF
    Teorema di Rice + dimostrazione
    dimostrazione che CValue è P-Completo
    Teorema di ricorsione + dimostrazione
    Teorema accelerazione lineare + dimostrazione
    dimostrare LOGSPACE < P
  • G_e_m_m_aG_e_m_m_a Posts: 6
    edited February 6
    Orale Degano dei compitini di oggi:
    Nota: stamani c'era lo scritto e la candidata non aveva visto il testo
    Esercizio 1 compito: lui la lascia parlare e poi la aiuta. Lei si infogna sulla direzione dell'implicazione e lui le chiede di scrivere una funzione parziale. Alla fine ce la fa arrivare.
    Esercizio 2: non sa dire un modo alternativo per la soddisfacibilità di un problema in forma normale disgiuntiva che non sia polinomiale. Alla fine la fa arrivare alla soluzione lineare. Domanda: come si dimostra che SAT disgiuntivo è np? Ce la fa arrivare (soluzione: con uno spazio esponenziale).
    Domanda di teoria: enuncia e dimostra il teorema di enumerazione. Lo fa bene
    Domanda di teoria: dimostra l'inclusione logspace C ptime. Lo fa bene.

    Voto 23, ma non so da quanto partisse
    Non riesco ad allegare il testo del compito da mobile :#
  • tkrx07mo0ntk.jpg
    Questo è il compito di ieri
Sign In or Register to comment.