Zobrazit příspěvky

Nerozumím tomu, proč se nedá říct, že ten spor dokazuje, že nejde udělat takový TS tímhle způsobem. Jak z tohodle důkazu plyne, že nejde udělat jiným způsobem, mi vždycky bylo záhadou, ale nikdy mě to nerajcovalo natolik, abych se na to někoho ptal nebo se na to snažil přijít

Ten důkaz ale nepředpokládá žádný konkrétní způsob. Pro spor prostě jen předpokládáš, že máš TS, který umí řešit halting problem.

Citace: Mirek Prýmek 11. 06. 2015, 00:02:27

Je to tak, že se dá dokázat, že kdyby takový TS existoval, tak by musel existovat i ten, o kterém víme, že existovat nemůže?

Ten důkaz je o tom, že pokud by existoval TS řešící halting problem, tak jde upravit na TS, který se zastaví, právě když se nezastaví, což je spor.

Studium a uplatnění / Re:Algoritmicky nerozhodnutelné problémy

« kdy: 10. 06. 2015, 01:14:13 »

Citace: Samufaj 10. 06. 2015, 00:27:23

-------------
Název: HP (Problém zastavení [Halting Problem] )
Vstup: Turingův stroj M a jeho vstup w.
Otázka: Zastaví se M na w (tzn. je výpočet stroje M pro vstupní slovo w konečný)?
---------
Jakto, že když znám konstrukci toho TS, nenení možné z toho vyvodit jestli se zastaví pro vstup w?

Tohle se asi nejlépe vysvětluje pomocí částečně rekurzivních funkcí, ale nevím, zda vám o nich někdo říkal. Nejlepší asi bude vysvětlit to neformálně pomocí programu v nějakém programovacím jazyce.

Představ si, že existuje program halt(code, input), který vrací true, pokud se program zapsaný v code nad vstupem input zastaví, jinak vrací false. Pak můžeš napsat následující program:

Kód: [Vybrat]

contradiction(code)
{
  if(halt(code, code))
    while(true);
  else
    return;
}

Tento program otestuje, zda se program zapsaný v code nad vstupem code zastaví, a pokud ano, zacyklí se. V opačném případě skončí. Co se stane, pokud programu contradiction dáš na vstup jeho vlastní kód? Pak pokud se contradiction nad vstupem contradiction zastaví, pak se musí contradiction nad tímto vstupem zacyklit. A naopak, pokud se contradiction nad vstupem contradiction nezastaví, pak se musí contradiction zastavit. Což je v obou případech spor a tedy žádný takový program halt nemůže existovat.

Studium a uplatnění / Re:Problémy P, NP, NP-úplné, NP-těžké

« kdy: 08. 06. 2015, 22:43:56 »

Ještě bych možná doporučil kouknout se na tento obrázek:

Předpokládá se, že asi P != NP a tedy platí ta varianta vlevo.

Studium a uplatnění / Re:Problémy P, NP, NP-úplné, NP-těžké

« kdy: 08. 06. 2015, 21:43:53 »

Citace: Samufaj 08. 06. 2015, 21:38:25

Ale ještě ti tam chybí NP-úplné problémy, to jsou pak jaké?

Nechybí, píšu o nich úplně dole.

Studium a uplatnění / Re:Problémy P, NP, NP-úplné, NP-těžké

« kdy: 08. 06. 2015, 20:42:18 »

Citace: Samufaj 08. 06. 2015, 19:55:10

A když se mě na to u státnic zeptají, tak jim to tak řeknu, protože já se omáčku kolem toho, co nedává smysl, šrotit nehodlám $:-\$

Uff, šíleně to motáš. Tvé "definice" založené na tom, zda musíme projít všechny možnosti, jsou spíše zavádějící. Docela by mne zajímalo, zda má ten předmět někde slidy, abychom se mohli podívat, co je důvodem tvého zmatení. Být tebou, držel bych se toho, co ti tu napsali lidé přede mnou.

