Kontrakce na Matriodu

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
Uživatelský avatar
Almer
Site Admin
Příspěvky: 686
Registrován: 12. 10. 2004 10:58
Typ studia: Informatika Ph.D.
Bydliště: Mala Strana - 203
Kontaktovat uživatele:

Kontrakce na Matriodu

Příspěvek od Almer »

Ahoj,

mam dotaz. Ucim se z jednech poznamek a je tam vysvetlena kontrakce na Matroidu, jako

{M}'=\left ( {S}', {I}' \right ); {S}' = \{y \in S; \{x,y\} \in I \}, {I}' = \{B \subseteq {S}'\setminus \{x\}; (B \cup \{x\}) \in I\}

ale ja bych to definoval jinak. Nejak se mi to nezda

{M}'=\left ( {S}', {I}' \right ); {S}' = S \setminus \{x\}, {I}' = \{B \subseteq {S}'; (B \cup \{x\}) \in I\}

Vysvetli mi to nekdo?
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: Kontrakce na Matriodu

Příspěvek od Myshaak »

Almer píše:Ahoj,
mam dotaz. Ucim se z jednech poznamek a je tam vysvetlena kontrakce na Matroidu, jako
{M}'=\left ( {S}', {I}' \right ); {S}' = \{y \in S; \{x,y\} \in I \}, {I}' = \{B \subseteq {S}'\setminus \{x\}; (B \cup \{x\}) \in I\}
ale ja bych to definoval jinak. Nejak se mi to nezda
{M}'=\left ( {S}', {I}' \right ); {S}' = S \setminus \{x\}, {I}' = \{B \subseteq {S}'; (B \cup \{x\}) \in I\}
Vysvetli mi to nekdo?
Tak definovat si to asi muzes jak chces, ne? :D Akorat ze Tvoje definice neni korektni - pripousti, aby mnozina {x} byla v I' (a ani by moc nedavalo smysl, kdyby tam nebyla), kdezto prvek x neni v S'. To za prve.
[EDIT: Ted koukam, ze jsem asi napsal blbost, Ty uz to rovnou beres z S', kde x neni, tak beru zpet]
Zadruhe podle slajdu se to nejak vyuzivalo pri hledani opt. podstruktury - hodne zjednodusene ze puvodni problem je nejak ekvivalentni s nalezenim opt. podmnoziny na tom novem matroidu M' -> cilem tedy logicky je, aby tam toho bylo co nejmin - prvni definice vyhaze vsechny prvky, ktere k {x} uz nejde pridat, aby to byla "nezavisla mnozina", "Tvoje definice" tam vesele da vsechno. :)

btw za treti: vim, ze to mas vsechno asi z uceni na statnice, presto... nebylo by lepsi hodit tyto dotazy do specializovanych "chlivecku" a toto forum nechat jen na opravdu "statnicove veci"? :) Neber to spatne, rozumim, ze tady si to aspon kazdy precte, ale kdyby sem kazdy, kdo se uci na statnice, hodil par svych zakysu, tak to by to tu vypadalo... :-/
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Almer
Site Admin
Příspěvky: 686
Registrován: 12. 10. 2004 10:58
Typ studia: Informatika Ph.D.
Bydliště: Mala Strana - 203
Kontaktovat uživatele:

Re: Kontrakce na Matriodu

Příspěvek od Almer »

Ad 1 - ano aby to bylo korektni

Ad 3 - presunuto

Ad 2 - asi hlavni cast odpovedi. To ze jsem tam nechal vsechny prvky jsem nechal zamerne.
EDIT: jsem debil, uz to sem to pochopil. I je mnozina vsech podmnozin prvku z S. Takze tam musi byt vsechny podmnoziny prvku ( a tedy mnozin ktere jsou v S ), ktere obsahuji to prvni x. Tedy odstranim kazdou mnozinu v S ktera nema v sobe x a pak odtrham vsechny x z nich a to co zbyde bude kontrahovany matroid.
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: Kontrakce na Matriodu

Příspěvek od Myshaak »

Almer píše:... Tedy odstranim kazdou mnozinu v S ktera nema v sobe x a pak odtrham vsechny x z nich a to co zbyde bude kontrahovany matroid.
Juhuu! (Ze je to dobry pocit, kdyz clovek konecne neco pochopi? :D) Ono slo prave o to, nechat tam toho co nejmin - kdyz uz si davame tu praci a prevadime nejaky jiny problem na tenhle kontrahovany matroid, tak cim min tam toho bude, tim lip pro nas, proto se nektere prvky vyhodi, i kdyz asi by to nejak fungovaloi s nima...
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Odpovědět

Zpět na „TIN062 Složitost I“