Domande Orale Degano

Velocemente le impressioni di questa giornata di orali per coloro che verranno:

- I compitini servono a voi, non a Degano
- Lo scritto che fa è pro forma
- Sono andato nel pallone sulla prima definizione, mi ha messo assolutamente subito a mio agio
- In genere ha chiesto un esercizio o due che richiedesse ragionamento, poi o definizioni o teoremi
- E' magnanimo con i voti ( "sarà che il vino è più cattivo quest'anno ma mi sembrate più bravi del solito")
- Continua a criticare i voti del Vanneschi ("chi le ha dato questo voto??")

Consiglio: Studiate e capite i Teoremi, ci tiene molto, e con quelli fate il resto.

Per il resto, le domande che mi ha posto sono più o meno le seguenti:

- Def di fun. appropriata
- Teo di Gerarchia
- Teo Lacuna di Borodin
- Teo Accelerazione di Blum
- Teo Accelerazione Lineare ( a grandi linee, i passi cruciali)
- Teo Forma Normale
- Myhill-Nerode (accennato)
- Teo Automa Minimo
- Teo Ricorsione (solo accennato)
- Un esercizio che non sto a riportare perché è stato abbastanza confuso. Si trattava di usare il teorema di ricorsione e sue conseguenze sul numero di punti fissi. Quindi sappiateli
- Dire se { x | FIx = FIx+1 } (con x e x+1 indici) è Ricorsivo. Risposta : no.

In bocca al lupo!
«1

