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

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010

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

od Š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

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

od 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:

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

od 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áš

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

od 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) ...

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

od 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

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

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

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

od 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

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

od 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
zadanie pisomky NTIN090 - 27.1.2010 kucerap
zadanie pisomky NTIN090 - 27.1.2010 kucerap

Nahoru