Informatyka UJ forum

r4ku

jak wszystkim wiadomo, we wtorek 13.06. o godzinie 11:15 jest egzamin z (naszego ulubionego przedmiotu) asd. Jesli ktos jest w posiadaniu dowolnych materialow mogacych pomoc w jego napisaniu to zamieszczajcie je tutaj:)
moze ktos posiada testy z zeszlych lat?

jagm

yy. a nie o 9?

Robson

[link widoczny dla zalogowanych]
Polecam lekture ;)

jagm

Hm. To może z so mi się pomyliło ;] Dobrze wiedzieć, bo bym za wcześniej przyszedł jeszcze ;]

hansu

@jagm: Pewnie jeszcze nie wiesz ale o 9 piszemy kolosa z algebry :p Wiec mozesz spokojnie przyjsc wczesniej :P:P:P

jagm

wiem, wiem :P Już się nawet uczę na nią ;]

kafex

yyy a nie o 10 ? :>

hansu

@kafex: Nie nie nie, kolos z algebry jest normalnie z poniedzialek o 10. A to o wtorkowym kolosie o 9 to pewien wredny dzolk ;)

kap00ch

hmm a sluman zarzucil gdzies wymaganymmi algorytmami?

Fidel

no podzielone na kilka plikow ale sa.. na kazdym z wykladow :P

kap00ch

pierdfoly gadasz;p mowil ze poda liste wymaganych tych co trza je na pamiec znac tak jak byly dane :P tak samo zreszta na WDI bylo...chyba...bo slabo pamietam;p

hansu

O liscie algorytmow ktore trzeba umiec na pamiec nic mi nie wiadomo, a bylem na ostatnich wykladach (inna sprawa ze moglo mi cos umknac :)). Obiecywal ze zamiesci przykladowy test na swojej stronie i tyle...

jagm

Mówił kiedyś, że zamieści listę algorytmów, które trzeba znać ;]

Spectro

Zaraz, a ktoś wie ile będzie trwał egzamin? Godzinę?

hansu

O ile wiem to poltorej godziny...

maniek

mam pytanko a skad na liscie z zaliczeniami jest az 14o kilka osob :) tak z ciekawosci bo ci cos juz zakonczyli przygode z uj nie są w niej wliczani

Spectro

A komu by się chciało ich odsiać? :P Poza tym część z nich dalej uczestniczy w zajęciach, chociaż już wylecieleli. Zbyt wiele przypadków jest spornych.

W każdym razie zaliczenie dostało aktualnie 60 osób. I tego można się trzymać.

maniek

ja na tej lisscie doliczyłem koło 50 osb :) moze mam klopoty z matematyka

Robson

Dr Slusarek mówił ze zamieści wymagane algorytmy ( znaczy nazwy do nich :) ) na stronie... dokładnie tak jak bylo na WDI... ale moze zapomniał? Wartoby mu moze przypomnieć...

Rogal

@maniek: faktycznie masz :wink:

exeman

dwuspójne ktoś rozumie? :/

Robson

exeman

Robson: wytlumacz prosze :P

Robson

A czy to bedzie koniecznie potrzebne?

Algorytm poleg w sumie na wykrywaniu krawedzi wstecznych, itp które wracają daleko w tył. Do tego potrzebujemy własnie numerowania preorder D[u] dla kazdego u.
No i teraz jak idziemy dfsem jak najdalej sie da to numerujemy sobie wierzcholki w kolejnosci pierwszej wizyty (w tym d[u]), no a jak spotkamy krawedz która biegnie w tył (tam gdzie juz byliśmy) to numer d[v] weirzcholka v (lub jego low[v] ! ) do ktorej idzie krawedz staje sie low[u] jesli jest mniejszy od aktulnego low[u]. Po prostu low[u] dla kazdego u pamieta dla nas numer preorder wierzcholka najwczesniejszego, czyli po prostu jakby mówi nam jak daleko mozemy cofnąć się w czasie w grafie. Po prostu tam juz byliśmy a teraz przyszlismy do u, czyli z u mozemy sie wrócić. Stąd wiemy ze napotkaliśmy cykl (bo odwiedziliśmy to v potem przez iles tam wierzcholków przeszlismy, doszlismy do u i teraz widzimy ze mozemy sie wrócić znowu do v).
no i to jest pierwszy etap algorytmu (ten dopuki damy rade isc dfsem w przód do nowych wierzcholków). dzieki temu wiemy dla kazego wierzcholka W DANYM PODDRZEWIE DFSA jak daleko mozemy sie cofnąc.
No to teraz czas na powrót z rekurencji. Jak powracamy to aktuyalizujemy wartości low[q] dla kazdego q na sciezce powrotu (no bo skoro powiedzmy z u dało sie dojsc do najwczesniejszego v to z q poprzednika u tez da sie dojsc do v, dla jego poprzednika tez i tak dalej i tak dalej...
no i teraz jest własnie ten myk:
jesli teraz cofając sie dojdziemy do wierzcholka q, dla którego istnieje krawed q->u i dla u nie da sie wrócić POWYZEJ q (low[u] >= d[q] ) to NA PEWNO wierzcholek q jest rozspójniający lub krawedz q->u jest mostem 9pojedyncza krawedzia której usuniecie rozspojnia graf).
No wiec teraz sciagamy krawedzie ze stosu (to jest wazne ze mu testujemy warunek low[u]>=d[q] w momencie powrotu DFSa z u!) az napotkamy ta krawedz która jest winowanczynią czyli krawedz q->u.
Wazne jest takze to ze zadne dwie dwuspojne nie mają wspólnej krawedzi (bo wtedy byłyby w jednej) dzieki temu jak raz sciagniemy cos ze stosu to nie musimy sie przejmować ze to moze byc potrzebne póxniej.
A dlaczego stos? Bo tak działa DFS - rekurencyjnie na stosie, wiec ten stos krawedzi to jest historia naszego chodzenia po grafie (daltego napisałem ze wazne jest to ze ten warunek low[u]>=d[q] nalezy testować po powrocie, bo jakbysmy sobie zapomnieli wtedy sciagnac ze stosu a poszli w inna krawedz to mogłoby to troche namieszac)

Tyle. Teraz prosze o pytania szczególowe :]

Robson

A ja mam jeszcze pytanie do matematyków: dlaczego Heap.Construct(); ma złozoność theta(n) ????