Algoritmi in podatkovne strukture (2021-22)

V neki datoteki (nalogi sta priložena dva primera) je seznam prepovedanih intervalov števil. Vrstica, ki vsebuje, recimo, 12-18, pove, da so prepovedana vsa števila od 12 do (vključno) 18. Intervali se lahko prekrivajo.

Med priloženimi datotekami je tudi par vrstic Pythona, ki preberejo datoteko s podatki. Uporabite po želji.

Zanima nas, katero je najmanjše dovoljeno število, torej, najmanjše celo število večje ali enako 0, ki ni vsebovano v nobenem intervalu.

Če imamo, recimo, prepovedane intervale

4-12
15-18
0-6
20-25
13-16

je najmanjše dovoljeno število 19. Vsa števila do (vključno) 6 so prepovedana v tretji vrstici, prva nam prepove še vse do 12, zadnja prepove še vse do 16 in druga vse do 18. 19 pa je dovoljeno.

Pri razmišljanju o časovnih zahtevnostih uporabljaj oznake (ni nujno, da boš potreboval(a) vse):

• N: največje možno (ne največje dovoljeno!) število; torej, števila so med 0 in N,
• k: število intervalov v datoteki,
• m: širina največjega intervala.

Pri reševanju naloge smete uporabljati poljubne funkcije in podatkovne strukture iz Pythona in modulov, ki se namestijo z njim. Dodatne knjižnice (numpy, matplotlib, jupyter) pa uporabljajte samo za morebitno risanje grafov ipd, ne pa znotraj dejanskih funkcij, ki rešujejo nalogo.

Glede na to, da vas je tako malo, res ne bo problem, če med reševanjem naloge pošljete kakšen mail in me vprašate, ali je taka in taka rešitev skladna s tem, kar sem si predstavljal in ali kako bi se mogoče dalo narediti še to in tisto. Te naloge ne dojemajte kot nekaj, kar naredite in oddate, temveč kot nekaj, na čemer delate in jaz vas pri tem usmerjam.

1. Obstaja očiten način, kako rešiti ta problem: po vrsti preverjamo vsa števila, dokler ne naletimo na najmanjše dovoljeno.

   • Sprogramiraj tak postopek.
   • Kako hiter je? V najboljšem in v najslabšem primeru? Hitrosti ne meri (razen, če si pripravljen napisati funkcijo, ki sestavlja pametno izbrane intervale), temveč jo poračunaj.

2. Najbrž si lahko izmisliš drug preprost algoritem, ki porabi N bajtov (ali bitov ali enot) pomnilnika. V Pythonu bi to pomenilo, da boste imeli seznam z N elementi, pri čemer bodo imeli elementi neko konstantno velikost, npr. le True ali False ali pa le števila, katerih velikost ne bo odvisna od števila intervalov ipd. (Namig: prečrtavanje.)

   • Opiši ga z besedami. Za primer si lahko izmisliš svojo nalogo (recimo nekaj intervalov s števili med 0 in 20), ter pokažeš algoritem na njih. A vseeno sestavi tudi splošen opis.
   • Sprogramiraj. Nasvet: ne preskušaj na prevelikih podatkih. :)
   • Kako hiter je ta algoritem? Pri razmišljanju uporabljaj N, k in m (če ga potrebuješ).

3. Izmisli si algoritem, ki je hitrejši od obeh prejšnjih in ne porabi dodatnega pomnilnika. Pri tem seveda ne upoštevamo pomnilnika za tabelo, v kateri so shranjeni intervali. Formalno: poraba pomnilnika je sorazmerna številu intervalov, k, ni pa odvisna od N in m.

   • Opiši ga.
   • Sprogramiraj ga. Deluje naj tudi na velikih podatkih.
   • Kako hiter je?

4. Zdaj pa nas zanima, koliko je vseh dovoljenih števil (med 0 in N).

   • Kako bi prilagodil(a) gornje algoritme za to vprašanje?
   • Kaj se zgodi z njihovimi časovnimi zahtevnostmi?
   • Ustrezno spremeni gornje tri programe.

5. Kaj pa tole: recimo, da imaš računalnik z zelo malo pomnilnika. Niti toliko ga ni, da bi lahko shranil tabelo vseh intervalov. Torej: v programu ne moreš uporabljati nobenih seznamov, množic, slovarjev, dreves, ... nič takega. Dovoljeno so izključno int-i in, da ne kompliciramo, pari, se pravi, tuple z dvema elementoma. Pač pa smeš poljubnokrat prebrati datoteko s podatki.

   • Kako se boš lotil(a) tega problema?
   • Sprogramiraj tak postopek. (Iz priloženega programa boš moral(a) uporabiti le vrstico for in tisto, ki ji sledi.)
   • Poraba pomnilnika je zdaj konstantna. Kakšna pa je časovna zahtevnost? Če je večja kot $$k^2$$, premisli ponovno in popravi.

Nalogo oddaj v dveh datotekah -- v eni bo program, druga pa PDF z ostalimi odgovori.

Za uspešno opravljeno nalogo (in s tem polovico pogoja za pristop k izpitu - imeli bomo namreč še eno nalogo) je potrebno pravilno rešiti vsaj prvi dve točki. Za višje ocene je potrebno rešiti več. Ocena bo odvisna od kvalitete rešitve in komentarjev.