Računalništvo 1

Algoritem je zahtevnosti O(1). To zato, ker vedno, ko želimo poiskati najmanjše število, zgolj pogledamo najvišje število v pomožnem skladu.

Ja. Obstaja tudi algoritem, kjer uporabljamo samo en sklad in pomožno spremenljivko min.  Več si lahko prebereš na: https://www.techiedelight.com/design-a-stack-which-returns-minimum-element-without-using-auxiliary-stack/.

Ja, zakaj? Vsak element v pomožnem skladu se nahaja tudi v glavnem. Ko odstranimo element iz glavnega sklada, hkrati tudi odstranimo element iz pomožnega sklada, če je le ta enak tistemu iz glavnega.

Ja, algoritem bi bil popolnoma enak, le da bi v pomožni sklad dodajali vedno večja/ enako velika števila (in ne vedno manjša/enako velika).

·         V primerih, kjer je sklad prazen, mora algoritem vrniti napako. (Podobno, če bi iskali minimalni element od prazne množice -> vrne napako)

>>> sklad = SkladMin()

>>> print(sklad.min())

ValueError: VRH: Sklad je prazen

·         Podobno tudi tukaj:

>>> sklad = SkladMin()

>>> sklad.vstavi(5)

>>> sklad.odstrani()

>>> print(sklad.min())

ValueError: VRH: Sklad je prazen

 

·         Nato bi dodal še nekaj 'navadnih' primerov (da bi preverjal pravilno sprotno delovanje algoritma, bi rešitve po vsakem koraku shranjeval v neko tabelo; verjetno obstaja veliko bolj pametna metoda 😊):

>>> tabela_minimumov = []

>>> sklad = SkladMin()

>>> sklad.vstavi(5)

>>> tabela_minimumov.append(sklad.min()) 

>>> sklad.vstavi(4)

>>> tabela_minimumov.append(sklad.min())

>>> sklad.vstavi(6)

>>> tabela_minimumov.append(sklad.min())

>>> sklad.vstavi(3)

>>> tabela_minimumov.append(sklad.min())

>>> sklad.vstavi(4)

>>> tabela_minimumov.append(sklad.min())

>>> sklad.odstrani()

>>> tabela_minimumov.append(sklad.min())       

>>> sklad.odstrani()

>>> tabela_minimumov.append(sklad.min())

>>> print(tabela_minimumov)

[5, 4, 4, 3, 3, 3, 4]

Tukaj je algoritem nekoliko drugačen. Eden izmed 'pametnih' načinov je, da uporabimo pomožno vrsto, kjer število vedno vstavimo noter. Tukaj je razlika v tem, da vsa števila, ki so večja od tistega, ki ga vstavimo v pomožni sklad, izbrišemo iz pomožnega sklada. Najmanjši element, je vedno na začetku pomožne vrste. Več si lahko ogledaš na: https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/.

En od možnih načinov je tak, kot sem ga omenil na koncu predstavitve (2. način izboljšave algoritma) in sicer z uporabo rekurzije. Saj nam je tisti algoritem vračal ravno velikost sklada. Je pa res da pri tem posredno vseeno uporabimo pomožen sklad, saj ga ustvari rekurzija sama.

Algoritem nam pobriše edini element v skladu. 

Z uporabo rekurzije ne izboljšamo časovne zahtevnosti algoritma. Predstavljen algoritem je le nek drugačen (mogoče nekoliko bolj eleganten) način, s katerim pridemo do željenega rezultata.  

Da, gre za mojo odločitev predvsem zaradi lažje predstavitve, saj lahko v tem primeru uporabimo kar celostevilsko deljenje (ali pa si pomagamo z int() – kot sem si jaz). Če pa bi hoteli odstraniti 3. element, bi si lahko pri pogoju pomagali z ukazom math.ceil(velikost/2 – 1).

Mislim, da sklada in seznama med sabo nemoremo neposredno primerjati. Saj je sklad podatkovna struktura, ki pa jo lahko predstavimo tudi s npr. seznamom. 

Tako je, s tem algoritmom odstranimo nižji element v skladu oz. element ki je bil prej vstavljen v sklad.

Da, lahko bi. Več o tem pa sem napisal pri podobnem vprašanju zgoraj.

Približno en teden. Od tega 1 – 2 dni bolj intenzivnega dela (ostalo pa so bili bolj popravki, priprava na predstavitev...🙂)

Kot sem omenil že pri podobnem vprašanju, težko primerjamo delo s skladi in s tabelami. Vsekakor bi bilo lažje (verjetno tudi hitrejše) uporabiti kar tabelo oz. seznam v Pythonu in odstraniti srednji element. Če pa smo omejeni le na metode, ki smo jih definirali pri skladu, to seveda ne pride v poštev.

Algoritem bi bil vsekakor nekoliko bolj zapleten, saj bi potreboval dodaten pogojni stavek. Lahko pa bi enostavno dodali novo funkcijo, ki v primeru, da je število elementov sodo, ta isti algoritem požene dvakrat. Saj v tem primeru izbrišemo oba srednja elementa.

Ne, v prikazanem primeru so slučajno bila samo pozitivna števila, funkciji bi delali tudi z negativnimi števili.

Časovna zahtevnost prve funkcije je O(n^2), druge pa O(n) (če uporabimo množico).

Pri prvi funkciji je O(1), saj si shranjujemo samo število parov in trenutna vozla kjer se nahajamo, pri drugi pa O(n), saj si vsa števila prvega verižnega seznama shranimo v množico/tabelo. Bolje je, da je množica/tabela ustvarjena iz verižnega seznama z manjšo dolžino, da zmanjšamo zavzeti prostor.

Mislim, da rešitve nebi mogli izboljšati, saj se v vsakem primeru moramo sprehoditi čez oba verižna seznama.

