Domande Orale Turini

[InformateciBot]

Ecco un elenco delle domande che fa il turini all'orale:

1. Albero di derivazione: foglie, nodi, categorie sintattiche e simboli terminali.
2. Dimostrare che l’insiseme dei linguaggi liberi è r.e
3. Teorema di Cook
4. Cosa è SAT
5. Quando un espressione booleana (P v Q) è soddisfacibile e quando non lo è?
6. Cosa è NP?
7. Definire un insieme r.e.
8. Listing Teorem
9. Teorema SMN
10. Funzionni primitive ricorsive non calcolano tutte le funzioni calcolabili totali
Dimostrazione per diagonalizzazione
Dimostrazione con funzione di Ackermann
11. Cosa è K?
12. Dimostrare che K è non ricorsivo
13. Godelizzazione, #P cosa vuol dire?
14. Come si dimostra che K segnato è non r.e.
15. Teorema del complemento + dimostrazione
16. Teorema per ogni ASFND esiste un ASFD + dimostrazione
17. Ogni linguaggio generato da una grammatica (qualsiasi è R.E.) + dimostrazione
18. Cosa è la notazione O()
19. Teorema di Cook (spiegazione ma no dimostrazione)

Davide Ginnasio
20. Dimostrare che gli insiemi r.e. sono chiusi rispetto a unione e intersezione
21. Dimostrare che un insieme è r.e se e solo se è in forma sigma
22. S-M-N
23. quando un ASFND riconosce una stringa?
24. è vero che qualsiasi linguaggio generato da una grammatica è r.e?

BreakingTheCode
25. Enunciare il teorema di Rice e dimostrarlo
26. Dimostrare che tutti i linguaggi sono r.e.
27. Definizione di NPC
28. Perché se dimostro che un problema NPC sta in P, allora posso dire che P = NP?

Francesco Cariaggi
29. Mostrare che gli ASFND sono un caso particolare degli APND (per ogni transizione dell' ASFND scrivere la transizione corrispondente dell'APND)
30. Perché sono portato a pensare che un problema in NP richieda un tempo esponenziale per essere risolto?
31. Mostrare che L vuoto (con L linguaggio libero) è un problema decidibile
32. ∀ASFND M ∃ G Regolare tale che L(M) = L(G)
33. Enunciato Pumping Theorem

Mpac
34. Definizione riducibilità
35. Dimostrazione del teorema che se A è riducibile a B e B è r.e. allora A è r.e.
36. Espressioni regolari
37. Enunciato e dimostrazione Pumping Lemma
38. Dimostrare che un problema P è NP-Completo