2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Du bebrai dirba

Taškai: 12

Du bebrai stato užtvanką ir turi atlikti 8 užduotis (nukirsti medžius, pašalinti šakas, surinkti kamienus ir pan.): A(2), B(3), C(5), D(7), E(10), F(9), G(4), H(6). Skaičius skliaustuose nurodo, kiek valandų reikia užduočiai atlikti. Kai kurias užduotis galima atlikti tik užbaigus ankstesnes, tai nurodoma rodyklėmis paveiksle. Bebrai darbuojasi vienu metu, tačiau kiekvienas imasi atskiros užduoties.

Bebrai naudoja strategiją: iš galimų užduočių pasirenka ilgiausiai trunkančią. Užduočių atlikimo planas atrodytų šitaip:

Bebrai pastatytų užtvanką per 32 valandas. Taikant kitokią strategiją, užtvanką galima būtų pastatyti per trumpesnį laiką.

Kiek mažiausiai valandų reikia dviem bebrams užtvankai pastatyti?

Paaiškinimas

Kai kuriems uždaviniams bebrų strategija (imk ilgiausiai trunkančią užduotį iš likusių) gali pateikti optimalų sprendimą – užduotys gali būti atliktos per trumpiausią laiką. Kitiems uždaviniams (kaip pateikta čia) geriau tinka ilgiausiai trunkančių užduočių paskirstymas skirtingiems atlikėjams. Deja, kiekvienai šiai strategijai galima rasti uždavinių pavyzdžių, kuriems ji netinka. Taip yra todėl, kad šiems uždaviniams nėra bendros procedūros (sprendimo) trumpiausiai laiko trukmei rasti – optimalų sprendimą galima rasti tik išbandant visus galimus užduočių paskirstymo variantus! Paprastai tai nėra realu, ir net skaičiuojant kompiuteriu procesas gali trukti ilgiau, nei vienas bebras pastatytų visą užtvanką!

Šio uždavinio pavyzdys buvo kruopščiai parinktas, kad bebrų strategija (imk ilgiausiai trunkančią užduotį iš likusių) netiktų. Tai nebuvo lengva. Daugumai uždavinių ši bebrų strategija (dažnai vadinama godžiąja) tinka gana gerai, galima greitai paskirstyti užduotis, ir bebrai gali imtis darbuotis nieko nelaukdami.

Sukurti pavyzdžius, netinkančius kurią nors sprendimo strategiją (kaip buvo daroma rengiant šį uždavinį), reikia kūrybiškumo ir gilaus strategijos suvokimo. Tačiau šie įgūdžiai reikalingi informatikui norint nustatyti, pavyzdžiui, ilgiausią programos atlikimo kompiuteriu laiką, kas vartojama algoritmų analizėje (skaičiavimų sudėtingumo teorijos srityje).

Raktiniai žodžiai: planavimas, trumpiausia laiko trukmė, užduočių paskirstymas, optimalus sprendimas.

Atsakymas

Teisingas atsakymas: 23.

Uždavinio lentelėje parodytas dviejų bebrų užduočių atlikimo planas. Matome, kad pirmasis bebras neturi darbo gana ilgą laiką, net 8 valandas, o antrasis – 6 valandas. Geriausia būtų, jeigu jie galėtų darbuotis visą laiką.

Taikysime kitą strategiją: planuosime, kad dvi ilgiausiai trunkančios užduotys E(10) ir F(9) neatitektų tam pačiam bebrui. Pateikiame vieną tokių užduočių paskirstymo planų.

Matome, kad užtvanką galima pastatyti net per 23 valandas!

Atkreipkite dėmesį, kad ši strategija leido atlikti darbą per trumpiausią laiką todėl, kad abu bebrai galėjo darbuotis be pertraukų.

Interaktyvi užduotis