VŠ z trochu jiného úhlu

j

Re:VŠ z trochu jiného úhlu
« Odpověď #1590 kdy: 04. 03. 2013, 13:54:42 »
Citace od: Radek Miček kdy 04. 03. 2013, 12:46:29
CitaceV čem přesně má být ten rozpor?

I v praxi je třeba řešit terminaci pro všechny vstupy, tudíž i v praxi se vyskytuje obecný HP.

V praxi jsou vstupy velmi omezene, kuprikladu neznam ucetni program, ktery by zvladal na vstupu cisla vetsi nez 10^99 ... protoze je to v praxi naprosta kravina. Realne zvlada vstupy cisel daleko mensich. Takze resit (teoreticky) co se stane kdyz ... je naprosta <>ina, protoze takova situace nikdy nenastane. Ony se v praxi dokonce neresi ani vstupy, ktere realne nastat muzou, pokud je pravdepodobnost takoveho vstupu dostatecne nizka.

Citace od: student kdy 04. 03. 2013, 13:35:44
...
Opet resis kokotiny, v praxi je pro me omezujici predevsim mnoztvi $$$ na mem konte, takze at uz budu resit jakykoli problem, musim ho vyresit za $$$ kteryma disponuju => reseni rozhodne nemusi byt dokonaly a schopny se vyporadat s koncem vesmiru, me staci reseni ktery dostatecne splni moje touhy.

Proto v praxi vazne nepotrebuju dokazovat, ze neco dobehne, protoze od toho neceho ocekavam nejaky vystup a nastavim podminku dle ocekavani. Stejne tak ocekavam ze to pobezi nejak dlouho a spotrebuje nejaky mnoztvi pameti, a problem budu resit az mi pamet dojde. Trebas prikoupim, trebas dojdu k tomu, ze je chyba v programu, trebas dojdu k tomu, ze program je az prilis dokonaly, ale porad nepotrebuju nic dokazovat.

BTW: Elektrinu vetsina lidi pouziva, sifrovani muze (a funguje) i bez prvocisel.


Rax

Re:VŠ z trochu jiného úhlu
« Odpověď #1591 kdy: 04. 03. 2013, 13:57:08 »
Citace od: student kdy 04. 03. 2013, 13:35:44
Ak ide len o aplikaciu postupov, tak na to sprav program - mozes ho predavat ako programatora na mojej urovni, ktory nebude robit chyby

To se nepochybně stane, virtuální kodéry očekávám kolem roku 2040, zatím na to není dostatečně výkonný hardware.

Re:VŠ z trochu jiného úhlu
« Odpověď #1592 kdy: 04. 03. 2013, 14:02:10 »
Citace od: Rax kdy 04. 03. 2013, 13:57:08
To se nepochybně stane, virtuální kodéry očekávám kolem roku 2040, zatím na to není dostatečně výkonný hardware.
Spis bych rekl, ze zatim je dostatek lidi, kteri jsou schopni to udelat levneji :)

Radek Miček

Re:VŠ z trochu jiného úhlu
« Odpověď #1593 kdy: 04. 03. 2013, 14:15:16 »
Citace od: Mirek Prýmek kdy 04. 03. 2013, 13:51:17
realne nikdy nemuze existovat jakykoli stroj/mechanismus/robot/cokoli... co by mohlo nabyvat stale nove a nove stavy. A jelikoz pocet stavu je nejak shora omezeny, tak proste k tehle TEORETICKE neresitelnosti nikdy nedojde.

Ale o to vůbec nejde. Důležité je, že logický systém je bezesporný. Funkce, jenž není totální zavádí do logického systému spor. Všimněte si, že vůbec nezáleží na tom, pro jak velký vstup je funkce nedefinovaná. A proto, když něco dokazujete, potřebujete, aby funkce byla totální pro všechny vstupy.

Re:VŠ z trochu jiného úhlu
« Odpověď #1594 kdy: 04. 03. 2013, 14:20:45 »
Citace od: Radek Miček kdy 04. 03. 2013, 14:15:16
Ale o to vůbec nejde. Důležité je, že logický systém je bezesporný.
Cili veta "je uplne jedno, o co se jedna, dulezite je ze..." nebyla pochopena.

Lamu hul.

Pokud jste ty a d.k. chteli dokazat, ze je kazdy informatik potrebuje znat Turinga, tak podle me jste dokazali jenom to, ze se Turing na nasich skolach uci tim zpusobem, ze z toho maji studenti jenom zamotanou hlavu a neumeji to aplikovat.

Kazdy at si o tom mysli, co chce.

Howgh.


student

