VŠ z trochu jiného úhlu

[JS]

Na elektroSŠ se probírají základy. Důležité věci jako FPGA nebo FFT nebo vysokofrekvenční technika se probírají až na elektroVŠ, protože je to prostě na SŠ moc složité.

Jo, protoze na to je potreba matematika. A nektere veci holt potrebuji par let studia, a tam ti nepomuze sebelepsi studijni program.

Turingův princip redukce je v praxi naprosto k ničemu, jednoduše ho nemáš jak a kde použít.

Jednou jsem videl na dailywtf nebo podobne strance jeden odstrasujici priklad v tomto smyslu. Nekdo se snazil resit halting problem, maskovany jako problem z praxe. Nicmene potrebujes vedet, co je TS abys mohl studovat slozitost (na tom je postavena Cookova veta, jestli se nepletu).

[Reklama]

[Zz]

Inak keď nestačí Google, tak je tu aj napríklad Eset - čo viem, tak pri poslednom nábore chceli od ľudí naprogramovať rýchly prevod medzi číselnými sústavami u veľmi veľkých čísel. Toto sa nedá zvládnuť vo vyžadovanom čase bez dobrých znalostí algebry.

Nesmysl, tohle jsme dělali na gymplu jako přípravu na maturitu (u nás šlo maturovat z počítačů). Provede se převod ze soustavy X do binární soustavy pomocí sčítání a násobení a pak obrácené z binární soustavy pomocí dělení a modulo do soustavy Y. Když jsou čísla veliké, tak se násobení a dělení a modulo proměnných převede pole a na něm sčítání a odčítání a porovnávání a posuny. Žádnou VŠ algebru na to nepotřebuješ, jenom programátorské schopnosti.

[JS]

Jo ještě bych doporučil stranu 41, kde se specificky mluví o ICT - hodně se sice mluví o matematice, ale středoškolské - tj. té úplně základní. Vyšší matika zjevně nikomu nechybí.

Vidis, ja tu stranku 41 chapu presne opacne, nez ty.

[Zz]

Jo, protoze na to je potreba matematika. A nektere veci holt potrebuji par let studia, a tam ti nepomuze sebelepsi studijni program.

Matematika na FFT jistě potřeba je, ale ne Gauss-Ostrohradský. Nikdo tady nikdy netvrdil, že matematika je jako celek k ničemu, jen že příliš teoretická matematika se v praxi nevyužije. A krátit studium také nikdo nechtěl.

Jednou jsem videl na dailywtf nebo podobne strance jeden odstrasujici priklad v tomto smyslu. Nekdo se snazil resit halting problem, maskovany jako problem z praxe. Nicmene potrebujes vedet, co je TS abys mohl studovat slozitost (na tom je postavena Cookova veta, jestli se nepletu).

Halting problém se v praxi neřeší. Buď algoritmus skončí do příštího pondělí nebo letí ze skály.
Složitost se v praxi nestuduje protože je to marná práce, teoretický výpočet příliš zatěžuji vnější vlivy jako cache nebo HDD. Všechny algoritmy které umíme naimplementovat se zbenchmarkují na testovacích datech (to by se dělalo tak jako tak) a máme jasno.

[poiu]

Nesmysl, tohle jsme dělali na gymplu jako přípravu na maturitu (u nás šlo maturovat z počítačů). Provede se převod ze soustavy X do binární soustavy pomocí sčítání a násobení a pak obrácené z binární soustavy pomocí dělení a modulo do soustavy Y. Když jsou čísla veliké, tak se násobení a dělení a modulo proměnných převede pole a na něm sčítání a odčítání a porovnávání a posuny. Žádnou VŠ algebru na to nepotřebuješ, jenom programátorské schopnosti.

Tak tak nejak som to implementoval ja (aj keď som preskočil binárnu sústavu - ide to aj bez nej) a bolo to veľmi pomalé aj po optimalizáciách (stačí prečítať môj pôvodný príspevok).
Karacuba je už oveľa lepší prístup k násebeniu (Schonhage-Strassen je ešte lepší, ale ten by som z pamäti nedal). A keďže tam bol len obmedzený počet číselných sústav, tak by som potom asi previedol delenie na násobenie.

[Reklama]

[Radek Miček]

Halting problém se v praxi neřeší. Buď algoritmus skončí do příštího pondělí nebo letí ze skály.
Složitost se v praxi nestuduje protože je to marná práce, teoretický výpočet příliš zatěžuji vnější vlivy jako cache nebo HDD. Všechny algoritmy které umíme naimplementovat se zbenchmarkují na testovacích datech (to by se dělalo tak jako tak) a máme jasno.

HP se řeší třeba při typové kontrole nebo typové inferenci. S tím benchmarkováním je problém - co když je algoritmus pomalý jen na určitých vstupech a vy zrovna ty vstupy neotestujete.

[Mirek Prýmek]

Vidis, ja tu stranku 41 chapu presne opacne, nez ty.

Nic ti nebrání v tom, přijít konečně taky s nějakými fakty (průzkumy, šetřeními, rozhovory...), které budou jasněji mluvit ve prospěch vysokoškolské matematiky nad rámec toho, co jsem za základní zmínil já.

[poiu]

Halting problém se v praxi neřeší. Buď algoritmus skončí do příštího pondělí nebo letí ze skály.
Složitost se v praxi nestuduje protože je to marná práce, teoretický výpočet příliš zatěžuji vnější vlivy jako cache nebo HDD. Všechny algoritmy které umíme naimplementovat se zbenchmarkují na testovacích datech (to by se dělalo tak jako tak) a máme jasno.

