Skúška 12.1.2023 Kučera
Napsal: 21. 1. 2023 13:40
Prišla som tam a už mal pre mňa pripravený papier s vytlačenými otázkami. Otázky boli presne tie isté ako sú v dokumente "Skúškové otázky".
Ja som dostala otázky:
1. Ekvivalencia RAM a TM
2. NP-completeness of SAT
V 1. som napísala ako sa jednotlivé veci ukladajú (kódovanie TM do pamäte a RAM na 4 pásky TM), nezabudnúť predpoklady na TM, keď ho dávame do RAM (unbound tape from one side, číslovanie stavov a abecedy), ako sa správa prechodová funkcia TM a inštrukcie v RAM. Potom sa ma pýtal na definíciu RAM a TM, definíciu programu v RAM a aké máme operácie na RAM.
V 2. som napísala, definíciu NP-completeness a s tým ako budeme postupovať v dôkaze. Potom takmer celú časť toho dôkazu. Pýtal sa na všetko čo mi chýbalo, čo bolo: ako PRESNE vyzerá
a prečo tak vyzerá (vyjadrenie initial configuration, accepting configuration, v každej cell práve jeden znak a prechodová funkcia) a na čo sú nám windows a platné windows.
Povedal, že síce som tam nemala všetko napísané, ale keď sa ma pýtal tak, že som mu na všetko správne odpovedala. Dal mi jednotku.
Ja som dostala otázky:
1. Ekvivalencia RAM a TM
2. NP-completeness of SAT
V 1. som napísala ako sa jednotlivé veci ukladajú (kódovanie TM do pamäte a RAM na 4 pásky TM), nezabudnúť predpoklady na TM, keď ho dávame do RAM (unbound tape from one side, číslovanie stavov a abecedy), ako sa správa prechodová funkcia TM a inštrukcie v RAM. Potom sa ma pýtal na definíciu RAM a TM, definíciu programu v RAM a aké máme operácie na RAM.
V 2. som napísala, definíciu NP-completeness a s tým ako budeme postupovať v dôkaze. Potom takmer celú časť toho dôkazu. Pýtal sa na všetko čo mi chýbalo, čo bolo: ako PRESNE vyzerá
Povedal, že síce som tam nemala všetko napísané, ale keď sa ma pýtal tak, že som mu na všetko správne odpovedala. Dal mi jednotku.