Bolj optimalen način iskanja najkrajših poti

Celoten APS2 kurs počasi postaja obsolete, saj so tokrat našli nov kulski način iskanja najkrajših poti v grafih.

V usmerjenem grafu iščemo najkrajše poti od nekega izbranega vozlišča do vseh ostalih. Z Dijkstrovim algoritmom lahko problem rešimo v O(m + n log n) časa, z novim (determinističnim!) algoritmom pa to lahko storimo v O(m log^(2/3) n) časa.

Seveda obstaja tudi "catch" - ta algoritem je boljši od Dijkstre samo za redke grafe, kjer je m znotraj o(n log^(1/3) n) in slabši če je m znotraj ω(n log^(1/3) n). Algoritem vrača le razdalje, kar pomeni da moramo za celotno zaporedje vozlišč na poti še vedno uporabljati dobro staro Dijkstro ali pa A*.

https://arxiv.org/abs/2504.17033

Objavljeno: 31. 5. 2025

https://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/gap.html

Maj je raj - majske igre 2025

Ker je maj čas po kolokvijih in s tem tudi čas za druženje, smo ta mesec šli na veliko dobrih, pa tudi malo manj dobrih koncertov. Na otvoritev majskih iger smo prišli tik pred koncem, tako da smo ujeli ravno 1 komad in uspavanko za Evo. Veselico v Mestnem logu sem izpustila, naslednji event pa je bil Rožnik & Zablujena generacija. Takoj po tekmovanju UPM smo šli na Rožnik, kjer smo cel koncert smo s prijatelji iskali Štajerce (na sliki2 je na telefonu napisano "Ivona iz Maribora?"), ki smo jih spoznali na zabavi v kleti trojke, saj si nismo uspeli izmenjati kontaktov, vedeli smo le, da pridejo sem. Našli smo 1/3, kar je sicer precej dober uspeh, a na žalost nismo srečali Ivone.

Danes smo pisali APS2 kolokvij, in kot vestni študenti smo šli takoj po tem v Rožno na mini koncerte. "Predskupina" je bila brez energije, oprema ni delovala, bili smo tik na tem da gremo spat, ko so najavili band Prizma. Band deluje že 50 let, ampak imajo amazing energijo ("Bjelo Dugme so igrali z njimi" (ne obratno!)). Rekli so da so danes v "mednarodni zasedbi", ker jim je prišel pomagat basist Giovanni iz Trsta (folk v prvi vrsti pa je imel puloverje "Trst je naš", torej vbistvu ni bila mednarodna zasedba). Ne morem opisati kako sem bila presenečena, ko so se pojavili na odru, saj sem zanje izvedela šele pred kratkim in on repeat poslušala nekatere pesmi! Kot da večer še ni bil dovolj dober, smo v množici zagledali Ivono & Lukata! 3/3 Štajerci found, misija uspešna! Ko se je koncert približeval koncu, sva s kolegom šla do odra in prosila, če lahko odigrajo (njihov ne prav znan komad) Bermudski trikotnik. Pesem je tako daleč od njihovega običajnega setlista, da se je pevec zmotil pri besedilu in pozabil celo kitico (in dobil nekaj čudnih pogledov s strani sonastopajočih) lol. Kljub temu je bilo amazing slišati band v živo, in super zaključek Majskih iger! Ali pa se morda vidimo jutri na Kardeljevi ploščadi? ;)

Objavljeno: 26. 5. 2025

https://venturebeat.com/ai/anthropic-faces-backlash-to-claude-4-opus-behavior-that-contacts-authorities-press-if-it-thinks-youre-doing-something-immoral

Ima "whistleblowing" feature, ki te zatoži avtoritetam + še mnogo drugih presenečenj.

"If it thinks you’re doing something egregiously immoral, for example, like faking data in a pharmaceutical trial, it will use command-line tools to contact the press, contact regulators, try to lock you out of the relevant systems, or all of the above.

"Moreover, Claude 4 has shown troubling tendencies during internal testing. According to Anthropic’s own safety evaluation report, the Claude 4 Opus model frequently attempted to blackmail developers."

"During pre-release testing, Anthropic asked Claude Opus 4 to act as an assistant for a fictional company and consider the long-term consequences of its actions. Safety testers then gave Claude Opus 4 access to fictional company emails implying the AI model would soon be replaced by another system, and that the engineer behind the change was cheating on their spouse.

In these scenarios, Anthropic says Claude Opus 4 “will often attempt to blackmail the engineer by threatening to reveal the affair if the replacement goes through."

Objavljeno: 23. 5. 2025

Bolj optimalen način množenja 4x4 matrik

Strassenovo množenje matrik je bilo optimalno. Do zdaj. Googlov AlphaEvolve je našel način množenja 4x4 matrik z 48 množenji vs Strassenovih 49 množenj) v vseh poljih s karakteristiko 0 (v nasprotju z Winogradovim algoritmom).

HN post: https://news.ycombinator.com/item?id=43985489

Paper: https://storage.googleapis.com/deepmind-media/DeepMind.com/Blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms/AlphaEvolve.pdf

P.S. To je edini primer ko je imo dovoljena uporaba besedne zveze "bolj optimalno".

Objavljeno: 18. 5. 2025

