<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Sziasztok!<br><br>Írtam Istvánnak, hogy mi a kettes szint (azt hiszem, elég embert érdekel). Igen részletes válaszát alább olvashatjátok. Megkérdezte, hogy akarunk-e konzultációt, ahol ezeket elmondaná. Mivel a 26-i vizsgán már 12-en vagyunk, előtte összegyűlhet elég érdeklődő. Aki szeretne jönni, az írjon nekem, olyan 5 főtől szólok, hogy legyen konz.<br><br>Ági<br><br>> Date: Mon, 17 May 2010 10:29:23 +0200<br>> From: miklosi@renyi.hu<br>> To: csagnes@math.bme.hu<br>> Subject: Re: bioinformatika vizsga<br>> <br>> Szia Ági!<br>> <br>> Azt gondolom, hogy egy matematikus-hallgatónak három dolgot kell tanulnia:<br>> <br>> - a precíz, szabatos matematika nyelvet<br>> - 'trükköket', bizonyítási eljárásokat<br>> - szemléletet.<br>> <br>> A "definíció-tétel-bizonyítás" nyelvet bizonyára mások <br>> megtaníták/megtanították nektek, a bioinfo kurzus célja részben néhány <br>> trükk tanulása, és leginkább a szemlélet megtanítása.<br>> <br>> Ennek tükrében az elégséges szint eléréséhez szükséges tudásra az <br>> alábbi sillabuszt állítottam össze a vizsgatételekre lebontva:<br>> <br>> 1. Tudni kell a Chomky- hierarchia négy szintjét. Tudni kell, hogy a <br>> felső két szint a 'reménytelenül nehéz' (eldönthetetlen, ill. <br>> NP-teljes), az alsó két szintre az érdekes kérdések döntő többsége <br>> polinom futási időben megoldható. Tudni kell, hogy a regularitás <br>> egyfajta memóriamentességet, illetve véges memóriát jelent, a <br>> környezetfüggetlenséggel pedig elérhető a teszőles mélységű beágyazás <br>> (gondoljatok pl. a zárójeles algebrai kifejezésekre, illetve az <br>> álcsomómentes másodlagos RNS térszerkezetkre).<br>> <br>> 2. Dinamikus programozni tudni kell az elégséges szinthez is, hiszen a <br>> kurzuson ez volt a legalapvetőbb trükk. Így az elégséges szinthez <br>> szükséges, hogy a vizsgázó segítséggel le tudja vezetni legalább a <br>> Viterbi és a Forward algoritmusokat.<br>> <br>> 3. Az EM bizonyítása elég nagy kuruzslás, nem sok szemléletet ad. <br>> Viszont a kettesért is illik tudni a bizonyítás trükkjét, nevezetesen, <br>> hogy feltételes entrópia soha nem negatív, és akkor és csak akkor <br>> nulla, ha a két eloszlás megegyezik. Tudni kell, hogy az EM <br>> gyakorlatban azt jelenti, hogy várható értékeket számolunk, és ezek <br>> alapján módosítjuk a paramétereket. Ki kell mondani a tételt: az EM <br>> algoritmusban a likelihood monoton nő (és értelmezni is kell).<br>> <br>> 4. Definiálni kell a posterior decodingot: annak a valószínűsége, hogy <br>> egy adott karaktert egy adott levezetési szabály szerint vezettünk le, <br>> feltéve, hogy a szekvenciát vezette le a nyelvtan. Tudni kell a <br>> Baum-Welch trükkjét: definíció szerint a levezetéseken összegezzük egy <br>> szabály használat számát szorozva a levezetés valószínűségével, <br>> gyakorlatban a pozíciókon összegezünk, és ez sokkal gyorsabb. (A <br>> kétféleképpen számoljuk össze ugyanazt az egyik leggyakoribb <br>> kombinatorikai trükk, gondoljátok végig, hogy a hol Pólya <br>> enumerációként, hol Burnside-lemmaként emlegetett csoportelméleti <br>> tétel az orbitok számainak összeszámolására is ugyanilyen trükkön <br>> alapul...)<br>> <br>> 5. Tudni kell a Chomsky Normál Formát, és azt, hogy CNF-ben a <br>> levezetések uni-bináris faként reprezentálhatóak (parse tree). <br>> Dinamikus programozni tudni kell, így a vizsgázónak kis segítséggel <br>> össze kell tudni eszkábálnia a CYK és az Inside algoritmust.<br>> <br>> 6. Tudni kell a posterior decodingot és az EM trükköt, ld. 4. tételnél.<br>> <br>> 7. Tudni kell, hogy a szubsztitúciókat időfolytonos Markov modellekkel <br>> modellezzük, és a dinamika felírható autonóm lineáris <br>> differenciálegyenletekként. A fa likelihoodja az, hogy a gyökérre <br>> felteszünk egy random szekvenciát, a stacionárius eloszlásból <br>> kisorsolva, hagyjuk, hogy minden élen függetlenül evolválódjon az <br>> adott szubsztitúciós modell szerint, mi a valószínűsége, hogy az adott <br>> szekvenciákat kapjuk a fa levelein. Aki tud dinamikus programozni, az <br>> kis segítséggel össze tudja lapátolni a Felsenstein algoritmusát.<br>> <br>> 8. Tudni kell a GTJ-féle HMM-et (marha nehéz ám, van három állapot, az <br>> alfa hélix, a béta lemez meg a rendezetlen, és minden össze van kötve <br>> mindennel, irányítottan, hurkok megengedettek), és azt, hogy a <br>> Knudsen-Hein nyelvtan álcsomómentes másodlagos térszerkezeteket vezet <br>> le. Tudni kell, hogy mindkét modell lényege, hogy a szubsztitúciós <br>> folyamat van összekapcsolva a nyelvtannal, így mindkét modell <br>> többszörös szekvenciaillesztéseket vezet le egyetlen szekvencia <br>> helyett. Érteni kell, hogy ez miért jó: a biológia struktúráknak nem <br>> csak a karakterösszetétele, hanem a karakterek megváltozásának a <br>> dinamikája is jellegzetes. Valamint feltesszük, hogy struktúra <br>> konzervatívabb, mint a szekvencia, a szekvencia megváltozhat, anélkül, <br>> hogy a struktúra megváltozna.<br>> <br>> 9. Tudni, kell, hogy az álcsomómentes térszerkezet felbontható <br>> körökre, és a térszerkezet energiája a körök energiáinak az összege. <br>> Tudni kell, hogy mi a partíciófüggvény, és hogy a partíciófüggvény <br>> számolása során olyan dinamikus programozási rekurzió kell, amelyben <br>> minden térszerkezetet pontosan egyszer veszünk figyelembe. Tudni kell <br>> olyan, középiskolában tanult algebrai azonosságot, hogy exp(a+b)= <br>> exp(a)exp(b). Valamint tudni kell dinamikus programozni, ezek alapján <br>> segítséggel a Zuker-Sankoff és a partíciófüggvény számoló algoritmus <br>> egyszerűbb részleteit össze kell tudni lapátolni.<br>> <br>> 10. Érteni kell, hogy a Markov modellekre hogyan írjuk fel a <br>> differenciálegyenleteket, ez alapján a diffegyenletrendszer felírása <br>> nem lehet nehéz. A trükk az, hogy bevezetünk egy generátorváltozót, a <br>> generátorváltozó megfelelő hatványával szorozzuk meg az egyenleteket <br>> és ezeket összeadjuk. Az egyenletben szereplő n-eket a <br>> generátorfüggvény generátorváltozó szerinti parciális deriváltjával <br>> hozzuk létre, így írjuk át a differenciálegyenletrendszert egy <br>> parciális differenciálegyenletbe. A kettesért nem kell tudni megoldani <br>> a parcdiffet, felírni a partikuláris megoldást, és azt Taylor-sorba <br>> fejtve kiszámolni az eredeti változókra a megoldást, de tudni kell, <br>> hogy ez a megoldás menete.<br>> <br>> 11. Tudni kell, hogy miben különbözik a TKF91 és TKF92 modell. Tudni <br>> kell, hogy mindkettő ekvivalens egy-egy páros rejtett Markov modellel. <br>> Tudni kell, hogy mi a páros rejtett Markov modell, és mit jelent az <br>> ekvivalencia (létezik valószínűségtartó bijekció a <br>> szekvenciaillesztések és levezetések között).<br>> <br>> 12. Tudni kell a Metropolis-Hastings algoritmust.<br>> <br>> 13. A SLEM definíciója, Lazy Markov chain. Ki kell tudni mondani a két <br>> tételt a SLEM-ről és az epszilonos relaxációs időről. Ki kell tudni <br>> mondani a multicommodity flow-s tételt és a Cheeger <br>> egyenlőtlenségeket. Ez utóbbit értelmezni is kell: egy Markov lánc <br>> akkor és csak akkor konvergál gyorsan, ha nincs benne 'üvegnyak'. Az <br>> üvegnyak lehet topologikus is (kevés él van a két részhalmaz között) <br>> és lehet valószínűségi is (az élek valószínűségei túl kicsik).<br>> <br>> 14. Tudni kell a Cheeger egyenlőtlenséget. A poset linearizációk <br>> definíciója. A poset politóp definíciója. Érteni kell a bizonyítás <br>> lényegét: konvex testben nem lehet üvegnyak.<br>> <br>> 15. #P, #P-teljes, FPRAS és FPAUS definíciói. 'Integetés' szintjén <br>> tudni kell az önhasonló leszámolási problémákat, és ki kell tudni <br>> mondani a tételt az FPRAS és FPAUS között.<br>> <br>> Rebesgettetek valamit konzultációról is. Egy konzultáción pl. <br>> végigmehetünk ezen a sillabuszon mégegyszer.<br>> <br>> Üdv,<br>> István<br>> <br>> Quoting Cseh Ágnes <csagnes@math.bme.hu>:<br>> <br>> ><br>> > Kedves István!<br>> ><br>> > Néhányak kérésének eleget téve szeretném megkérdezni, hogy van-e a <br>> > vizsgán kijelölt elégséges szint. Kérlek, ne vedd zokon a <br>> > kérdésemet, természetesen nem mindenki a kettesre hajt, de van, aki <br>> > nem lát esélyt többre (többségünk ráadásul most végez), és szeretné <br>> > tudni, hogy ehhez pontosan milyen felkészültségre van szüksége. Ha <br>> > megengeded, a válaszodat továbbítom az évfolyamlistára.<br>> ><br>> > Köszönettel,<br>> ><br>> > Cseh Ági<br><br> <br /><hr />Hotmail: Megbízható e-mail szolgáltatás a Microsoft hatékony LEVÉLSZEMÉT elleni védelmének használatával. <a href='https://signup.live.com/signup.aspx?id=60969' target='_new'>Regisztráljon most!</a></body>
</html>