Můžeme to zkusit vzít postupně, soustřeďme se nyní pouze na rozhodovací problémy - tedy takové, pro které existuje odpověď ano/ne.

Máme dva výpočetní modely:
1. (Deterministický) Turingův stroj (TS) - ten má svůj stav, vstupní pásku a nějaké pracovní pásky (nad kterými se pohybují hlavy). Přechodová funkce na základě stavu stroje a symbolů pod hlavami definuje pokračování, tj. nový stav stroje, co se má zapsat na pracovní pásky a kam se mají pohnout hlavy (doleva, doprava, nikam). Výsledek je ano, pokud stroj skončí v přijímacím stavu. Pokud skončí v jiném stavu (anebo se zacyklí) výsledek je ne.

2. Nedeterministický Turingův stroj (NTS) - Ten je stejný jako TS, ale přechodová funkce vrací množinu možných pokračování (a ne jen jedno jako u TS). Jak psal JSH, představ si to pro zjednodušení klidně tak, že NTS má navíc orákulum, které NTS řekne, které z těchto možných pokračování vybrat (aby se nejrychleji dostal k výsledku).

Problémy P jsou pak takové, které TS vyřeší v polynomiálním čase (TS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.

Problémy NP jsou pak takové, které NTS vyřeší v polynomiálním čase (NTS udělá polynomiálně mnoho kroků) vzhledem k velikosti vstupních dat.

Z toho plyne, že problém, který je P, je zároveň NP, protože na TS se klidně můžeš dívat jako na takový degenerovaný NTS, ve kterém přechodová funkce všude vrací jednoprvkové (či prázdné) množiny možných pokračování.

To, zda každý problém, který je v NP, je také v P, se neví. Předpokládá se (a doufá se), že tomu tak není, tj. že existují problémy, které jsou NP, ale nejsou P.

Tak a teď co to je NP-těžký problém: Problém X je NP-těžký, pokud každý problém Y, který je NP, lze (v polynomiálním čase) převést na řešení problému X.

Možná ti může dělat trochu problém, že v definici je psáno, že na něj musí být převoditelný každý NP problém. V praxi se využívá toho, že pokud o problému Z víš, že je NP-těžký, a pokud umíš problém Z (v polynomiálním čase) převést na řešení problému W, pak W je také NP-těžký. To je dáno tím, že pokud ti někdo dá libovolný problém Y (z NP), tak ten lze (protože o Z víš, že je NP-těžký) převést na Z, který už umíš převést na W - tedy celkově umíš každý problém Y (z NP) převést na W.

Pozor na to, že problémy, které jsou NP-těžké, nemusí být řešitelné v polynomiálním čase na NTS. Tedy NP-těžké problémy nemusí být NP!

Kvůli tomu je zde závěrečná definici: NP-úplné jsou takové problémy, které jsou NP-těžké a zároveň jsou NP. Jak zde už někdo psal, NP-úplné problémy jsou z ty nejtěžší z NP, protože každý problém z NP lze na ně (v polynomiálním čase) převést.

Moc jsem to po sobě nečetl, ale snad to dává nějaký smysl.

Studium a uplatnění / Re:Je titul potřebný pro praxi?

« kdy: 30. 05. 2015, 23:31:46 »

Citace: iwtu 30. 05. 2015, 22:29:33

Jo, za tuto diskuzi si sypu popel na hlavu, bylo velmi hloupé nechat se do ní zatáhnout.

Studium a uplatnění / Re:Je titul potřebný pro praxi?

« kdy: 30. 05. 2015, 03:42:03 »

Takže aby bylo jasno, co to je slušný důkaz:

Mějme rekurentní rovnici: a(n+1) = c₁*a(n-k+1) + ... + c_k*a(n) = Σ^k_j=1 c_j*a(n-k+j). (1)

Definujme v_i (pro i = 1...k) následovně:
v_i(t) = 1 pro t=i
v_i(t) = 0 pro t≠i & t≤k
v_i(t) = Σ^k_j=1 c_j*v_i(t+j-k-1) pro t > k (2)

A chceme dokázat, že každý (nekonečný) vektor x, který je řešením naší rovnice (1), lze zapsat jako lineární kombinaci vektorů v_i, přičemž x(i) pro i=1...k tvoří souřadnice našeho řešení x. Tedy cheme dokázat následující:

x = Σ^k_i=1 x(i)*v_i (3)

Budeme postupovat indukcí podle složek, chceme tedy dokázat, že pro každé t (od jedné po nekonečno) platí následující:

x(t) = Σ^k_i=1 x(i)*v_i(t) (4)

V prvník kroku ukážeme, že vztah platí pro t=1...k:

Σ^k_i=1 x(i)*v_i(t) = x(t)*v_t(t) = // protože v_i(t) = 0 pro t≠i
= x(t) // protože v_t(t) = 1

První krok je tedy dokázán a zbývá druhý: Předpokládejme, že námi dokazovaný výpočet (4) platí až po t-1 (t>k) a máme ukázat, že platí i pro t:

x(t) = Σ^k_j=1 c_j*x(t+j-k-1) = // plyne z toho, že x je řešením (1)
= Σ^k_j=1 c_j*(Σ^k_i=1 x(i)*v_i(t+j-k-1)) = // plyne z indukčního předpokladu
= Σ^k_j=1 Σ^k_i=1 c_j * x(i)*v_i(t+j-k-1) =
= Σ^k_i=1 Σ^k_j=1 c_j * x(i)*v_i(t+j-k-1) =
= Σ^k_i=1 x(i) * Σ^k_j=1 c_j *v_i(t+j-k-1) =
= Σ^k_i=1 x(i) * v_i(t) // plyne z definice v_i (2)

Takto jsme indukcí dokázali, že x = Σ^k_i=1 x(i)*v_i.

Studium a uplatnění / Re:Je titul potřebný pro praxi?

« kdy: 30. 05. 2015, 02:29:52 »

Citace: slowthinker 30. 05. 2015, 01:44:54

V důkazu předpokládám a využívám toho, že v_i jsou řešení:

Ano, jsou to řešení. Ale jak dokážeš, že každé jiné řešení jde zapsat jako lineární kombinace těchto řešení? Pokud bys měl rekurentní vztah s absolutním členem, tak stejným způsobem definovaná v_i by sice byla řešením takové rovnice, ale zároveň by libobolné řešení nešlo zapsat jako lineární kombinace vektorů v_i.

Prostě máš libovolné řešení x a máš dokázat, že jde zapsat jako lineární kombinace v_i. Jasně, prvních k složek x ti jasně určuje souřadnice x v bázi v_i. Fajn, a teď musíš dokázat, že suma přes i=1,...,k x(i)*v_i dává x. To v tom svém důkazu ale fakt neukazuješ.

Studium a uplatnění / Re:Je titul potřebný pro praxi?

« kdy: 30. 05. 2015, 01:28:00 »

Citace: slowthinker 30. 05. 2015, 00:58:38

Nechápu, jak chceš určovat složku/člen 2k. Ten je jednoznačně určený (používal jsem slovo "vyexpandovaný") na základě rekurentního vztahu.
Určovat můžeš prvních k členů. A to jsi udělal a s tím v důkaze počítám.

Ne, já definuji v_i a klidně si mohu nějaký jejich člen definovat jinak. Pak to samozřejmě ale není báze prostoru řešení té rovnice. V tom případě by měl ten tvůj důkaz na nějakém kroku selhat. Na kterém?

Studium a uplatnění / Re:Je titul potřebný pro praxi?

« kdy: 30. 05. 2015, 00:53:04 »

Fajn, tak dokaž, že jsou bází prostoru řešení, protože to, cos napsal, zrovna důkaz není. Neboť když pozměním to, jak jsem ty v_i definoval (definuji jinak jejich složku 2k), tak tvůj důkaz přestane platit v jakém místě?

Stran: 1 2 [3] 4 5 ... 23