2. kolokvij (informacija)

[Ivecus]

Jel zna netko koje gradivo ulazi u drugi kolokvij?

_________________
Mihi est propositum in taberna mori!

[Crazylamb1]

Opet bi bilo dobro ak netko zna koje sve gradivo ulazi u drugi kolokvij, plus ako je netko pokusao rijesiti ili ima rjesenja nekih zadataka sa starih drugih kolokvija, ak mozete staviti ovdje, bilo bi super

[frances]

Gradivo (odvojeni pdf - ovi):
- sortiranje
- dinamicko programiranje
- konstrukcije algoritama
- ona velika skripta (od 63. str. do kraja)
- tiskana skripta (od 43. str. do kraja)
____________________________________
148 stranica (samo)

[Crazylamb1]

a fast fourier??

[Tygy]

FFT je od 43 do kraja


Nego, jel netko rješio proslogodišnje kolokvije.... npr one trake....pliiiiiiiiz neka ih pošalje (a može i objavit jer znam da i drugi imaju problem s njima )

[mona]

Ja se slažem, mnogima bi dobro došlo riješenje zadatka s trakama, pa ako bilotko ima, neka podijeli s drugima

[glava]

Nisam 100% ali mislim da bi ovo moglo biti ok:
Dakle pod a) uzmemo sljedeće primjere:

l1 = 1 p1 = 0.04
l2 = 2 p2 = 0.06
l1 = 3 p3 = 0.9
T = 5.6

l1 = 3 p1 = 0.9
l2 = 2 p2 = 0.06
l1 = 1 p3 = 0.04
T = 3.24

i

l1 = 3 p1 = 0.5
l1 = 2 p1 = 0.3
l2 = 1 p1 = 0.2
T = 4.2

l1 = 3 p1 = 0.5
l1 = 1 p1 = 0.2
l2 = 2 p1 = 0.3
T = 4.1

Pod b) gotovo sam siguran da bi poredak trebao ići na način tako da ih sortiramo po omjeru vjerojatnost/duljina trake, tako da onaj s najvećim takvim omjerom ide na prvo mjesto, a onaj s najmanjim na zadnjem. Nisam raspisivao to niti dokazivao, ali mi se na svim primjerima pokazalo da je ok Ako netko to raspiše i vidi da je ok/krivo neka pliz javi ovdje da znam. Pod c) dalje ide bez problema, znaci samo neki sort po tim omjerima napravit.

Added after 6 minutes:

malo sam krivo napisao ove indekse kod l i p znaci ovaj prvi primjer je:
l1, l2, l3 –(optimalnije)→ l3, l2, l1
drugi:
l1, l2, l3 –(optimalnije)→ l1, l3, l2
naravno indeksi vjerojatnosti su isti kao i kod l-ova.

[mona]

Ček, sad sam se ja malo zbunila glava

Znači za a) dio - redoslijed rastući po li:

l1=1, p1=0,04, l2=2, p2=0,06, l3=3, p3=0,9

=> T = p1*l1 + p2*(l1+l2) + p3*(l1+l2+l3) = 5,6

Taj dio je okej

A ovaj drugi:

l3=3, p3=0,04, l2=2, p2=0,06, l1=1, p1=0,04

=> T = 1,32 ?!?!?!

Tu meni nešto krivo ispada, pa ako ti nije problem, napiši opet kako si točno to zamislio

[glava]

znaci stavimo u rastući poredak l1 = 1, sa vjerojatnošću p1 = 0.04, l2 = 2 sa p2 = 0.06 i l3 = 3 sa p3 = 0.9. Sad stavimo na prvo mjesto l3 = 3, njegova vjerojatnost je i dalje p3 = 0.9, (a ne 0.04), pa l2 ostavimo tu di je, a na kraj stavimo l1. Pa je prosječno vrijeme:

T = 3*0.9 + (3+2)*0.06 + (3+2+1)*0.04 = 3.24

Znači ovaj redoslijed gdje nisu duljine poredane uzlazno daje bolje riješenje od ovog prvog gdje su poredane uzlazno.

[Ivecus]

E hvala ti Glava, puno si mi pomogao, karma +

_________________
Mihi est propositum in taberna mori!

[mona]

A da, jesam smotana, fala

[Tygy]

najs.
hoćemo dalje?
još neki...npr 4.2.2009. 1 zad
i dakako, puno hvala na odg

[mona]

E sad... Ja sam probala na par primjera, npr.

t1=2, t2=4, t3=8

Ako poslužujemo redom:

1-2-3, ukupni boravak svih kupaca u trgovini: T = 24

3-2-1, T=36

1-3-2, T=27

Znači, ako sortiramo ti uzlazno i prvo poslužujemo kupce s manjim ti, ukupni boravak je minimalan...

To su sve naklapanja, pa ako netko ima lijepo dokazano/opovrgnuto ovo moje, nek se javi

[Tygy]

ček ček
takve i slične zadatke rješavamo ovak...nađemo si primjer i zaključujemo?????? i onda ak uspijemo to i dokažemo????
štaaa??
pa onda i ni tak teško

Added after 7 minutes:

mona...kak dobiješ te brojeve ta T...?

[mona]

A ne znam jel se tak riješava, al mislim da se nekom zdravom logikom može doć do najoptimalnijeg algoritma

Znači za redoslijed 1-2-3:

1.kupac je u dućanu vrijeme t1=2
2.kupac:
t1 (čeka dok se posluži 1.kupac) + t2 (posluživanje 2.kupca) = 2+5 = 7
3.kupac:
t1+t2+t3=15

Znači, ukupno vrijeme je T = 2+7+15 = 24

Sad analogno za 3-2-1:
3.kupac: 8
2.kupac: 8+5 = 13
1.kupac: 8+5+2 = 15

Ukupno, T=8+13+15 = 36

Ja se nadam da je kolko-tolko razumljivo

[Tygy]

fala mona

[bleki88]

Ako netko zna koje gradivo ulazi ove godine u drugi kolokvij?

[sunny]

Da li netko zna rijesiti 1.a) zadatak iz 2. kolokvija od prosle godine? Evo kolokvij: http://web.math.pmf.unizg.hr/~singer/oaa/oaa_1213/2012_k2.pdf
Trebao bi mi samo kriterij pohlepnosti

[kkarlo]

[sunny]