 |
Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kap00ch
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów
Skąd: ja sie tu wzialem?
|
 Wysłany: Śro 19:37, 31 Maj 2006 Temat postu: |
|
|
|
od bidy mozna zapuscic brutala ;pppp
|
|
| Powrót do góry |
|
 |
|
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Madras
Omylny Admin
Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów
Skąd: Z Pokoju :]
|
| Wysłany: Śro 19:49, 31 Maj 2006 Temat postu: |
|
|
|
Dobra, niewyspany dzisiaj jestem ;P.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Śro 20:09, 31 Maj 2006 Temat postu: |
|
|
| Rogal napisał: | | @Robson: To się chyba da zrobić kwadratowo, a może nawet szybciej. Ale nie jestem pewien czy to będzie na 100% działać :wink: |
Hehe...
BTW. A co z tym Dijkstrą? Chodzi o moje ostatnie pytanie... czy chciałeś tylko zmienić relax i/lub inicjowanie tablic na poczatku? Bo mi to spać nie daje...
BTW. Czy ktoś inny pamieta co było na wykładzie o tych najdluzszych sciezkach? Serio sie pytam, nie dlatego ze to ma być na kolosie, ale tak z czystej złos... ciekawości ;)
hansu? Ty sie przeciez ze Slumanem o to kłuciłeś, i nawet omal mu nie opchnołeś dowodu ze P = NP ;)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Śro 20:20, 31 Maj 2006 Temat postu: |
|
|
|
No ja bym to zrobil klasycznie Bellmanem-Fordem, bez jakiegos kombinowania z Dijkstra czy innym dziadostwem... Przeciez tak naprawde znak nie jest problemem: jezeli odpowiednio "zmirrorujemy" zalozenia Bellmana-Forda to to wszystko bedzie chodzic az milo... A ta dyskusja z drem Slusarkiem to byla wlasnie przy innych zalozeniach niz mirror BFa... Co nie zmienia faktu ze prawie go przekonalem ze P = NP... ;) Ale jeszcze kiedys mi sie uda to udowodnic :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
ostoj
Przewijak Tasmy
Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów
Skąd: Tychy
|
| Wysłany: Śro 20:28, 31 Maj 2006 Temat postu: |
|
|
|
hansu, moglbys zdefiniowac '"zmirrorujemy" zalozenia Bellmana-Forda'?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Śro 20:37, 31 Maj 2006 Temat postu: |
|
|
|
Wyjsciowy grafo powinien spelniac zalozenie: nie posiada cykli dodatnich (no bo wtedy nie istnieje najdluzsza sciezka). Wtedy zmieniamy wagi krawedzi na przeciwne i mamy graf bez cykli ujemnych. W nim wyszukujemy najkrotsza sciezke z a do b. Po odwroceniu wag z powrotem sciezka ta stanie sie najdluzsza. To jest oczywiscie rozwiazanie modelowe, wiadomo ze jakby co to nie bedzie sie przebiegac calego grafu i zmieniac wag sciezek tylko wystarczy odpowiedznio zmienic relax (ew przeladowac operator < zeby dzialal jak > :P)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Śro 20:44, 31 Maj 2006 Temat postu: |
|
|
| hansu napisał: | | Ale jeszcze kiedys mi sie uda to udowodnic :P |
Nie wątpię... ;)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Fidel
żul
Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów
Skąd: Kraków
|
| Wysłany: Śro 20:56, 31 Maj 2006 Temat postu: |
|
|
| kap00ch napisał: | | rogal nie jest (jeszcze?) az taka lamka zeby na publica dawac leaka :> |
a kap00ch rymuje :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kap00ch
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów
Skąd: ja sie tu wzialem?
|
| Wysłany: Śro 20:57, 31 Maj 2006 Temat postu: |
|
|
|
ha! wiedzialem ze w koncu ktos zauwazy :P
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Skrobocik
[SKROBORANGA]
Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów
Skąd: Skarżysko , Kraków
|
| Wysłany: Śro 21:04, 31 Maj 2006 Temat postu: |
|
|
Ja tylko chciałem przypomnieć wszystkim, że jutro mamy kolokwium z Algorytmów i Struktur Danych :wink:
(To tak jakby wszyscy zapomnieli, dżast in kejz) :twisted:
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Śro 21:07, 31 Maj 2006 Temat postu: |
|
|
|
a nie z Algebry?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kap00ch
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów
Skąd: ja sie tu wzialem?
|
| Wysłany: Śro 21:09, 31 Maj 2006 Temat postu: |
|
|
|
o qfa to juz jutro? a z czego ma byc?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Śro 21:13, 31 Maj 2006 Temat postu: |
|
|
| Skrobocik napisał: | Ja tylko chciałem przypomnieć wszystkim, że jutro mamy kolokwium z Algorytmów i Struktur Danych :wink:
(To tak jakby wszyscy zapomnieli, dżast in kejz) :twisted: |
:LOL:
moze jakieś zakłady co bedzie?
Ja stawiam:
1. Spójne składowe w grafie nieskierownym (na rozgrzewke powiedzieli ze bedzie łatwe ;) )
2. Insert/Delete/Rotacje z AVLi :P
3. Algorytm Prima/Jarnika MST
4. metoda offline znajdowania najkrotszej sciezki majac dane oszacowania i graf... (wiem proste, ale moze beda chcieli sprawdzic kto na wykład chodzi)
5. DAG-Paths?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Śro 21:13, 31 Maj 2006 Temat postu: |
|
|
sortowanie bąbelkowe
edited: Robson co to jest ten offline z pkt. 4?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kap00ch
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów
Skąd: ja sie tu wzialem?
|
| Wysłany: Śro 21:15, 31 Maj 2006 Temat postu: |
|
|
eee? wtf z tym offline? :P
i nie nie tylko nie delete z AVLi :D blagam...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Madras
Omylny Admin
Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów
Skąd: Z Pokoju :]
|
| Wysłany: Śro 21:31, 31 Maj 2006 Temat postu: |
|
|
|
No chodzi o to, ze nie bedziesz mial dostepu do neta...
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Śro 21:33, 31 Maj 2006 Temat postu: |
|
|
Zadanie:
Zapominalski Bajtazar policzył w Grafie G wszystkie najkrotsze odleglosci z wierzcholka 1 do pozostałych, ale zapomniał je (sciezki) zapamietać. Jego trudna praca nie moze sie zmarnować! Pomoz Bajtazarowi! Majac dane D[u] dla kazdego u nalezacego do grafu - dlugosci najkrotszych sciezek z 1 do u i Graf G, znajdz dla kazdego u P[u] takie ze P[u] jest poprzednikiem u w najkrotszej sciezce z 1 do u
enjoy it :)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Śro 21:37, 31 Maj 2006 Temat postu: |
|
|
|
@Robson: Czy to można zrobić szybciej niż kwadratwo?
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Śro 21:42, 31 Maj 2006 Temat postu: |
|
|
hmmmm... dla wszystkich wierzcholków chyba nie.
Wiem ze dla jednego (ustalonego) b mozna zrobić (n+m)
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
hansu
Nieomylny Admin
Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów
Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?
|
| Wysłany: Śro 21:49, 31 Maj 2006 Temat postu: |
|
|
|
No mnie sie wydaje ze da sie to zrobic w O(E)... ale moge sie mylic, bo z okreslania zlozonosci algorytmow grafowych leze :/
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kap00ch
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów
Skąd: ja sie tu wzialem?
|
| Wysłany: Śro 21:49, 31 Maj 2006 Temat postu: |
|
|
|
nie tyle co mozna a nawet trzeba :P i to w rowniusienkim (m+n) :]
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Śro 21:50, 31 Maj 2006 Temat postu: |
|
|
Jak?
edited: Dobra, już wiem, mam zaćmienie mózgowe.
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
kap00ch
Mistrz grilla
Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów
Skąd: ja sie tu wzialem?
|
| Wysłany: Śro 21:51, 31 Maj 2006 Temat postu: |
|
|
|
a nic :]
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Rogal
Zjeb z kaszanką
Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów
Skąd: koło podbiegunowe
|
| Wysłany: Śro 21:55, 31 Maj 2006 Temat postu: |
|
|
Dłuższa sygnatura się nie zmieści. Licz na łaskawość funkcji losującej 8)
@Kap00ch: cheater! :twisted:
Ostatnio zmieniony przez Rogal dnia Śro 21:55, 31 Maj 2006, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
Robson
zielony żul
Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów
Skąd: Z Lasu :]
|
| Wysłany: Śro 21:55, 31 Maj 2006 Temat postu: |
|
|
@hansu: Poczytaj notatki dr Slusarka:
| notatki z ASD napisał: |
Typowe oznaczenie: |V|= n, |E| = m.
|
teraz juz wiesz :P
@kap00ch: Masz racje ;)
@Rogal: info^.next := @12_Grafy_3.doc;
|
|
| Powrót do góry |
|
|
|
|
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Szukaj
Użytkownicy
Grupy
Galerie
Rejestracja
Zaloguj się, by sprawdzić wiadomości
Zaloguj