Časovna zahtevnost se ne spremeni, saj v drugi zanki samo dodamo dodaten pogoj.

Problem je, da se po vrsti ne moremo sprehoditi brez da jo spreminjamo, kot se lahko v verižnih seznamih. Če nas po algoritmu vrsta več ne zanima, se algoritem nebi spremenil, če pa želimo vrsto ohraniti nespremenjeno, bi pa to morali narediti s pomočjo »stražarja«.

Za vrsto sem že odgovoril pri prejšnjem vprašanju, za sklad je pa zelo podobno, če bi želeli sklad ohraniti, bi morali to narediti s pomožnim skladom.

Ta algoritem bi lahko uporabili kadarkoli, ko bi iskali pare, kakršnekoli oblike, iz dveh verižnih seznamov.

Mislim, da rešitve nebi mogli izboljšati, saj se v vsakem primeru moramo sprehoditi čez oba verižna seznama/sklada/vrsti. Izboljšamo lahko le, če točno vemo s kakšnimi podatki imamo opravka, npr. z urejenimi po velikosti.

Lahko, in sicer takole:

{

def bisekcija_rekurzija(tabela_stevil, k, zacetek = None, konec = None):

    if zacetek == None: #definiramo interval pri prvemu klicu

        zacetek = max(tabela_stevil)

        konec = sum(tabela_stevil)

    

    if zacetek > konec: #zaustavitveni pogoj, ki je bil prej v pogoju while zanke

        return float('inf')

    

    #enako kot prej izračunamo najmanjše število delitev, da je maksimalna vsota namjša ali enaka sredini

    sredina = (zacetek + konec) // 2

    vsota = 0

    stevec = 1

    for i in range(len(tabela_stevil)):

        if vsota + tabela_stevil[i] > sredina:

            stevec += 1

            vsota = tabela_stevil[i]

        else:

            vsota += tabela_stevil[i]

    

    #namesto da spremenimo interval in gremo naprej v zanki, rekurzivno pokličemo funkcijo s spremenjenim intervalom

    if stevec <= k:

        odgovor = min(sredina, bisekcija_rekurzija(tabela_stevil, k, zacetek, sredina - 1))

    else:

        odgovor = bisekcija_rekurzija(tabela_stevil, k, sredina + 1, konec)

    return odgovor

}

Hitrost reševanja se pa ne spremeni, saj s tem nismo nič zmanjšali števila operacij, samo namesto while zanke smo uporabili rekurzijo.

Če nastavimo k na dolžino tabele vrne algoritem največji element v tabeli, saj je to najmanjša maksimalna podvsota.

V primeru, da je k večji, bo algoritem vrnil isti odgovor, vendar to ni smiselno vprašanje, saj tabele ne moremo

razdeliti na več podtabel, kot je elementov.

Časovna zahtevnost iskanja vseh možnosti je enaka O((n−1)c(k−1)), kjer c predstavlja število vseh kombinacij, katerih je(n - 1)! / ((n - k)! * (k - 1)!). Časovna zahtevnost bisekcija pa je O(n log(sum)). n predstavlja število elementov v tabeli, k število podtabel in sum vsoto vseh elementov v tabeli.

Kolikor jaz vem je to optimalna rešitev.

Za reševanje tega problema ni smiselno uporabljati katerekoli posebne podatkovne strukture, saj ni treba hraniti večjega števila podatkov.

Časovna zahtevnost bi bila še vedno O(n log(sum)), bi pa porabili več časa, saj ko bi iskali najmanjšo delitev vrste, da je maksimalna vsota podvrste enaka sredini, bi med tem, ko gremo čez vse elemente v vrsti te elemente shranjevati v pomožno vrsto, nato pa bi jih morali še spraviti nazaj v prvotno vrsto.

Ne vem točno, kaj je mišljeno s tem vprašanjem.

Mi vemo, da je naš odgovor nekje med začetkom in koncom. Nato se vprašamo, na koliko podtabel moramo razdeliti tabelo, da je maksimalna vsota manjša ali enaka sredini. Če je število podtabel manjše ali enako podani, vemo, da je maksimalna vsota manjša ali enaka sredini, zato nastavimo odgovor na sredino in se z istim postopkom vprašamo, če je odgovor mogoče  med sredino in začetkom. Če ne pa se vprašamo, kje med sredino in koncom je odgovor.

Rešitev ne bi bila primerna za velike $ m $ (dolžina poti) ter za grafe, ki so gosto prepleteni s povezavami(npr. vsako vozlišče je povezano z vsemi ostalimi v grafu).

Če bi želeli a problem rešiti za velik $ m $ bi bilo treba graf analizirati, da vidimo kje so povezave z negativno vrednostijo. Ko vemo, največ koliko lahko trenutna cena pade med potjo do končnega vozlišča, vemo tudi kdaj lahko iskanje po trenutni poti predčasno ustavimo. Menim, da bi ta optimizacija prinesla največ k znižanju povprečne časovne zahtevnosti. 

Za problem, ki je zastavljen ne vidim boljše rešitve. Seveda bi lahko uvedli optimizacije, ki v povprečju zmanjšajo število operacij, a časovna zahtevnost v najslabšem primeru bi ostala enaka.

Pot s točno določenim številom povezav iščemo, ker je bil tako zastavljen problem, sicer pa v praksi ni smiselno fiksirati števila povezav pri problemu najcenejše poti.

V tem primeru bo algoritem vrnil $ \infty $, kar si lahko razložimo, tako da za pot med dvema nedosegljivima vozliščema potrebujemo neskončno sredstev.

Glej Ali obstaja tudi bolj časovno optimalen algoritem za rešitev problema?

Časovna zahtevnost(v najslabšem primeru) je pri obeh rešitvah enaka, ampak bo v povprečju prva rešitev hitrejša, saj ni potrebno iskati poti po povezavah, ki smo jih že prečkali.