Comments

  • MindFlyerMindFlyer Posts: 436
    edited February 2015
    diningphil wrote: »
    - I compitini servono a voi, non a Degano
    - Lo scritto che fa è pro forma

    Sottoscrivo,
  • aggiungo alcune domande dal mio orale:
    - dati due linguaggi regolari, dimostrare che l'unione è regolare (banale con le grammatiche)
    - cosa possiamo dire invece per l'unione infinita? (non vale, va dimostrato)
    - dimostrare che LOGSPACE incluso in P
    - cosa succede se coNP = NP ? (in particolare cosa possiamo dire di P=NP)
    - sappiamo dal padding lemma che esiste una funzione che restituisce indici di macchine equivalenti. Ne può esistere una che li restituisce tutti?
  • MindFlyerMindFlyer Posts: 436
    E' utile anche dire da che voto di scritto si partiva (quando questo esiste...).
  • JokerJoker Posts: 82
    Le mie:

    - Discutere l'esistenza di una f calcolabile totale tale che
    dominio di phi_x = complemento di phi_f(x)

    - Dimostrazione teorema del punto fisso
    - Dimostrazione teorema di enumerazione
    - Dimostrare che l'unione di due linguaggi regolari è regolare, costruendo l'automa
    - Dimostrare che NP è incluso in EXP

    Sinceramente visti i commenti di chi ci ha preceduto mi sarei aspettato più discussioni e meno dimostrazioni a memoria, il che mi ha un po' spiazzato per come mi ero preparato l'esame... Paradossalmente avrei fatto meglio semplicemente imparandomi quelle poche dimostrazioni che cercando di capire davvero la materia :D
  • MindFlyer wrote: »
    E' utile anche dire da che voto di scritto si partiva (quando questo esiste...).

    Non mi sembra dia mai voti ai compiti. Io avevo fatto l'unico compitino dell'anno, dove è comparso l'esercizio che trovate anche nella cartella Dropbox del 2011. Gli altri due completamente sbagliati, e ti assicuro che il voto finale non tiene conto del compitino.
  • Il mio voto era un OK scritto sul compitino, che ho conservato io fino al giorno dell'orale, potevo benissimo correggermelo a casa. Giusto per ribadire che vale veramente zero.
  • baababaaba Posts: 23
    Queste sono le domande (meno qualcuna che non ho ascoltato bene) fatte a me e altri due ragazzi al preappello di dicembre2014. Niente scritto. Dei compitini quest'anno ha fatto solo il primo ,che non ha considerato (io manco l'avevo fatto).

    1.L'unione finita di insiemi ricorsivi è ricorsiva?
    2.L'unione infinita di insiemi ricorsivi è ricorsiva?
    3.L'unione infinita di insiemi ricorsivi può essere non ricorsivamente enumerabile?
    4.Dimostrare che TOT è non ricorsivamente enumerabile riducendo ¬K a TOT.
    5.L'intersezione di linguaggi regolari è regolare? Come si dimostra?
    6.Qual'è la differenza tra il teorema di accelerazione lineare e quello di accelerazione di Blum? 7.Definizione di funzione appropriata e come mai è importante che sia monotona crescente e non strettamente crescente

    8. ? (Esercizio la cui soluzione richiamava il teorema del parametro)
    9.Dimostrare il teorema del parametro.
    10.Dimostrare che la gerarchia di Chomsky è una gerarchia "propria" (ha le inclusioni strette)
    11.Perchè il linguaggio [tex]\{a^n b^n c^n|n>0\}[/tex] non è libero? Dimostrare il pumping lemma per linguaggi liberi.
    12.Dimostrare che le funzioni in LOGSPACE classificano P ed NP.

    13 ?
    14.Dimostrare che [tex]CRICCA \leq_{logspace} MEZZACRICCA[/tex] (che ha spiegato essere il problema di decidere se in un grafo esiste una cricca di esattamente N/2 nodi dove N è il numero (pari) dei nodi del grafo).
    15.Discutere la decidibilità di [tex]I_k = \{x | \exists y .\psi_x(y) = \psi_k(y)[/tex] e [tex] x < k\}[/tex] ( o na cosa simile )
    16.Enunciato e dimostrazione del teorema di enumerazione e come mai diciamo che [tex]\phi_z[/tex] ha due soli parametri (i,x) e non tre parametri (i,x,y).
    17.Dimostrare che dato un ASFND esiste un ASFD equivalente in maniera formale ( o meglio: impostare formalmente cosa si deve andare a dimostrare e dare un'idea di come si potrebbe fare)
  • MindFlyerMindFlyer Posts: 436
    Il mezzacricca è un evergreen di Degano. :D

    Aggiungo anche una domanda che fece a me: dimostrare che LOGSPACE è chiuso per composizione.
    Questo fatto, sepolto nelle dispense all'interno della dimostrazione del Teorema 3.5.2 e bollato come "banale", è invece abbastanza delicato. La dimostrazione che ne dà la dispensa è solo accennata, ma è sostanzialmente giusta. Certo però che meriterebbe più risalto.
  • caoscaos Posts: 9
    Io ho fatto l'orale oggi.
    Venivo dai compitini e da un mezzo orale terminato "male" perchè mi sono bloccato.
    Innanzitutto il prof si è reso conto della situazione, al primo orale, e mi ha offerto di tornare un'altra volta, senza bocciarmi.
    In ogni caso è in grado di metterti a tuo agio e, a me, ha tenuto buone le domande alle quali avevo risposto correttamente la prima volta (che però non ricordo :( ).
    Oggi mi ha quindi chiesto:
      * Dimostrare che [tex] NP \subseteq EXP [/tex]
      * Mostrare che una MdT non deterministica può essere simulata da una MdT deterministica con perdita in tempo esponenziale
      * Classificare il linguaggio [tex]\{ a^i b^j | i - j \geq 3\}[/tex]
      * Dimostrare che [tex]K[/tex] non è un i.i.r.f.
  • DiamonDinoiaDiamonDinoia Posts: 9
    edited December 2015
    Posto anche io le domande dell'orale del Degano

    1. L'insieme delle funzioni estendibili a totali {EXT} è ricorsivo, è ricorsivamente enumerabile?
    2. L'ASFD minimo che riconosce un linguaggio regolare è unico?
    3. L'unione di due linguaggi regolari è regolare? l'unione infinita di linguaggi regolari?
    4. NP e CO-NP possono essere uguali? Come verrebbe influenzata questa gerarchia se questo accadesse?

    Non ricordo altre domande, nel caso le aggiungo, comunque queste sono state abbastanza lunghe poichè ho dovuto dimostrare ogni singolo punto, anche se alcuni solo intuitivamente.
  • Lucio MessinaLucio Messina Posts: 139
    edited March 2016
    Le mie:

    1. (non avevo fatto lo scritto) dimostrare che INF (l'insieme degli algoritmi con dominio infinito) si riduce a COST (l'insieme degli algoritmi che ritornano una costante)
    2. il linguaggio nel quale la b compare solo in posizioni dispari è regolare? E il linguaggio composto da a^3n con n>0 lo è?
    3. la concatenazione dei due linguaggi di cui sopra è regolare? E in generale la concatenazione di due linguaggi regolari? Come si dimostra con le grammatiche? (occhio c'è un trabocchetto)
    4. Enunciazione e dimostrazione del teorema di forma normale
    5. Dimostrare che P = co-P. Costruire la funzione che manda elementi di P in elementi di co-P mediante una Macchina di Turing.
  • E il linguaggio composto da a^n3 con n>0 lo è?

    Che è a^n3?
    Forse [tex]a^{3n}[/tex]?
    Usiamo [tex]\LaTeX[/tex]!

  • gp27gp27 Posts: 6
    Le mie:
    dimostrare che INF (l'insieme degli algoritmi con dominio infinito) si riduce a COST (l'insieme degli algoritmi che ritornano una costante)

    Lucio, questo come l'avevi fatto?
  • MindFlyerMindFlyer Posts: 436
    edited February 2016
    gp27 wrote: »
    Le mie:
    dimostrare che INF (l'insieme degli algoritmi con dominio infinito) si riduce a COST (l'insieme degli algoritmi che ritornano una costante)
    Lucio, questo come l'avevi fatto?

    Non so come l'ha fatto lui, ma comunque un modo è questo:
    dato un programma A, costruisci un programma B che, su input n, simula A a coda di rondine su ogni input, e termina restituendo 0 la n-esima volta che A termina su qualche input. Allora B calcola la costante 0 se e solo se A ha dominio infinito (altrimenti B non termina su qualche input).

    Ah, le prossime volte cerchiamo di aprire un nuovo thread per fare una domanda del genere. Vogliamo almeno provare a tenere le cose ordinate? La differenza tra forum e facebook è proprio questa: l'ORDINE.
  • gp27gp27 Posts: 6
    Quindi usando alle solite il primo teorema di ricorsione e quello s-m-n

    [tex] ψ(x,y) = φ_{f(x)}(y) = \begin{cases} 42 & \text{se almeno y esecuzioni a coda di rondine di } φ_x \text {terminano} \\ indefinita & \text{altrimenti} \end{cases}[/tex]

    Ero più o meno arrivato all'idea si usare una coda di rondine, ma mi ero bloccato cercando di limitare con y il numero di passi piuttosto che il numero di terminazioni.

    Grazie, e mi scuso per la necessità del richiamo, ripensandoci avrei dovuto aprire un thread...
  • MindFlyer wrote: »
    Il mezzacricca è un evergreen di Degano. :D

    Aggiungo anche una domanda che fece a me: dimostrare che LOGSPACE è chiuso per composizione.
    Questo fatto, sepolto nelle dispense all'interno della dimostrazione del Teorema 3.5.2 e bollato come "banale", è invece abbastanza delicato. La dimostrazione che ne dà la dispensa è solo accennata, ma è sostanzialmente giusta. Certo però che meriterebbe più risalto.

    Io proprio adesso stavo studiando quella dimostrazione, ma non riesco proprio a capirla!
  • Io proprio adesso stavo studiando quella dimostrazione, ma non riesco proprio a capirla!
    Allora apri un thread e ricostruiamola.
  • Gaspare FerraroGaspare Ferraro Posts: 44
    edited January 13
    Finito adesso l'orale, le domande che mi ha fatto Degano:

    - Dire se l'insieme [tex]I = \{ x \mid dom(\varphi_{x}) = \{ 0 \} \}[/tex] è non-R.E. e dimostrarlo
    - Enunciare il teorema di enumerazione e dimostrarlo ( e quindi enunciare anche il teorema di formale normale )
    - Dimostrare che [tex]LOGSPACE \subseteq PTIME[/tex]
    - Trovare un algoritmo e la relativà complessità che risolve la soddisfacibilità di una espressione in forma normale disgiuntiva ( quindi [tex]( A \land B \land ... ) \lor ( C \land D \land ...) \lor ... [/tex] )
    - Che relazione ha il precedente problema con SAT ?

    Risposte per i curiosi:
    - Si e per dimostrarlo si riduce a [tex]\overline{K}[/tex] con la funzione:

    [tex]
    \psi(x,y) = \varphi_{f(x)}(y) = \begin{cases}
    1 & x \in K \lor y = 0 \\
    indefinita & altrimenti \\
    \end{cases}
    \\
    [/tex]

    - vedi dispense
    - vedi dispense ( numero di passi massimo con [tex]log(n)[/tex] celle )
    - Vediamo che per essere soddisfacibile basta che una delle clausole sia soddisfacibile, visto che ogni clausola è composta da solo AND tra letterali è soddisfacibile solo se al suo interno non c'è un "ff" oppure contemporaneamente un letterale e la sua negazione. L'algoritmo scorre da sinistra verso destra le clausole e controlla quanto detto prima, ovviamente è lineare nell'input e quindi polinomiale.
    - Possiamo controllare una espressione in forma normale disgiuntiva in tempo polinomiale, mentre SAT controlla una espressione in forma normale congiuntiva in tempo polinomiale non-deterministico. Se si trasforma una espressione in forma disgiuntiva in una congiuntiva il numero delle clausola cresce esponenzialmente.

    Per il resto orale molto tranquillo, ti lascia il tempo di ragionare e ti aiuta se sei in difficoltà, conta molto la forma con la quale si espongono i teoremi (quantificatori, premesse ecc..).
  • Le domande che ha fatto Degano a un orale nella sessione di gennaio:

    - dimostrare che con le funzioni u-ricorsive si possono calcolare i cicli for
    - dimostrare che Sat è np-completo
    - com'è fatta la funzione di transizione della macchina non deterministica in Sat
    - come funziona la MdT che dice se l'assegnamento di Sat è giusto o no
    - insieme di indici che rispettano le funzioni
    - tesi di Church-Turing
    - dimostrare che FIN non è ricorsivamente enumerabile
  • Posto le domande che ha fatto al mio orale nella sessione di febbraio:

    - dimostrare che [tex]K_1[/tex] non è ricorsivo
    - dimostrare che [tex]K_1[/tex] è ricorsivamente enumerabile
    - definizione di insieme ricorsivamente enumerabile
    - lemma dopo la definizione
    - dimostrare il lemma
    - definizione di funzione appropriata
    - teorema di Borodin
  • Manutio wrote: »

    - dimostrare che con le funzioni u-ricorsive si può calcolare i cicli for
    - dimostrare che sat è np-completo
    - com'è fatta la funzione di transizione della macchina non deterministica in sat
    - come funziona la MdT che dice se l'assegnamento di sat è giusto o no
    - insieme di indici che rispettano le funzioni
    - tesi di church-touring
    - dimostrare che FIN non è ricorsivamente enumerabile

  • edited April 5
    Domande orale appello straordinario Aprile 2017, senza scritto, programma di CC (quindi anche i linguaggi):

    - trovare un insieme A contenuto in N , A completo per riduzioni secondo la classe delle funzioni calcolabili totali (rec) (la risposta e' che tanti sottoinsiemi di N sono completi, ma non N intero, non K (che e' contenuto in N) e non tutti i sottoinsiemi ricorsivamente enumerabili)

    - RE-completezza di K (e' sulle dispense)

    - linguaggi liberi, pumping lemma per linguaggi liberi con dimostrazione che a^n b^n c^n non e' libero (con il pumping lemma per linguaggi liberi), dimostrare che i linguaggi liberi non sono chiusi per intersezione (fornendo un esempio che lo dimostri, l'esempio e' simile a quello da fornire per dimostrare che l'unione infinita di linguaggi regolari non e' detto che sia regolare, pero' da fare con a^n b^n c^n)

    - dimostrare se 3-SAT e' completo per NP, dove 3-SAT e' il problema SAT in cui ogni congiunto e' composto esattamente da 3 elementi e da qui avendo problemi mi ha chiesto la riduzione da circuit-sat a sat.

  • MindFlyerMindFlyer Posts: 436
    - trovare un insieme A contenuto in N , A completo per riduzioni secondo la classe delle funzioni calcolabili totali (rec) (la risposta e' che tanti sottoinsiemi di N sono completi, ma non N intero, non K (che e' contenuto in N) e non tutti i sottoinsiemi ricorsivamente enumerabili)

    Come fa a essere la risposta? E' un elenco arbitrario di non-risposte.
  • MindFlyer wrote: »
    Come fa a essere la risposta? E' un elenco arbitrario di non-risposte.

    Ciao, questo e' quello che mi ha detto il professore, in quanto ogni sottoinsieme di N puo' essere ridotto ad un altro sottoinsieme di N purche' non sia r.e.
  • MindFlyerMindFlyer Posts: 436
    Ciao, questo e' quello che mi ha detto il professore, in quanto ogni sottoinsieme di N puo' essere ridotto ad un altro sottoinsieme di N purche' non sia r.e.

    Scusa, ma continui a dirla doppiamente sbagliata, perché
    1) gli insiemi ricorsivamente enumerabili sono anche ricorsivi, e tra questi ve n'è qualcuno REC-completo, e inoltre
    2) esistono insiemi non ricorsivamente enumerabili, i quali ovviamente non possono essere REC-completi, non essendo nemmeno REC.

    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.
  • andreRondoandreRondo Posts: 24
    Le domande che ha fatto Degano a un orale nella sessione di gennaio:

    - dimostrare che con le funzioni u-ricorsive si possono calcolare i cicli for

    Come si risponde a questa?
  • MindFlyerMindFlyer Posts: 436
    andreRondo wrote: »
    Le domande che ha fatto Degano a un orale nella sessione di gennaio:

    - dimostrare che con le funzioni u-ricorsive si possono calcolare i cicli for

    Come si risponde a questa?

    Il Corollario 1.9.4 è una risposta indiretta.
    In realtà non serve nemmeno l'operatore di minimizzazione, ma bastano le funzioni ricorsive primitive per calcolare i cicli FOR. La costruzione si fa a colpi di ricorsione primitiva, similmente all'Esempio 1.6.2.
  • andreRondoandreRondo Posts: 24
    edited May 23
    @MindFlyer Per quanto riguarda la macchina universale U, esempio 1.9.9, successivo al teorema di Enumerazione, è stato mai chiesto come fare ad impostarla?
  • MindFlyerMindFlyer Posts: 436
  • andreRondoandreRondo Posts: 24
    edited May 23
    @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?
Sign In or Register to comment.