21.11.06

Teoretická informatika a matematické struktury v informatice

Tak dneska už to balím. Po celodenním maratónu učení se na zítřejší, ha, dnešní půlsemestrálku z teoretické informatiky to teď zabalím, půjdu se vykoupat, vyspím se a zítra jdu na "popravu".
Jen tak přemýšlím, k čemu je ten předmět vlastně dobrej. Pro ty, co neví, o co jde, tak je to opravdu teorie o jazycích, gramatice apod., čili ani jeden řádek kódu, nic praktickýho. Příkladem budiž definice:
Nechť M = (Q, Σ, δ, q0, F) je úplně definovaný DKA. Říkáme, že řetězec ω∊Σ* rozlišuje q1, q2, jestliže (q1, ω) ⊢ (q3, ε) ∧ (q2, ω) ⊢ (q4, ε) pro nějaké q3,q4 a právě jeden ze stavů q3,q4 je v F.
Není to úplně dokonale přepsaný, nad znakem ⊢ by měla být hvězdička * a pod ním znak M, ale pro představu stačí.
Přijde mi, že v praxi se s tímto člověk nikdy nesetká. Snad při programování překladače či interpretu, ale to člověk nedělá tak často. Předmět Matematické struktury v informatice je ještě horší, tam už opravdu vůbec nemůžu přijít na to, v čem by se mi to hodilo. Možná někomu, kdo dál bude studovat doktorský program a vymýšlet nějaké teorie...
Pravda, jsem v magisterském studiu, tak bych měl vědět i něco víc do hloubky, ale přesto mi to přijde zbytečné. V bakalářském studiu jsem měl předmět Diskrétní matematika, který byl dost podobný Matematickým strukturám a za celé 3 roky jsem to nikdy v žádném předmětu nepoužil.
Takže myslím, že ta matika i teoretická informatika je prostě na pročištění řad studentů. Za zástěrkou "budete o tom víc vědět něco do hloubky" na tom vyletí hodně studentů, možná i já. :-) A přitom by to nikdy v životě nepoužili.
No co už, jsem si postěžoval a už fakt jdu, drž mi, blogísku, palce. :-))

12 komentářů:

mirka řekl(a)...

hmm, no ked som zbadala ten nadpis, tak som si povedala, coby Mgr. so specializaciou mat. struktury a v sucasnosti PhD studentka teoretickej informatiky, ze na tom si zgustnem. Tak ted zacnem. Viem, ze asi uplne iny pohlad na tieto veci maju ludia z technik a z matfyzu (hoci nie vzdy), ale vidim to takto - preco chodia ludia na matfyz studovat cs? Vela preto, ze medzi ostatnymi exaktnymi vedami to znie celkom prakticky, mnoho preto, ze ich bavia kompy, hackovanie etc. a matfyz ma koniec koncov prestiz. A mnoho z nich sa hned vidi na softwarovom inzinierstve s naslednym teplym programatorskym miesteckom, ktore polahky ziskaju vdaka diplomu v rukach. A vacsina z nich nema prilis tucha, co to ta informatika/cs vlastne je. A su zdeseni, kolko je tam vysoko abstraktnej matiky. No mnohi z tychto ludi su velmi, velmi bystri, a kto iny, ak nie oni, by mohli vyvoj v tejto oblasti posunut dopredu? Ak by ich vsak v skole nezoznamili zo zakladmi teorie formalnych jazykov, semantiky, zlozitosti, logiky a vycislitelnosti, pravdepodobne by ich nikdy nespoznali a nemohli sa pre ne nadchnut. A tiez zalezi na tom, comu sa chces venovat. Programovacie jazyky vyvijaju ludia s hlbokou znalostou prave onych formalnych jazykov, semantiky a pod., ludia co sa vrtaju v algoritmoch musia vediet co to zo zlozitosti, hoci nie z tej velmi pokrocilej (ktora je mimochodom hadam to najkrajsie co sa da v teor. inf. najst). Takze to mozes brat tak, ze hoci vela veci, ktore sa ucite, bezny datlic nepotrebuje, ale nie kazdy sa nim stane, a tie teoreticke predmety co mas ti daju prehlad o mnohych disciplinach, a tym viac moznosti, kadial povedie tvoja cesta.

prunus řekl(a)...
Tento komentář byl odstraněn autorem.
mirka řekl(a)...

