Zestawienie tematów objętych zakresem egzaminu z budowy i analizy algorytmów
Nr
Tematy Przykładowe zadania egz.
zad.
1. Utworzono jednokierunkowÄ… listÄ™ wskaz
nikowÄ… z
" Schematy blokowe podstawowych struktur sterujÄ…cych:
rekordów o trzech polach: A1, A2 i NST.
wyboru warunkowego, pętli  dopóki , pętli  aż do , pętli
Pola A1 i A2 sÄ… typu liczbowego, a pole NST jest
ograniczonej.
wskaz
nikiem na kolejny rekord. We wszystkich
" Przerabianie schematu algorytmu opartego na pętli
rekordach listy pola A1 i A2 wypełniono liczbami.
 dopóki na schemat oparty na pętli  aż do i odwrotnie.
W oparciu o pętlę (iterację) warunkową typu  dopóki
" Budowanie pętli ograniczonej w oparciu o pętlę
narysuj schemat blokowy algorytmu do wyznaczenia
warunkowÄ… i zmiennÄ… licznikowÄ….
najmniejszej spośród takich liczb zapamiętanych w
" Podstawowe struktur danych: tablice jedno- i
polach A1, które są większe lub równe liczbie z pola A2
wielowymiarowe, rekordy, wskaz
nikowe listy rekordów,
tego samego rekordu.
ukorzenione drzewa rekordów (rozróżnianie struktur
Odwołanie do zawartości pola A w rekordzie
statycznych i dynamicznych).
wskazanym przez wskaz
nik np. X oznacz A[X].
" Budowa prostych algorytmów wykorzystujących
Przyjmij, że zmienna wskazująca na pierwszy rekord
podstawowe struktury sterujÄ…ce i struktury danych 
nazywa siÄ™ GA a pole wskaz
nikowe NST w ostatnim
organizowanie współpracy pomiędzy strukturą danych a
rekordzie na liście zawiera wartość NIL.
strukturą sterującą, np. budowa algorytmów wyszuki-
Wprowadz
odpowiednie zmienne pomocnicze i
wania wartości ekstremalnych (wielkości lub położenia),
zapewnij poprawne działanie algorytmu dla pustej listy.
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.
2. a) Z jakich obiektów i jak powiązanych może być
" Schemat działania stosu i kolejki, które zbudowano w
zbudowana struktura danych zwana ukorzenionym
oparciu o listÄ™ wskaz
nikowÄ… (realizacja operacji
drzewem binarnym? Jaka specyficzna struktura
wstawiania i usuwania rekordów z tych struktur).
sterująca w algorytmie jest często powiązana z
" Zasada działania algorytmów rekurencyjnych.
drzewiastÄ… strukturÄ… danych? Jaka cecha drzewa
" Schematy algorytmów przeszukiwania podstawowych
narzuca to pokrewieństwo? Zbuduj drzewo BST dla
struktur danych (współpraca struktur sterujących ze
ciągu liczb: 7, 4, 6, 2, 11, 5, 8, 12, 9. Podaj ile liści
strukturami danych): pętle zagnieżdżone dla tablic
będzie zawierało to drzewo.
wielowymiarowych, iteracyjne algorytmy przeglÄ…du
drzewa w głąb i wszerz, rekurencyjny algorytm przeglądu b) Opisz, w jaki sposób w oparciu o wskaz
nikowÄ… listÄ™
drzewa binarnego. jednokierunkową można by zbudować strukturę
danych zwanÄ… kolejkÄ…. Opisz realizacjÄ™ podstawo-
" Budowa drzewa BST.
wych operacji, które pozwalałyby modyfikować tę
" Podstawowe algorytmy sortowania: bÄ…belkowego, ze
strukturę zgodnie z przyjętymi w kolejce zasadami.
scalaniem i drzewiastego (szczegóły działania).
Jakie są te zasady? Przyjmij w opisie, że lista
" Algorytm binarnego wyszukiwania (przez połowienie)
jednokierunkowa utworzona jest z rekordów
elementu z listy uporządkowanej (szczegóły działania).
posiadajÄ…cych tylko dwa pola: kluczowe i
" Przybliżony algorytm wyznaczania upakowania plecaka
wskaz
nikowe.
oparty na metodzie zachłannej (szczegóły działania).
3. Podaj charakterystyczne cechy algorytmów opartych na
" Cztery metody budowania algorytmów:  wędruj i
metodzie  programowania dynamicznego . Opisz krok
sprawdzaj ,  dziel i zwyciężaj ,  zachłanna ,
po kroku (podając, co jest wyznaczane, zapamiętywane
 programowanie dynamiczne  schemat działania i
i z czym powiÄ…zane) jak przebiega realizacja algorytmu
przykładowe realizacje wśród algorytmów omówionych
wykorzystujÄ…cego tÄ™ metodÄ™ w celu znalezienia
na wykładach (zapis w pseudojęzyku).
 najkrótszej drogi z punktu A do punktu J w podanej
