Domande Orale Turini

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)

Comments

  • 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?
  • 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?
  • 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
  • MpacMpac Posts: 10
    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
Sign In or Register to comment.