[NTIN090] Základy složitosti a vyč. - Zk 27.1.2010
-
- 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
[NTIN090] Základy složitosti a vyč. - Zk 27.1.2010
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
Ozaj, do prihlohy pripajam zadanie prikladov.
Drzim palce vsetkym ostatnym.
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
Ozaj, do prihlohy pripajam zadanie prikladov.
Drzim palce vsetkym ostatnym.
- 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
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
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.
Re: [NTIN090] Základy složitosti a vyč. - Zk 27.1.2010
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.
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!
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.
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!
- Lada
- 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
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
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)
-
- 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
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) ...
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) ...
-
- 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
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áš
Lukáš
- 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
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
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
Hele mozku, nemáš rád mně a ja zas tebe. Ale tohle musíme udělat a pak tě vyřídim jedním pivem.
-
- 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
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ů?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
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