Pomohl vám titul k lepší práci?

[Mirek Prýmek]

Niezeby som sa citil extra kvalifikovane v tomto smere, ale od slusneho OS by som intuitivne ocakaval veci ako:
"tento program hrozi zacyklenim, fakt ho chces spustit?"
"program sa nie je schopny skoncit, mam ho zabit?"

Hm, tak to jednak vůbec nesouvisí s teorií složitosti, jednak to neumí žádný běžný OS, takže tvoje "intuitivní očekávání" asi musí být realitou docela zklamáváno

[Reklama]

[Mirek Prýmek]

"tento program hrozi zacyklenim, fakt ho chces spustit?"
"program sa nie je schopny skoncit, mam ho zabit?"

Mimochodem, JS ti jistě milerád vysvětlí, že to není proveditelné, protože problém zastavení není ani teoreticky řešitelný.

...což je omyl a JS tím jenom demonstruje neznalost právě té látky, jejíž znalost považuje za klíčovou ale určitě tě plamenně vyvede z údajného omylu

[Pavel...]

Niezeby som sa citil extra kvalifikovane v tomto smere, ale od slusneho OS by som intuitivne ocakaval veci ako:
"tento program hrozi zacyklenim, fakt ho chces spustit?"
"program sa nie je schopny skoncit, mam ho zabit?"

Hm, tak to jednak vůbec nesouvisí s teorií složitosti, jednak to neumí žádný běžný OS, takže tvoje "intuitivní očekávání" asi musí být realitou docela zklamáváno

a) problem zastavenia  nie je sucast vycislitelnosti? Uz su to roky, takze uznavam, ze mozem zit v blude

b) este aj ohovarany produkt MS za ktorym sedim ponuka bod c.2., ocividne sa snazia s tym nieco spravit. To, ze to z podstaty veci nejde idealne spravit je presne to co presahuje polhodinovy rychlokurz geniality kde sa student dozvie, ze to nejde.

[Pavel...]

Hm, tak to jednak vůbec nesouvisí s teorií složitosti

a) problem zastavenia  nie je sucast vycislitelnosti? Uz su to roky, takze uznavam, ze mozem zit v blude
[/quote]

hm... mal by som sa tusim naucit citat vycislitelnost a zlozitost su uznavam rozne veci

k zlozitosti:
- sprava pamati nie je dostatocny priklad?

[Mirek Prýmek]

a) problem zastavenia  nie je sucast vycislitelnosti? Uz su to roky, takze uznavam, ze mozem zit v blude

To je celkem jedno, jak tomu říkáme, můžeme to klidně považovat za součást, beru.

Jenže znovu opakuju:

1. problém zastavení Turingova stroje není totožný s problémem zastavení reálného počítače. Takže pokud se naučíš formálně dokázat, že problém zastavení TS nejde na TS řešit, o problému řešitelnosti zastavení PC na PC ti to (formálně) neříká vůbec nic.

2. bavili jsme se o tom, jestli je určitá znalost potřeba k psaní OS. Znalost problému zastavení TS k psaní OS prostě potřeba není.

b) este aj ohovarany produkt MS za ktorym sedim ponuka bod c.2., ocividne sa snazia s tym nieco spravit.

Ovšem to jistě dělají nějakou heuristikou, která s teorií nemá nic moc společného.

To, ze to z podstaty veci nejde idealne spravit je presne to co presahuje polhodinovy rychlokurz geniality kde sa student dozvie, ze to nejde.

Omyl. Ideálně to (aspoň teoreticky) udělat jde. Akorát je oproti idealizovanému TS potřeba pár podmínek navíc (které běžný výpočet na běžném PC splňuje). Např. si za model PC můžeme místo TS zvolit linear bounded automaton.

- sprava pamati nie je dostatocny priklad?

Za dostatečný příklad budu považovat, když mi někdo ukáže konkrétní aplikaci konkrétní netriviální teorie, bez jejíž znalosti tu správu paměti nikdo nebude schopen napsat. Nebo ji aspoň napíše řádově hůř.

Jsem otevřený diskusi - ale rád bych viděl opravdu konkrétní příklad. Jenom takové plácnutí "memory management" mě fakt nemůže přesvědčit.

[Reklama]

[Jakub Galgonek]

k zlozitosti:
- sprava pamati nie je dostatocny priklad?

Po praktické stránce ze složitosti potřebuješ (hlavně) vědět, co to je asymptotická, průměrná nebo amortizovaná složitost. Hodí se znát pár postupů, jak se dá spočítat ta amortizovaná složitost a jak se počítá složitost rekurzivních algoritmů. Dobré je také umět ukázat, že problém je NP-úplný. Ale to všechno lze prakticky zvládnout, aniž bys musel cokoliv vědět o turingově stroji.

[Mirek Prýmek]

Ale to všechno lze prakticky zvládnout, aniž bys musel cokoliv vědět o turingově stroji.

Hlavně tohle všechno se (na skutečně potřebné úrovni) dá zvládnout velice rychle a vůbec na to nepotřebuješ se tomu věnovat celý semestr.

