1 / 2

Zestawienie tematów objętych zakresem egzaminu z budowy i analizy algorytmów

Nr
zad.

Tematy

Przykładowe zadania egz.

1.

•

Schematy blokowe podstawowych struktur sterujących:
wyboru warunkowego, pętli „dopóki”, pętli „aż do”, pętli
ograniczonej.

•

Przerabianie schematu algorytmu opartego na pętli
„dopóki” na schemat oparty na pętli „aż do” i odwrotnie.

•

Budowanie pętli ograniczonej w oparciu o pętlę
warunkową i zmienną licznikową.

•

Podstawowe struktur danych: tablice jedno- i
wielowymiarowe, rekordy, wskaźnikowe listy rekordów,
ukorzenione drzewa rekordów (rozróżnianie struktur
statycznych i dynamicznych).

•

Budowa prostych algorytmów wykorzystujących
podstawowe struktury sterujące i struktury danych –
organizowanie współpracy pomiędzy strukturą danych a
strukturą sterującą, np. budowa algorytmów wyszuki-
wania wartości ekstremalnych (wielkości lub położenia),
sumowania, mnożenia i normalizacji liczbowych
elementów zbioru danych wejściowych umieszczonych w
różnych strukturach danych.

•

Opisywanie algorytmu za pomocą schematu blokowego i
pseudojęzyka programowania – przechodzenie z jednego
sposobu opisu na drugi.

Utworzono jednokierunkową listę wskaźnikową z
rekordów o trzech polach: A1, A2 i NST.
Pola A1 i A2 są typu liczbowego, a pole NST jest
wskaźnikiem na kolejny rekord. We wszystkich
rekordach listy pola A1 i A2 wypełniono liczbami.
W oparciu o pętlę (iterację) warunkową typu „dopóki”
narysuj schemat blokowy algorytmu do wyznaczenia
najmniejszej spośród takich liczb zapamiętanych w
polach A1, które są większe lub równe liczbie z pola A2
tego samego rekordu.
Odwołanie do zawartości pola A w rekordzie
wskazanym przez wskaźnik np. X oznacz A[X].
Przyjmij, że zmienna wskazująca na pierwszy rekord
nazywa się GA a pole wskaźnikowe NST w ostatnim
rekordzie na liście zawiera wartość NIL.
Wprowadź odpowiednie zmienne pomocnicze i
zapewnij poprawne działanie algorytmu dla pustej listy.

2.

•

Schemat działania stosu i kolejki, które zbudowano w
oparciu o listę wskaźnikową (realizacja operacji
wstawiania i usuwania rekordów z tych struktur).

•

Zasada działania algorytmów rekurencyjnych.

•

Schematy algorytmów przeszukiwania podstawowych
struktur danych (współpraca struktur sterujących ze
strukturami danych): pętle zagnieżdżone dla tablic
wielowymiarowych, iteracyjne algorytmy przeglądu
drzewa w głąb i wszerz, rekurencyjny algorytm przeglądu
drzewa binarnego.

•

Budowa drzewa BST.

•

Podstawowe algorytmy sortowania: bąbelkowego, ze
scalaniem i drzewiastego (szczegóły działania).

•

Algorytm binarnego wyszukiwania (przez połowienie)
elementu z listy uporządkowanej (szczegóły działania).

•

Przybliżony algorytm wyznaczania upakowania plecaka
oparty na metodzie zachłannej (szczegóły działania).

a)

Z jakich obiektów i jak powiązanych może być
zbudowana struktura danych zwana ukorzenionym
drzewem binarnym? Jaka specyficzna struktura
sterująca w algorytmie jest często powiązana z
drzewiastą strukturą danych? Jaka cecha drzewa
narzuca to pokrewieństwo? Zbuduj drzewo BST dla
ciągu liczb: 7, 4, 6, 2, 11, 5, 8, 12, 9. Podaj ile liści
będzie zawierało to drzewo.

b)

Opisz, w jaki sposób w oparciu o wskaźnikową listę
jednokierunkową można by zbudować strukturę
danych zwaną kolejką. Opisz realizację podstawo-
wych operacji, które pozwalałyby modyfikować tę
strukturę zgodnie z przyjętymi w kolejce zasadami.
Jakie są te zasady? Przyjmij w opisie, że lista
jednokierunkowa utworzona jest z rekordów
posiadających tylko dwa pola: kluczowe i
wskaźnikowe.

3.

•

Cztery metody budowania algorytmów: „wędruj i
sprawdzaj”, „dziel i zwyciężaj”, „zachłanna”,
„programowanie dynamiczne” – schemat działania i
przykładowe realizacje wśród algorytmów omówionych
na wykładach (zapis w pseudojęzyku).

