[NAISP] Gradivo

pero122

Bobicki Pa ja predlazem neku kombinaciju slajdova + pogledat neke algoritme na yt jer neke stvari je teško skužit preko prezentacije te onda rokove riješavat, ali ofc ovo ovise o pojedincu jer neko voli odma skočit u ispite, a neko prvo proć sve preze.

doakes

Je li netko znao onda kako rješiti točno oni zadnji zadatak i oni sa B stablom 2. reda??
Mislim da nije u redu da nam tako komplicira živote sa glupim ispitima i 70% pragom

pero122

doakes Hmmm ja nisam siguran, ali ja sam doslovce to napravio ko obično binarno stablo… doslovce ne znam kak bi drugačije, mozda @M̵̧̩͑̀͝î̶͍̉ć̴̝̾́̀o̶̺̟̣͂̽ ima neku ideju

Kad vec postavljamo pitanje jel zna neko teorijsku pitanja ovo za T/N?
. (5; –5) Koje su tvrdnje istinite?
a) Dinamičko programiranje je posebna vrsta (grana) linearnog programiranja.
b) Kada je primjenjiva lakoma (greedy) strategija, primjenjivo je i dinamičko programiranje.
c) Kada je primjenjivo dinamičko programiranje, primjenjiva je i lakoma (greedy) strategija.
d) Nužan uvjet za primjenu dinamičkog programiranja je preklopljenost podproblema
(overlapping subproblems), a dovoljan optimalna podstruktura (optimal substructure)
problema.
e) Nužan uvjet za primjenu dinamičkog programiranja je optimalna podstruktura (optimal
substructure) problema, a dovoljan preklopljenost podproblema (overlapping subproblems)

TentationeM

doakes Mislim da je caka bila da čvorovi mogu biti prazni. Zapravo meni je pola stabla bilo prazno na kraju. Mislim da sam ga čak dobro napravio, kad stignu rezultati ako jesam stavim svoje rješenje.

doakes

teslaFan Provjerio sam na prezentacijama i jos neznam sta je tocno sta netocno, jer nepise nigdi za nuzne i dovoljne uvjete i ostalo

TentationeM

doakes Tko bi ga znao, ovaj put je valjda sve bilo moguće, onaj s grafom je zaista brzo bio rješiv u 5 minuta, a u njega sam dosta siguran.

teslaFan Ja sam stavio [F F T F F] - ali stvarno nisam siguran u ovo.

doakes

TentationeM ja sam prvo napravio prepostavia da treba napraviti binarno stablo i onda sam od njega uravnotezia sa dsw algoritmom, malo je komplciiranjije bilo al izvedivo, sad neznam jesam li totalno pogrijesio sa idejom

pero122

Jel ima neko neku dojavu da će sigurno dns rezultati ili? Mislim ako je usmeni fkt sutra ujutro ..

TentationeM

doakes To je bila i moja prvotna ideja, ali sam se sjetio da su B-stabla posebna po tome da uvijek rastu u visinu što garantira njihovu uravnoteženost pa sam odustao od klasičnog stabla.

pero122

doakes Yeah… to i mene muci, definitivno se spomenu ti pojmovi, ali ništa u vezi koji je nužan/dovoljan. Btw zar u prezentaciji postoji nešto za a) b) i c) jer ni to nisam našao

doakes

teslaFan ja sam stavio a ) T , b)T, c) N , d) N , e) T , ali to je samo onako bezveze jer nisan htio ostavit sve prazno.

pero122

TentationeM Jel znaš ti možda ta teorijska pitanja?

doakes

TentationeM da ali ako se ide tom teorijom, zadatak se rjesi u 5 minuta pa mi je bilo sumljivo…

micho

TentationeM Ja sam stavio [F F T F F] - ali stvarno nisam siguran u ovo.

E a točno sam si mislio da su ta zadnja dva isti odgovor i da je scam u pitanju, nisam odgovorio na zadnja 2 radi toga jer sam mislio da ću taman biti na granici ali da, mislim da su ti odgovori dobri.

