# Skúška 12.1.2023 Kučera

<{ForumPost(poster="muffined", timestamp=2023-01-21 13:40:16)}>
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.
<{/ForumPost}>