a co sa tyka tej naoko nezrozumitelnej hantyrky - ono sa to mozno nezda, ale normo-vyjadrovanie je fakt potrebne, ak chce clovek nieco pochopit z clanku, ktory napisal niekto iny. Hoci to moze posobit velmi divoko na prvy pohlad, normo-slang prechadza uz nejaky cas optimalizaciou, takze snad nie je taky zly. Este dodatok k predchadzajucemu - PhD studium nie je standardom. Pre to ta nieco/niekto musi nadchnut. Nemozes z rydzo praktickych a intuitivne pochopitelnych veci skocit niekde k modalnym logikam, alebo PCP vete. Jednak by to bol dobry sok, a jednak bez predchadzajuceho zoznamenia (co aj nedobrovolneho) by bola nulova motivacia to robit.

m1c4a1 řekl(a)...

Ha, to mě mohlo napadnout, kdo zareaguje! ;))
Nepopírám, že to svůj účel nemá. Jenže zajímá to opravdu minimum lidí. Dal bych to jako volitelný předmět a bylo by na každém, jestli to chce nebo nechce podstoupit. Je fakt, že kdyby všecko bylo v PhD studiu, tak to bude hrr, ale opět - kolik lidí ročně začne studovat PhD obor? 20? A kvůli 20 lidem se tím má trápit 300 (+ 150 opakujících) znova?
Možná jde jen o přístup. V předmětu formální jazyky a překladače, které na naši teoretickou informatiku navazují, jsme měli přednášejícího Alexandra Medunu. Možná jsi o něm něco slyšela, mám za to, že je to v oboru kapacita. Tendle člověk umí přednášet nejlíp, co jsem kdy slyšel, proto mě ten předmět jakžtakž bavil. Ale teď s jiným přednášejícím? Neumí tomu dodat šťávu, motivaci, proč se to učit, nějaký konkrétní příklady...
A ještě ta nesrozumitelná hantýrka - je jasný, že když se v tom někdo hrabe do detailů, tak potřebuje vědět přesně, co a jak. Jenže já, když se to učím, to fakt takto nestíhám. Příklad (pro tebe už asi trivialita, pro mě ne): minimalizace DKA. Ve skriptech obšírně a dopodrobna popsaný na několika stranách ve vzorečcích a algoritmických postupech, než bych se tím prolouskal, je to na čtvrt dne. Za kámošem dojdu, vysvětlí mi to lidsky za 10 minut a vím to samý a pak na to můžu nabalovat ty složitější věci a detaily, protože už chápu, o čem to je.

Nechci tím shazovat význam teoretické informatiky, jen mi přijde, že je to dost specifická oblast, do které by se měli pouštět jen ti, které to opravdu zajímá, toť vše.

mirka řekl(a)...

ad. minimalizacia automatu - tak na to su cvika;) uz to bolo davno, skoro nic si z toho nepamatam, ale aspon tusim o com to je. no a k tym skriptam ... su dobre a zle knihy. btw. mna pre PhD "nadchlo" to, ze po rokoch orientacie na teoriu mam dojem, ze sa na nic prakticke nehodim, takze aspon ten certifikat, ze mam mozog sa hodi. ale ktovie, mozno raz zo mna bude ... programatorka, etnografka, alebo potulna pesnickarka.

m1c4a1 řekl(a)...

Jo no, to by mě zajímalo - naprogramovala jsi něco, v čem využiješ tu teoretickou informatiku?

mirka řekl(a)...