Glej Ali je drugi algoritem časovno bolj zahteven kot prvi?

Ne, saj lahko pri obeh rešitvah obiščemo isto vozlišče poljubno mnogokrat, kar lahko tvori cikel.

Zanimiv primer bi bil graf s ciklom, v katerem bi imele vse povezave negativno ceno. Rešitev, ki lahko prepotuje iste povezve večkat, bi najverjetneje, pri velikem $ m $, ta cikel uporabila za znižanje cene, tako da nekajkrat zaokroži po njem.

Ideja je, da bi kot argument imeli tudi slovar, v katerem bi kot ključe hranili pare $ (m,voz) $, kot vrednosti pa ceno od trenutnega do končnega vozlišča z $ m $ povezavami. Tako bi lahko vsakič, ko se vrnemo iz rekurzivnega kilca lahko dodali izračunano vrednost v ta slovar. To bi lahko uporabili, tako da bi ob vstopu v nov rekurzivni klic preverili, če je par $ (trenutniM,trenutnoVoz) $ v slovarju. Če bi bil, lahko vrnemo ceno iz slovarja ter prekinimo iskaje po tisti poti.

V primeru, da je v grafu le eno vozlišče, bo cena najcenejše poti $ \infty $, razena, ko je $ m = 0 $. Takrat bo cena enaka 0.  

Ta ideja bi delovala, če bi za ceno povezav veljala nenegativnost. V predstavljenem problemu pa se lahko zgodi, da je nekje blizu končnega vozlišča povezava, ki je negativana, a po absolutni vrednosti zelo velika. Če bi pred tem odkrili neko slabo pot do končnega vozlišča, bi se lahko zgodilo, da nikoli ne odkrijemo te idealne povezave z nizko ceno, saj bi prej nehali iskati.

Glej Ali obstaja tudi bolj časovno optimalen algoritem za rešitev problema?

Primera uporabe za ta algoritem ne vidim, saj je fiksiranje $ m $ zelo nenevadna zahteva. Problem pa je zelo podoben iskanju najcenejše ali najkrajše poti v splošnem. Trenutni rešitvi za te probleme iz časovne zahtevnosti ne bi bili primerni.

Ja, v vrsti se shranjujejo indeksi elementov iz matrike kot pari oblike (i, j), kjer i prestavlja i-to vrstico matrike, j pa j-ti stolpec matrike, ki sem jo poimenovala "košara".

Verjetno obstaja, vendar se mi zdi, da je najlažje pregledati "mrežo" podatkov s pomočjo matrike, saj morajo biti podatki v "2-dimenzionalnem prostoru", da lahko pogledamo sosednje celice.

Ne, če bi bile v košari samo gnile pomaranče, nam algoritem vrne "Minimalno število korakov, da zgnijejo vse pomaranče = 0", saj so gnile že vse in ne potrebujemo dodatnih korakov. Če bi bile v košari samo sveže pomaranče, nam algoritem vrne "Vse pomaranče ne morejo zgniti", ker nimamo nobene gnile, svežih pa celo košaro. Uporabila sem if stavek in sicer if vrsta.prazna(), nato pa še en if stavek in sicer if sveze == 0 da se prepričamo da ni košara prazna ampak da so v košari le sveže pomaranče. Če pa je vrsta prazna in svežih pomaranč ni, nam algoritem vrne "Košara je prazna".

https://www.geeksforgeeks.org/minimum-time-required-so-that-all-oranges-become-rotten/

Na danem linku je opisan algoritem, katerega sem uporabila za glavni vir. Pri rešitvi si pomagajo s podobno strukturo kot je vrsta in sicer QUEUE (https://docs.python.org/3/library/queue.html). Deluje podobno, le da ima vgrajene funkcije kot so append, pop, put, get, ... S pomočjo vstavljanja strukture queue bi blo verjetno lažje, a sem želela vključiti vrsto, kot smo jo definirali na predavanjih in vajah.

Vse elemente v matriki pregledamo le na začetku. Kasneje gledamo le še sosede gnilih pomaranč. Mislim pa, da se bi temu težko izognili, ker potrebujemo vsaj začetno stanje košare, tako da se enkrat vsaj moramo sprehoditi čez vse elemente. Morda le, če začetni pogoji ne bi bili shranjeni v matriki.

Lahko, kot sem že zgoraj napisala, bi v tem primeru dobili rezultat oblike "Vse pomaranče ne morejo zgniti."

Časovna zahtevnost: O((V*S)*(V*S))

• V je število vrstic
• S je število stolpcev
• matrika mora biti pregledana dokler ni nobenih sprememb, to se zgodi max(V*S)/2-krat

Prostorska zahtevnost: O(1)

• Ne potrebujemo dodatnega prostora za shranjevanje

Mislim, da je časovna zahtevnost O(V*S), da na začetku pregledaš celo matriko, čas ki ga potrebujemo da zgnijejo vse pomaranče pa je manjši od O(V*S), zato ga ne upoštevamo.

Mogoče, če bi jabolka vplivala tudi na diagonalne sosede. Odvisno od domišljije ;)

Algoritem bi lahko nekoliko modificirali in poiskali pot z najnižjo ceno v grafu. V posebnem primeru, ko so vse cene v grafu pozitivne, bi bilo potrebno pogledati le poti prve stopnje iz podanega začetnega vozlišča in med istimi izbrati povezavo z najnižjo ceno. Preverjanje vseh poti iz začetnega vozlišča do katerega koli drugega vozlišča ni potrebno, saj se bo ob pregledu poti druge stopnje cena povečala.

Medtem ko imamo v grafu tudi negativne uteži se lahko zgodi, da nam bo določena povezava z utežjo -10 prispevala k bolj optimalni rešitvi in v tem primeru preverimo vse možne poti. 

