Cvičení ze Složitosti I
V zimním semestru 2014/2015 vedu cvičení k přednášce ze Složitosti I Ondřeje Čepka. Cvičení se koná každé druhé úterý od 9:00 v posluchárně S8.
Zápočet se udílí za získání alespoň 100 bodů z domácích úkolů. Úkoly prosím posílejte na adresu mj+sloz@ucw.cz.
Cvičení v sudé týdny
| datum | co jsme dělali |
|---|---|
| 7. 10. | Hladové algoritmy pro rozvrhování a protipříklady na většinu z nich. Interpretace pomocí intervalových grafů. Matroidy: hraní si s definicí; jak vypadá báze matroidu. |
| 21. 10. | Hledání stoku coby příklad algoritmu, který nemusí přečíst celý vstup. Mosty, artikulace a různé vlastnosti DFS. |
| 4. 11. | Polosouvislost orientovaných grafů. Různé algoritmy na hledání komponent silné souvislosti. Hledání nejkratšího cyklu v ohodnoceném rovinném grafu jako příklad použití planárních separátorů. |
| 18. 11. | Exkurze do Turingovy strojovny. Různé typy strojů a vztahy mezi nimi. Akceptory vs. funkce. Přijímání zastavením vs. koncovým stavem. Je v řetězci stejně nul jako jedniček? Redukce oboustranně nekonečné pásky na jednostranně nekonečnou, redukce stroje se zarážkami na stroj bez zarážek. |
| 2. 12. | Nedeterministické výpočty a orákula. Použití rozhodovací verze problému (vrcholové pokrytí, SAT) k nalezení optima. NP kontra co-NP, certifikáty (ne)prvočíselnosti. |
| 16. 12. | Redukce a různé jejich použití. Různé varianty hamiltonovských cest a kružnic. Tautologičnost v CNF a DNF. Lineární rovnice a nerovnice nad {0,1}. |
Cvičení v liché týdny
| datum | co jsme dělali |
|---|---|
| 14. 10. |
Hladové algoritmy pro rozvrhování a protipříklady na většinu z nich.
Interpretace pomocí intervalových grafů.
Jen 7.10.: Matroidy: hraní si s definicí; jak vypadá báze matroidu. |
| 11. 11. | Hledání stoku coby příklad algoritmu, který nemusí přečíst celý vstup. Mosty, artikulace a různé vlastnosti DFS. Hledání nejkratšího cyklu v ohodnoceném rovinném grafu jako příklad použití planárních separátorů. |
| 25. 11. | Exkurze do Turingovy strojovny. Různé typy strojů a vztahy mezi nimi. Akceptory vs. funkce. Přijímání zastavením vs. koncovým stavem. Je v řetězci stejně nul jako jedniček? Redukce oboustranně nekonečné pásky na jednostranně nekonečnou. O definici algoritmu a výpočetních modelech. |
| 9. 12. | Nedeterministické výpočty a orákula. Použití rozhodovací verze problému (vrcholové pokrytí, SAT) k nalezení optima. NP kontra co-NP, certifikáty (ne)prvočíselnosti. |
| 6. 1. | Redukce a různé jejich použití. Různé varianty hamiltonovských cest a kružnic. Tautologičnost v CNF a DNF. Co je za NP? |
Domácí úkoly
| Datum | Kód | Body | Zadání |
|---|---|---|---|
| 7. 10. | chem | 15 | Mějme n chemikálií a u každé z nich určený rozsah teplot pro bezpečné skladování. Chceme si pořídit co nejméně ledniček a každou nastavit na konkrétní teplotu tak, aby každou chemikálii bylo možné bezpečně uskladnit. Navrhněte efektivní algoritmus na řešení této úlohy (nejlépe hladový). |
| strom | 20 | Uvažujme následující hladové algoritmy na hledání největší nezávislé
množiny ve stromu:
| |
| 24. 10. | hous | 15 | Housenka je graf, který je tvořen cestou ("páteř") a listy připojenými k této cestě ("štětiny"). Navrhněte algoritmus, který v zadaném stromu najde co největší housenku (podgraf s největším možným počtem vrcholů). Nápověda: DFS. |
| zgm | 20 | Navrhněte algoritmus, který zbaví graf všech mostů přidáním nejmenšího možného počtu hran. | |
| 4. 11. | ssep | 15 | Separátor stromu je vrchol, po jehož odebrání se strom na n vrcholech rozpadne na komponenty, z nichž žádná neobsahuje více než αn vrcholů (kde α je nějaká konstanta mezi 0 a 1 nezávislá na konkrétním stromu). Navrhněte lineární algoritmus, který nalezne separátor daného stromu s co nejmenším α. Dokažte, že lepší hodnoty α nejde dosáhnout. |
| tri | 20 | Popište efektivní algoritmus, který zjistí, zda v zadaném rovinném grafu existuje trojúhelník. | |
| 18. 11. | mul | 10 | Sestrojte Turingův stroj, který vynásobí dvě dvojková čísla.
Čísla jsou zapsána na vstupní pásce od nejvyššího řádu k nejnižšímu,
oddělena od sebe znakem #. Výsledek zanechte na výstupní
pásce, opět od nejvyššího řádu k nejnižšímu.
|
| n2 | 15 | Sestrojte Turingův stroj, který na vstupu dostane posloupnost n hvězdiček a provede právě n2 kroků, než se zastaví. Můžete předpokládat, že n≥n0 pro vámi zvolené n0. (V terminologii z přednášky: funkce n2 je časově konstruovatelná.) | |
| tsan | 15 | "Turingova saň" je dvouhlavý Turingův stroj: nad každou pracovní páskou pracují dvě nezávislé hlavy. Ukažte, jak tento stroj efektivně simulovat na klasickém Turingově stroji. Můžete předpokládat, že pokud se hlavy setkají na jednom políčku pásky, zapíší totéž. | |
| 2. 12. | comp | 10 | Sestrojte nedeterministický Turingův stroj, který na vstupu dostane n hvězdiček a tento vstup přime právě tehdy, je-li n složené číslo. Časová složitost stroje nechť je O(n). |
| color | 15 | Mějme orákulum, které umí v konstantním čase odpovědět, zda daný graf je možné obarvit třemi barvami. Nalezněte v polynomiálním čase na stroji s tímto orákulem konkrétní obarvení. | |
| prime | 20 | Ukažte, že prvočíselnost leží v NP (na vstupu uvažujeme dvojkový zápis čísel). Následujte nápovědu z cvičení: certifikát pro číslo n bude obsahovat generátor multiplikativní grupy modulo n, faktorizaci čísla n-1 a rekurzivně sestrojené certifikáty pro prvočísla vystupující ve faktorizaci. Zbývá doplnit detaily a zejména dokázat, že celý certifikát je polynomiálně dlouhý. | |
| 16. 12. | ham | 15 | Převeďte hamiltonovskou kružnici na SAT. |
| spg | 10 | Uvažujme následující problém: jsou dány grafy G a H a číslo K, existuje indukovaný podgraf grafu G o K vrcholech, který je isomorfní s nějakým indukovaným podgrafem grafu H? Dokažte, že tento problém je NP-úplný. | |
| lineq | 15 | Uvažujme následující problém: je dána soustava lineárních rovnic, jejíž koeficienty i pravé strany jsou jen nuly a jedničky, existuje vektor z nul a jedniček, který ji řeší? Dokažte, že tento problém je NP-úplný. |
