Fórum studentů MFF UK

Godelovy věty a Pseudopolynomiální algoritmy Godelovy vety mi vzdycky pripadaly zajimave, ale nevim o MFF prednasce, ktera by o nich pojednavala do takove miry, ze by je clovek pak skutecne aktivne chapal. Ani ve Vycislitelnosti II se o tom clovek nic nedozvi. Mozna Rekurze I? Logika v informatice ...

Tak jsme to včera dali všichni čtyři:). Zkoušení probíhalo v příjemné atmosféře. Seděli jsme v malé učebně, na každou otázku bylo kolem půl hodiny času na přípravu a pak si k nám zkoušející přisedávali (někdy po jednom, někdy po dvou). Moje otázky: Logika a výpočtová složitost (neznámý mladý hodný t...

Dík za info, i když moc jsi mě tím neuklidnil (že na to fórum před státnicemi lezu…).

Doporučuju to zapít a od zítra dělat jako by se nic nestalo , na příštím termínu to určitě vyjde! (Tuhle strategii plánuju já, když státnice neudělám.)

Z dobře informovaného zdroje jsem se dozvěděl, že se chystá implementace iCalendaru přímo v SISu. Moje udělátko bude tedy doufejme nejpozději příští semestr zastaralé:).

Ahoj, vyrobil jsem udělátko, co z rozvrhu z ISu (Rozvrh NG > Rozvrh > Můj rozvrh > CSV) umí vytvořit soubor ve standardním formátu iCalendar (RFC 2445). Ten pak můžete importovat do do iCalu, Google Calendaru nebo jiného kalendářovače. Pro každý lístek v rozvrhu to vytvoří událost s týdenním opaková...

Jak jsem si dnes mohl na vlastní kůži ověřit, tak se zkouší i věci, co se dělají na cvikách a nejsou ve slajdech, což je podle mě prima, protože je to jednodušší než mnohé důkazy, co se dělaly na přednášce. Ale trochu mě to překvapilo:). Měl jsem (1) PSPACE-úplný problém a dokázat aspoň, že je v PSP...

Zkouška 15. 6. vypadala takto: 1. Limitní vyčíslitelnost, 2. Příklady \Sigma_2 , resp. \Pi_2 -úplných. Tzn. ve druhé otázce nebylo nic na výběr. Podle mě je to z těch otázek "na výběr", co se vyskytují, asi ta nejjednodušší, ale plyne z toho ponaučení, že by člověk neměl spoléhat na to, že...

Zkoušel jsem to na FF. Ani po mně nechtěli nic podepisovat, prostě jsem jim dal ISIC a vypůjčil jsem si knížku. Knihovnice sice brblala, že se systém tváří, že mám kartičku prošlou, ale stačilo jí vidět kupón – nakolik to souvisí s jinou fakultou nevím, ale v půjčení mi to nezabránilo:). EDIT: Ha, k...

Jo, omylem jsi asi několikrát napsal "NP-úplný" místo "z třídy NP": jsme schopni převést libovolný NP-úplný problém na KACHL. Má být "libovolný problém z třídy NP ". Někdo nám tedy dá NP-úplný problém Q Má být "dá problém Q z třídy NP ". tvrdí, že Q je NP-úpln...

Na kachlíkování je právě nejlepší, že si tam člověk může krásně představit prostorovou a časovou složitost. Přesně tak. Prima, že to tady někdo pro příští myslitele shrnul:). Jen k tomu pro úplnost dodám pár technických drobností, doufám, že správných: Pracujeme-li s modelem TS, který má jednu obou...

Teď začínám být nějaký nejistý. Možná, že doopravdy řeším blbost. Asi bych mohl chtít, aby mi nepřítel, co mi předhazuje nějaký problém z NP a stroj M, který ho řeší mi dal i polynom, který shora odhaduje prostor použitý při přijímacím výpočtu. A ještě jednou si odpovím:): Ano, skutečně v tom není ...

Teď začínám být nějaký nejistý. Možná, že doopravdy řeším blbost. Asi bych mohl chtít, aby mi nepřítel, co mi předhazuje nějaký problém z NP a stroj M, který ho řeší mi dal i polynom, který shora odhaduje prostor použitý při přijímacím výpočtu.

No, každý problém ve třídě NP je řešitelný v polynomiálním čase na NTS. Tak si vezmeš ten polynom a čtvercová síť bude mít délku/šířku nastavenou podle toho polynomu. Já myslím ,že stačí EXISTENCE toho polynomu... (Poznámka: Celý následující argument je naprosto nesmyslný, což si nyní plně uvědomuj...

Koukám na svoje zápisky z (d)úkazu, že Kachlíkování (dále KACHL ) je NP -úplné a mám problém s jednou podstatnou věcí. Mám tušení, že se to řešilo i na přednášce (snad se na to ptal Martin Černý), a tehdy jsem to si myslel, že to chápu, nebo mě Čepek prostě nějak uchlácholil, takže jsem si z toho ni...

Ano, zkouška vypadá zhruba tak, jak jsem čekal po přečtení informací z předchozích let. Já měl to hledání v uspořádaném poli. Korektní popis a pochopení funkce algoritmů a nějaká základní fakta/pozorování na trojku stačí, to ostatně doc. Koubek říkal už na přednášce. Já jsem k tomu u zobecněného kva...