Skúška 12.1.2023 Kučera

muffined
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 21. 1. 2023 12:38
Typ studia: Informatika Mgr.

Skúška 12.1.2023 Kučera

Příspěvek od muffined »

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á \varphi 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.
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“