no hlavne som toho nenaprogramovala vela - zapoctove programy + nejake srandicky na lustenie trapnych sifier a tak, takze programovat neviem, ale nemyslim, ze je to nieco, do coho by som sa na low-level nevedela zakratko dostat (ad mozna "kariera" programatorky). koniec koncov, Mgr. mam z matiky, a teoreticku informatiku studujem preto, ze medzi nou a matikou nie je ziadny rozdiel. Ale iste, v tom co programujes (ak to robis dobre a nie spagetenim kodu) teoreticku informatiku pouzivas - v neproceduralnom programovani velmi - i v tych trapnych zapoctikoch bolo dolezite, aby malo navrhnute riesenie strukturu, ktora je dobre vyjadritelna jazykom predikatovej logiky, ci na pokrocilejsej urovni - jazykom lambda-kalkulu (s tymto ale nemam skusenosti). V proceduralnom programovani - takytak - pouzivane algoritmy a datove struktury maju zazemie v teoretickej informatiky. V diskretke ste iste mali zaklady teorie grafov, co je myslim, velmi oblubeny model (rozne stromy, branching programs, booleovske obvody ...). A v ich jazyku je formulovana spusta algoritmov. Tie ta vedu k tomu, ako vhodne zvolit datovu strukturu, napriklad. Je potrebne vediet o NP-hard problemoch a efektivnych algoritmoch na riesenie ich specialnych pripadov, hoci sama som sa v programovani ani nedostala niekam za Floyd-Warshallov algoritmus. Dalej constraint programming, staci si vziat tak jednoduchu a pouzivanu simplexovu metodu (multiparty computation - napr. v ekonomii dost dolezite). Networking, petriho siete, neuronove siete, evolucne programovanie, efektivne heuristiky. Bez teoretickej inf. by vyhladavace neboli co su - tam je optimalizacia dolezita, v krypto - one-way funkcie, pseudonahodnost, hardcore predikaty, RSA a viac maticka interpolacia polynomov a rozne ine algoritmy v polynomialnych okruhoch (secret sharing, multiparty computation) - cosi z toho som pred par rokmi programovala. no som sa nejak rozpisala, zatial radsej stacilo.

m1c4a1 řekl(a)...

Nóó, to už zní zajímavěji. Mohli bychom se to ale učit nějak průběžně na praktických ukázkách a ne se tím prokousávat takhle kondenzovaně. :-D
Jak říkám, jedinej program, co jsem napsal, byl kdysi interpret programovacího jazyka, kde se musela dělat tabulka symbolů a podle té jsme nějak postupovali. Už si nepamatuju přesně detaily, tak neřeknu. :-)
Studuju obor Inteligentní systémy, předpokládám, že podobný hrátky se vzorečkama si ještě užiju. Mě nevadí nějaký algoritmy apod., vadí mi suchá teorie, kterou si jen tak do kódu převést nemůžu.
Je jasný, že 90% programátorů to nevyužije, protože jsou buď lepiči kódu a nebo to prostě nepotřebují - třeba programování webů nebo nějakých účetních programů opravdu složitý algoritmy a formální důkazy nepotřebují. :)

Lukas řekl(a)...

Znas snad neco lepsiho, nez KA na zpracovani konfiguracnich souboru?
To je jenom jeden praktickej priklad vyuziti deterministickech automatu.
Kdyz vymyslis gramatiku a pouzijes dvojici lex/yacc mas po programovani, proste hotovo a nemusis to ladit.

Teoreticka informatika, to jsou taky hotovy algoritmy a postupy. Kdyz se v tom vyznas, nemusis pracne vymyslet spustu veci. Proste si zvolis neco, co uz je davno vymyslene a teoreticky odvozene.

Maly priklad. Vetsina prostredi ma implementovany Quick sort a Select sort. Proc oba? Proc ne jenom jeden z nich?

m1c4a1 řekl(a)...

lukas: Tak ano, pokud víš, pro co se daný třidicí (řadicí? mám v tom teď zmatek :-) algoritmus používá, tak je to dobře. Jenže tady to v té teoretické informatice nebereme. Bereme nějakýho Chomskýho formy, který si jinde představit neumím.
Ano, pokud někdo programuje lex/yacc, tak by měl o tom něco vědět, ale jak jsem psal, je to už celkem dost specifická věc a 90% programátorů použije právě tyto nástroje, než aby si je odvozovali a optimalizovali pro svůj problém sami.

Neříkám, že je teoretická informatika nanic. Říkám, že je nanic pro mě a 90% dalších lidí, proto se mi nelíbí, že to do nás hustí. Ale holt je to takový nutný zlo asi.
A to jsem ještě nezmínil ty matematický struktury, ještě větší peklo o ničem. :-) Nějaký operace, predikátový logiky, grupy, třídy a tisíc + 1 exotických symbolů a ani řádek kódu nebo jediná ukázka, kde se to může hodit. :-) Holt mě to zajímá i po praktické stránce, nač něco vědět, když to nemůžeš využít.

Lukas řekl(a)...

Kdyz mas vetsi rozhled, tak umis resit veci elegantnejsim zpusobem.
Ver mi, ze TI se ti bude hodit. Budes lepsi programator, pac budes vedet proc delas to, co delas. Min improvizace, vic jistoty.
Ja programuju 15 let a vejsku mam dlouho za sebou a TI se mi hodi.

m1c4a1 řekl(a)...

Třeba bude. :-) Pokud nebudu dělat někde admina a vyměňovat uživatelům myši. :-D