10695232643726803876426912271 n

Egzamin z Zaawansowanych algorytmów 24.06.14

krupa A

Imię i nazwisku: numer indeksu

II' zadaniach. w których wymagane jest uzasadnienie, jego hrak powoduje II punktów

I (.1 pkl.) I);my jesl wzorzec I’:

0	1	2	3	4	5	6	7	8	9	10
a	a	a	b	a	a	a	b	a	a	a

u) Uzupełnij tabelę przesunięć dla powyższego wzorca, zgodnie ze slabs) funkcji) dobrego prefiksu (algorytm Morrisa-Pralta):

0	1	2	3	4	5	6	7	8	9	10

b) Uzupełnij tabelę przesunięć dla powyższego wzorca, zgodnie z. mocni) funkcją dobrego prefiksu (algorytm Knutha-Morrisa-Pratta):

0	1	2	3	4	5	6	7	8	<)	10

c) Dany jest tekst postaci T=[aaabaaabaaac...|. Z którymi /.Itakami wzorca P (podaj numer zostanie porównany znak numer 11 w tekście T (literka 'c' numerujemy od zera), według mocnej funkcji dobrego prefiksu ?

Odpowiedź:......................................

2. (I pktJJakiego rodzaju kolejki używamy w algorytmie UPS?

Odpowiedź:........................................

3. (2 pkt.jDany jest graf:

0: I 4 5 2 1:3 0 2:0 5 6 3:4 I 4:0 3 5:0 2 6:2