IMHO úplně stačí to "teoreticky" znát na téhle úrovni: http://www.algoritmy.net/article/3024/Amortizovana-slozitost -- zbytek už je jenom projít si pár konkrétních algoritmů a pro ně složitost stanovit.

Žádné důkazy, žádná teorie. Prostě ti stačí tušit, kde se hodí použít linked list, kde normální list, kde hashtabulku... A aby to nebylo tk jenoduchý, tak při psaní skutečného OS se nemůžeš omezit na tu teoretickou složitost, ale musíš vzít v úvahu skutečnou, praktickou složitost - s jakými daty se obvykle, v praxi setkáš -- a teprve tomu implementaci přizpůsobit, i kdyby teoreticky bylo jiné řešení lepší...

[Pavel...]

b) este aj ohovarany produkt MS za ktorym sedim ponuka bod c.2., ocividne sa snazia s tym nieco spravit.

Ovšem to jistě dělají nějakou heuristikou, která s teorií nemá nic moc společného.

"nejaka heuristika" je presne to, co bez znalosti teorie je zvycajne vo vysledku vyrazne horsie ako ked teoriu viete.
Zakladny rychlokurz povie: "nejde to".

Jednoduchy priklad zo zivota: na ZS som pocitil potrebu zoradit pole. Naprogramoval som maxsort, pretoze som nemal ani tuch o nejakej teorii. Presne takto si predstavujem, ze by postupoval programator bez teoretickeho vzdelania, ktory by bol postaveny pred ulohu "sprav nejaky memory management"/"nejaku heuristiku na zacyklenie".

Omyl. Ideálně to (aspoň teoreticky) udělat jde. Akorát je oproti idealizovanému TS potřeba pár podmínek navíc (které běžný výpočet na běžném PC splňuje). Např. si za model PC můžeme místo TS zvolit linear bounded automaton.

Z praktickeho hladiska bude podla mna zastavenie na LBA s dostatocne dlhou paskou ekvivalentne TS - kvoli zlozitosti.

Odpoved "ide riesit problem zastavenia na realnom PC" by bola v rychlokurze asi este horsia, pretoze by to mohol realne niekto skusit . Takto pevne verim, ze absolvent kazdej dedinskej IT univerzity si zapamata aspon tolko, ze to nema skusat.

- sprava pamati nie je dostatocny priklad?

Za dostatečný příklad budu považovat, když mi někdo ukáže konkrétní aplikaci konkrétní netriviální teorie, bez jejíž znalosti tu správu paměti nikdo nebude schopen napsat. Nebo ji aspoň napíše řádově hůř.

Videl som par clankov na temu sprava pamati a celkom sa to tam hemzilo nie uplne trivialnymi algoritmami.
Ale uznavam, ze mozno je to len odborna latina.

Napriklad by som cakal, ze tam treba vediet rozumne implementovat toto: http://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu
Co nepovazujem, za "vseobecne vzdelanie ako povedzme sortenie".

[Pavel...]

k zlozitosti:
- sprava pamati nie je dostatocny priklad?

Po praktické stránce ze složitosti potřebuješ (hlavně) vědět, co to je asymptotická, průměrná nebo amortizovaná složitost. Hodí se znát pár postupů, jak se dá spočítat ta amortizovaná složitost a jak se počítá složitost rekurzivních algoritmů. Dobré je také umět ukázat, že problém je NP-úplný. Ale to všechno lze prakticky zvládnout, aniž bys musel cokoliv vědět o turingově stroji.

Ono je to jednoduche: na prakticky hocico (aj na povedzme odobratie slepeho creva) vam staci najvyssie poschodie vedomosti.
Donedavna som nemal ani tuch, ako exaktne vyzera attachment v mailoch napriek tomu, ze mnou napisana aplikacia ich posielala.
Nad isty stupen komplexity, ale potrebujete mat o trochu hlbsie vedomosti. (takto som sa dostal k tomu, ze som preskumal, ako presne ten attachment vyzera)

Je pomerne usmevne, ked tu prezentujete "staci vediet co je asymptoticka zlozitost", "vediet ukazat NP-uplnost" a sucasne argumentujete, ze "staci mat zakladne prakticke vedomosti". Ked niekto ma vediet toto, tak uz moze mat absolvovany polrocny kurz, ktory mu aj vysvetli aj zaklady teorie.

[Mirek Prýmek]

"nejaka heuristika" je presne to, co bez znalosti teorie je zvycajne vo vysledku vyrazne horsie ako ked teoriu viete.
[...] Odpoved "ide riesit problem zastavenia na realnom PC" by bola v rychlokurze asi este horsia, pretoze by to mohol realne niekto skusit . Takto pevne verim, ze absolvent kazdej dedinskej IT univerzity si zapamata aspon tolko, ze to nema skusat.

Jak vidíš, POLOteoretické vzdělání, které se našim absolventům dostává, jim k dobré heuristice nepomůže - přesně jak jsi demonstroval teď, je naopak vede k mylnému dojmu, že "to nejde" a dokonce k pocitu "to je dobře, že to ani nezkusí".