Za iskanje najcenejše poti v grafu se uporabljajo nekoliko drugačni pristopi, v odvisnosti od specifikacij problema. Znana tovrstna problema sta ''Problem trgovskega potnika'' in ''Problem razvoza''.  Več o problemu trgovskega potnika si lahko ogledate na povezavi https://en.wikipedia.org/wiki/Travelling_salesman_problem. Za problem razvoza prilagam članek, ki sem ga lani pripravila pri predmetu Komuniciranje v matematiki.

Pri osnovnem algoritmu iskanja v širino je dovolj da si zapomnimo podatek o pregledanih vozliščih, lahko jih hranimo v seznamu, pomembno je, da običajno ne obiskuje že odkritih vozlišč. To ne ustreza našim pogojem, če želimo zajeti vse možne poti iz danega vozliča, zato to preverjanje odstranimo iz osnovnega algoritma. V seznamu pregledanih vozlišč, poleg vozlišča in skupne cene do tega vozlišča, hranimo še pot. Ta pot predstavlja pot po kateri smo prišli od začetka do tega vozlišča. Potem vemo, da bi dobili cikel, če je naslednje vozlišče že na tej trenutni poti, zato tega vozlišča ne dodamo.

Namesto seznama, za shranjevanje podatkov, lahko uporabimo tudi vrsto :

     > vrsta = deque()

     > vrsta.append((trenutni_vrh, trenutna_cena_poti, nabor_do_sedaj_obiskanih_vozlišč))

V vrsti seveda spet hranimo potrebne podatke.

Sama implementacija grafa je poljubna. Podatke lahko hranimo s seznamom sosednosti, kjer za vsako vozlišče xi imamo seznam sosedov, če je graf neusmerjen in z matriko sosednosti, imamo n x n matriko, kjer vsaka vrstica in vsak stolpec predstavljata vozlišče. Vrednost elementa c_i,j je 1 če in samo če obstaja povezava (x_i, x_j).
 

Uteži so lahko negativne. Ko iščemo pot z najvišjo ceno se v globalnem ne splača sprehajat po poteh z negativnimi utežmi, saj nam znižajo ceno poti. Vendar na lokalni ravni, se nam lahko zgodi, da nas bo negativna povezava, na primer nekje na začetku poti, privedla k najboljši končni rešitvi in bomo s tem ko bomo preverili vse možne poti, le to izbrali za najbolj optimalno. Če povzamem, pot z negativno utežjo je lahko na določenem koraku slaba odločitev, a jo vseeno ''prehodimo'' in dodamo trenutni poti, saj bo mogoče na koncu le ta pot imela najvišjo ceno v primerjavi z ostalimi.  V primeru, ko je negativna utež čisto na koncu naše trenutne najbolj optimalne poti je smiselno, da jo izpustimo in se ustavimo na prejšnjem vozlišču.

Časovna zahtevnost algoritma je O(V+E), kjer je V število vozlišč in E število povezav v grafu. Glede na to, da je uporabljan algoritem iskanja v širino, ''Breadth-First Search (BFS)'', O(E)  je lahko med O(1)  in O(V^2).

V bistvu moj algoritem ni smiseln za iskanje najkrajše poti, saj bi v tem primeru rešitev bila enostavna in to, vse poti prve stopnje, torej od začetnega vozlišča do njegovih prvih sosedov.  Če bi imeli problem zastavljen nekoliko drugače, na primer, da bi iskali pot od podanega začetnega vozlišča do podanega končnega vozlišča bi uporabili drugačne pristope in poiskali najkrajšo možno pot.

Če pa je mišljeno na najcenejšo pot, glej odgovor na vprašanje: ''Ali bi lahko s podobnim algoritmom iskali tudi najcenejšo pot?''

Pri tem problemu je koncept modificiranega algoritma iskanja v širino edina možnost, ki jo poznam. V posebnih primerih in ob posebnih pogojih bi se dalo algoritem izboljšat.  

Običajno v usmerjenem grafu imamo spremenjen seznam sosednosti, kjer za vsako vozlišče Xi, imamo seznam naslednikov in seznam predhodnikov. V neusmerjenem grafu smo imeli en sam seznam sosedov.  V našem primeru to pomeni, da bi iz začetnega vozlišča  preverjali poti samo v smeri, ki jo graf omogoča, oziroma preverimo možne poti do vozlišč iz seznama naslednikov trenutnega vozlišča.

Algoritem bi deloval tudi na grafih z veliko vozlišč, je pa časovna zahtevnost algoritma odvisna od števila vozlišč in je O(V+E), kjer je V število vozlišč in E število povezav v grafu in je O(E)  lahko med O(1)  in O(V^2).

Če je niz oklepajev prazen se ne zgodi ničesar. Funkcija nima elementov oklepajev, na katerih bi lahko preverjala ali je niz uravnotežen ali ne.

V vhodnem nizu so lahko samo odprti in zaprti oklepaji ene vrste. Moja funkcija dela le za zavite oklepaje, če pa bi želeli izvedeti število zamenjav v izrazu iz navadnih ali oglatih oklepajih, bi bilo v kodi funkcije potrebno ustrezno spremeniti pogoje.

Ne.

Idejo, ki sem imela je bla ta, da bi za vsako vrsto oklepajev definirala svoj par skladov v katere bi hranila oklepaje in z njimi počela to kar sem počela v moji nalogi. Problem pa bi se pojavili, pri gnezdenju oklepajev. Če bi imeli niz oblike '([{]})' bi v našem primeru ta že bil uravnotežen, kar pa v resnici ne velja. Potrebne bi bile še menjave vrstnega reda oklepajev, ne le menjava zaprtega oklepaja v odprt in obratno.

