1. Grafai ir jų vaizdavimo b dai. (2 balai) 30psl
2. Surūsiuoti duotą skaičių masyvą sąlajos būdu ir rasti palyginimo operaci 222r1711c ju˛ skaičių:
A . (1.5 balo) 16psl.
3. Isvardinkite pagrindines algoritmų savybes ir jas paaiskinkite. (0.5 balo) 8psl.
4. Suformuluokite uzdavinį apie matricų daugybos tvarką. (0.5 balo) 45psl
5. Ką zinote apie Hamiltono ciklo egzistavimo uzdavinio sudėtingumą? Kurioms is sudėtingumo klasių P, NP, NPC jis priklauso? Kiekvienai klasei pateikti atsakymą ("taip", "ne", "nezinoma") ir jį paaiskinti (0.5 balo) 98psl
6. Ką zinote apie minimalaus grafo karkaso paieskos uzdavinio udėtingumą? Kurioms is sudėtingumo klasių P, NP, NPC jis priklauso? Kiekvienai klasei pateikti atsakyma˛ ("taip", "ne", "nezinoma") ir jį paaiskinti (0.5 balo 82psl
7. Kas yra NP-pilni uzdaviniai ir uzdavinių sudėtingumo klasė NPC? Pateikite pavyzdi˛ uzdavinio is sios klasės. (0.5 balo) 97psl.
|
