AISDE - Kolokwium Poprawkowe 11 czerwca 2007

Tu podpisać:

Zadanie 1

Dane: N=0,1,2,...;Wynik: S - l. całkowita Function S = Alg (N) S=0; For I=1:N K=0; While (K<I) K=K+1; End S=S+K; End Dla podanego algorytmu napisać wzory analityczne na złożoność czasową T1(N), T2(N), gdy operacją dominującą jest odpowiednio: porównanie i dodawanie.

T1(N) = T2(N) =

Zadanie 2

Wykazać z definicji (nie z granicy) że :

Dowód:

Zadanie 3

Dla wykładnika m algorytm rec_power wykonał 10 mnożeń, zaś dla wykładnika zwiększonego o 1 wykonał 6 mnożeń. Określić m.

m =

Zadanie 4

W algorytmie mergesort etap łączenia dwóch wyników wymaga w najgorszym przypadku n operacji porównania. Napi­sać równanie rekurencyjne na złożoność W(n). Obliczyć W(n). Narysować pesymistyczne drzewo rekurencji.

Równanie: W(n)= Drzewo rekurencji:

Zadanie 5

Buildheap stosujemy do tablicy a. Obliczyć zł­ożoność oczekiwaną, jeżeli elementy a losujemy bez powtórzeń w {1,2,3}, a operacją do­mi­nującą jest wzajemna wy­miana elementów.

A =

Zadanie 6

W tekście T o długości n=11 znaleziono algorytmem Naive wzorzec P o długości m. Alfabet V={0,1). Wykonano 36 porównań symboli. Określić wszystkie możliwe T i P.

T= .................................................................... .......................................................................... P=...................................................................... ..........................................................................

Zadanie 7

W tekście T wyszukujemy wzorzec P o długości 4 za pomocą algorytmu automatów sko­ńczonych. Alfabet V={1,2}. Wykonano 10 odwołań do tablicy prz­­ejść i 7 przejść w stan 4. Określić wszystkie możliwe T, P.

T=..................................................................... ......................................................................... P=.................................................................... ........................................................................

Zadanie 8

Algorytmem search_tu_bin znaleziono w tab­licy K: elem­ent x za pomocą 1 porównania, e­l­ementy y,z za pomocą 2 porównań (y<z) i el­ementy a,b,c za pomocą 3 porów­nań (a<b<c). Wypisać K zakładając, że są to wszy­stkie klu­cze słownika.

K=.....................................................................

Zadanie 9

Narysować graf nieskierowany, którego przeszukiwanie algorytmem bfs_tss będzie miało złożoność 3, jeżeli operacją dominującą jest kolorowanie wierzchołków na szaro i złożoność 6 jeżeli operacją dominującą jest odczytanie wierzchołka sąsiadującego z tss. Wybrać w tym grafie wierzchołek źródłowy i wykonać BFS.

Zadanie 10

W wyniku wykonania algorytmu dfs_tss otrzymano następujące atrybuty wierzchołków: A - 1/8, B-2/7, C-3/4, D-5/6. Ile maksymalnie cięciw powrotnych może zawierać ten graf. Uzasadnić za pomocą atrybutów d/f. Narysować drzewo przeszukiwania i wszystkie cięciwy powrotne.

---