Časovna zahtevnost v primeru reševanja z rekurzijo bi bila O(2^n) Časovna zahtevnost v primeru reševanja s podatkovno bazo skladi pa bi bila O(n), kjer je n število elementov v nizu, kar je časovno ustreznejše.

Rekurzija ima eksponentno časovno zahtevnost O(2**n), kjer na vsakem koraku dvakrat kliče samo sebe. To bi delala tudi v našem primeru.

Tu odgovarjam še na vprašanji od kje pride formula ter, razlog zakaj je formula taka kot je.

Formulo, ki smo uporabili v rešitvi je oblike:

Številu elementov sklada smo prišteli ena, enako storili z številom elementov v pomoznem_skladu ter celoštevilsko delili z dva.

Torej, imamo niz sode dolžine, ki ga je potrebno uravnotežiti. Uravnotežen del niza bo sode dolžine (vsak odprt oklepaj ima svoj zaprt oklepaj) in prav tako bo neuravnotežen del sode dolžine. Imeli bomo m število zaprtih oklepajev in n število odprtih oklepajev. Tu imamo dva primera:

• število obeh oklepajev je sodo

V tem primeru bo število zamenjav točno m/2 + n/2. Na primer: če imamo dva zaprta oklepaja '}}' potrebujemo natanko eno zamenjavo oklepaja, da bomo imeli uravnotežen izraz, enako velja, če imamo dva odprta oklepaja '{{' prav tako potrebujemo n/2 torej 2/2 eno zamenjavo. Število zamenjav nato le seštejmo.

• število obeh oklepajev je liho

V tem primeru bo število zamenjav navzgor zaokroženo število m/2 + navzgor zaokroženo število n/2 , ki jih na koncu seštejmo. Če imamo na primer tri zaprte oklepaje '}}}' in en odprt oklepaj '{' bo število zamenjav enako vsoti navzgor zaokoroženemu številu 3/2 + navzgor zaokroženemu številu 1/2, kar je 2 + 1 = 3.

Če rešitvi združimo in v pythonu uporabimo funcijo math.ceil, bi rešitev imela obliko:

V mojem primeru sem se v izogib funkcije math.ceil uporabila celoštevilsko deljenje, kjer sem v obeh primerih števila oklepajev dodala 1, ter dobila zgornjo formulo, ki je tudi uporabljena v implementaciji kode v pythonu.

Moja naloga je bila implementirati dva sklada v isto tabelo. Na obeh skladih morata delovati metodi vstavi in odstrani, kjer metodi vstavi v sklada vstavita element ter metodi odstrani vrneta vrhnji element sklada in element tudi odstranita. Naloga od mene zahteva še, da so časovne zahtevnosti teh metod O(1) ter da je hranjenje podatkov prostorsko učinkovito.

Konstruktor razreda dvaSklada izgleda takole:

Lahko, en način bi bil da bi tako kot sedaj 2 sklada hranili v skrajnih koncih tabele, ostale sklade pa med njima. Sklada v skrajnih koncih tabele bi imela vsak le po en kazalec vrhov, skladi med njima pa po 2 kazalca, eden bi kazal na dno sklada ter drugi na vrh. Sklade v sredini bi bilo potrebno premikati levo in desno, saj če bi prišlo do česa takšnega:
[elementi prvega sklada, elementi drugega, elti tretjega, par praznih mest, elti zadnjega]
in bi sedaj želeli vstaviti element v prvi sklad bi morali vse elemente drugega in tretjega sklada premakniti v desno. Pogoji za pregledovanje prostora pa bi bilo malenkost drugačni kot so samo za hranjenje dveh skladov.

Seveda. Kar se zgodi v konstruktorju je inicializacija tabele dolžine n, katere vsi elementi so na začetku None. Ko vstavimo ogromno podatkov v kateregakoli od skladov ne bo nobenega problema, dokler tabela ne bo polna. Metodi odstrani pa se prav tako ne obremenjujeta s številom podatkov v skladih, dokler ne poskusimo odstraniti elementa iz praznega sklada, tako da bi moral algoritem deluje tudi za ogromno število podatkov.

Tabela bi imela ta en element na prvem ali zadnjem mestu, torej bi izgledala tako
[elt, None, None, None, None] ali pa tako
[None, None, None, None, elt].
V prvem primeru, bi bil atribut vrh1 = 0, torej kazal bi na vrh prvega sklada, ki je na indeksu 0. Drugi kazalec vrh2 pa bi imel vrednost, ki mu jo dodelimo na začetku - vrh2 = n, torej v tem primeru vrh2 = 5.
V drugem primeru, kjer pa bi ta en element bil v drugem skladu, bi kazalca imela sledeče vrednosti: vrh1 = -1 in vrh2 = 4.

Torej če v naprej vemo, da smo prostorsko omejeni in bomo potrebovali 2 sklada, katerih posamezna velikost ni v naprej predpisana... se stvari dela tako XD

Profesor je na vajah obrazložil prav to vprašanje, jaz pa sem si njegov odgovor slabo zapomnil.
Zato odgovor na to vprašanje sledi v ponedeljek, po konzultaciji z njim :) 

Ja, algoritem nemoteno deluje tudi, če mu damo prazno drevo. V tem primeru vrne prazno tabelo povprečnih vrednosti.

Pristopa sta načeloma enakovredna, imata tudi isto časovno zahtevnost. Pri zelo velikih drevesih oziroma pri drevesih z veliko višino je pa boljši pristop BFS (iskanje v širino), saj z njim lažje pregledamo celotno drevo, saj ga pregledujemo po nivojih. Pri DFS (iskanje v globino) se pa lahko pri velikih drevesih zakomplicira, saj moramo priti čisto do konca levega poddrevesa in šele potem pregledati desno poddrevo.

Pri tej nalogi je ključnega pomena, da vsako vozlišče obiščemo natanko enkrat, se pravi je karakteristična operacija obisk vozlišča, saj potem lahko seštejemo vse vrednosti vozlišč na vsakem nivoju.