" Demonstracja działania przykładowych algorytmów na
sieci połączeń:
podanych zestawach danych wejściowych (krok po
1
kroku).
B E
4
2
3
H
3 3
3
2
4
A C F J
3
6
2
I
2
5
1
D G
6
Podaj na koniec długość wyznaczonej drogi i jej
przebieg. Wypunktuj te cechy użytego algorytmu, które
wskazujÄ… na zastosowanie programowania
dynamicznego.
1 / 2
Nr
Tematy Przykładowe zadania egz.
zad.
4. Wyznacz rząd złożoność w najgorszym przypadku dla
" Definicje podstawowe dla asymptotycznej analizy
algorytmu o podanym schemacie:
złożoności czasowej algorytmów prowadzonej w
najgorszym przypadku.
" Formalne porównywanie asymptotycznych rzędów
petla Q? petla
złożoności.
N lgN razy C lgN razy
" 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
2 3
O(N lgN) O(N )
rzędów złożoności przez siebie.
" PowiÄ…zanie elementów rachunku O(Å") ze strukturami
sterującymi analizowanych algorytmów.
Przy pętlach podano liczbę ich powtórzeń. Przyjmij, że
" Wyznaczanie rzędu asymptotycznej złożoności algorytmu
N oznacza rozmiar zadania a C pewną stałą niezależną
w notacji O(Å") na podstawie podanego schematu
od rozmiaru danych wejściowych. Przyjmij, że wybór
blokowego lub opisu w pseudojęzyku (algorytm może
warunkowy Q zależy od danych wejściowych. Posługuj
zawierać podprogramy o podanych rzędach złożoności).
siÄ™ rachunkiem O(Å"), formalnie porównuj rzÄ™dy
złożoności i uzasadniaj postępowanie.
5. a) Wyjaśnij, na czym polega problem algorytmiczny
" Rozstrzyganie całkowitej i częściowej poprawności
zwany problemem  stopu w algorytmie . Podaj
algorytmu: definicje i rozróżnienie, istota metody
cechy charakterystyczne tego problemu i określ, do
niezmienników i zbieżników.
jakiej klasy problemów algorytmicznych on należy.
" Relacja pomiędzy analizą złożoności algorytmu a analizą
Krótko przedstaw jakiś inny problem z tej samej
złożoności problemu algorytmicznego.
klasy.
" Podział na problemy o złożoności wielomianowej i ponad
wielomianowej: formalne określenie, teoretyczne i b) Wyjaśnij związki pomiędzy klasami problemów
praktyczne znaczenie podziału. algorytmicznych: P, NP, i NP-zupełne.
Posługując się maszyną Turinga wyjaśnij pojęcie
" Podział na klasy problemów P, NP i NP-zupełne: cechy
niedeterministycznej złożoności wielomianowej.
charakterystyczne problemów z tych klas, relacje
pomiędzy wymienionymi klasami, rozstrzyganie
c) Skonstruuj diagram przejść dla automatu skończenie
podstawowego problemu algorytmiki  P=NP .
stanowego, który pracując nad alfabetem {x, y, z}
" Podział problemów algorytmicznych na rozstrzygalne potrafi stwierdzić w ciągu danych wejściowych
(obliczalne) i nierozstrzygalne. Przykłady wystąpienie przynajmniej raz sekwencji  zyyx .
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.
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
2 / 2