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 16:11 | Nová verze

    Bylo vydáno openSUSE Leap 16 (cs). Ve výchozím nastavení přichází s vypnutou 32bitovou (ia32) podporou. Uživatelům však poskytuje možnost ji ručně povolit a užívat si tak hraní her ve Steamu, který stále závisí na 32bitových knihovnách. Změnily se požadavky na hardware. Leap 16 nyní vyžaduje jako minimální úroveň architektury procesoru x86-64-v2, což obecně znamená procesory zakoupené v roce 2008 nebo později. Uživatelé se starším hardwarem mohou migrovat na Slowroll nebo Tumbleweed.

    Ladislav Hagara | Komentářů: 0
    dnes 16:00 | IT novinky

    Ministerstvo průmyslu a obchodu (MPO) ve spolupráci s Národní rozvojovou investiční (NRI) připravuje nový investiční nástroj zaměřený na podporu špičkových technologií – DeepTech fond. Jeho cílem je posílit inovační ekosystém české ekonomiky, rozvíjet projekty s vysokou přidanou hodnotou, podpořit vznik nových technologických lídrů a postupně zařadit Českou republiku mezi země s nejvyspělejší technologickou základnou.

    … více »
    Ladislav Hagara | Komentářů: 0
    dnes 12:55 | Nová verze

    Radicle byl vydán ve verzi 1.5.0 s kódovým jménem Hibiscus. Jedná se o distribuovanou alternativu k softwarům pro spolupráci jako např. GitLab.

    Ladislav Hagara | Komentářů: 2
    dnes 03:22 | IT novinky

    Společnost OpenAI představila text-to-video AI model Sora 2 pro generování realistických videí z textového popisu. Přesnější, realističtější a lépe ovladatelný než předchozí modely. Nabízí také synchronizované dialogy a zvukové efekty.

    Ladislav Hagara | Komentářů: 4
    včera 23:11 | Nová verze

    UBports, nadace a komunita kolem Ubuntu pro telefony a tablety Ubuntu Touch, vydala Ubuntu Touch 24.04-1.0, tj. první stabilní vydání založené na Ubuntu 24.04 LTS.

    Ladislav Hagara | Komentářů: 0
    včera 21:00 | Komunita

    Rakouská armáda přechází na LibreOffice. Ne kvůli licencím (16 000 počítačů). Hlavním důvodem je digitální suverenita. Prezentace v pdf z LibreOffice Conference 2025.

    Ladislav Hagara | Komentářů: 23
    včera 12:44 | Bezpečnostní upozornění

    Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) upozorňuje na sérii kritických zranitelností v Cisco Adaptive Security Appliance (ASA) a Firepower Threat Defense (FTD) a Cisco IOS, CVE-2025-20333, CVE-2025-20363 a CVE-2025-20362. Zneužití těchto zranitelností může umožnit vzdálenému neautentizovanému útočníkovi spustit libovolný kód (RCE). Společnost Cisco uvedla, že si je vědoma aktivního zneužívání těchto zranitelností.

    Ladislav Hagara | Komentářů: 16
    včera 12:11 | IT novinky

    Ochrana uživatelů a zároveň příznivé podmínky pro rozvoj umělé inteligence (AI). Ministerstvo průmyslu a obchodu (MPO) připravilo minimalistický návrh implementace evropského nařízení o umělé inteligenci, tzv. AI aktu. Český zákon zajišťuje ochranu občanům a bezpečné používání AI, ale zároveň vytváří pro-inovační prostředí, ve kterém se může AI naplno rozvíjet, firmy mohou využít jeho potenciál a nebudou zatíženy zbytečnou administrativou. Návrh je nyní v meziresortním připomínkovém řízení.

    Ladislav Hagara | Komentářů: 8
    včera 05:11 | Komunita

    Dle plánu Linus Torvalds odstranil souborový systém bcachefs z mainline Linuxu. Tvůrce bcachefs Kent Overstreet na Patreonu informuje, že bcachefs je nově distribuován jako DKMS modul.

    Ladislav Hagara | Komentářů: 2
    29.9. 17:44 | IT novinky

    PIF, Silver Lake a Affinity Partners kupují videoherní společnost Electronic Arts (EA) za 55 miliard dolarů (1,14 bilionu korun).

    Ladislav Hagara | Komentářů: 2
    Jaké řešení používáte k vývoji / práci?
     (39%)
     (48%)
     (12%)
     (14%)
     (17%)
     (14%)
     (18%)
     (14%)
     (14%)
    Celkem 146 hlasů
     Komentářů: 9, poslední 24.9. 17:28
    Rozcestník


    Vložit další komentář
    20.12.2007 00:55 Martin | skóre: 10 | blog: Nádraží Perdido
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Pole N čísel můžeš na místě sestavit do binární haldy (to jde v čase O(N)), pak z ní K-krát odebrat maximum (pro odebrání maxima potřebuješ čas O(log(N)), takže pro nalezení K-tého největšího prvku potřebuješ čas O(N + K * log(N)).
    20.12.2007 03:26 Kyosuke | skóre: 28 | blog: nalady_v_modre
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    +1 :-) A Freshmouse by si konečně mohl koupit ty "správný amíky". :-) (A já bych si je měl přečíst. ;-))
    freshmouse avatar 20.12.2007 08:02 freshmouse | skóre: 42 | blog: Bruno Banány
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Jaký správný Amíky?

    (Mimochodem, včera jsem si koupil k Vánocům Návrhový vzory od Pecinovskýho, jak jste mi je minule někdo doporučoval. Babička měla v knihkupectví jistou slevu, a tak mi řekla, ať si vyberu nějakou knížku. Já bral tuhle. Mimochodem, ta knížka je asi dost horký zboží, už ji nikde moc nemaj. Včera jsem před spaním dal tak sto stránek, a musím říct, že se mi to líbí. Je to psaný hodně zajímavou formou. Rozhodně jsem její koupí neprohloupil.)
    bazil avatar 20.12.2007 03:38 bazil | skóre: 33 | blog: sluje | Miroslav
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    udělal bych to ještě jinak, hodil bych pole do binárního vyhledávacího stromu (časová náročnost O(N)), při tom bych si zapamatoval, kam se mě ukládá nějvětší číslo pole (tohle nezvýší časovou náročnost ne?), nastavil bych si kořen na nejvyšší číslo (pokud by strom měl obousměrné ukazatele(jooo jak ukazatele udělat v javě, mno nic no), tak je časová náročnost teoreticky 1) a pak bych provedl průchod stromem, a to o počtu n kroků (kde n je n-té největší číslo) s tím, že bych se vydal dycky po té větvi, v které by leželo větší číslo (časová náročnost n) ... a nebo tu oba mluvíme o stejné věci jen jinak?? :-)
    20.12.2007 04:39 Martin Tůma | skóre: 39 | blog: RTFM | Praha
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole

    Nemluvíte. To co navrhuješ ty je blbost. Obecný binární vyhledávací strom má MIN i MAX vždy v listu. Takže odtamtud se těžko vydáš "dolů". (A kdyby tě snad napadlo jít "nahoru", tak n kroků ti taky nezaručuje nalezení n-tého prvku)

    Jinak obecně se pod O(N*log(N)) nelze dostat, neboť nalezení n-tého prvku z podstaty věci vyžaduje seřazení pole a to rychleji (pomocí algoritmů založených na porovnávání) než O(N*log(N)) nelze provést.

    Každý má právo na můj názor!
    20.12.2007 08:38 MJ | Tady a teď
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Jinak obecně se pod O(N*log(N)) nelze dostat, neboť nalezení n-tého prvku z podstaty věci vyžaduje seřazení pole a to rychleji (pomocí algoritmů založených na porovnávání) než O(N*log(N)) nelze provést.
    Proč by to vlasně mělo vyžadovat seřazení pole? A proč by ho pak nemělo vyžadovat nalezení druhého největšího prvku?

    P.S.: Samozřejmě existuje lineární algoritmus :-)
    20.12.2007 12:46 Martin | skóre: 10 | blog: Nádraží Perdido
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Ach jo, já veděl, že existuje ještě lepší řešení. Ale že jsem ho viděl minulý semestr na Tvé přednášce, to už mě nenapadlo. Jsem to ale ostuda. :-)
    bazil avatar 20.12.2007 13:34 bazil | skóre: 33 | blog: sluje | Miroslav
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    ježiš, můžu se stydět? teď sem si uvědomil můj strašlivej omyl při přerovnávání toho stromu, aby představoval setříděný pole ... mě to hned nedošlo tak brzo ráno/pozdě v noci
    20.12.2007 08:40 MJ | Tady a teď
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    udělal bych to ještě jinak, hodil bych pole do binárního vyhledávacího stromu (časová náročnost O(N)), [...]
    Tohle určitě v lineárním čase stihnout nejde, na vytvoření vyhledávacího stromu je potřeba čas alespoň Ω(N log N). Ale tady je vyhledávací strom overkill.
    20.12.2007 12:49 Martin | skóre: 10 | blog: Nádraží Perdido
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Zajímalo by mě, jak se takový binární vyhledávací strom vyrábí v lineárním čase. To by se mohlo celkem hodit, prozradíš mi to (pokud to není velké tajemství)? :-D ;-)
    freshmouse avatar 20.12.2007 07:58 freshmouse | skóre: 42 | blog: Bruno Banány
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Hmm, díky. Fakt vás ma tom Matfyzu asi něco učí! :-)

    Sice moc nerozumím tomu, co říkáš, ale rozhodně už jsem inspirován. :-) Podívám se po tom.
    20.12.2007 11:41 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    mne osobne sa pozdáva Fibonacci heap, hlavne vďaka jeho náročnosti pri spájaní viacerých "háld" (ble, to slovo sa mi nepáči)
    20.12.2007 12:40 Martin | skóre: 10 | blog: Nádraží Perdido
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Nemyslíš si, že programovat kvůli úloze nalezení K-tého největšího prvku Fibonacciho haldu je trochu zbytečné? :-) Jako cvičení by to bylo určitě přínosné, ale jinak... já třeba vím jen to, že něco takového existuje, že je to lepší než binární halda (takže může urychlit spoustu algoritmů, třeba Dijkstru), ale to je asi tak všechno. :-) Myslím, že pro začátek freshmousovi postačí prachobyčejná halda binární. :-)
    20.12.2007 13:16 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    no ... Fibonacci heap nie je na naprogramovanie zložitý, možno i jednoduchší, aj keď pochopenie princípu môže byť náročnejšie.

    pomocou toho pdf to imho naprogramuje aj začiatočník :-)

    20.12.2007 12:36 Martin | skóre: 10 | blog: Nádraží Perdido
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Pokud by tě to opravdu zajímalo (což je chvályhodné), tak tohle dělává i pan docent Töpfer na přednášce z Programování I. Mělo by tam být vše o binární haldě a operacích na ní (včetně hezkého důkazu, že se dá z pole halda vytvořit v lineárním čase, pokud bys tomu nevěřil – já tomu třeba nevěřil do té doby, než jsem si ten důkaz tehdy přečetl :-D) a probíral i vyhledání K-tého nejmenšího prvku (to je principiálně úplně stejná uloha jako hledání K-tého největšího prvku, akorát při ní máš haldu "obráceně" :-)).

    A že je ten čas vánoční, tak udělám dobrý skutek a najdu tu přednášku za tebe. Tady to je, přeju příjemnou zábavu. :-)
    Hmm, díky. Fakt vás ma tom Matfyzu asi něco učí! :-)
    No jak jsem si tak přečetl MJův příspěvek výše, tak nevím nevím. :-D
    Josef Kufner avatar 20.12.2007 01:17 Josef Kufner | skóre: 70
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Nejlepší by bylo to udělat už při načítání/sestavování pole a držet si indexy, kde co je.
    Hello world ! Segmentation fault (core dumped)
    20.12.2007 03:05 Jirka P
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Určitě existuje. Jednak je tu velmi profláklý O(N) algoritmus, který se učí snad všude (medián mediánů). S jeho efektivitou je to ale všelijaké a člověk si s tím musí dost pohrát. Pak jsou modifikace třídících algoritmů (např qsort -> zahodit půlku, kde ten prvek určitě není).

    Viz Wikipedii.
    freshmouse avatar 20.12.2007 08:05 freshmouse | skóre: 42 | blog: Bruno Banány
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    O(N) algoritmus, který se učí snad všude.
    Hmm, tak já o tom snad ani neslyšel. Naše algoritmizace začala slovy "otevřete si Netbeans"... No, to trošku přeháním, ale je fakt, že jsme se hned učili spíš Javu než algoritmizovat.
    Pak jsou modifikace třídících algoritmů (např qsort -> zahodit půlku, kde ten prvek určitě není).
    Mrknu na to.
    andree avatar 20.12.2007 08:42 andree | skóre: 39 | blog: andreeeeelog
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    ten upraveny quicksort sa na toto pouziva asi najcastejsie... je to relativne rychle, lahko naprogramovatelne a prehladne ;-)
    20.12.2007 08:12 Tom.š Ze.le.in | skóre: 21 | blog: tz
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    IMHO neexistuje. Nejlepší algoritmus podle mne závisí tom, zda n je malé (v porovnání s rychlou pamětí kterou na to jsme ochotni vyčlenit) nebo ne. Zda se všechny prvky vejdou do paměti nebo ne. A i na dalších podmínkách zadání - space vs. speed, zda to to pole musí přežít a pod.
    wake avatar 20.12.2007 08:34 wake | skóre: 30 | blog: wake | Praha
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Když se google cítí jako lucka při zaklínadle algorithm finding nth smallest number, vypadne z něj tohle.
    Tento příspěvek má hlavičku i patičku!
    20.12.2007 08:44 MJ | Tady a teď
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    To je pěkný algoritmus, pokud se ovšem smíříme s tím, že má lineární časovou složitost jen v průměrném případě.
    20.12.2007 09:29 MJ | Tady a teď
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Možnosti, jak vybrat k-tý největší z n prvků, jsou asi tak tyto:
    • pole setřídit: čas O(n log n), paměť O(n)
    • algoritmus šitý na míru konkrétnímu k (třeba ten výše pro k=2): čas O(n), paměť O(1)
    • pamatovat si v poli k zatím nejvyšších prvků, které jsme viděli, a nový vždy do tohoto pole zatřídit: čas O(nk), paměť O(k)
    • použít pro totéž vyhledávací strom nebo lépe haldu: čas O(n log k), paměť O(k)
    • postavit haldu pro všech n prvků (to jde lineárně) a pak k-krát smazat minimum: čas O(n log n), paměť O(n)
    • modifikovaný QuickSort – vyberu si pivot, rozházím prvky na menší a větší a všimnu si, že jednu z částí mohu zahodit: čas O(n) v průměrném případě, paměť O(n)
    • rekurzivní trik s pěticemi, kterým lze předchozí algoritmus zrychlit na O(n) v nejhorším případě
    • různé algoritmy pro konkrétní typy hodnot – třeba pro integery z rozsahu [0,U] lze použít Van Emde-Boasovy stromy: čas O(n log log U), paměť O(U).
    Viz třeba poznámky k přednášce o algoritmech a datových strukturách (trochu nekompletní, ale zrovna vybírání je tam popsané docela podrobně).
    20.12.2007 09:56 Kyosuke | skóre: 28 | blog: nalady_v_modre
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Hmm, u té haldy přes všechny prvky platí čas O(n.log n) i pro k << n?
    20.12.2007 10:07 Ondrej 'SanTiago' Zajicek
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Ne, to bude O(n+k*log(n)).
    20.12.2007 23:46 MJ | Tady a teď
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Jo jo, upsal jsem se.
    elviin avatar 20.12.2007 09:41 elviin | skóre: 29 | blog: elviin | Plzeň-Praha
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole

    O(nlog k)

       using namespace std;
    
       partial_sort(
          size_coll.begin(), 
          size_coll.begin() + GREATEST_K_ELEMENT, 
          size_coll.end(), 
          greater<size_type>() 
       );
    
       cout << size_coll.at(GREATEST_K_ELEMENT - 1) << endl;
    
    Funkcni prog. je na pastebin.com.
    20.12.2007 09:59 zde | skóre: 9 | blog: Linuch | Brno
    Rozbalit Rozbalit vše Šmankote co řešíte?
    Vezmu normální insert sort, jen omezím tu vnitřní smyčku, aby se nedotřiďovalo celé pole, a bude to dělat přesně to co potřebujete.
    Táto, ty de byl? V práci, já debil.
    20.12.2007 10:23 srigi | skóre: 10 | blog: sricont
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Mno keby sa jednalo o C-ko, velmi vyhodne by som nasadil pointeri. Hlavne teda pri hladani druheho najvyssieho prvku bu bola ucinnost velmi vysoka (staci si po najdeni noveho MAX do pomocneho pointra odkladat adresu predchadzajuceho prvku). Pri hladani k-teho prvku z mnoziny n cisel by sa tiez naslo nejake krasne riesenie s max. dvoma for () {}
    Josef Kufner avatar 20.12.2007 12:42 Josef Kufner | skóre: 70
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Ještě je důležité nezapomenout na případ, kdy je kontrolovaný prvek menší než dočasné maximum, ale větší než předposlední maximum.
    Hello world ! Segmentation fault (core dumped)
    20.12.2007 12:50 peter
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Pokial sa bavime o casovej narocnosti O(..), tak ta nejake pointery nezachrania. Najlepsie co sa da dosiahnut je to O(n) a az potom si to mozes optimalizovat trebarz aj v assembleri. Dva fory byvaju O(n^2), co je o dost horsie. (radovo 1000 krokov vs. milion)
    Josef Kufner avatar 20.12.2007 12:56 Josef Kufner | skóre: 70
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    Ono to nebude O(n^2), ale O(n*k).
    Hello world ! Segmentation fault (core dumped)
    20.12.2007 13:00 peter
    Rozbalit Rozbalit vše Re: Nejvhodnější algoritmus pro druhé (n-té) nejvyšší číslo pole
    No ked k=konst. tak O(n*k)=O(n), ze. Ale ja som myslel k-ty prvok, az teraz som si uvedomil co bol povodny problem. Tam je skutocne najjednoduchsie prejst cele pole a nechavat si okrem maxima aj stare maximum.

    Založit nové vláknoNahoru

    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.