| Meno: | András
|
|---|
| Priezvisko: | Varga
|
|---|
| Názov: | Rekurentné postupnosti
|
|---|
| Vedúci: | RNDr. Martin Sleziak, PhD.
|
|---|
| Rok: | 2011
|
|---|
| Kľúčové slová: | Fibonacciho postupnosť, Rekurentné postupnosti druhého rádu, Výpočet n-tého člena postupnosti, Efektívne algoritmy, Dynamické programovanie, Výpočet celočíselnej druhej odmocniny pomocou binárneho vyhľadávania, Umocňovanie matíc, Príslušnosť k rekurentnej postupnosti
|
|---|
| Abstrakt: | Hlavným cieľom práce je vytvorenie, implementácia a dokázanie korektnosti rýchlych algoritmov pracujúcich na rekurentných postupnostiach druhého rádu. Základným problémom je výpočet n-tého
člena takýchto postupnosti, potom zistenie či dané číslo je členom danej postupnosti. Pri skúmaní týchto problémov sme narazili na problém umocňovania matíc.
V práci sa teda popisuje aj algoritmus na riešenie problému umocňovania matíc, jeho uvedenie pomôže jednoduchšie pochopiť celú tematiku. Uvedené problémy sa dajú riešiť v čase O(n). V tejto práci sme sa snažili
vytvoriť také algoritmy, ktoré počas ich behu používajú O(log n) aritmetických operácií. Súčasťou práce je aj dôkaz korektnosti algoritmov ako aj popis a dôkaz všetkých potrebných matematických tvrdení.
Implementácia týchto algoritmov slúži ako skúška ich korektnosti. Samotná implementácia algoritmov dáva možnosť aj reálne porovnávať efektívnosť jednotlivých algoritmov s efektívnosťou už existujúcich algoritmov.
|
|---|