10862594204392358107056U63634853946399871 o

Wydział Informatyki WSISiZ

Nazwisko i imię

Grupa.

STUDIA DZIENNE

Zestaw pytań egzaminacyjnych z budowy i analizy algorytmów Odpowiedź na każde z pytań jest punktowana w skali od 0 do podanej przy nim liczby punktów.

1 Lp. 1 Pytanie	Maks. pki. 1	Uzysk.
| 1 1 Kwadratową tablicę dwuwymiarową TAB o N wierszach i N kolumnach 1 wypełniono liczbami. W oparciu o iterację warunkową typu „dopóki” narysuj I I schemat blokowy algorytmu, który wyznaczy indeks wiersza, w którym znajduje 1 się największa z liczb umieszczonych na przekątnej tej tablicy oraz indeks 1 kolumny, w której znajduje się najmniejsza z tych liczb. Odwołanie do elementu tablicy położonego w wierszu X i kolumnie Y oznacz TAB(X, Y). Wprowadź odpowiednie zmienne do przekazania wyniku i zmienne pomocnicze.	20
3. Opisz, w jaki sposób w oparciu o wskaźnikowa listę jednokierunkowa można zbudować strukturę danych zwana stosem. Opisz możliwie dokładnie realizację podstawowych operacji, które pozwalałyby modyfikować tę strukturę zgodnie z przyjętymi w stosie zasadami. Podaj te zasady. Przyjmij, że lista jednokierunkowa tworzona jest z rekordów posiadających tylko	15

13. Podaj charakterystyczne cechy algorytmów opartych na metodzie programowania dynamicznego.

Opisz krok po kroku, jak według algorytmu wykorzystującego | tę metodę zostanie znaleziona „najkrótsza droga” od punktu A I do punktu L w podanej obok sieci połączeń:

Podaj długość wyznaczonej drogi. Wskaż te cechy użytego algorytmu, które wskazują na zastosowanie programowania dynamicznego._

15

14. Wyznacz rząd złożoność w najgorszym przypadku dla algorytmu o podanym obok schemacie.

Przyjmij, że 7V oznacza rozmiar zadania a C pewną stałą niezależną od danych wejściowych. Natomiast wybór warunkowy Q zależy od danych wejściowych. Przy pętlach podano liczbę ich powtórzeń.

Posługuj się rachunkiem O(-), formalnie (asymptotycznie) porównuj rzędy złożoności i uzasadniaj postępowanie. ____

Scharakteryzuj problemy należące do klasy P i porównaj je z problemami należącymi do klasy NP.Wyjaśnij związki pomiędzy tymi dwoma klasamr problemów algorytmicznych.______

SUMA:

15

10

75