Algoritmy

Během studia na MFF občas implementuji (ať už z nutnosti nebo z radosti) nějaký ten algoritmus, o kterém nám vyprávějí na přednáškách. Protože si myslím, že algoritmy v sobě obsahují mnoho překvapivého a krásného, chtěl bych se s vámi o své implementace (a případně vědomosti) podělit. Většina zdrojáků je napsána v Delphi, jenžto je to můj nejoblíbenější programovací jazyk.

Pollardova P-1 metoda faktorizace
Druhý domácí úkol z předmětu Faktorizace velkých čísel. Metoda velmi dobře funguje, pokud má faktorizované číslo N dělitele, který je B-mocný pro nějaké relativně malé B - tedy skládá se pouze z mocnin prvočísel menších než B. Opět si můžete stáhnout pouze implementaci. Bližší vysvětlení snad bude později.

Faktorizace čísel - Pollardova metoda Rho
Jelikož v tomto semestru (léto 2010) navštěvuji předmět Faktorizace velkých čísel, rozhodl jsem se do algoritmické sekce postupně přidávat jednotlivé probírané metody. Jelikož se jejich implementace dává za domácí úkol, nemělo by dojít k tomu, že bych zveřejnil jen tuto Pollardovu metodu a pak by všechno umřelo (jak se stalo třeba u popisu růyných technik hashování). Alespoň implementace zveřejním. Pravděpodobně ale napíšu něco málo i o teoretickém pozadí jednotlivých algoritmů.
Pollardova metoda Rho patří mezi nejjednodušší faktorizační metody a její asymptotická složitost se pohybuje kolem O (N^1/4), kde N je číslo, které chceme rozložit. Je složitější než metoda zkusmého dělení, kterou zná asi každý, ale pokud jste se lehce pohybovali v konečných tělesech či okruzích, nic těžkého na ní neshledáte. Zatím si můžete stáhnout pouze jednoduchou implementaci, která by měla faktorizovat číslo do třech miliard (pro vyšší dochází k přetečení).

Ošklivé B-stromy
Již je to pár měsíců, možná i rok, co jsem se rozhodl implementovat základní variantu B-stromu. Po dvou dnech čtení knížky o algoritmech, programování a nadávání jsem dosáhl svého cíle. Jelikož to ale byla velmi vyčerpávající práce, nikdo do kódu neumístil žádné komentáe a celkový výsledek vypadá velmi ohavně a neoptimalizovaně. Ale fungovat by měl, naprogramoval jsem i randomizovaný test, který mi zatím ještě nespadl. Moje B-stromy tedy neposlouží jako pomůcka učební, k tomuto účelu si radši přečtěte příslušnou kapitolu v knížce Introduction to algorithms. Jinak řečeno: berte to s rezervou.

Binární vyhledávací strom
Tento soubor obsahuje několik rutin pro práci s binárními vyhledávacími stromy (vytvoření, přidání uzlu, smazání uzlu, vyhledávání). Komenáře zde bohužel příliš neuvidíte, alespoň prozatím.

Vyhledávání v textu
Zde naleznete implementaci tří algoritmů pro vyhledávání vzorků v textovém řetězci - jedná se o naivní algoritmus (naivní = nejhorší), algoritmus Rabin-Karp a algoritmus Aho-Corrasickové. Balíček vznikl na základě mé zvídavosti - zajímalo mne, o kolik jsou "nenaivní" algoritmy rychlejší a zjistil jsem, že zrychlení je velmi výrazné. Možná vás překvapí, že ve zdrojácích jsou i komentáře. Důvodem je fakt, že jsem potřeboval nějak získat zápočet z Algoritmů a datových struktur II.

Fronta
Implementace jednoduché fronty pomocí pole. Tuto datovou strukturu využívám v algoritmu Aho-Corrasickové, jehož implementace je obsažena v balíčku výše.

AVL strom
U běžného binárního vyhledávacího stromu se může ve vzácných případech stát, že zdegeneruje až do podoby spojového seznamu a tím pádem ztratí své jedinečné vlastnosti. AVL strom je binární vyhledávací strom, u kterého se to stát prostě nemůže. Jedná se o tzv. samovyvažovací binární vyhledávací strom, který garantuje logaritmickou hloubku za jakýchkoliv okolností. Otázka je, kdy takovouto garanci potřebujeme, protože hloubka obyčejného binárního vyhledávacího stromu je v průměrném případě také logaritmická. Zdrojáky jsou opět bez komentářů a tentokrát i celkem nepřehledné - snažil jsem se totiž AVL strom implementovat na co nejméně obrazovek.