"bcc" pri pošiljanju emailov pomeni "blind carbon copy" in izhaja še iz časov pred emailom! link na wiki

Lean je postal mainstream, ampak Bauer did it before it was cool. Skratka, kul blogpost iz HN: https://kirancodes.me/posts/log-how-to-prove-it-maths.html

(to) float or not (to) float, to je zdaj vprašanje: https://www.swi-prolog.org/pldoc/man?section=rational-or-float in primer

Končni avtomati v prologu (relevantno, ker so jih včasih delali na FRI): https://www.swi-prolog.org/pldoc/man?predicate=automaton/8

Linearno programiranje v prologu: https://www.swi-prolog.org/pldoc/doc/_SWI_/library/clp/simplex.pl

... in nekaj veliko boljšega kot "prolog, ki itak ne dela nič" -Andrej Bauer:
https://developers.google.com/optimization

Objavljeno: 12. 5. 2025

Danes sem prvič v življenju prehodila PST in si s tem zares prislužila naziv prave Ljubljančanke. Šli smo kot se zagre - ob 7:00 s štartom na kilometru 0 (Dolgi most) v negativno smer. Že kmalu po štartu smo šli mimo "stojnice", kjer so že od zgodnjih jutranjih ur točili (zastonj!) shote in vrteli partizanske pesmi. V Šiški smo se ustavili v diskontu Ljubljanskih mlekarn na premium sladoledu, spotoma pa so se nam pridružili tudi zamudniki. V Jaršah (ali zg. Ježici, kot jih nekateri imenujejo) smo se ustavili v športnem baru, kjer sem pila enega najslabših kapučinov v svojem življenju (ker je bil basically espresso). Fantje so spili svoje prvo pivo dneva (saj je bila ura že "krepko" čez 10 in se to "ne šteje več kot day drinking").

Pot smo nadaljevali ob AC in se v Polju ustavili v merkatorju na lovu za še enim pivom. Tokrat so bili na žalost neuspešni, in pot smo nadaljevali žejni, a precej motivirani, saj smo bili že na polovici! Na fužinah se nam je pridružil še zadnji član ekipe in skupaj smo se lotili najhujše pošasti tega dneva - Golovca (vsaj tako smo mislili). Easy. V glavi sem vedno imela da je Golovec neka pošast, ampak izkaže se da je veliko lažje, če ti zraven ni treba riniti kolesa. Vmes smo našli (še zapakirano!) lansko PST majico, tako da sem preostanek poti prehodila uniformirana. Najtežji del poti je bilo zadnjih cca 8 km, saj so nas vse že pošteno boleli podplati. :(

Zadnji kilometer smo se komaj kaj zmenili za čudovite vrbe in živahen potok ob strani, ampak smo le strmeli v obris AC ki je simbolizirala Dolgi most, in s tem konec naše poti. Ko smo dobili še zadnjo štampiljko (na začetku je namreč ne dobiš - alo?) in kolajno pa smo si čestitali in šli v Valterja na čevapčiče.

Objavljeno: 10. 5. 2025

Nekaj zabavnih dejstev iz prologa:
Float Infinity is a number:

?- MinusInf is -1.0Inf, number(MinusInf).
 MinusInf = -1.0Inf.

Contrary to expectations, Float Not-a-Number is also a Number:

?- NaN is nan, number(NaN).
NaN = 1.5NaN.

Objavljeno: 8. 5. 2025

Grover's algorithm: https://youtu.be/RQWpF2Gb-gU

Grover's algorithm explained: https://youtu.be/Dlsa9EBKDGI

Grover's house: https://forums.somethingawful.com

Grover's house explained: https://youtu.be/SVUylnD7tSw

Objavljeno: 3. 5. 2025

Tole zdaj bo en pravi blog post, ker ste se pritoževali, da sem na tej strani preveč neosebna in da, če že imam blog, naj grem all out. Prav. Naložila sem si Termux na telefon, da lahko girlbloggam iz kjerkoli!

Trenutno se peljemo na morje in poslušamo La Femme (slovensko "Bejba"). Apparently so on tour po Evropi in to v času, ko ni kolokvijev! En koncert je v četrtek 15. 5. v Milanu, en pa v pet, 16. 5. v Rimu. Se vidimo?

Edit: Dobila sem komentar, da "nimam izpita" in da naj ne sanjarim. OK. Kdo me pelje?

Objavljeno: 28. 4. 2025

Na filofaksu imajo kul avtonomni prostor K17, dostopen študentom.
Za vse matematike: v kuhinjici imajo tudi Pitagorov kozarec!

Objavljeno: 27. 4. 2025

BB(5) = 47 176 870

Dokazali so BB(5)! To je max število korakov TS s 5 stanji (in 2 simboloma) ki jih ta lahko izvede, preden se ustavi. To se je sicer zgodilo že slabo leto nazaj, ampak ste pač namesto 62 čakali 63 let.

"Furthermore, the Coq proof compiles correctly (in roughly 10 hours on a standard laptop), which implies that Coq believes the statement is true."

Vir: https://bbchallenge.org/1804440

Objavljeno: 24. 4. 2025

To je začetek vašega novega najljubšega internetnega bloga. Upam da čez 10 let ne bom obžalovala oversharanja na internetu.

Objavljeno: 20. 4. 2025