pero122

Lol… sretno momci fkt će nam trebat hahah

doakes

ali ovo je teski tryhard za rokove od njegove strane… previse se trudi zakomlicirat sve

doakes

I zasto stavljat teoriju u pismeni dio ispita ako postoji i USMENI

micho

AFAIK to s B stablom se ponaša kao AVL stablo. Samo je trebalo simulirati prepunjeni čvor, traženje medijana s konzistentnim prioritetom (tj. ili si uvijek birao da ti je 2. element medijan, ili da ti je 1.) i onda samo propagirao ako je što trebalo gore, pa se odvijalo rekurzivno.

Ono što se meni dogodilo je da je cijeli taj mehanizam izgledala kao komplicirana rotacija elemenata, a na kraju je sve izgledalo kao balansirano AVL stablo.

I ne, čvorovi ne mogu biti prazni jer kod B stabla moraš imati popunjenost čvora bar 50% (tako barem piše u prezama). Mislim da to nije striktno pravilo nego posljedica kako se B stablo puni (cijepanje čvorova i korijena, pa ti ni ne može biti ispod 50%)

TentationeM

M̵̧̩͑̀͝î̶͍̉ć̴̝̾́̀o̶̺̟̣͂̽ Ali u prezentacijama isto tako piše:

Svaki čvor, osim korijena i listova, sadrži barem k–1 ključeva i k pokazivača na podstabla (ima k djece), pri čemu je m/2 ≤ k ≤ m (ako rezultat dijeljenja nije cijeli broj, uzima se najmanji veći cijeli broj).

Ako dobro pratim, po tome svaki čvor treba imati barem 1 pokazivač, i barem 0 ključeva, odnosno čvorovi mogu biti prazni. Ja sam rješavao tako da kad god nije bilo prostora u desnom čvoru, rascijepao sam ga na dva, lijevog ostavio praznog, srednjeg proslijedio razinu više, a desnog ostavio kako je. Iako počinjem sve više sumnjati u ispravnost toga.

doakes Ostao sam na kraju kratko pitati Brčića, trebalo je riješiti prvu fazu dvofaznog simpleksa, čime dokažeš da postoje bazična rješenja, odnosno skup je omeđen/neprazan.

doakes

Kako se rješava 6. zadatak, ovi sa je li skup S neprazan?

micho

doakes Ja sam riješio kao sustav jednadžbi i par jednadžbi s rangovima. Tj. našao sam za sve varijable koji su mogući rangovi da jednadžbe budu zadovoljene. Prvo ti je najlakše naći z (za koji vrijedi z \in \left[ 3, \frac{16}{3} \right] ), onda možeš naći y kraćenjem x-eva, i finalno x. Samo mislim da to nije “pravi” postupak jer sam iz toga odmah dobio i odgovor na b) pitanje. Kad ne bi bilo rješenja onda bi mi u nekom koraku trebala naići kontradikcija (npr. x > 3 i x < 2). Ali ja nisam imao nikakvih kontradikcija i brojevi su bili pristojni.

A što se tiče formalno b) zadatka, mislim da se to može riješiti grafički ako fiksiraš z (ili bilo koju drugu varijablu, ali za z je najlakše naći raspon).

pero122

doakes Hmmm nisam siguran, ali ja sam to rješio na onaj dvofazni način. Stoga mi je zapravo ciljna funckija postala min(A1), te ako pokažem da ta funckija ima vrijednost 0, onda i počeni problem ima rješenje stoga nije prazno… To sam po ovom zakljucio

73/90 str u prezi za simpleks

a kaj se tiče b) zadatka nemam pojma

pero122

M̵̧̩͑̀͝î̶͍̉ć̴̝̾́̀o̶̺̟̣͂̽ E ovaj tvoj “bit će za par sati rezultati” jel to neka dojava od profesora/asistena ili jednostanvo pretpostavljas? Kuzis sad ne znam da se rano probudim sutra ili šta da radim lol

« Prethodna stranica Sljedeća stranica »