Komiks ze života na matfyzu (a nebo ze snů o něm)
Víte, jak vyhledávají v textu lední medvědi? Zamysleli jste se někdy nad tím, odkud se berou všechny ty epsilony, ošklivá obarvení, grafy s nevhodným počtem hran a podobné radosti? Pokud ne, následující dva komiksy vás seznámí s medvědím matfyzákem a Tím, jenž zná všechny protipříklady.Omluvte prosím mizernou kvalitu (lze ji ovšem prudce zvýšit kliknutím na obrázek), pořád si víc rozumím s tužkou a pastelkami než tabletem.
Ledním medvědům se hrubě nevyplácí učit se cizí řeči, protože si přidělají spoustu práce. Tenhle komiks mě kdysi napadl na přednášce jednoho ledního medvěda, který se tím neřídil...
O zkoušce z Kombinatoriky a grafů 2 se mi zdálo ještě zhruba tři noci poté. Jedna z nich přinesla i zjevení...
Teda nechapu jak nekdo
qk
(27. 2. 2008 - 19:10)
Sbalit(6)
Teda nechapu jak nekdo nepochopi hned Aho-Corasicka, to znam teda rozhodne horsi algoritmy, treba takova furierova transformace :)
jinak dobry komixy z matfyzu jsou tady http://www-ucjf.troja.mff.cuni.cz/scheirich/index.php?s=4&strip=1
jinak dobry komixy z matfyzu jsou tady http://www-ucjf.troja.mff.cuni.cz/scheirich/index.php?s=4&strip=1
No ja nevim... do fourierky
anicka
(27. 2. 2008 - 20:47)
Sbalit(1)
No ja nevim... do fourierky se nezamotas, jakmile si jednou prectes nebo poslechnes, jak funguje, je to zcela pruzracne...
...ale pochopit aho-corasicka ze zmeti car na tabuli nebylo az tak trivialni, byt to taky slo ... a nad nekterymi ulohami na tohle tema, treba nad cenzorem, jsem pak jeste stejne stravila vic casu nez nad celou slavnou fourierkou - a jak rada jsem byla, kdyz jsem u zkousky dostala tu, a zadne hledani :-))
...ale pochopit aho-corasicka ze zmeti car na tabuli nebylo az tak trivialni, byt to taky slo ... a nad nekterymi ulohami na tohle tema, treba nad cenzorem, jsem pak jeste stejne stravila vic casu nez nad celou slavnou fourierkou - a jak rada jsem byla, kdyz jsem u zkousky dostala tu, a zadne hledani :-))
Aho-Corasicková
Martin Mareš
(7. 3. 2008 - 10:02)
Sbalit(4)
Vlastně si dodneška nejsem jistý, že jsem AC pochopil až na dno.
Krátký test: Mějme úlohu o cenzorech, o které se už Anička zmiňovala: je dán text a seznam zakázaných slov (podřetězců), chceme vystříhnout všechna zakázaná slova (čímž mohou vzniknout nová zakázaná slova a tak dále). Je jasné, jak udělat lineární řešení, které si bude pamatovat v zásobníku stavy automatu, kterými prošlo? Opravdu? Už? A je teď jasné, proč doopravdy lineární není? :-)
Krátký test: Mějme úlohu o cenzorech, o které se už Anička zmiňovala: je dán text a seznam zakázaných slov (podřetězců), chceme vystříhnout všechna zakázaná slova (čímž mohou vzniknout nová zakázaná slova a tak dále). Je jasné, jak udělat lineární řešení, které si bude pamatovat v zásobníku stavy automatu, kterými prošlo? Opravdu? Už? A je teď jasné, proč doopravdy lineární není? :-)
No za nas se teda asi ucila
qk
(8. 3. 2008 - 10:41)
Sbalit(3)
No za nas se teda asi ucila zjednodusena verze. Rozhodne zadne upravy textu v tom nebyli, akorat se vratilo co se naslo(a to nejak rozumne i ve vicenasobnych stavech, aby nevadila abeceda s prilisnym opakovanim jako a,aa,aaa). Coz je linearni. Kdyz ma vysledna funkce modifikovat text, tak je to horsi a chce to vic rozmysleni.
Složitost
Martin Mareš
(9. 3. 2008 - 10:34)
Sbalit(2)
Pozor, tohle lineární s délkou vstupu určitě nebude, a to z toho jednoduchého důvodu, že samotný výstup může být větší než lineární. Ovšem lineární s délkou vstupu a výstupu to už samozřejmě je.
Půvabné na tom ale je, že u většiny úloh založených na hledání textu (třeba počítání, kolikrát se které slovo vyskytuje) není potřeba všechny výskyty vyjmenovat, takže jdou řešit lineárně s délkou vstupu.
Půvabné na tom ale je, že u většiny úloh založených na hledání textu (třeba počítání, kolikrát se které slovo vyskytuje) není potřeba všechny výskyty vyjmenovat, takže jdou řešit lineárně s délkou vstupu.
To sem prave myslel tim
qk
(9. 3. 2008 - 20:19)
Sbalit(1)
To sem prave myslel tim rozumnym vystupem ve vicenasobnych vystupnich stavech...neco jako kdyz jeden vystupni tak dej to slovo a kdyz vic, tak dej jedno slovo a potom rekni ze jsou jeste dalsi bez vypsani. Tim padem bude vystup vzdy konstatni vuci poctu slov vstupnich slov, ale ne vuci delce slov vstupni abecedy.
Možná trochu off-topic,
aToM
(28. 3. 2008 - 8:13)
Sbalit(1)
Možná trochu off-topic, ale jen trošičku. Neříkala jsi, že máš ráda obojky?
http://lh4.google.ca/abramsv/R-q9KPXRgtI/AAAAAAAAMrY/WoWqhzhlazw/s1600-h/102534563456.jpg
http://lh4.google.ca/abramsv/R-q9KPXRgtI/AAAAAAAAMrY/WoWqhzhlazw/s1600-h/102534563456.jpg
:-) hezké... Obzvláště
m4r3k
(26. 2. 2008 - 22:16)
Sbalit(1)
:-) hezké... Obzvláště ten první se mi líbil... Ale u toho druhého.... Jaká je ta adresa? :)