IB102 Automaty, gramatiky a složitost
12. týden: NP-úplné problémy. Prostorová složitost algoritmů a problémů. Třída PSPACE. Vztahy složitostních tříd.
V ISu již jsou vypsané zkouškové termíny, nezapomeňte se na ně včas přihlásit. Pokud budete předem vědět, že na zkoušku nemůžete přijít, nezapomeňte se prosím odhlásit (šetřte naše lesy).
Domácí úkoly - zadání
sada 11, úkol 1
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 12. 12. 9:00 fyzicky do schránky před D1 nebo elektronicky ve formátu .pdf do příslušné odevzdávárny. Papír nesmí být přeložený či jinak poškozený a musí být vyplněná hlavička, i elektronicky odevzdané verze se budou tisknout a následně skenovat. Pro tvorbu řešení můžete přímo upravit .tex se zadáním (k nalezení v této složce) + potřebujete styl ib102.cls rovněž zde, můžete použít přiložený návod na sazbu.
sada 11, úkol 2
Svá řešení odevzdávejte prosím na skenovatelném formuláři do 12. 12. 9:00 fyzicky do schránky před D1 nebo elektronicky ve formátu .pdf do příslušné odevzdávárny. Papír nesmí být přeložený či jinak poškozený a musí být vyplněná hlavička, i elektronicky odevzdané verze se budou tisknout a následně skenovat. Pro tvorbu řešení můžete přímo upravit .tex se zadáním (k nalezení v této složce) + potřebujete styl ib102.cls rovněž zde, můžete použít přiložený návod na sazbu.
Domácí úkoly - odevzdávárny
Odevzdávárna DÚ: sada 11, úkol 1
Prosím odevzdávejte jen 1. příklad 11. sady. Ve formátu PDF a podepsaný (tedy se jménem uvnitř dokumentu).
Odevzdávárna DÚ: sada 11, úkol 2
Prosím odevzdávejte jen 2. příklad 11. sady. Ve formátu PDF a podepsaný (tedy se jménem uvnitř dokumentu).
Domácí úkoly - řešení
Při přípravě na závěrečnou písemku můžete využít níže uvedené odpovědníky. Odpovědníky můžete zodpovídat opakovaně, slouží pouze k procvičení a vaše odpovědi nebudou mít žádný vliv na celkové hodnocení. Pokud však v odpovědnících najdete chybu (třeba i překlep) a upozorníte na ni (nejlépe v diskusním fóru) jako první, dostanete 1 tvrdý bod. Odpovědníky nepokrývají vyčíslitelnost a složitost.