•

Demonstracja działania przykładowych algorytmów na
podanych zestawach danych wejściowych (krok po
kroku).

Podaj charakterystyczne cechy algorytmów opartych na
metodzie „programowania dynamicznego”. Opisz krok
po kroku (podając, co jest wyznaczane, zapamiętywane
i z czym powiązane) jak przebiega realizacja algorytmu
wykorzystującego tę metodę w celu znalezienia
„najkrótszej drogi” z punktu A do punktu J w podanej
sieci połączeń:

2

5

2

2

3

3

4

6

3

6

2

1

A

C

B

D

F

E

G

J

H

I

3

1

4

3

Podaj na koniec długość wyznaczonej drogi i jej
przebieg. Wypunktuj te cechy użytego algorytmu, które
wskazują na zastosowanie programowania
dynamicznego.

2 / 2

Nr
zad.

Tematy

Przykładowe zadania egz.

4.

•

Definicje podstawowe dla asymptotycznej analizy
złożoności czasowej algorytmów prowadzonej w
najgorszym przypadku.

•

Formalne porównywanie asymptotycznych rzędów
złożoności.

•

Posługiwanie się rachunkiem O(

⋅

) w zakresie: mnożenia

rzędu złożoności przez wartość niezależną od rozmiaru
danych wejściowych, mnożenia go przez wartość funkcji
zależnej od rozmiaru danych, dodawania i mnożenia
rzędów złożoności przez siebie.

•

Powiązanie elementów rachunku O(

⋅

) ze strukturami

sterującymi analizowanych algorytmów.

•

Wyznaczanie rzędu asymptotycznej złożoności algorytmu
w notacji O(

⋅

) na podstawie podanego schematu

blokowego lub opisu w pseudojęzyku (algorytm może
zawierać podprogramy o podanych rzędach złożoności).

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

Q?

O(

lg )

N

N

2

O(

)

N

3

C

N

lg razy

N

N

lg razy

petla

petla

Przy pętlach podano liczbę ich powtórzeń. Przyjmij, że
N oznacza rozmiar zadania a C pewną stałą niezależną
od rozmiaru danych wejściowych. Przyjmij, że wybór
warunkowy Q zależy od danych wejściowych. Posługuj
się rachunkiem O(

⋅

), formalnie porównuj rzędy

złożoności i uzasadniaj postępowanie.

5.

•

Rozstrzyganie całkowitej i częściowej poprawności
algorytmu: definicje i rozróżnienie, istota metody
niezmienników i zbieżników.

•

Relacja pomiędzy analizą złożoności algorytmu a analizą
złożoności problemu algorytmicznego.

•

Podział na problemy o złożoności wielomianowej i ponad
wielomianowej: formalne określenie, teoretyczne i
praktyczne znaczenie podziału.

•

Podział na klasy problemów P, NP i NP-zupełne: cechy
charakterystyczne problemów z tych klas, relacje
pomiędzy wymienionymi klasami, rozstrzyganie
podstawowego problemu algorytmiki „P=NP”.

•

Podział problemów algorytmicznych na rozstrzygalne
(obliczalne) i nierozstrzygalne. Przykłady
nierozstrzygalnych problemów algorytmicznych.

•

Maszyna Turinga: czym jest, budowa i zastosowanie.

•

Teza Churcha-Turinga i jej znaczenie dla analizy
problemów algorytmicznych.

•

Automaty skończenie stanowe: czym są, a czym nie są,
budowa i zastosowanie.

a)

Wyjaśnij, na czym polega problem algorytmiczny
zwany problemem „stopu w algorytmie”. Podaj
cechy charakterystyczne tego problemu i określ, do
jakiej klasy problemów algorytmicznych on należy.
Krótko przedstaw jakiś inny problem z tej samej
klasy.

b)

Wyjaśnij związki pomiędzy klasami problemów
algorytmicznych: P, NP, i NP-zupełne.
Posługując się maszyną Turinga wyjaśnij pojęcie
niedeterministycznej złożoności wielomianowej.

c)

Skonstruuj diagram przejść dla automatu skończenie
stanowego, który pracując nad alfabetem {x, y, z}
potrafi stwierdzić w ciągu danych wejściowych
wystąpienie przynajmniej raz sekwencji „zyyx”.

Typowa punktacja zadań:

Nr zad.

Liczba punktów

1.

20

2.

15

3.

15

4.

15

5.

10

Suma:

75

J. Sikorski

w roku akademickim 2011/2012