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

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

Příspěvekod bcmiko » 27. 1. 2010 14:12

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
SNC00098.jpg
zadanie pisomky NTIN090 - 27.1.2010 kucerap
bcmiko
Matfyz(ák|ačka) level I
 
Příspěvky: 2
Registrován: 27. 1. 2010 13:58
Typ studia: Informatika Mgr.
Login do SIS: markm5am

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

Příspěvekod Lucas » 27. 1. 2010 14:16

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.
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ěvekod LadaN » 27. 1. 2010 16:55

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!
LadaN
 

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

Příspěvekod Lada » 27. 1. 2010 17:54

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)
Uživatelský avatar
Lada
Donátor
Donátor
 
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Bydliště: Slaný / zácpa na Evropské

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

Příspěvekod bcmiko » 27. 1. 2010 17:59

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) ...
bcmiko
Matfyz(ák|ačka) level I
 
Příspěvky: 2
Registrován: 27. 1. 2010 13:58
Typ studia: Informatika Mgr.
Login do SIS: markm5am

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

Příspěvekod lukas.hermann » 28. 1. 2010 20:26

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áš
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ěvekod Lucas » 28. 1. 2010 21:01

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.
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ěvekod Štefan » 9. 2. 2011 10:16

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
Štefan
Matfyz(ák|ačka) level I
 
Příspěvky: 6
Registrován: 27. 1. 2005 16:17
Bydliště: Praha


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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník