| Typ súboru | APK |
|---|---|
| Verzia | 3.2.2 |
| Vydavateľ | Ofek Ron |
| Dátum vydania | 20. 8. 2020 |
| Dátum pridania | 20. 8. 2020 |
| Požiadavky OS | Android |
| Požiadavky | Requires Android 4.1 and up |
| Celkový počet stiahnutí | 0 |
| cena | Free |
Popis
Problém P verzus NP je hlavným nevyriešeným problémom v informatike. Pojednáva o tom, či každý problém, ktorého riešenie dokáže rýchlo overiť počítač, dokáže rýchlo vyriešiť aj počítač. Je to jeden zo siedmich problémov s cenou tisícročia, ktoré vybral Clay Mathematics Institute na získanie ceny 1 000 000 USD za prvé správne riešenie. Problém Hamiltonovho cyklu je dobre známy NP-úplný problém z oblasti teórie grafov. Vyriešenie takéhoto problému, napríklad nájdenie polynomiálneho algoritmu, ktorý ho rieši pri akomkoľvek danom vstupe, by priviedlo ľudstvo bližšie ako kedykoľvek predtým k vyriešeniu problému P versus NP.
V tejto hre dostanete graf, čiže množinu uzlov a hrán, ktoré niekedy obsahujú hamiltonovský cyklus (viac sa dozviete tu https://en.wikipedia.org/wiki/Hamiltonian_path_problem) a niekedy nie, a vy treba to vyriešiť buď odhalením hamiltonovského cyklu, alebo rozhodnutím, že pre daný graf neexistuje.
veľký tip na rozhodnutie, či je graf hamiltonovský (obsahuje Hamiltonov cyklus), nájdete tu https://en.wikipedia.org/wiki/Graph_toughness.
Poďte a vyriešte problém za 1 milión dolárov a naučte sa pritom teóriu grafov!
