20.500.12556/RUL-162179 Saddle point detection algorithms in matrices Iskanje sedla matrike This diploma thesis addresses the problem of finding saddle points in matrices, a critical concept in various applications of linear algebra and optimization techniques. The thesis begins with the mathematical definition of saddle points, followed by a comprehensive review of existing methods for their detection, including the algorithms proposed by Donald Knuth and more recent advancements. A significant focus is given to the analysis of the article "Finding a Saddle Point Faster than Sorting", which presents a crucial improvement in the time complexity of saddle point detection. The article introduces a new algorithm with a complexity of $O(n \log^* n) \subset o(n \log n)$, representing a substantial advancement over previous methods. Experimental analysis on various matrix types demonstrates that this new approach enables faster and more efficient detection of saddle points with reduced computational requirements. 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. saddle points matrices linear algebra optimization techniques algorithm sedlo matrike optimizacijske tehnike algoritem true false false Angleški jezik Slovenski jezik Diplomsko delo/naloga 2024-09-19 12:20:01 2024-09-19 12:20:07 2024-11-06 13:48:29 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37305 213915139 Danevska_Ana_-_Iskanje_sedla_matrike.pdf Danevska_Ana_-_Iskanje_sedla_matrike.pdf 1 E72058C4D86F9B831AE1290689217CCA a72f9df912fc12a6d26cffd25f05002c419feb8ea1355909108a3f410df4ca33 a28e1983-7670-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=191351 Fakulteta za računalništvo in informatiko 0 0 0