Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Beharangozó: Rónyai Lajos, Tablók - algoritmusok, növő sorozatok, genetikai sorozatok

Rónyai Lajos

http://www.sztaki.hu/~ronyai/

Tablók - algoritmusok, növő sorozatok, genetikai sorozatok

A 2006. március 7-ei előadás előzetese

Keressünk az alábbi számsorozatban minél hosszabb növekvő részsorozatot!

3, 7, 21, 4, 6, 16, 12, 33.

A 3, 7, 16, 33 egy növekvő részsorozat, de van-e nála hosszabb? Az előadáson az ilyen feladatok gyors megoldásával, és az erre szolgáló módszerek egy nevezetes biológiai alkalmazásával ismerkedünk meg.

A gyors algoritmushoz a tablókon keresztül vezet az út. A tabló olyan egészekből álló táblázat, amelyben a sorok hossza nem növekszik, ahogy lefelé megyünk. A táblázatba írt számok pedig jobbra vagy lefelé haladva növekednek. Íme két példa:

A tablók meghatározó szerepet játszanak az algebrai kombinatorikában és annak alkalmazásaiban. Az előadáson bemutatjuk a Robinson--Schensted-algoritmust, amivel egy tablóba új egészet illeszthetünk be, és ezzel eggyel több dobozból álló tablót kaphatunk.

A módszer segítségével egyfelől érdekes azonosságok nyerhetők. Másfelől gyors algoritmust kapunk a leghosszabb növő részsorozatok feladatára. Kitérünk arra is, hogy az utóbbi módszert miként alkalmazzák a genetikai kódsorozatok szerkezetének feltárása során.

Előadások, 2005/2006. tanév
Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.