Diplomska naloga obravnava problem iskanja sedla v matrikah, ki so ključne v različnih aplikacijah linearne algebre in optimizacijskih tehnik. V nalogi je najprej predstavljena matematična definicija sedlastih točk, nato pa sledi podroben pregled obstoječih metod za njihovo iskanje, vključno z algoritmi Donalda Knutha ter novejšimi izboljšavami. Poseben poudarek je namenjen analizi članka "Finding a Saddle Point Faster than Sorting", ki predstavlja pomemben napredek v časovni kompleksnosti iskanja sedlastih točk. Članek uvaja nov algoritem s kompleksnostjo $O(n \log^* n) \subset o(n \log n)$, kar je bistveno izboljšanje v primerjavi z dosedanjimi metodami. Eksperimentalna analiza preučevanih algoritmov na različnih vrstah matrik je pokazala, da nov pristop omogoča hitrejše in učinkovitejše iskanje sedla z nižjimi računskimi zahtevami.
|
