abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×

    dnes 19:46 | Zajímavý software
    Projekt llama-modchip je sada úprav a nástrojů pro llama.cpp, které mají umožnit spouštět rozsáhlé jazykové modely lokálně na běžných domácích počítačích, a to bez použití grafické karty. Například čínský model DeepSeek-V4-Flash o 284 miliardách parametrů se díky kompresi vleze do 64GB RAM. Háček je v agresivní kvantizaci (v uvedeném příkladu průměrně 1,71 bitu na parametr), která výrazně snižuje kvalitu výstupů. Zdrojové kódy projektu jsou dostupné pod licencí Apache‑2.0.
    👻 | Komentářů: 0
    dnes 19:45 | IT novinky

    Turecko-americká vycházející matematická hvězda Levent Alpöge ze společnosti Anthropic vyvolal pozdvižení oznámením (PDF), že s pomocí superinteligence Claude od Antropicu dokázal vyřešit jeden ze sedmi největších matematických problémů tisíciletí, slavnou Riemannovu hypotézu (prvočísla se mezi čísly objevují zdánlivě nepravidelně, hypotéza tvrdí, že za jejich rozmístěním je určitý řád). Svůj důkaz uvolnil jako open-source

    … více »
    👻 | Komentářů: 0
    20.11. 23:36 | Nová verze
    Student kyberbezpečnosti na SSPŠ vydal verzi 1.0.1 distribuce LuxOS, která stojí na Arch Linuxu a pod povrchem používá Xfce upravené do podoby macOS. … více »
    Luxopes | Komentářů: 10
    20.11. 21:02 | Zajímavý software
    Open source projekt BUI zpřístupňuje legendární, bleskurychlé a optimalizované uživatelské rozhraní 3D editoru Blender coby samostatnou GUI knihovnu pro jazyky Python, Rust, JavaScript a C/C++, případně pro knihovnu Dear ImGui. … více »
    👻 | Komentářů: 0
    20.11. 20:31 | Zajímavý software
    Vývoj je pomalý, ale desktopové prostředí MATE je stále živé. Podľa správy z OSNews.com tu máme nový správca okien pre MATE. Viac informácií nájdeš na GitHub stránke Polo od autora KeremSoke. Je to naozaj skvelá správa pre používateľov MATE a aj vybrané meno Polo podľa Marca Pola je cool.
    lukve | Komentářů: 0
    20.11. 08:57 | Komunita

    Skotský vývojář Mike Lothian pozastavil vývoj svého otevřeného ovladače Vino (nedostupné) pro dokovací stanice DisplayLink poté, co mu Synaptics v reakci na žádost o pomoc pohrozil žalobou kvůli údajnému porušování patentů. Firma nejprve předložila seznam 125 patentů bez specifikace, které konkrétně měl ovladač porušovat, a následně požadovala 25 tisíc dolarů za náklady na jejich přiřazení ke kódu s hrozbou, že se tato částka bude

    … více »
    👻 | Komentářů: 10
    19.11. 20:14 | Zajímavý software
    RunWisp je jedna Go binárka, ktorá spúšťa crony aj udržiava dlho bežiace procesy z jedného TOML súboru. Pri každom behu si uloží logy, exit code, trvanie, využitie CPU a RAM a všetko sa dá pozrieť vo webovom rozhraní alebo v TUI už počas behu. Vie poslať notifikácie na Slack, Discord, Telegram, na telefón atď. Licencia GPL-3.0, funguje na Linuxe, macOS aj WSL.
    Riki | Komentářů: 4
    19.11. 20:12 | Zajímavý software
    BenchUp (původně KetchUp) je open-source alternativa k proprietárnímu software SketchUp, zaměřená především na 3D návrh nábytku a práci se dřevem. Tento editor funguje v prohlížeči i jako desktopová aplikace pro Linux, Windows a macOS. Zdrojový kód projektu (převážně Rust) je dostupný na GitHubu, pod licencí MIT.
    👻 | Komentářů: 12
    19.11. 20:09 | Pozvánky
    Pražský MobileLinux Hackday je zpět, tentokrát už s devátým pokračováním! Už tento pátek 20. listopadu od 10:00 se opět sejdeme v Praze v SUSE. Přijďte si popovídat o Linuxu na telefonech, poslechnout si pár krátkých přednášek a hlavně si společně něco rozběhat, opravit nebo naprogramovat.… více »
    lkocman | Komentářů: 0
    19.11. 20:04 | Humor
    Po serii zero-day zranitelností vyšla nejfatálnější zranitelnost všech dob s CVSS 10.0. Autoři nálezu jí pojmenovali sleep2shell a týká se všech systémů.
    Max | Komentářů: 16
    Které desktopové prostředí na Linuxu používáte?
     (8%)
     (7%)
     (4%)
     (21%)
     (30%)
     (9%)
     (5%)
     (2%)
     (14%)
     (20%)
    Celkem 3086 hlasů
     Komentářů: 36, poslední 11.11. 22:38
    Rozcestník


    Vložit další komentář
    29.5.2006 06:34 mivrap | blog: Mirkovo
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    a co je to za slovo, to "pokuď" ?
    29.5.2006 09:07 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

    Ty asi nebudeš Pražák, co?! ;-)

    Každý má právo na můj názor!
    29.5.2006 07:27 lukipuki | skóre: 4 | blog: | Štokholm
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Tvoj algoritmus má zložitosť O(|H| log |U^2|), čo je O(H log |U|). Totiž log(x^2)=2log(x).

    Tvoje riešenie je korektné. Mimochodom, vlastnosť visited musíš mať implementovanú aj v pôvodnej verzii algoritmu.
    /dev/null: Permission denied
    29.5.2006 09:07 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Mimochodom, vlastnosť visited musíš mať implementovanú aj v pôvodnej verzii algoritmu.

    Nemusím. Ne-mu-sím! ;-) Standartně jsou všechny vrcholy zařazeny do fronty při inicializaci algoritmu a jejich náležení/nenáležení frontě již samo o sobě udává, zda-li byl vrchol již "objeven" či nikoliv.

    Každý má právo na můj názor!
    29.5.2006 08:27 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    1) Dijkstrův algoritmus lze aplikovat na grafy s nezáporným ohodnocením hran, což je dost důležité zmínit.

    2) Časová složitost v případě použití binární haldy je obecně O(|V+E|lg|V|), což je O(|E|lg|V|), když jsou všechny vrcholy dosažitelné z výchozího vrcholu.

    3) Ve skutečnosti můžeme dosáhnout složitosti O(|V|lg|V|+|E|) použitím Fibonacciho haldy (lepší amortizovaná složitost). Ale tohle nám asi neříkali ani na matfyzu;-).
    Math, as Barbie says, is hard.
    29.5.2006 09:12 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

    Tohle jsou samozřejmě další dobře známé vlastnosti Dijkstrova algoritmu (dokonce i ta možnost využití Fibonacciho haldy se udává snad v každém popisu algoritmu), některé vlastnosti jsem dokonce zmínil v textu, ale oč tu běží je čistě implementační záležitost a vlastnosti "přiohnutého" algoritmu.

    Každý má právo na můj názor!
    29.5.2006 09:19 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Zajímavé. V textu tvrdíš, že se moc neví, že při "implementaci" s použitím binární haldy je potřeba měnit prioritu uvnitř haldy. Mohl bys tedy ukázat pseudokód (rozuměj popis algoritmu), který by bez této "funkce" fungoval? A pokud ne, jak je možné, že se o tom "moc neví":-)?
    Math, as Barbie says, is hard.
    29.5.2006 09:35 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Mohl bys tedy ukázat pseudokód (rozuměj popis algoritmu), který by bez této "funkce" fungoval?

    Uááá. Agoritmus, který tuto funkci nepotřebuje je právě ten ukázkový kód. O něm to celý je!

    A pokud ne, jak je možné, že se o tom "moc neví"?

    To že se o nutnosti této funkce použité fronty "moc neví" je myšleno tak, že si to člověk naplno uvědomí, až když musí algoritmus implementovat, protože takovou frontu obyčejně nemá k dispozici. Rozhodně to ale neni nějaký zajímavý a málo probádaný teoretický aspekt Dijkstrova algoritmu jako takového.

    Každý má právo na můj názor!
    29.5.2006 09:47 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    No vidíš;-). Já to nedočetl, protože nechápu, proč bych měl algoritmus zpomalit kvůli tomu, že knihovna neobsahuje triviální funkci nad binární haldou. Klíčové slovo je to _nechápu_:-). Tak se nezlob...
    Math, as Barbie says, is hard.
    29.5.2006 13:10 Honza Král | skóre: 3 | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Ale tohle nám asi neříkali ani na matfyzu;-).
    Predmet slozitost, fibbonaciho haldy i jejich aplikace v Dijstrove algoritmu se probiraly... ;)
    29.5.2006 16:16 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Ještě pořád je to povinné? Karolinky hledat nebudu;-)... Co mě na matfyzu vždycky pobaví je předmět, který probere látku vcelku povrchně, ale nakousne toho co nejvíc. Za pár semestrů ho totiž v rámci takřka stejného sylabu rozšíří další. Viz třeba ADS - Složitost. Jinak co se algoritmů týče, tak si člověk (nejen) na matfyzu vystačí s Introduction to algorithms z MIT. Jen je třeba dávat pozor v předmětech, kde se pracuje s B-stromy - zavádějí je tam trochu jinak (ve výsledku je to samozřejmě stejné) a algoritmy operací jsou taky trochu jiné (ve srovnání s evergreenem od prof. Pokorného či zmíněných ADS).
    Math, as Barbie says, is hard.
    elviin avatar 29.5.2006 09:09 elviin | skóre: 29 | blog: elviin | Plzeň-Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Ja to nikdy nepouzil, ale mozna se ti to Martine hodi. Je to funkce z boostu:
    dijkstra_shortest_paths
    29.5.2006 11:44 Kníže Ignor | skóre: 19 | blog: stoupa
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Podle mě to korektní není, protože to nezajišťuje, že "nevisited" vrcholy budou v té frontě uspořádány podle odhadu délky nejkratší cesty.

    Vezměme si takovýto podgraf nějakého grafu
    B____C
     \  /
      \/
      A
      |
      |
      D
    
    délky hrany tyto d(A,D)=3, d(A,C)=4, d(A,B)=1, d(B,C)=1

    začneme v A, do fronty přijde B(1), D(3), C(4); v dalším kroku teda zkoumám B, C dám nový odhad 2

    takže fronta "nevisited" vrcholů je D(3), C(2)

    což by asi být nemělo, ne?

    (kdyby z D vycházela nějaká hrana a na ní byl nalepenej nějakej graf H, přidali bychom ještě hranu CD s ohodnocením třeba 0.5, tak se správně nenajde nejkratší cesta do H přes AB, BC, CD, ..)
    Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
    29.5.2006 15:09 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

    Možná to neni z popisu zcela zřejmý, ale použitá fronta je samozřejmě stále prioritní. Situace, že by v ní byla posloupnost D(3), C(2) tak nemůže nastat.

    Prošel jsem si tebou uváděnej příklad, a nevidim v tom problém, na danym grafu algoritmus funguje korektně.

    Každý má právo na můj názor!
    29.5.2006 16:44 Kníže Ignor | skóre: 19 | blog: stoupa
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Možná to neni z popisu zcela zřejmý, ale použitá fronta je samozřejmě stále prioritní. Situace, že by v ní byla posloupnost D(3), C(2) tak nemůže nastat.
    Tak to jsem teda nepochopil. Píšeš, že "Prioritní fronta ze standartní šablonové knihovny STL totiž touto vlastností neoplývá...", kde "touto vlastností" sem pochopil jako změna priority. Tedy jsem se domníval, že fronta 3, 4, 5 se nepřeuspořádá, pokud změním prioritu u druhého prvku na 2, tedy bude v podobě 3, 2, 5. Takhle to teda není? Pokud ne, tak jsem nějak nepochopil celý blogpost.

    Jinak na tom "nakresleném grafu" by to neselhalo, domnívám se, že by to selhalo až na grafu, kde z D vede nějaká hrana a přidáme ještě hranu CD váhy 0.5 (což jsem naznačil v minulém příspěvku v závorce).
    Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
    29.5.2006 17:08 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Tak to jsem teda nepochopil. Píšeš, že "Prioritní fronta ze standartní šablonové knihovny STL totiž touto vlastností neoplývá...", kde "touto vlastností" sem pochopil jako změna priority. Tedy jsem se domníval, že fronta 3, 4, 5 se nepřeuspořádá, pokud změním prioritu u druhého prvku na 2, tedy bude v podobě 3, 2, 5. Takhle to teda není? Pokud ne, tak jsem nějak nepochopil celý blogpost.

    Změnu priority fronta z STL neumožňuje, proto se taky místo změny priority přidává uzel do fronty znovu, čímž se samozřejmě zařadí na správné místo. Vrchol tedy může být ve frontě několikrát, přičemž jen jeho první výskyt je "platný".

    Jinak na tom "nakresleném grafu" by to neselhalo, domnívám se, že by to selhalo až na grafu, kde z D vede nějaká hrana a přidáme ještě hranu CD váhy 0.5 (což jsem naznačil v minulém příspěvku v závorce).

    Uvažoval jsem samozřejmě ten rozšířený graf (s hranou CD)

    Každý má právo na můj názor!
    29.5.2006 17:17 Kníže Ignor | skóre: 19 | blog: stoupa
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Nevšiml jsem si toho queue.push(neighbour); Prostě po změně odhadu vzdálenosti sousedů už jsem zvyklý, že dál nic není :-)

    Takže sorry, podcenil jsem tě :-)
    Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
    29.5.2006 16:49 Kníže Ignor | skóre: 19 | blog: stoupa
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    BTW Nechceš někam dát kompletní zdroják?
    Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
    29.5.2006 16:55 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    Zdroják být ani nemusí - stačí důkaz správnosti algoritmu.
    Math, as Barbie says, is hard.
    29.5.2006 17:01 Kníže Ignor | skóre: 19 | blog: stoupa
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry
    No já bych si spíš chtěl vyzkoušet, jak teda vlastně funguje ta fronta...
    Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
    29.5.2006 18:03 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

    A Kefalín, čo Vy si predstavujete pod takým "důkaz správnosti algoritmu"?! ;-)

    Obávám se, že ten už si budeš muset udělat sám. Nejsem matfyzák, takže se do podobných "experimentů" pouštím jen v případech krajní nouze, což zrovna tenhle není...

    Každý má právo na můj názor!
    29.5.2006 17:51 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

    Tady ho máš, ten "majstrštyk" ;-)

    http://tumic.wz.cz/fel/#36CPP

    Každý má právo na můj názor!
    29.5.2006 22:11 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

    Slíbil jsem, že zde vyslovím můj názor na složitost takto modifikovaného algoritmu, která je IMHO (a už to tady zaznělo stále O(|H|log|U|).

    Jediné co se mění je počet prvků(uzlů) v prioritní frontě, který oproti "originálnímu" algoritmu může být až |U|^2. Nicméně proto, že log(|U|^2) = 2log|U| = O(log|U|), zůstává asymptotická časová složitost algoritmu O(|H|log|U|). Skutečná složitost nicméně samozřejmě naroste, ale na "běžných" grafech IMHO nijak výrazně.

    Nějaké námitky?

    Každý má právo na můj názor!
    29.5.2006 23:43 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Noční můra Edsgera Dijkstry

    Tak si odpovím sám. Zas tak růžový to asi přece jenom nebude... "Hlavní" cyklus se může provést až |H|*|U|, zařazení do fronty pak má složitost log(|H|*|U|). Celková asymptotická složitost řešení tedy spíše bude O(|H|*|U| + log(|H|*|U|)) = O(|H|*|U|), tedy horší, než u "originálu".

    Každý má právo na můj názor!

    Založit nové vlákno • Nahoru

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.