Letní programování (diskuse)

[MCThrall]

Pamatuji si tyto ukoly jeste z gymplu. Uz v nekdy v prvaku nam to s kamaradem prislo pomerne primitivni. Ale pokud to vychova nejakeho programatora, jenom dobre.

[MCThrall]

A to nerikam jen tak. Uz v tom prvaku jsme kazdy fungoval v nejake spolecnosti a nefungovali jsme po dve sta za hodinu. Byla to fajn doba.

[adssa]

Co jsi ty za vola?

[Lukáš Lánský]

Spoustě lidí podobné soutěžení nevyhovuje, protože programování berou jen jako prostředek obživy, popř. nachází uspokojení v zářících očičkách šťastných uživatelů.

[Radek Miček]

Uz v nekdy v prvaku nam to s kamaradem prislo pomerne primitivni.

Nejsou tam i NP-úplné problémy?

[Lukáš Lánský]

Jsou.

[JS]

Chtel jsem odpovedet take v tom smyslu, ale nejsem si 100% jisty. Jelikoz je to v rovine, tak tam se dost NP-uplnych problemu redukuje na polynomialni. I kdyz uznavam ze 4 a 6 nevim, jak optimalne resit, i kdyz si myslim, ze 4 by se dala (polynomialni TSP pro rovinne grafy tusim dokazal Tarjan, ale jak to delal, nevim).

[JS]

(Tedy, je mi jasne, ze 4 neni ciste TSP, ale treba by se ten Tarjan dal na to nejak zmodifikovat, co ja vim.)

[žito]

To je jen minimální kostra na grafu který vznikne propojením všeho se vším + ohodnocením hran.

[Radek Miček]

TSP je NP-těžký i pro rovinné grafy.

[JS]

Jo mas pravdu. Spletl jsem si to s izomorfismem grafu.

[Radek Miček]

I kdyz uznavam ze 4 a 6 nevim, jak optimalne resit.

Myslím, že ani 5 neumíte řešit optimálně v polynomiálním čase.

[zdgadgsdfg]

problem obchodniho cestujiciho, tj. NP uloha.

[JS]

Myslel jsem, ze 5 je minimalni kostra grafu. Ta mi naopak prisla resitelna.

[Radek Miček]

Pokud to dobře chápu, tak zadání nezakazuje větvení mimo obce – jde o nalezení Steinerova stromu.

[Lukáš Lánský]

Je to zákeřný. Ale za minimální kostru se udělují 2/3 bodů. Koneckonců je pravděpodobně v rovině rozdíl mezi délkou minimální kostry a Steinerova stromu jen něco jako 15 %.

[JS]

Ale to ze tam maji nekteri maximum bodu znamena, ze se to optimalni reseni nalezt da, ne? Nebo maji maximum protoze nasli nejlepsi?

[Lukáš Lánský]

150 bodů dostává aktuálně nejlepší řešení. U toho Steinera bychom byli bývali mohli dát ten domněný horní odhad na rovinný případ, ale u těch zbývajících dvou úloh jsme nic takového neměli, tak jsme to vyřešili takhle, lehce matoucně.

Optimální řešení na Steinera pro 6000 obcí asi nikdy nikdo znát nebude. Aproximační schéma sice pro rovinnou variantu je, ale děsím se polynomu, který z toho vyskočí. Bylo by hezké to přesně napočítat aspoň pro krajská města.

[mato]

tak vies, chuck norris naratal 2x do nekonecna; MCThrall povazuje NP tazke ulohy za primitivne ;)

[Jablíčko]

Primitivní? Hmm, namátkou co třeba tohle? Dokázat správnost je zde primitivní, že.

[ng]

Podle toho seznamu nejsou Samotíšky, ale Samotišky a mají 668114 obyvatel, což se mi nezdá.

[Lukáš Lánský]

1260 obyvatel – první číslo ten počet udává, další dvě jsou souřadnice.