[Mat07] FW: bioinformatika vizsga

2010. Május. 17., H, 10:49:24 CEST

Sziasztok!

Í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.

Ági

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

_________________________________________________________________
Hotmail: Megbízható e-mail szolgáltatás a Microsoft hatékony LEVÉLSZEMÉT elleni védelmének használatával.
https://signup.live.com/signup.aspx?id=60969
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: http://lists.math.bme.hu/pipermail/mat07/attachments/20100517/79bd2e2b/attachment.htm 