Myslím si, že máte zlý prístup a z toho vyvodzujete nepoužiteľnosť teórie (týmto nehovorím, že sa to používa - akurát sa mi zdajú spomínané dôvody nezmyselné).
Na cache máme cache-oblivious prístup, ktorý umožňuje navrhovať algoritmy tak, aby sa správali optimálne ku cache, aj keď nevedia jej veľkosť. Pri HDD sa zase počíta zložitosť tak, že sa zanedbajú jednoduché výpočty CPU a počítajú sa hlavne časy seekov, "pootočenia disku", čítania dát a pár zanedbateľne malých časov. Vďaka tomu môžem aj zjednodušiť celý systém tak, že nebudem uvažovať zbytočne veľké dátové štruktúry nad dátami chovajúce sa teoreticky veľmi dobre, ak viem, že ma samotný seek až toľko nestojí (10ms na seek pri 100MB/s je 1MB - takže ak by som mal čítať štruktúru o veľkosti viac ako 1MB, tak uprednostním seek).

[Zz]

Tak tak nejak som to implementoval ja (aj keď som preskočil binárnu sústavu - ide to aj bez nej) a bolo to veľmi pomalé aj po optimalizáciách (stačí prečítať môj pôvodný príspevok).
Karacuba je už oveľa lepší prístup k násebeniu (Schonhage-Strassen je ešte lepší, ale ten by som z pamäti nedal). A keďže tam bol len obmedzený počet číselných sústav, tak by som potom asi previedol delenie na násobenie.

Pokud jsou soustavy známé dopředu a je jich omezený počet, jako třeba hex a dec a tak, tak to je samozřejmě jiná.

[poiu]

Pokud jsou soustavy známé dopředu a je jich omezený počet, jako třeba hex a dec a tak, tak to je samozřejmě jiná.

Sústavy boli tuším so základom 2-36 a prevod medzi ľubovolnou dvojicou. Podľa mňa je to stále o tom istom.

HP se řeší třeba při typové kontrole nebo typové inferenci.

Len pre zaujímavosť - ako sa tam rieši a v akom jazyku to je pri akom výreze? Mňa nenapadá, ako by sa to dalo napasovať na pomerne

[poiu]

Len pre zaujímavosť - ako sa tam rieši a v akom jazyku to je pri akom výreze? Mňa nenapadá, ako by sa to dalo napasovať na pomerne

Sorry, odoslal som to predčasne - v akom je to výraze? Nenapadá ma, ako to napasovať na pomerne priamočiary postup ako je v C (priamočiary na pohľad).

[Patrik]

Mladý člověk by měl počítat s tím, že programátorem nemůže zůstat po celý svůj profesní život a výše postavené profese, na které
je možné postoupit, potřebují výrazně vyšší podíl měkkých dovedností.

Výše postavené profese? Například? Nějaký byznys poskok je brán lépe než vývojář? Tak to je hezký průzkum a asi bych se měl učit nějaké měkké dovednosti, než mě nějaký Ind vyhodí z práce? Myslím, že celý průzkum je docela chudý, ale jsou to reálná fakta a o to přeci jde!

[Zz]

HP se řeší třeba při typové kontrole nebo typové inferenci.

To se mi vůbec nezdá že by se při typové kontrole mohl vyskytnout problém HP. Existuje na to nějaký ukázkový problém ?

S tím benchmarkováním je problém - co když je algoritmus pomalý jen na určitých vstupech a vy zrovna ty vstupy neotestujete.

To riziko samozřejmě může vzniknout, nicméně málokdy se dělá takový špek aby to bylo reálně možné.

[Radek Miček]

Len pre zaujímavosť - ako sa tam rieši a v akom jazyku to je pri akom výreze? Mňa nenapadá, ako by sa to dalo napasovať na pomerne

Například v programovacích jazycích založených na polymorfním lambda kalkulu (otypovat jdou pouze programy, které skončí). Takže, když navrhujete takový jazyk, je třeba udělat určitá omezení typového systému, aby typová inference vždy skončila. Jiným příkladem jsou instance typových tříd v Haskellu (když se zapne přepínač -fallow-undecidable-instances, tak kompilace nemusí skončit).

[Zz]

Myslím si, že máte zlý prístup a z toho vyvodzujete nepoužiteľnosť teórie (týmto nehovorím, že sa to používa - akurát sa mi zdajú spomínané dôvody nezmyselné).
Na cache máme cache-oblivious prístup, ktorý umožňuje navrhovať algoritmy tak, aby sa správali optimálne ku cache, aj keď nevedia jej veľkosť. Pri HDD sa zase počíta zložitosť tak, že sa zanedbajú jednoduché výpočty CPU a počítajú sa hlavne časy seekov, "pootočenia disku", čítania dát a pár zanedbateľne malých časov. Vďaka tomu môžem aj zjednodušiť celý systém tak, že nebudem uvažovať zbytočne veľké dátové štruktúry nad dátami chovajúce sa teoreticky veľmi dobre, ak viem, že ma samotný seek až toľko nestojí (10ms na seek pri 100MB/s je 1MB - takže ak by som mal čítať štruktúru o veľkosti viac ako 1MB, tak uprednostním seek).

Netvrdím že je to nepoužitelné, jen že se to moc nepoužívá.
Na cache-oblivious přístup jednoduše nevěřím, na to už jsem strávil v životě příliš mnoho času optimalizací a víc než teoretické znalosti mě pomohla znalost mechanismu cacheování a paměťového řadiče.
Práce HDD obsahuje ještě cache v RAID poli, diskovou cache v RAM a mohu si implementovat svoji vlastní cache v aplikaci a celý problém se stává tak složitý, že je to prakticky nemožné nějak solidně vypočíst dopředu.