Proč by to, do psích kulek, neměli zkoušet? Teoreticky to jde a každému (úplně každému) je jasné, že prakticky to bude komplikované. Ale proč by to propánajána neměl zkusit? Copak AVGčko nemá/nemělo heuristický test, který simuloval spuštění programu a zkoumal, o co se program pokusí? To je přece skoro totéž. Takže smyslem toho slavného POLOteoretického vzdělání má být, že do AVGčka přijde pětadvacetiletý Brouk Pytlík čerstvě vylezlý z univerzity, který začne AVGčku tvrdit, že nejde udělat to, co oni dělají?!

Videl som par clankov na temu sprava pamati a celkom sa to tam hemzilo nie uplne trivialnymi algoritmami.
Ale uznavam, ze mozno je to len odborna latina.

Já jsem v Básnících viděl přednášku na téma "Hygiena psacího stolu", kde se to taky hamžilo odbornými termíny... A přesto si každý z nás umí psací stůl uspořádat...

Napriklad by som cakal, ze tam treba vediet rozumne implementovat toto: http://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu

A to jako implementace nějakého algoritmu má být ta teorie? Nebo co tím chceš říct?

[gamer]

A aby to nebylo tk jenoduchý, tak při psaní skutečného OS se nemůžeš omezit na tu teoretickou složitost, ale musíš vzít v úvahu skutečnou, praktickou složitost - s jakými daty se obvykle, v praxi setkáš -- a teprve tomu implementaci přizpůsobit, i kdyby teoreticky bylo jiné řešení lepší...

Ještě dodám, že při psaní skutečného OS je dobré vzít v úvahu nejen praktická data, ale i praktický hardware, na kterém to poběží. Ono je hezké, že hledání v RB tree má složitost O(log N) a hledání v obyčejném nesetříděném poli O(N), ale většinou se už neříká, že přístup k prvku v RB tree generuje typicky docela drahý cache miss, takže když se celková velikost všech prvků vejde do několiká málo cache lines, je pole výrazně výhodnější než RB tree, ušetří se čas CPU i celková pamět.

[Mirek Prýmek]

Nad isty stupen komplexity, ale potrebujete mat o trochu hlbsie vedomosti. (takto som sa dostal k tomu, ze som preskumal, ako presne ten attachment vyzera)

Jasně, zjistil jsi, že to potřebuješ, tak sis to sám dostudoval. A pointa je?

Je pomerne usmevne, ked tu prezentujete "staci vediet co je asymptoticka zlozitost", "vediet ukazat NP-uplnost" a sucasne argumentujete, ze "staci mat zakladne prakticke vedomosti". Ked niekto ma vediet toto, tak uz moze mat absolvovany polrocny kurz, ktory mu aj vysvetli aj zaklady teorie.

Ano, myslím si, že každý člověk, co studuje IT, by měl mít jeden semestr jeden předmět, který by polopaticky na praktických příkladech vysvětloval praktické důsledky nejdůležitějších teoretických informatických objevů. Předmět by měl jít hlavně do šířky, aby každý absolvent měl přestavu, jaké ty objevy jsou a jaké mají implikace pro praxi. Kdo by chtěl, mohl by si vybrat konkrétní oblast, která ho zajímá (např. složitost) a v té jít v rámci volitelného předmětu hlouběji - tj. teprve tam se seznámit se všemi důkazy, formalismy apod.

[Mirek Prýmek]

Ještě dodám, že při psaní skutečného OS je dobré vzít v úvahu nejen praktická data, ale i praktický hardware, na kterém to poběží. Ono je hezké, že hledání v RB tree má složitost O(log N) a hledání v obyčejném nesetříděném poli O(N), ale většinou se už neříká, že přístup k prvku v RB tree generuje typicky docela drahý cache miss, takže když se celková velikost všech prvků vejde do několiká málo cache lines, je pole výrazně výhodnější než RB tree, ušetří se čas CPU i celková pamět.

Jasně, to je přesně ono. Nebo se třeba šahá na disk křížem krážem a ve finále je to pomalý jako prase... To je přesně to, co jsem říkal výš: umíme přesně a teoreticky vyfutrovaně předpovídat výsledek dostihů idealizovaných koulí

P.S. na hw jsem při psaní myslel, ale už jsem to nechtěl prodlužovat

[Jakub Galgonek]

Ked niekto ma vediet toto, tak uz moze mat absolvovany polrocny kurz, ktory mu aj vysvetli aj zaklady teorie.

No ale také by místo toho mohl absolvovat půlroční kurz něčeho jiného :-). Já měl "těžkotonážní" teoretickou informatiku hodně rád. A na to, že nejsem teoretický informatik, jsem ji absolvoval docela hodně (třeba složitosti a vyčíslitelnosti dohromady 8 semestrů). Ale mezi touto teorií a programátorskou praxí je docela propast.

[Mirek Prýmek]

A na to, že nejsem teoretický informatik, jsem ji absolvoval docela hodně (třeba složitosti a vyčíslitelnosti dohromady 8 semestrů).

To víš, čím víc pruhů, tím víc Adidas čím víc teorie, tím víc univerzita. Světová! (hlavně ve srovnání s Ulanbátarem a Horní Voltou).