|
|
Procházky v grafech a genetické algoritmy
Szépe, Peter ; Pangrác, Ondřej (vedoucí práce) ; Bajer, Lukáš (oponent)
Název práce: Procházky v grafech a genetické algoritmy Autor:Peter Sépe Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalárské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: pangrac@kam.mff.cuni.cz Abstrakt: Řešíme optimalizační úlohy nalezení maximálního tahu mezi dvěma vrcholy v orintovaném grafu s omezením na délku tohoto tahu. Je dán orientovaný graf, startovní a cílový vrchol, délková funkce na hranách a váhová funkce na vrcholech grafu a parametr omezení délky cesty L. Úkolem je najít tah ze startovního do cílového vrcholu celkové délky nejvýše L maximalizující součet vah navštívených vrcholů (každý se započítává pouze jednou).Tato úloha je NP-těžká a ani aproximační algoritmy nedávají příliš dobré výsledky. Proto je třeba pro praktické aplikace použít heuristické přístupy. Klícová slova: optimalizace, evolučné algoritmy, genetické algoritmy, grafy, procházky v grafech
|
|
|
Vícenásobná podobnost RNA struktur
Szépe, Peter ; Hoksza, David (vedoucí práce) ; Novák, Jiří (oponent)
Práce vychází z algoritmu SETTER (SEcondary sTructure-based TERtiary Structure Similarity Algorithm), což je určen k porovnání 3D struktur RNA. SETTER v původní verzi umí porovnávat pouze dvojice RNA, nicméně mnoho reálných aplikací vyžaduje přiřazení podobnosti n-tici RNA struktur. Hlavní myšlenkou MultiSETTERu je dobře známý postup používaná pro vícenásobné sekvenční zarovnání, což je založen na metodě Neigbour-Joining - metoda pro kalkulaci taxonomického stromu ze vzdálenosti mezi taxony - a na zarovnání dvojic. V každém kroku zarovnáme nejbližší dvojici podle taxonomického stromu. Pro dosažení dobrého výsledku bylo nezbytné vymyslet metodu, která vytvoří takzvanou průměrnou RNA strukturu z dvou RNA, nesoucí v sobě charakteristické vlastnosti obě struktur.
|
|
|
Procházky v grafech a genetické algoritmy
Szépe, Peter ; Bajer, Lukáš (oponent) ; Pangrác, Ondřej (vedoucí práce)
Název práce: Procházky v grafech a genetické algoritmy Autor:Peter Sépe Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalárské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: pangrac@kam.mff.cuni.cz Abstrakt: Řešíme optimalizační úlohy nalezení maximálního tahu mezi dvěma vrcholy v orintovaném grafu s omezením na délku tohoto tahu. Je dán orientovaný graf, startovní a cílový vrchol, délková funkce na hranách a váhová funkce na vrcholech grafu a parametr omezení délky cesty L. Úkolem je najít tah ze startovního do cílového vrcholu celkové délky nejvýše L maximalizující součet vah navštívených vrcholů (každý se započítává pouze jednou).Tato úloha je NP-těžká a ani aproximační algoritmy nedávají příliš dobré výsledky. Proto je třeba pro praktické aplikace použít heuristické přístupy. Klícová slova: optimalizace, evolučné algoritmy, genetické algoritmy, grafy, procházky v grafech
|
host ::
RSS.