[NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

bcmiko
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 27. 1. 2010 13:58
Typ studia: Informatika Mgr.

[NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od bcmiko »

Hello ludia,

prave som absolvoval skusku zo zlozitosti a vycislitelnosti, vlastne nie, odrodil som si ju ... aj s pupocnou snurou za 3.

Priklady som mal 2 (z jedneho som nemal nic, jeden som mal zle, 2 dobre a jeden (prevod np-uplneho problemu) som mal len co by som pouzil, nic viac).
Sedel som tam dokopy 4,5 hodiny a to som som jeden z prvych, co to dali.

Na ustnej som dostal:

1) Funckia f je CRF <=> jej graf je RSM.
2) Dokazat NP-uplnost 3SAT.

Na ustnej sa ma pytal (kedze som to tam nemal uplne jasne vysvetlene, hlavne ze preco je riesenie korektne v jednom <=> ak je v prevedenom) veci ohladne toho,
ale dost ma navadzal a spolu s nim som to tam aj vymyslel. Taktiez u druhej otazky.

Inak bol dost dobry, v pohode, snazil sa ludi zachranit aj pripadnou inou otazkou na ustnej, ak jedna z nich nebola nejaka extra.

To je moja skusenost s poslednou povinnou skuskou, vdakabohu :D 8)

Ozaj, do prihlohy pripajam zadanie prikladov.

Drzim palce vsetkym ostatnym.
Přílohy
zadanie pisomky NTIN090 - 27.1.2010 kucerap
zadanie pisomky NTIN090 - 27.1.2010 kucerap
Uživatelský avatar
Lucas
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 15. 1. 2007 20:34
Typ studia: Informatika Mgr.

Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od Lucas »

Ja som rodil o pol hodky dlhsie ako kolega. Tiez mam prirastok v podobe krasnej zdravej 3ky.

Aj ked .. mal som dobre 4 priklady, a z ustnej dobre s_m_n vetu ..
No druhu otazku - dokaz (tj prevod z VP) ze HK je NP-uplna som len nejak popisal .. ale nechapal som tomu velmi
Nacoz mi dal nahradnu (ale uz zachrannu) otazku - dokaz ze SAT je NP-uplna (t.j. dalsi prevod). Ten som sice nevedel napisat uplne technicky ale chapal som mu .. takze tak.

gl
Hele mozku, nemáš rád mně a ja zas tebe. Ale tohle musíme udělat a pak tě vyřídim jedním pivem.
LadaN

Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od LadaN »

U ústní jsem dostal:
1) důkaz věty o rekurzi (důkaz věta 10.1)
2) definice NP a dokázat, že jsou ekvivalentní (def. 12.5 a def 12.7 NTIME, důkaz lema 12.8)

Jinak u toho důkazu o rekurzi jsem napsal vše, ale chtěl po mě, abych mu vysvětlil co se tam vlastně dělá - co dělá ta funkce d(v) - jaká je její interpretace, nedokázal jsem mu to říct, protože ten důkaz více méně umím na zpaměť...
Půl hodiny trvalo, než jsme se dohrabali k výsledku a musím říct, že ještě teď to nechápu:D ale chtěl tam něco prý z přednášky - něco přes matice - diagonála jsou funkce fi s godelovym číslem fi_v(v).

A co jsem tak sledoval, tak nikdy mu nestačilo jen napsat důkaz - vždycky ho chtěl převyprávět ústně a ptal se proč co můžem udělat. A ten druhej důkaz jen přejel očima a řekl dobrý. Odešel jsem s dvojkou jen kvůli tomu, že jsem nevěděl co se vlastně děje v té rekurzi (příklady jsem měl 4 z 5).

Hodně zdaru!
Uživatelský avatar
Lada
Donátor
Donátor
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Typ studia: Informatika Bc.
Bydliště: Slaný / zácpa na Evropské

Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od Lada »

Zdarek
mel bych dotaz na ty co uz byli na zkousce: je mozne u pisemky zase mit vytistene slajdy (jak to slo na zapoctu)?

dik Lada
Hail to you, champion:o)
bcmiko
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 27. 1. 2010 13:58
Typ studia: Informatika Mgr.

Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od bcmiko »

Nie, nemozes. Ale ... :)

Dalo sa tam podla mna celkom dost dobre opisovat, on sedel za MacBookom a tukal si tam cely cas nieco. A pocas ustnej chodil hore dole, ked sa to odohravalo na chodbe (ked to bolo v ucebni, zase nieco pozeral do ntb, pripadne s niekym preberal uz napisanu ustnu) ...
lukas.hermann
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 13. 1. 2007 16:42

Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od lukas.hermann »

Ahoj, nechcete někdo z těch, kdo jste měli tolik příkladů dobře, přihodit alespoň náznak řešení? Těm, co se na to teprve připravují, by to určitě pomohlo. Díky!

Lukáš
Uživatelský avatar
Lucas
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 15. 1. 2007 20:34
Typ studia: Informatika Mgr.

Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od Lucas »

Moje riesenia resp. naznaky riesenia:

1. nevedel som .. mal sa pouzit podobny dokaz ako v riceovej vete (ale ten si nejak nepamatam :) )
2. prva cast otazky plati podla vety o rekurzii ale druha cast, t.j. ci to bude opat ORF uz neplati, pretoze univerzalna fcia ORF funkcie (obecne) nie je ORF
3. najprv som napisal ze DTIME je stale mensi nanajvys rovny DSPACE a teda som obmedzil DSPACE .. podobne ako v jednej vete o konstante tusim 2^(Cm*f(n))
4. vraj sa to malo prevadzat z vrcholoveho pokrytia, no ja som to skusil zo SATu .. bolo to na celu A4ku .. a tak sa mu to nechcelo dopodrobna citat :)
5. nakreslil som si par grafov, .. dopracoval som sa k tomu ze to plati (napr.) pre bipartitne grafy. Optimalnym riesenim su vrcholy z mensej "komponenty" pricom aproximacny algoritmus vrati pary (jeden vrchol z mensej a jeden z vacsej)

snad to niekomu pomoze :wink:
Hele mozku, nemáš rád mně a ja zas tebe. Ale tohle musíme udělat a pak tě vyřídim jedním pivem.
Štefan
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 27. 1. 2005 16:17
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

Příspěvek od Štefan »

Lada píše:Zdarek
mel bych dotaz na ty co uz byli na zkousce: je mozne u pisemky zase mit vytistene slajdy (jak to slo na zapoctu)?

dik Lada
Můžete mi někdo potvrdit nebo vyvrátit tučně vyznačený text, jak to bylo v lednu 2011 se zápočty, tj. smělo se opisovat z přinesených vytištěných slajdů?
Byl tam nějaký borec, co měl vytištěné poznámky z přednášky (tj. ne slajdy, ale kompletní materiály k předmětu)?

Díky
Odpovědět

Zpět na „NTIN090 Základy složitosti a vyčíslitelnosti“