Re:VŠ z trochu jiného úhlu
« Odpověď #1595 kdy: 04. 03. 2013, 14:23:16 »
Citace od: Mirek Prýmek kdy 04. 03. 2013, 13:50:55
Zaprve to neni pravda. Moznosti kazdeho stroje jsou celkem jasne omezene. Stavovy prostor kazdeho stroje je a vzdy bude omezeny.
Stavovy priestor je v kazdom okamihu niecim obmedzeny, ale priebezne sa moze zvacsovat, kde je prave ten mnou opisany problem.

Cim je (celkovo) obmedzeny stavovy priestor serveru, ktory ked mi napise "no space left on device", tak mu tam za behu pridam dalsi disk alebo vymenim stary maly za novy velky? A ked mi zacne dochadzat miesto aj tak, tak zacnem pouzivat vzdialene ulozisko?

Citace od: Mirek Prýmek kdy 04. 03. 2013, 13:50:55
Zadruhe to je hloupy predpoklad, protoze pokud se bavime o skutecne realnych problemech ve skutecne realnych podminkach, tak vzdy mame ramcovou predstavu o narocnosti algoritmu. Spravne to rika Rax: pokud soucet dvou 32bitovych cisel bude trvat deset let, tak nas proste uz vysledek nezajima.
To som uz opisoval ako "bezne programy".

Citace od: Rax kdy 04. 03. 2013, 13:57:08
Citace od: student kdy 04. 03. 2013, 13:35:44
Ak ide len o aplikaciu postupov, tak na to sprav program - mozes ho predavat ako programatora na mojej urovni, ktory nebude robit chyby

To se nepochybně stane, virtuální kodéry očekávám kolem roku 2040, zatím na to není dostatečně výkonný hardware.
A na co je tam treba vykonny HW? Mozno tam niekde bude odpoved na to, co uz nepovazujem za mechanicke aplikovanie postupov a je na to (aspon momentalne) treba clovek, ktory nad tym musi rozmyslat a moze navrhnut aj lepsie riesenie.


Citace od: j kdy 04. 03. 2013, 13:54:42
Citace od: student kdy 04. 03. 2013, 13:35:44
...
Opet resis kokotiny, v praxi je pro me omezujici predevsim mnoztvi $$$ na mem konte, takze at uz budu resit jakykoli problem, musim ho vyresit za $$$ kteryma disponuju => reseni rozhodne nemusi byt dokonaly a schopny se vyporadat s koncem vesmiru, me staci reseni ktery dostatecne splni moje touhy.

Proto v praxi vazne nepotrebuju dokazovat, ze neco dobehne, protoze od toho neceho ocekavam nejaky vystup a nastavim podminku dle ocekavani. Stejne tak ocekavam ze to pobezi nejak dlouho a spotrebuje nejaky mnoztvi pameti, a problem budu resit az mi pamet dojde. Trebas prikoupim, trebas dojdu k tomu, ze je chyba v programu, trebas dojdu k tomu, ze program je az prilis dokonaly, ale porad nepotrebuju nic dokazovat.
Jasne, nastavis podmienku napr. 5GB na kompilaciu Linux kernelu (lebo to by malo stacit) a ono to nezbehne. Nepotrebujes nic dokazovat, ale niekedy "by bolo dobre" vediet, ci sa oplati kupovat novy disk / rychlejsi CPU a to este pred jeho kupou a niekolkymi hodinami kompilacie (ci nie je bug v gcc/inde).

Citace od: j kdy 04. 03. 2013, 13:54:42
BTW: Elektrinu vetsina lidi pouziva, sifrovani muze (a funguje) i bez prvocisel.
Vsak aj TV sa da pozerat aj pri svieckach ;-).

Rax

Re:VŠ z trochu jiného úhlu
« Odpověď #1596 kdy: 04. 03. 2013, 14:26:35 »
Citace od: Radek Miček kdy 04. 03. 2013, 14:15:16
A proto, když něco dokazujete, potřebujete, aby funkce byla totální pro všechny vstupy.

Nepotřebuji znát chování funkce pro všechny vstupy, protože mám HDD 1 TB tak mi to bohatě stačí pro nějakých 2^2^43 vstupních kombinací. Je zásadní rozdíl mezi "2^2^43" a "všechny".

Re:VŠ z trochu jiného úhlu
« Odpověď #1597 kdy: 04. 03. 2013, 14:32:58 »
Citace od: student kdy 04. 03. 2013, 14:23:16
Stavovy priestor je v kazdom okamihu niecim obmedzeny, ale priebezne sa moze zvacsovat, kde je prave ten mnou opisany problem.
Ale to neni podstata problemu. Podstata problemu je v tom, ze napr. nikdy nebudes potrebovat resit vypocet, ktery ma tolik stavu, kolik je atomu ve vesmiru. Proste nebudes. A jestlize nejaka takova hranice existuje (libovolne jak velka, ale nejaka), tak je HP teoreticky resitelny.

