Zaawansowane algorytmy i struktury danych/Ćwiczenia 1

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Sprawdz w czasie liniowym, czy słowo jest pierwotne.

Rozwiązanie

Zadanie 2

Pokaż redukcję w czasie liniowym problemu liczenia tablicy PREF do liczenia tablicy P

Rozwiązanie

Zadanie 3

Załóżmy, że wzorzec jest ustalony, ma długość , a tekst , w którym szukamy , jest losowym tekstem długości , alfabet zaś jest binarny. Każdy symbol jest zerem lub jedynką niezależnie, z takim samym prawdopodobieństwem 1/2.

Skonstruuj algorytm, który będzie szukał wzorca w czasie oczekiwanym (średnim)

Rozwiązanie

Zadanie 4

Udowdnij, że w modelu takim, jak w poprzednim zadaniu, algorytm BM nie ma złożoności oczekiwanej rzędu mniejszego niż liniowy.

Rozwiązanie

Zadanie 5

Pokaż, że jeśli cn jest górnym oszacowaniem liczby porównań w algorytmie BM (dla dostatecznie dużych n) to

Rozwiązanie