2R-SAT

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.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

2R-SAT

Příspěvek od Him »

Zdravim,

koukal jsem, ze se tady na foru resil 2R-SAT, trochu jsem to hledal a prijde mi velmi srozumitelne toto reseni:

http://www.cc.gatech.edu/classes/AY2008 ... rsions.pdf - str. 3

Rezoluce se vyklada treba na Umele Inteligenci (UI) nebo na log. programku. Uplny a korektni algoritmus vykladany na UI generuje z klazuli pomoci rezoluce vsech moznych kombinaci dvou klazuli a ceka se, az se tento proces ustali.

Asi by to chtelo jeste argument, ze kdyz mam promenne x a y a pro obe bych mohl provest rezoluci ve dvou klauzulich, tak je jedno, pro kterou to provedu drive. Provedu-li rezoluci pro x, tak dostanu klauzuli, ve ktere bude obsazeno: y v -y .. a tuto klauzuli teda mohu v nasledujicim kroku odebrat jako splnitelnou.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Odpovědět

Zpět na „TIN062 Složitost I“