Ja, algoritem se izvede tudi za negativna števila in lahko vrne tudi negativno povprečje nivoja.

V bistvu pri BFS ne vemo na katerem nivoju smo (npr. ali smo na četrtem ali petem nivoju). Funkcija nikjer ne izpisuje število trenutnega nivoja, le sešteva vse vrednosti vozlišč in prešteje, koliko jih je. Ko vozlišča iz pomožne vrste vstavimo v vrsto vemo, da smo s pregledovanjem trenutnega nivoja končali, vendar ne vemo kateri nivo je to. Lahko pa v kodi dodamo novo spremenljivko za trenutni nivo, ki jo po tem, ko vsak nivo pregledamo, povečamo.

Pri BFS pa moramo vedeti kje smo, zato bi v sklad dodajali dva podatka, vrednost vozlišča in nivo, na katerem se to vozlišče nahaja, saj dokler ne pregledamo celotnega levega poddrevesa se ne premaknemo na desno poddrevo.

Ja, dalo bi se. Pri tem bi sosede dodajali v sklad, najprej pregledamo koren, nato levo poddrevo in na koncu desno poddrevo. Kot sem že odgovorila pri prejšnjem vprašanju, v sklad dodajamo dva podatka, vrednost vozlišča in nivo, na katerem se to vozlišče nahaja.

Lahko bi šlo tudi s tabelo. Pri vrsti je pomemben vrstni red, zanašamo se na FIFO (first in first out), pri tabeli bi se tako morali sklicevati na indekse. V tem primeru bi se naša tabela morala obnašati kot vrsta.

Pristop deluje tudi za drevo, ki ni dvojiško, saj sta tako BFS kot DFS definirana za poljuben graf. Namesto kvečjemu 2 sinova bi imeli več sinov, in bi se posledično sklicevali ne le na levo in desno poddrevo, ampak na več poddreves.

Ja, prvi predstavljeni algoritem deluje v vseh drevesih ne glede na to ali je dvojiško iskalno drevo ali ne.

Žal, moj algoritem vrne samo en par števil. Obstaja sicer način, ki je podoben algoritmu s tabelo, le da pri tem uporabimo sklad. Na začetku bi imeli dva prazna sklada in bi potem uporabili „prednost“ da delamo s dvojiškim iskalnim drevom.  V prvi sklad bi dali najbolj leva vozlišča skupaj s korenom, ki bo prvi element prvega sklada;  v drugi sklad pa najbolj desna vozlišča skupaj s korenom, ki v tem primeru bo zadnji element našega sklada. Na enak način kot pri predstavljenemu algoritmu bi primerjali vsote. Imamo spet dve puščici ki kažeta na vrh prvega in drugega sklada.

Na podoben način pregledujemo vsote parov števil na kateri kažeta puščici, ter ustrezno „potiskamo“ navzdol. Več o tem si lahko preberete tudi na spletni strani: https://www.geeksforgeeks.org/find-all-the-pairs-with-given-sum-in-a-bst-set-2/

Prosim, glej prejšnji odgovor.

Na podlagi meritev ki sem jih opravila, iskaže se da je drugi algoritem malce hitrejši.

 Iskaže se, da je algoritem s pomočjo množice najhitrejši, kar pomeni da se ga najbolj splača izbrati.

Časovna zahtevnost algoritma s tabelo je O(n), kjer n predstavlja število elementov v tabeli.

Najbolj primeren pristop je pregled elementov s pomočjo množice.

spomnimo se zadnjega algoritma: v urejenem seznamu seštevamo elemente na način, da seštejemo en element iz leve strani z elementom z desne strani in nato ustrezno se premikamo k večjemu/manjšemu elementu v tabeli.

Pri zadnjem algoritmu se zanka ustavi ko je levo == desno; oziroma ko se „puščici sprimeta“.

V vozliščih so lahko tudi negativna števila.

Dejstvo da delamo z dvojiškim iskalnim drevesom nam lahko pomaga pri brute force algoritmu, kjer si izberemo eno vozlišče in primerjamo z ostalimi vozlišči. Ker vemo da so v dvojiškem iskalnem drevesu levo od korena števila, ki so manjša;  desno pa števila, ki so večja od korena, lahko si na podlagi razlike med dano vsoto in izbranega vozlišča olajšamo delo in pregledujemo samo eno stran drevesa.

Recimo, pri drugem algoritmu elemente vstavljamo v množico, kjer ponovljenih elementov ni. Pri tretjem algoritmu pa drevo itak preoblikujemo v urejeni seznam.

Algoritma, ki sem ju opisala, vrneta le odgovor (True ali False) ali neusmerjen graf (povezan ali nepovezan) vsebuje cikel ali ne. Odgovor vrneta po prvem najdenem ciklu. Bi se pa seveda oba algoritma dalo preoblikovati tudi tako, da bi vračala število ciklov ali pa vozlišča v ciklu ipd. Seveda pa vsaka taka implementacija zahteva še nekaj dodatnega dela.

Oba algoritma imata enako časovno zahtevnost, vendar pa je prostorska zahtevnost različna. Pri BFS si mora algoritem hraniti podatke vseh vozlišč v posameznem nivoju, medtem ko se lahko DFS zapiše tako, da hrani podatke le svojega predhodnika. Iz tega razloga se drug algoritem uporablja nekoliko pogosteje, še posebej pri večjih grafih.

Implementacija razreda Graf in algoritmov, ki sem jih zapisala je bazirana na povezavah med vozliščih. Torej je velikost problema število povezav. V najboljšem primeru, lahko cikel zaznamo že takoj na začetku in je tako časovna zahtevnost konstantna. V najslabšem primeru, ko pa graf ne vsebuje cikla, pa se moramo pri obeh algoritmih sprehoditi po vseh teh povezavah. Zato je v tem primeru časovna zahtevnost O(E), kjer je E število povezav.

