text: výpočetní složitost – Sciencemag.cz
  Archiv článků: výpočetní složitost
  Pavel Houser 24. 2. 2022	Články, Nepřehlédněte
  David Gamarnik z MITu popsal novou metodiku, jak by se dalo přistupovat k problému P vs. NP, tedy otázce spadající do výpočetní složitosti, obou někde mezi informatikou a čistou matematikou. Otázka, zda P se může rovnat NP, patří mezi největší problémy současné matematiky, za jejich řešení vypsal Clayův matematický ústav …
  Dokázali výpočetní nadřazenost kvantového počítače
  Pavel Houser 14. 10. 2020	Články
  Tentokrát jde o něco jiného než o demonstraci rychlosti řešení konkrétního problému, jak loni tvrdil Google v menším sporu s IBM. Nyní tu máme mít formální důkaz. Vše ovšem vyžaduje trochu vysvětlování: to, že kvantové počítač využívá superpozici a nachází se během výpočtu "v mnoha stavech současně", samo o sobě …
  Dokázali Kellerovu domněnku pro 7 dimenzí
  Pavel Houser 8. 10. 2020	Články
  90 let starý problém z oblasti geometrie padl díky speciálnímu nasazení algoritmu, který převedl matematickou otázku na problém splnitelnosti. Kellerova domněnka spadá do kategorie populárních problémů dláždění. Otázka zní, zda rovinu můžeme pokrýt jedním typem dlaždic, aniž by se překrývaly jejich hrany (viz obrázek pro čtverce; jindy se problém formuluje …
  Fotonický počítač efektivně řeší NP úplný problém
  Pavel Houser 4. 5. 2020	Články
  Jako subset sum se označuje úloha, kdy je na jedné straně zadána množina přirozených čísel, na druhé straně (větší) přirozené číslo. Ptáme se, zda v množině existuje podmnožina, jejíž součet dává dané číslo. Úloha patří do kategorie NP úplných problémů, to znamená, že s velikostí zadání (součtu i prvků podmnožiny) …
  P-bity – pravděpodobnostní počítače mezi klasickými a kvantovými
  Pavel Houser 24. 9. 2019	Články
  Aneb jakési kvantové počítače pro chudé, než se podaří uvést do praxe ty skutečné. A už umí faktorizovat. Na Purdue University a japonské Tohoku University předvedli první hadrware, který umožňuje pravděpodobnostní (probabilistické) počítání. Má jít o něco mezi klasickými a kvantovými počítači. P-bity (probabilistic) mají pro úlohy řady typů fungovat …
  Na optimalizace paralelně
  Pavel Houser 26. 9. 2018	Články
  Nový algoritmus má slibovat až exponenciální zrychlení pro řešení určitých optimalizačních problémů, a to včetně známého problému obchodního cestujícího. Vědci z Harvard John A. Paulson School of Engineering and Applied Sciences popisují svůj nový algoritmus následujícím způsobem. Tradičně algoritmy tohoto typu, které se de facto objevily už v 70. letech, …
  Riemannova hypotéza a kryptografie
  Pavel Houser 24. 9. 2018	Glosy
  Britský matematik Michael Atiyah tvrdí, že se mu podařilo dokázat Riemannovu hypotézu. Co si o tom máme myslet? Plus pokus o vysvětlení, proč se o bezpečnost šifer sotva třeba bát. Jak lze zjistit krátkým prohledáváním zdrojů, Atiyahovi je 90 let a uvádí, že se mj. snaží rozbourat tradiční představu o …
  Algoritmy pro práci s DNA a problém P vs. NP
  Pavel Houser 20. 3. 2017	Články, Nepřehlédněte
  Genetici a bioinformatici už asi 40 let používají k porovnávání sekvencí DNA tzv. Wagner-Fischerův algoritmus. Tímto způsobem lze zjistit minimální počet elementárních operací, jimiž jednu sekvenci dokážeme přeměnit na druhou, tedy rozdílnost obou řetězců. Za elementární operace považujeme vložení nebo smazání "písmene" nebo jeho přepis za jiné písmeno. (Poznámka: někdy …