Forum » Programiranje » Grafi (Kruskal, Dijkstra,...)
Grafi (Kruskal, Dijkstra,...)
robinzon ::
Pozdravljeni!
Ucim se za izpit iz Algoritmov in podatkovnih struktur in me bega nekaj vprasanj iz teorije grafov.Prosil bi ce poleg odgovora, podate vsaj kako skopo razlago. hvala vnaprej vsem dobrim dusam, ker sem res ze v dreku....
ALI BI ALGORITMI DELOVALI, ČE JE IZPOLNJEN EDEN OD SPODNJIH POGOJEV:
1.namesto najkrajših poti iščemo najdaljše oziroma obratno tako, da samo zamenjamo pogoje večji-manjši
2.ima graf cikle
3.imajo povezave tudi negativne dolžine
4.če je graf ena sama pot?
5.če je graf nepovezan?
6.imajo lahko povezave v grafu tudi dolžine enake 0 ?
7.če je graf en sam cikel
A) KRUSKALs ALGORITHM
1.ne.
2.
3.da.
4.
5.
6.
7.
B) PRIMs ALGORITHM
1.da
2.ne
3.da
4.
5.
6.
7.
C) DIJKSTRAs ALGORITHM
1.da
2.ne
3.ne
4.
5.
6.da
7.
D) Critical Path ALGORITHM ( longest possible path )-->ALGORITMI ZA ISKANJE KRITIČNE POTI
1.da
2.ne
3.da
4.
5.
6.da
7.
Ucim se za izpit iz Algoritmov in podatkovnih struktur in me bega nekaj vprasanj iz teorije grafov.Prosil bi ce poleg odgovora, podate vsaj kako skopo razlago. hvala vnaprej vsem dobrim dusam, ker sem res ze v dreku....
ALI BI ALGORITMI DELOVALI, ČE JE IZPOLNJEN EDEN OD SPODNJIH POGOJEV:
1.namesto najkrajših poti iščemo najdaljše oziroma obratno tako, da samo zamenjamo pogoje večji-manjši
2.ima graf cikle
3.imajo povezave tudi negativne dolžine
4.če je graf ena sama pot?
5.če je graf nepovezan?
6.imajo lahko povezave v grafu tudi dolžine enake 0 ?
7.če je graf en sam cikel
A) KRUSKALs ALGORITHM
1.ne.
2.
3.da.
4.
5.
6.
7.
B) PRIMs ALGORITHM
1.da
2.ne
3.da
4.
5.
6.
7.
C) DIJKSTRAs ALGORITHM
1.da
2.ne
3.ne
4.
5.
6.da
7.
D) Critical Path ALGORITHM ( longest possible path )-->ALGORITMI ZA ISKANJE KRITIČNE POTI
1.da
2.ne
3.da
4.
5.
6.da
7.
demoness ::
Dej ne bodi taka lenoba, odpri Kononenkovo knjigo in si preberi algoritme, pa poskušaj naštete primere miselno "vstavit" noter, pa ti bo takoj jasno, kaj ne dela in zakaj ne. Itak jih moraš razumet, če bi rad izpit naredil.
Don't you want to die, walk beside me evermore,
Don't you feel alive, like you never felt before...?
Don't you feel alive, like you never felt before...?
Realist ::
Rabil bi malce pomoci izkusenejsih kolegov pri casovni kompleksnosti,ki mi niso cisto jasne.
Bi mi kdo lahko podal algoritme s povprecnimi casovnimi zahtevnostmi in sicer
O(logn)
O(n)
O(n^2)
O(2^n)
O(n^m)
Kaj sploh pomeni ta O(n) ?
Rabil bi cimbolj simple primere teh funkcij..
Bolj kot gledam, manj mi je jasno tole..
Bi mi kdo lahko podal algoritme s povprecnimi casovnimi zahtevnostmi in sicer
O(logn)
O(n)
O(n^2)
O(2^n)
O(n^m)
Kaj sploh pomeni ta O(n) ?
Rabil bi cimbolj simple primere teh funkcij..
Bolj kot gledam, manj mi je jasno tole..
Seadoo ::
Ja tudi meni se zdi da so to prepisana vprašanja iz izpitov.
Realist: tudi ti si preberi knjigo. Rad bi primere algoritmov z časovnimi zahtevnostmi, pa sploh ne veš kaj to je!!!
Realist: tudi ti si preberi knjigo. Rad bi primere algoritmov z časovnimi zahtevnostmi, pa sploh ne veš kaj to je!!!
Realist ::
Ja rabim jih zato ker moram nujno seminarsko narediti. Poleg tega v knjigi ni primerov..Ce bi imel en trivialen primer bi slo precej lazje..
Pa daj malce razlozi, ce ti je to bolj jasno. Prosim.
Pa daj malce razlozi, ce ti je to bolj jasno. Prosim.
jype ::
O(n) = linearna zahtevnost: toliko kot je elementov, toliko casa traja resitev problema
O(log n) ne bos nikjer dobil, ker samo branje n elementov iz spomina vzame O(n) casa.
O(n log n) je zahtevnost npr. quicksort algoritma (D. Knuth, The Art of Programming).
O(n^2) je kvadratna zahtevnost.
for (x=0;x<n;x++) for (y=0;y<n;y++) dosomething(x,y); Butast(tm) bubblesort rabi toliko.
O(2^n) je eksponentna zahtevnost. Ne spomnim se nobenega primera. Tak algoritem je ponavadi ze zelo slab.
O(n^m) je isto kot kvadrat, ce je m=2, slabse, ce je m vecji, boljse, ce je m manjsi. Ce je m=1 je to linearna casovna zahtevnost O(n).
O(log n) ne bos nikjer dobil, ker samo branje n elementov iz spomina vzame O(n) casa.
O(n log n) je zahtevnost npr. quicksort algoritma (D. Knuth, The Art of Programming).
O(n^2) je kvadratna zahtevnost.
for (x=0;x<n;x++) for (y=0;y<n;y++) dosomething(x,y); Butast(tm) bubblesort rabi toliko.
O(2^n) je eksponentna zahtevnost. Ne spomnim se nobenega primera. Tak algoritem je ponavadi ze zelo slab.
O(n^m) je isto kot kvadrat, ce je m=2, slabse, ce je m vecji, boljse, ce je m manjsi. Ce je m=1 je to linearna casovna zahtevnost O(n).
sid_dabster ::
Pas zeca, ampak to pa celo jaz vem, pa sem z elektro faksa
Potem pa se clovek vprasa, kaksne inzenirje bomo imeli, ce bo slo tako dalje...
To se mi zdi ravno tako hudo, kot ce stromar v drugem letniku faksa ne bi vedel, kaj sta to kirchoffova zakona...
Whatever...
Potem pa se clovek vprasa, kaksne inzenirje bomo imeli, ce bo slo tako dalje...
To se mi zdi ravno tako hudo, kot ce stromar v drugem letniku faksa ne bi vedel, kaj sta to kirchoffova zakona...
Whatever...
Fallen beyond all grace deeper and deeper
The sound of her own blood dripping
Like sacred tears from a bleeding rose...( Embraced, Within)
The sound of her own blood dripping
Like sacred tears from a bleeding rose...( Embraced, Within)
Sergio ::
Malo bi popravil jypovo izjavo
>>O(log n) ne bos nikjer dobil, ker samo branje n elementov iz spomina vzame O(n) casa.
O(log n) dobis, ce v binarnem drevesu poisces element. Aplikacij casovne zahtevnosti je poleg prej nastete se ogromno.
>>O(log n) ne bos nikjer dobil, ker samo branje n elementov iz spomina vzame O(n) casa.
O(log n) dobis, ce v binarnem drevesu poisces element. Aplikacij casovne zahtevnosti je poleg prej nastete se ogromno.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Realist ::
Gorezh: Zivjo!
Ves kaj ti bom rekel.. Saj ni tako hudo kot sem napisal, a vseeno. Na fax sem bolj malo hodil, ker sem vecino casa delal. In ko enkrat pricnes delat, ugotovis, da tovrstnih stvari niti ne potrebujes po studijuin da se v vecini primerov v firmi kjer delas moras uciti cisto na novo. Tovrstno znanje pa ti pride prav ce gres potem za raziskovalca in teras teorijo naprej. Na predavanja sem hodil ze dolgo nazaj, tako da sem ze vse pozabil.Narediti moram se seminarsko in glede na to da vmes delam mi gre vse skupaj zelo na tesno. Zato sprasujem tu.
Sedaj sem ze nasel ustrezne algoritme, potrebujem samo se algoritma za
O(n^m) - kaj smiselnega bi rabil, pa da ga je mozno dokaj enostavno pretvoriti v rekurzijooz.obratno
O(2^n)- prav tako kaj smiselnega... ali pa tudi ne... vazno da je.
Ves kaj ti bom rekel.. Saj ni tako hudo kot sem napisal, a vseeno. Na fax sem bolj malo hodil, ker sem vecino casa delal. In ko enkrat pricnes delat, ugotovis, da tovrstnih stvari niti ne potrebujes po studijuin da se v vecini primerov v firmi kjer delas moras uciti cisto na novo. Tovrstno znanje pa ti pride prav ce gres potem za raziskovalca in teras teorijo naprej. Na predavanja sem hodil ze dolgo nazaj, tako da sem ze vse pozabil.Narediti moram se seminarsko in glede na to da vmes delam mi gre vse skupaj zelo na tesno. Zato sprasujem tu.
Sedaj sem ze nasel ustrezne algoritme, potrebujem samo se algoritma za
O(n^m) - kaj smiselnega bi rabil, pa da ga je mozno dokaj enostavno pretvoriti v rekurzijooz.obratno
O(2^n)- prav tako kaj smiselnega... ali pa tudi ne... vazno da je.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | [c++] nalogeOddelek: Programiranje | 6234 (4774) | technolog |
| » | Quick sortOddelek: Programiranje | 2517 (1265) | drola |
| » | Časovna zahtevnostOddelek: Programiranje | 3115 (2659) | technolog |
| » | C++, časovna zahtevnostOddelek: Programiranje | 1732 (1601) | ERGY |
| » | Išče se hiter algoritem za izračun ene čudne matrične operacije.Oddelek: Znanost in tehnologija | 2209 (1700) | Thomas |