Poleg iskanja cikla, se algoritma lahko uporabljata tudi na mnogih drugih problemih.

BFS je predvsem učinkovit za iskanje najkrajše poti med dvema poljubnima vozliščema v grafu, ugotavljanje ali je graf dvodelen pa tudi za pomoč pri reševanju Rubikove kocke in iskanju sosednjih lokacij pri navigaciji.

DFS pa se uporablja pri topološkem urejanju, ugotavljanju ali je graf 2-povezan, ugotavljanju ali je graf ravninski ter reševanju ugank z eno samo rešitvijo, kot sta labirint in sudoku.

Vprašanja ne razumem popolnoma. Pri obeh algoritmih obiščemo vsako vozlišče (če seveda prej ne najdemo cikla), iz katerega začnemo pa je popolnoma vseeno, saj tudi če bomo začeli v nekem vozlišču recimo znotraj levega poddevesa, bomo s časom obiskali tudi sam koren drevesa, ali obratno. Oba algoritma sta tako (v primeru, da graf ne vsebuje cikla) le dva načina pregleda grafa.

Velikost problema je število vozlišč n, število operacij za določeno vozlišče, pa je v najslabšem primeru log(n). Torej je časovna zahtevnost za predstavljen algoritem O(n*log(n)).

Prostorska zahtevnost za dani algoritem je kar število vozlišč drevesa, torej O(n).

Prednost je ta, da lahko v primeru, ko imamo res veliko dvojiško drevo, si lažje predstavljamo, katera vozlišča se prekrivajo.

Algoritem seveda deluje tudi za negativne vrednosti vozlišč. Prilagam kodo in primer drevesa, z nekaterimi negativnimi vrednosti vozlišč, kjer lahko sami preizkusite, da deluje.

 

Primer: drevo =

Drevo(28,levo=Drevo(23,levo=Drevo(222,levo=Drevo(13),desno=Drevo(5)),desno=Drevo(25,levo=Drevo(5),desno=Drevo(66))),desno=Drevo(43,levo=Drevo(2,levo=Drevo(-12),desno=Drevo(-7)),desno=Drevo(93,levo=Drevo(-3),desno=Drevo(103))))

Dejansko nam x-koordinata pove na kateri vertikali je poljubno vozlišče. Torej, če bi nam bila prioriteta, da vemo na kateri navpičnici je posamezno vozlišče, bi potem samo poleg vrednosti vozlišča izpisali zraven še x-koordinato, kot nek par vrednosti.

Če vi drevo obhodili po nivojih, potem ne bi vedeli katera vozlišča se prekrivajo, saj ne vemo na kateri navpičnici so vozlišča, ampak vemo samo na kateri horizontali so. Torej če bi imeli naslednje drevo:

Naslednji:

6

5, 53

22, 33, -1, 7

0

 

Več o obhodu po nivojih pa si lahko preberete na spletni strani: https://www.geeksforgeeks.org/print-level-order-traversal-line-line/

Ta algoritem pregleda drevo in izpiše seznam seznamov. V vsakem seznamu so vrednosti vozlišč na isti vertikali, po vrstnem redu od zgoraj navzdol.

Vertikalen pregled bi bil uporaben, kadar bi želeli vedeti katera vozlišča se prekrivajo v drevesu. Ko imamo podano neko dvojiško drevo si ne moremo tega predstavljati, ampak če pa imamo napisane koordinate vozlišč pa lahko vidimo katera vozlišča imajo iste koordinate.

Torej kot sem že omenila  v prejšnjih odgovorih: Vertikalen pregled bi bil uporaben, kadar bi želeli vedeti katera vozlišča se prekrivajo v drevesu. Ko imamo podano neko dvojiško drevo si ne moremo tega predstavljati, ampak če pa imamo napisane koordinate vozlišč pa lahko vidimo katera vozlišča imajo iste koordinate.

Časovna zahtevnost je O(n). Vemo, da bomo enkrat šli čez vse elemente vhodne vrste. Na vsakem koraku se nam lahko zgodi, da kakšen element sklada izbrišemo torej naredimo več kot eno primerjavo. Teh primerjav pa ne more biti poljubno mnogo saj več kot jih je na enem koraku manj jih bo na naslednjem, ker se sklad prazni. Iz tega potem sklepamo, da očitno nimamo več kot linearne časovne zahtevnosti.

Prostorska zahtevnost pa je tudi O(n) saj samo napolnimo sklad z n elementi (najslabši primer).

Poglejmo primer:

Vhodna vrsta = [2,3,1,4,5], izhodna vrsta = [5, 3, 2, 1, 4].

Opazimo, da če imamo v izhodni vrsti element (v primeru je ta 5), ki se nahaja na koncu vhodne vrste, obstaja samo ena rešitev in sicer obraten vrstni red vhodne vrste. Za zgornji primer bi torej dobili, da izhodna vrsta ni skladna permutacija vhodne vrste, če pa bi izhodna vrsta bila [5, 4, 1, 3, 2] bi imeli skladno permutacijo. Sedaj je vprašanje ali se nam bi splačalo ta primer obravnavati v programu. Po mojem mnenju se nebi, saj če imamo za izhodno vrsto podano naključno generirano permutacijo je verjetnost, da je v njej prvi element zadnji element vhodne vrste enaka 1/n, kjer je n število elementov. Kot vidimo bi nam implementacija te zaustavitve pomagala pri približno 1/n primerih torej zelo malo če imamo opravka z dolgimi permutacijami.

Ne, saj če pomislimo vidimo, da si z vrsto ne moremo pomagati pri spreminjanju vrstnega reda. Če elemente vstavljamo v vrsto bodo ostali v enakem vrstnem redu.