Jako nezlob se na me, ale jestli tohle nechapes, a zaroven argumentujes tim, jak je teoreticka informatika a matematika strasne dulezita, tak si o tom chte nechte musim myslet svoje...

Rax

Re:VŠ z trochu jiného úhlu
« Odpověď #1598 kdy: 04. 03. 2013, 14:40:06 »
Citace od: student kdy 04. 03. 2013, 14:23:16
A na co je tam treba vykonny HW? Mozno tam niekde bude odpoved na to, co uz nepovazujem za mechanicke aplikovanie postupov a je na to (aspon momentalne) treba clovek, ktory nad tym musi rozmyslat a moze navrhnut aj lepsie riesenie.

I mechanická aplikace postupů vyžaduje výkonný HW, například řízení automobilu. Při řízení nic nevymýšlíš, stejně tak nic nevymýšlíš při kódování www stránek pro LAMP.

student

Re:VŠ z trochu jiného úhlu
« Odpověď #1599 kdy: 04. 03. 2013, 14:54:22 »
Citace od: Mirek Prýmek kdy 04. 03. 2013, 14:32:58
Ale to neni podstata problemu. Podstata problemu je v tom, ze napr. nikdy nebudes potrebovat resit vypocet, ktery ma tolik stavu, kolik je atomu ve vesmiru. Proste nebudes. A jestlize nejaka takova hranice existuje (libovolne jak velka, ale nejaka), tak je HP teoreticky resitelny.
Skor ... tak je HP teoreticky resitelny pro pocet stavu mensi jak pocet atomu ve vesmiru.

Ale to je podla mna nezmysel - atomov vo vesmire je nieco ako 10^80 ~= 2^265.75. A nejaky vypocet, ktory moze pouzivat 266 bitov (tj. moze mat az 2^266 stavov) zase nie je az taka vzacnost. Niektore jeho vetvy jednoducho nezastavia a nezriedka by sa oplatilo vediet, ci su aj take.

Citace od: Mirek Prýmek kdy 04. 03. 2013, 14:32:58
Jako nezlob se na me, ale jestli tohle nechapes, a zaroven argumentujes tim, jak je teoreticka informatika a matematika strasne dulezita, tak si o tom chte nechte musim myslet svoje...
Tak nieco o "strasnej dolezitosti" som AFAIK nikde nepisal. Akurat som sa staval proti tomu, ze je z principu zbytocna a nikdy ju nebude na nic treba (prip. ze ju bude menej treba ako pravo atd - ale tam bola explicitne spomenuta len moja skusenost a skusenosti inych sa mozu lisit).

Radek Miček

Re:VŠ z trochu jiného úhlu
« Odpověď #1600 kdy: 04. 03. 2013, 15:12:08 »
Citace od: Rax kdy 04. 03. 2013, 14:26:35
Citace od: Radek Miček kdy 04. 03. 2013, 14:15:16
A proto, když něco dokazujete, potřebujete, aby funkce byla totální pro všechny vstupy.

Nepotřebuji znát chování funkce pro všechny vstupy, protože mám HDD 1 TB tak mi to bohatě stačí pro nějakých 2^2^43 vstupních kombinací. Je zásadní rozdíl mezi "2^2^43" a "všechny".

Když dovolím divergenci, tak mohu dokázat cokoliv (verifikace ztrácí smysl).

Re:VŠ z trochu jiného úhlu
« Odpověď #1601 kdy: 04. 03. 2013, 15:24:09 »
Citace od: student kdy 04. 03. 2013, 14:54:22
Ale to je podla mna nezmysel - atomov vo vesmire je nieco ako 10^80 ~= 2^265.75. A nejaky vypocet, ktory moze pouzivat 266 bitov (tj. moze mat az 2^266 stavov) zase nie je az taka vzacnost. Niektore jeho vetvy jednoducho nezastavia a nezriedka by sa oplatilo vediet, ci su aj take.
Promin, ale ty jsi opravdu tak natvrdlej, nebo si ze me delas srandu? To se jako budeme ted bavit o tom, kolik je atomu ve vesmiru? Promatkuprirodu, jiste ze jsem myslel tolik BITU, kolik je tech atomu. Ale to je jedno, na tom totiz vubec nezalezi...

Prosimte, kdyz te ta teoreticka informatika tak bavi a je tak strasne dulezita, dobre si promysli, proc je HP resitelny pro linear bounded automata. Cim to je? Co je tak zasadne odlisuje od TM?
A proc vlastne problemy zacinaji u counter automata?
A pak si poloz zapeklitou otazku: umi pocitac, ze ktereho prave pises na root, skutecne rozeznavat jazyk na a^{n}b^{n}? Proc? Pokud ne, jak bys ho musel rozsirit, aby to umel?

