[01TSLO] Teorie složitosti

Asi těžko by se hledal předmět s tak rozdílnými hodnoceními v anketě a i moje pocity z něj byly částečně rozporuplné. Na přednáškách probíraná látka spadala do kategorií "zapomněnka" (skoro všechno) a "nezapomněnka" (poměrně malá část). Zapomněnku tvořily věci, které je dobré slyšet, ale které nebylo potřeba umět ke zkoušce. Do nezapoměnky patřily věty o inkluzích tříd složitosti (DTime, ...), věty o hierarchii a převody NP-úplných úloh (+ Turingovy stroje). Na zkoušku si nakonec stačilo procvičit inkluze mezi třídami složitosti a převody NP-úplných úloh (včetně stanovení, odkdy je úloha "lehká"). V obou případech si myslím, že se jedná o užitečnou znalost (v prvním případě povědomí, co všechno se ví o výpočetních možnostech při nějakém omezení, a v druhém případě, aby člověk uměl rozpoznat, že je něco NP-úplné, optimálně to asi nepůjde a měl by sáhnout po nějaké aproximaci...). Celkově si myslím, že jediné co brání předmětu být skutečně skvělým, je špatné vyrozumnění toho, co všechno bude požadováno u zkoušky. Nebylo to (příliš) zřejmé a pokus učit se podrobně zapomněnku ze skript, případně z vlastních zápisků z hodin, může být pro některé traumatizujícím zážitkem. I když se podle mě jedná o velmi zajímavé téma, látku ze skript je někdy poměrně těžké plně pochopit a docenit (a matroidy a některé další kapitoly jsou na vlastní nebezpečí).

Nebylo to špatné. Zajímavý kontrast k ostatním teoreticky-informatickým předmětům na FJFI. Vzhledem k tomu, že v nich naprosto chybí jakékoliv propojení matematické teorie s elementárními pojmy z informatiky, student přichází na Teorii složitosti s poměrně špatným základem, což může pro někoho činit tento předmět obtížným. Díky tomu je předmět vykládán v poměrně omezeném rozsahu a k absolvování zkoušky stačí velmi malý výsek z celkové problematiky.

Základní třídy složitosti, hodně se to točí kolem Turingových strojů.

Kvalitní přednáška z teorie složitosti by určitě na Jaderce neměla chybět. Nicméně takhle odpřednášená by klidně chybět mohla. První část přednášky, která se netýká zkoušky, je sice možná zajímavá, ale kvůli tomu jsme pak v té další části nestihli plno věcí a ve výsledku se zkouší z něčeho, co se ani neprocvičilo ani na jednom příkladě s alibistickým "tady máte věty, tak příklady budou triviální". Což je samozřejmě hloupost nad kterou se shodne drtivá většina top pedagogů po celém světě (stačí se kouknout na online kurzy...) . Takže až vás u zkoušky pan Majerech nachytá na nějaké blbosti u vět o hierarchii a podobně (ověřeno - dělá to pravidelně každý termín), pak se nedivte. Nevadilo by mi, kdyby se tedy probíralo něco jiného - ale ať se pak u zkoušky vyžaduje toto a nebo se raději vůbec nezkouší... Komu by to vadilo :-P .

Naprosto nevhodně zařazený předmět, který by měl následovat až po probrání automatů. Chtělo by to nějakou aktualizaci skript.

Obsahove zajimavy, nicmene bohuzel jednoznacne nejhure vedeny predmet, ktery jsem na FJFI absolvoval.

Podivný předmět, vůbec jsem to nepochopil. Pan Majerech má však zajímavý výklad. Nakonec jsem se rozhodl zkoušky nezkladat i když jsem odchodil všechny hodiny

Předmět je výborný. Látka je dost často vysvětlována s jistým nadhledem. Nezabíhá se do detailů, ale ukazují se hlavní principy. Mnohým studentům se tak může zdát mírně nesrozumitelný, avšak mám dojem, že v magisterském studiu už by si student měl být schopen detaily doplnit sám a důležité by opravdu měly být jen principy důkazů. Přednášející navíc často ukazuje i užitečné triky, jak s problémy pracovat. Díky nim je možné ukázat složité důkazy sice bez korektního zápisu, avšak tak, aby je byl člověk schopný sledovat a pochopit.