Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

przed kolosem
Idź do strony 1, 2  Następny
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Pon 16:18, 22 Sty 2007    Temat postu: przed kolosem

mam pewne pytanko:

dokładnie chodzi mi o czytelne rozwiązanie problemu który pojawił się na drugiej kartkówce u Kecima:

mamy daną policzoną tablice KMP dla konkatenacji wzorca i tekstu. wyznaczyć wszystkie poprawne przesunięcia wzorca w tekście.
Powrót do góry
Zobacz profil autora
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?

PostWysłany: Pon 17:11, 22 Sty 2007    Temat postu:

No wiec mamy ta tablice KMP. Bedziemy sobie tworzyc tablice o takiej samej dlugosci zlozona z zer i jedynek (czyli de facto tablice booli). Oznaczmy
W - wzorzec
T - tekst
WT - katenacja powyzszych.
w - dl wzorca
t - dl tekstu
A[] - nasza tablica.

A[i] == 1 oznacza ze w tekscie WT wystepuje W i konczy sie dokladnie na i-tej pozycji.

Inicjalizacja

Kod:
A[1..w+t] = 0;
A[w] = 1;


Algorytm

Kod:
for i = w+1 to w+t do
  if (KMP[i] == w)  //to znaczy ze dokladnie W sie w tym miejscu konczy
     A[i] = 1;
  else if (KMP[i] > w) //to znaczy ze w tym miejscu konczy sie jakies slowo S zlozone z W i jeszcze czegos (to slowo S konczy sie w polu o indeksie KMP[i])
     A[i] = A[KMP[i]] // jezeli S koczy sie slowem W to w i-ty polu tez sie konczy W, jezeli nie to nie


No i teraz jesli chcemy wypisac wszystkie wystapienia W w T to przelatujemy wszystkie pola tablicy A poczawszy od 2*w do konca, i kazda jedynka oznacza ze w tym polu konczy sie wzorzec.

Mam nadzieje ze to jest dobrze i ze jest to miare zrozumiale...
Powrót do góry
Zobacz profil autora
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

PostWysłany: Pon 17:21, 22 Sty 2007    Temat postu:

hansu napisał:
(...) No i teraz jesli chcemy wypisac wszystkie wystapienia W w T to przelatujemy wszystkie pola tablicy A poczawszy od 2*w do konca, i kazda jedynka oznacza ze w tym polu konczy sie wzorzec (...)

Mości hansu, miałeś chyba na myśli od (2*w)-1 ;)
Powrót do góry
Zobacz profil autora
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?

PostWysłany: Pon 17:30, 22 Sty 2007    Temat postu:

Nie mosci Skrobocie. Piszac 2w mam na mysli wlasnie 2w a nie 2w-1. Dlaczego?No bo jesli A[2w] == 1 to znaczy ze w polu 2w konczy sie wzorzec, czyli to znaczy ze zaczyna sie w w+1 czyli dokladnie na poczatku tekstu. (tekst jest indeksowany od 1 do t+w).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Azhag
pijak



Dołączył: 16 Paź 2006
Posty: 33
Przeczytał: 0 tematów


PostWysłany: Pon 17:46, 22 Sty 2007    Temat postu:

Kecim mowil ze zrobi gdzies pkt za aktywnosci obecnosci .. wiecie gdzie to jest/ bedzie ?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Roxel
pijak



Dołączył: 06 Kwi 2006
Posty: 249
Przeczytał: 0 tematów

Skąd: Pszczyna

PostWysłany: Pon 18:44, 22 Sty 2007    Temat postu:

@Dudzio: na forum tcs jest wątek na ten temat
Powrót do góry
Zobacz profil autora
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

PostWysłany: Pon 19:37, 22 Sty 2007    Temat postu:

hansu napisał:
(...) (tekst jest indeksowany od 1 do t+w).

Oki, ja liczyłem od zera ;)
Powrót do góry
Zobacz profil autora
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

PostWysłany: Pon 20:23, 22 Sty 2007    Temat postu:

Rabina-Karpia wogóle nie musimy umieć?
Powrót do góry
Zobacz profil autora
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

PostWysłany: Pon 20:49, 22 Sty 2007    Temat postu:

Rogal napisał:
Rabina-Karpia wogóle nie musimy umieć?
tak wynika z tego co na forum tcsu ktos pisal w temacie o hopcroftcie
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Pon 22:22, 22 Sty 2007    Temat postu:

czy ktoś ma jakieś kody/dodatkowe materiały do Hopcrofta-Karpa? poza tym co jest na wykładzie...
Powrót do góry
Zobacz profil autora
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?

PostWysłany: Pon 22:41, 22 Sty 2007    Temat postu:

to co jest na wykladzie + kartka + olowek jest wystarczajace do implementacji i zrozumienia dzialania w razie potrzeby nie wspominajac o IoD - Implementation on Demand
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Pon 23:39, 22 Sty 2007    Temat postu:

wytlumaczcie mi prosze, czy moje rozwiazanie jest poprawne? Jesli nie to prosze o kontrprzyklad.


Kod:

BZDURY, NIE CZYTAC, NIEAKTUALNE.
for (i = 1; i < (n div k) - 1; i++)
   if (kmp[(i + 1)*k - 1] < k*i)
       return false;
return true;