Samozrejme pokud nechces, tak se nad tim nezamyslej, ale mel bys to udelat, protoze chapat tyhle veci je straaaasne dulezite pro kazdeho ajtaka, aaaaaaano?

Ja si s dovolenim na nejaky cas dam od tohodle tematu pauzu, jinak me fakt jebne.

student

Re:VŠ z trochu jiného úhlu
« Odpověď #1602 kdy: 04. 03. 2013, 21:38:16 »
Citace od: Mirek Prýmek kdy 04. 03. 2013, 15:24:09
Promin, ale ty jsi opravdu tak natvrdlej, nebo si ze me delas srandu? To se jako budeme ted bavit o tom, kolik je atomu ve vesmiru?
Tak v praxi sa castejsie hovori o konkretnych cislach ako o "nejakom pocte" X atomov a podobne. Chcel som sa tomu pripodobnit uz tu ;-).

Citace od: Mirek Prýmek kdy 04. 03. 2013, 15:24:09
Promatkuprirodu, jiste ze jsem myslel tolik BITU, kolik je tech atomu. Ale to je jedno, na tom totiz vubec nezalezi...
Nemam kristalovu gulu, aby som mohol tusit, co si myslel. Ak ma nejaku funkcnu nejaky zaryty odporca matematiky, tak nech mi ju prosim poskytne a budeme moct viest aj takuto debatu.

Citace od: Mirek Prýmek kdy 04. 03. 2013, 15:24:09
Prosimte, kdyz te ta teoreticka informatika tak bavi a je tak strasne dulezita,
Citace od: Mirek Prýmek kdy 04. 03. 2013, 15:24:09
Samozrejme pokud nechces, tak se nad tim nezamyslej, ale mel bys to udelat, protoze chapat tyhle veci je straaaasne dulezite pro kazdeho ajtaka, aaaaaaano?
Odkazujes na nieco, co som nepisal a upozornil som na to aj v prispevku, na ktory reagujes. Tak sa citujem:
Citace od: student kdy 04. 03. 2013, 14:54:22
Tak nieco o "strasnej dolezitosti" som AFAIK nikde nepisal. Akurat som sa staval proti tomu, ze je z principu zbytocna a nikdy ju nebude na nic treba (prip. ze ju bude menej treba ako pravo atd - ale tam bola explicitne spomenuta len moja skusenost a skusenosti inych sa mozu lisit).

Citace od: Mirek Prýmek kdy 04. 03. 2013, 15:24:09
dobre si promysli, proc je HP resitelny pro linear bounded automata. Cim to je? Co je tak zasadne odlisuje od TM?
Pre danu dlzku vstupu mame u LBA len obmedzeny pocet konfiguracii. A kedze mame v HP zadany aj vstup, tak jeho dlzku mozeme pouzit a obmedzit nou pocet stavov.

Citace od: Mirek Prýmek kdy 04. 03. 2013, 15:24:09
A pak si poloz zapeklitou otazku: umi pocitac, ze ktereho prave pises na root, skutecne rozeznavat jazyk na a^{n}b^{n}? Proc?
V ziadnom momente nie (v lubovolnom okamihu ma obmedzeny pocet stavov, viz moj prispevok skor - to ma vlastne ale aj Turingov stroj - v lubovolnom momente pouziva len konecne velku cast pasky). Ak mi ale das vstup a pockas si na vystup, tak som schopny* ho rozhodnut - pockam si az dokedy nejaky HW bude schopny udrzat cisla do n (nech je to polovica dlzky vstupu) a potom si ten HW pripojim napr. cez siet a necham ho to spocitat z mojho PC.

* to ma samozrejme nejake predpoklady - vykon a ulozna kapacita HW bude stale rast, co vyzera byt pravda podla Moorovho zakona, ale ktovie, ako to bude za 10, 100 alebo 1000 rokov.

Re:VŠ z trochu jiného úhlu
« Odpověď #1603 kdy: 04. 03. 2013, 22:03:34 »
Bezva. Tak to já umím podobně řešit zcela libovolný problém - prostě si počkám, až bude k dispozici patřičném orakulum. A dokud nebude, budu prostě čekat. Výhodou je, že tímto způsobem umím řešit i problémy, které jsou prokazatelně neřešitelné ani teoreticky.

No, tak to bysme měli dneska za F, tak se na to ještě koukněte pane kolego a zkusíme to někdy příště.

Re:VŠ z trochu jiného úhlu
« Odpověď #1604 kdy: 04. 03. 2013, 22:12:56 »
P.S. doporučuji úvahu zaměřit směrem k pojmu "stavový prostor". To totiž není to samé jako popsaná část pásky.