Mislim, da vprašanje govori o skladnih permutacijah vrste. Same eksplicitne formule za vse možne skladne permutacije n elementov sicer nimamo (kot jo imajo vse možne permutacije n!), vendar lahko povem to, da jih je v primerjavi z vsemi torej n! zelo malo.

Če imamo 3 elemente ima vsaka permutacija med njimi 5 možnih skladnih permutacij. To pomeni, da če vzamemo vrsto s tremi elementi (vrstni red poljuben) in dobimo eno od njenih permutacij, le v enem primeru le-te ne moremo dobiti s permutacijo s skladom.

Primer: iz vhodne vrste [1,3,2] ne moremo dobiti s pomočjo sklada permutacije [2,1,3] (to se zlahka vidi iz odgovora na zgornje vprašanje Ali se lahko kdaj hitro opazi, da ne gre za permutacijo?).

Torej je skladnih permutacij za vrsto s tremi elementi 5 v primerjavi z vsemi ki jih je 3! = 6.

Za vrsto s štirimi elementi je skladnih permutacij 14 od vseh možnih 4! = 24.

Za vrsto s petimi elementi je skladnih permutacij 42 od vseh možnih 5! = 120.

Za vrsto s šestimi elementi je skladnih permutacij 132 od vseh možnih 6! = 720.

Za vrsto s sedmimi elementi je skladnih permutacij 429 od vseh možnih 7! = 5040.

Za vrsto s osmimi elementi je skladnih permutacij 1430 od vseh možnih 8! = 5040.

Za vrsto s devetimi elementi je skladnih permutacij 4862 od vseh možnih 9! = 362880.

Iz zadnje lahko razberemo, da je skladnih permutacij okoli 1% vseh možnih če imamo v vrsti več kot 9 elementov, torej njihovo število res zelo hitro pada.

Moja rešitev nebi delovala dobro če bi se lahko elementi ponavljali. Vendar če pomislimo vemo, da ko govorimo o permutacijah imamo v mislih množico, kjer se elementi ne ponavljajo. Torej če za permutacije velja, da se morajo elementi razlikovati med seboj sem mnenja, da to velja tudi za permutacije s skladom.

Predstavil sem dva možna načina, kako lahko problem rešimo. En način(brute force) ima časovno zahtevnost O(n^2), drugi pa ima časovno zahtevnost O(n).

Druga metoda je boljša od prve in bo tudi vedno delovala. Zanimivost, ki sem jo povedal je, da otroci, ki imajo isto oceno ne-nujno dobijo isto število sladkarij. Na sliki vidimo dva otroka za oceno 3, vendar en dobi 2 sladkariji, drug pa samo 1.

Sladkarije moramo vedno razdeliti. Prvi pogoj je, da vsak otrok dobi vsaj eno sladkarijo.

Problem se da rešiti še na en način, kjer uporabimo samo eno spremenljivko. Pri tem načinu gledamo naraščanja in padanja ocen po tabeli. Za globjo razlago predlagam ogled https://medium.com/javarevisited/how-to-solve-the-minimum-candy-distribution-problem-4c868740f16a kjer je razložen ta način.

Potem pa bi vsi dobili samo eno sladkarijo in bi tako potrebovali le n sladkarij. Prvi pogoj bi bil izpolnjen in noben od otrok nima večje ocene od sosedov, torej nihče ne dobi več kot eno sladkarijo.

Najbolje je gledati koliko otrok zapored ima večjo oceno od svojega soseda. Recimo na primeru bi se otroku z oceno 7 bolj splačalo postaviti za eno mesto bolj levo(desno od otroka z oceno 5) in bi dobil 5 sladkarij namesto samo 2.

Časovne zahtevnosti ne bi mogli zmanjšati pod O(n), lahko pa izboljšamo prostorsko zahtevnost na O(1), kjer bi uporabili samo eno spremenljivko.

Izkaže se, da je važno koliko otrok ima “zapored” večjo oceno od svojega soseda(vsi od istega soseda, recimo da imajo trije otroci večjo oceno od svojega levega soseda zapored kot na sliki imajo otrok z oceno 3, oceno 4 in oceno 5). Torej če pogledamo kako ocene naraščajo od leve proti desni, potem pa še od desne proti levi, bo max obeh rešitev za posameznega otroka pravilna.

Nekako tako ja. Seveda je sama ocena še vedno pomembna, saj otroci, ki bodo imeli najmanjšo oceno, bodo vedno dobili le eno sladkarijo, zato  se splača imeti višjo oceno .

Da bo poraba največja, jih postavimo v naraščajoči/padajoči vrstni red, da bo vsak imel eno sladkarijo več od soseda in bo zato naraščanje sladkarij večje. Moramo pa paziti, da če imamo otroke z itso oceno, jih ne postavimo enega za drugim, saj s tem uničimo to metodo, zato na koncu prve razporeditve naredimo še eno(in še eno, glede na to, koliko otrok ima isto oceno). Glej sliko 1 za primer. Da jih porabimo najmanj, pa tako da ocene čim več “skačejo” gor in dol. Torej bi na prvo mesto dali nekoga z visoko oceno, na drugo mesto nekoga, ki ima manjšo od prvega, potem na tretje nekoga, ki ima večjo od drugega, na četrto spet nekoga, ki ima manjšo od tretjega. glej sliko 2. Vidimo, da v primeri 1 potrebujemo 18 sladkarij, v primeru 2 pa 10

Ja, če imajo vsi enako oceno. V tem primeru bi vsi dobili eno sladkarije. Da bi vsi dobili recimo 2 sladkariji pa je nemogoče. Otrok, ki bo imel najmanjšo oceno bo vedno imel le 1 sladkarijo, ne glede na sosede in ne bo nikdar imel dveh ali več sladkarij.