Ostatnio zmieniony przez exeman dnia Pon 23:51, 22 Sty 2007, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Yoter
zielony żul



Dołączył: 19 Lis 2005
Posty: 1033
Przeczytał: 0 tematów

Skąd: Gościeradów

PostWysłany: Pon 23:46, 22 Sty 2007    Temat postu:

albo masz konflikt oznaczeń albo nie możesz użyć k bo nie masz jej na wejściu albo ja czegoś nie wiem...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Pon 23:47, 22 Sty 2007    Temat postu:

O fuck. Myslalem, ze k mamy dane :P I mi sie to trywialne wydalo :P Ok, to ide robic to jeszcze raz.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Wto 0:25, 23 Sty 2007    Temat postu:

Dobra, to prosze teraz o znalezienie kontrprzykladu na ponizsze rozwiazanie, ew. milo mi bedzie, jesli bedzie on poprawny :P
Kod:

delta = n - kmp[n];
i = n - 1;
while (i >= delta){
  i = kmp[i] - 1;
}
if (i == delta){
  return true; // Istnieje o dlugosci delta
} else
{
  return false; // Nie istnieje!
}

Nie potrafie udowodnic inaczej niz przez przyklad, oraz nie moge znalesc kontrprzykdu.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Wto 17:36, 23 Sty 2007    Temat postu:

Eh, w takim razie bede wdzieczny za poprawne rozwiazanie :>
Powrót do góry
Zobacz profil autora
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

PostWysłany: Wto 22:33, 23 Sty 2007    Temat postu:

u nas na cwiczeniach bylo takie zadanie:

mamy juz jakies skojarzenie w grafie dwudzielnym i trzeba sprawdzic czy jest to skojarzenie maksymalne, pamieta ktos jak to zrobic?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Wto 22:36, 23 Sty 2007    Temat postu:

Fidel napisał:
mamy juz jakies skojarzenie w grafie dwudzielnym i trzeba sprawdzic czy jest to skojarzenie maksymalne, pamieta ktos jak to zrobic?

Tak. Bierzemy wolny wierzchołek i szukamy ścieżki alternującej, która istnieje <=> skojarzenie nie jest maksymalne ;) .
Powrót do góry
Zobacz profil autora
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?

PostWysłany: Wto 23:05, 23 Sty 2007    Temat postu:

@exeman:

Zalozenia: slowo W o dlugosci w

Teza:

(istnieja takie U i k ze W = U^k) <==> (w - KMP(w)) dzieli w

Dowod "<=" trywialny
Dowod "=>" tez trywialny, jesli sie zalozy ze U jest minimalne z mozliwych (czyli takie jakby "nieokresowe" - nie jest sklejeniem dwoch lub wiecej takich samych slow)

(sorki ze tak pisze skrotowo, ale to naprawde sa automatyczne dowody jak tylko sie to rozrysuje - a zapisanie tego zajeloby mi chwile)

Algorytm - no bez jaj :P
Powrót do góry
Zobacz profil autora
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

PostWysłany: Wto 23:12, 23 Sty 2007    Temat postu:

a jak najlepiej ja policzyc sciezke powiekszajaca w tym przypadku? trzeba graf rezydualny tworzyc czy jest jakis ciekawszy sposob?
Powrót do góry
Zobacz profil autora
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

PostWysłany: Wto 23:15, 23 Sty 2007    Temat postu:

@Fidel: Ja bym zrobił taki przejście jak jest w H-K, tj. takiego BFS-a zaczynając od wszystkich wierzchołków z lewej strony.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Wto 23:19, 23 Sty 2007    Temat postu:

Fidel: a nie wystarczy raz Edmonds Karpa puscic? To zlozonosc liniowa by mialo, wiec brzmi obiecujaco moim zdaniem :>
Powrót do góry
Zobacz profil autora
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

PostWysłany: Wto 23:33, 23 Sty 2007    Temat postu:

a mi sie wydaje ze to trzeba zrobic tak jak w wazniaku jest algorytm wyszukiwania sciezki rozszerzajacej dla grafu (bez zadnych przeplywow) wyklad:
[link widoczny dla zalogowanych]

przynajmniej cos takiego z cwiczen pamietam ze robienie z tego sieci przeplywowej byloby nieoptymalne, tam w wazniaku to jest dobrze wytlumaczone. robi sie tylko graf skierowany i szuka sciezki
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Śro 0:05, 24 Sty 2007    Temat postu:

no własnie: tam(czyli w algorytmie z wazniaka do znajdowanie ścieżki alternujacej) jest taki myk "usuń cykle z P tak aby P było ścieżką prostą" - jak to zaimplementować na przykład, to chyba nie jest jakies trudne?
Powrót do góry
Zobacz profil autora
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

PostWysłany: Śro 0:55, 24 Sty 2007    Temat postu:

Fen napisał:
no własnie: tam(czyli w algorytmie z wazniaka do znajdowanie ścieżki alternujacej) jest taki myk "usuń cykle z P tak aby P było ścieżką prostą" - jak to zaimplementować na przykład, to chyba nie jest jakies trudne?
tam wystarczy chyba kolorowac odwiedzone krawedzie i jesli dochodzisz do odwiedzonej masz cykl
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Idź do strony 1, 2  Następny
Strona 1 z 2

 
Skocz do:  
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
Regulamin