Procedura rekurencyjna- procedura która wywouje sama siebie pośrednio lub bezpośrednio.
Złożoność pamięciowa- Pamięć potrzebna do wykonania algorytmu jako funkcji rozmiaru zadania.
Lista (rekurencyjnie)- struktura zdefiniowana na skończonym zbiorze elementów, która albo nie zawiera żadnego elementu i jest nazywana listą pustą, albo jest połączeniem elementów i listy.
Spójny graf niekierowany - to taki, którego para wierzchołków jest połączona ścieżką.
Wierzchołek stosu- ostatni element położony na stosie, jedyny który można pobrać ze stosu w danym momencie.
Algorytm - pewien przepis (sposob postępowania), który ma prowadzić do rozwiązania określonego zadania.
Algorytmiczna dziedzina - zbior obiektow i dostępnych w algorytmie pierwotnych operacji.
Algorytmu określoność - wymog, aby każda operacja w algorytmie była sformułowana w sposob zapewniający jej jednoznaczną interpretację.
Algorytmu skończoność - algorytm powinien zakończyć swoje działanie po wykonaniu skończonej liczby operacji.
Algorytmu wejście - pewne dane pobierane przez
algorytm w celu ich przetworzenia.
Algorytmu wyjście - wynik działania algorytmu.
Algorytmu wykonywalność - pisząc algorytm, wystarczy się jedynie posłużyć dostępnymi poleceniami.
Cykl w grafie nieskierowanym - droga, dla ktorej
wierzchołek początkowy jest tym samym wierzchołkiem, co wierzchołek końcowy, wszystkie wierzchołki są rożne, a ich ilość jest większa lub rowna 2.
Cykl w grafie skierowanym - droga, dla ktorej
wierzchołek początkowy jest tym samym wierzchołkiem, co wierzchołek końcowy.
Drzewo binarne - drzewo, ktorego każdy węzeł posiada co najwyżej dwoch synow, z ktorych da się wyrożnić lewy i prawy.
Drzewo binarne (definicja rekurencyjna) - struktura
zdefiniowana na skończonym zbiorze węzłow w ten
sposob, że albo nie zawiera żadnych węzłow i jest
nazywana drzewem pustym, albo składa się z trzech
rozłącznych zbiorow węzłow: korzenia, lewego
poddrzewa i prawego poddrzewa.
Drzewo niezorientowane - graf nieskierowany, ktory jest spojny, acykliczny i posiada wyrożniony wierzchołek nazywany korzeniem.
Drzewo pełne - binarne drzewo, w ktorym istnieje liczba k taka, że dla każdego węzła o głębokości mniejszej niż k występują oba węzły będące jego synami, a każdy węzeł o głębokości k jest liściem.
Drzewo przeszukiwań binarnych (BST) - drzewo binarne, w ktorym wartości kluczy są przechowywane w taki sposob, aby spełniały tzw. własność drzewa BST, zgodnie z ktorą dla dowolnego węzła x, jeśli y jest węzłem jego lewego poddrzewa, to key[y] ≤ key[x], a jeśli y jest węzłem jego prawego poddrzewa, to key[y] ≥ key[x].
Drzewo regularne - binarne drzewo, w ktorym każdy z
węzłow jest albo liściem, albo posiada jednocześnie
lewego i prawego syna.
Drzewo uporządkowane - drzewo, w ktorym zbior synow każdego węzła jest uporządkowany.
Drzewo zorientowane (skierowane) - acykliczny
skierowany graf, posiadający dokładnie jeden
wierzchołek, do ktorego nie dochodzi żadna krawędź
(korzeń drzewa). Dla dowolnego wierzchołka w drzewie tym istnieje droga prowadząca od korzenia do tego wierzchołka i jest to droga jedyna. Każdy wierzchołek nie będący drzewem ma dokładnie jedną krawędź wchodzącą do niego.
Głębokość węzła - długość drogi od korzenia do tego
węzła.
Graf - para zbirow G = (V, E), gdzie V jest skończonym zbiorem wierzchołkow, a E jest zbiorem krawędzi.
Graf acykliczny - graf nie zawierający cykli.
Infiksowy zapis matematyczny - tradycyjny zapis
matematyczny, gdzie operandy są oddzielone znakiem
operacji, np. 5*(((9 + 8)*(4 * 6)) + 7).
Kolejka - struktura z ograniczonym dostępem, dla której określono początek i koniec. Elementy są obsługiwane według porządku „pierwszy przyszedł, pierwszy wyszedł”.
Kolejka proprytetowa - struktura przechowująca S
elementow, z ktorych każdy ma przyporządkowaną
wartość klucza.
Kopiec (heap) - struktura, ktora może być rozpatrywana jako rodzaj „prawie pełnego” drzewa binarnego. Drzewo to jest pełne w tym sensie, że jest wypełnione na wszystkich poziomach z wyjątkiem bić może najniższego, ktory jest wypełniony od lewej do prawej do pewnego miejsca.
Korzeń drzewa - wierzchołek drzewa skierowanego, do ktorego nie dochodzi żadna krawędź.
Lista - skończony ciąg elementow należących do pewnego zbioru.
Lista (definicja rekurencyjna) - struktura zdefiniowana na skończonym zbiorze elementow, ktora albo nie zawiera żadnych elementow i jest nazywana listą pustą, albo jest połączeniem elementu i listy.
Liść - węzeł nie posiadający potomkow.
Operacje dominujące - operacje charakterystyczne dla
danego algorytmu, a ich liczba jest proporcjonalna do
liczby wykonań wszystkich operacji jednostkowych w
dowolnej realizacji komputerowej danego algorytmu.
Poddrzewo - pewien węzeł v (określony tu jako korzeń
tego poddrzewa) wraz ze wszystkimi swoimi potomkami.
Porządek całkowity (liniowy) - częściowy porządek relacji R na zbiorze S, taki, że dla dowolnej pary elementow tego zbioru (a, b) zachodzi aRb lub bRa.
Porządek częściowy - relacja R na zbiorze S, posiadająca właściwości: zwrotność, przechodniość,
antysymetryczność.
Postfiksowy zapis matematyczny (odwrotny zapis polski) - pośrednia postać zapisu matematycznego, w której operandy występują zawsze przed znakiem operacji, np. 5 9 8 + 4 6 * * 7 + *. Idealny zapis pośredni dla wyrażeń arytmetycznych, ktore mają być obliczane za pomocą stosu.
Potomek węzła - węzeł w dla węzła v, jeśli w drzewie
zorientowanym istnieje droga prowadząca od węzła v do węzła w. Dla drzewa niezorientowanego, węzeł v jest położony wyżej w strukturze drzewa, niż węzeł w.
Przodek węzła - węzeł v dla węzła w, jeśli w drzewie
zorientowanym istnieje droga prowadząca od węzła v do węzła w. Dla drzewa niezorientowanego, węzeł v jest położony wyżej w strukturze drzewa, niż węzeł w.
Rekurencja - procedura, ktora bezpośrednio lub
pośrednio wywołuje samą siebie.
Rodzic wierzchołka - węzeł v dla wierzchołka w w
krawędzi (v, w) є E w drzewie zorientowanym. W
drzewie niezorientowanym, węzeł v jest węzłem
położonym o jeden poziom wyżej w strukturze drzewa,
niż węzeł w.
Rozmiar zadania (wejścia) - konkretna liczba
charakteryzująca objętość danych wejściowych.
Spojność grafu nieskierowanego - każda para
wierzchołkow jest połączona ścieżką (drogą).
Silna spojność grafu skierowanego - każde dwa
wierzchołki są osiągalne jeden z drugiego.
Sterowanie - zmiana kolejności elementow pewnego
ciągu tak, aby zostały one ustawione w porządku
niemalejącym lub nierosnącym.
Stopień wierzchołka w grafie nieskierowanym - liczba incydentnych z nim krawędzi.
Stopień wejściowy - liczba krawędzi wchodzących.
Stopień wyjściowy - liczba krawędzi wychodzących.
Stos - struktura posiadająca ustalony element nazywany
wierzchołkiem, ktory jest jedynym dostępnym w danej
chwili jej składnikiem. Elementy są obsługiwane według porządku „ostatni przyszedł, pierwszy wyszedł”.
Sumator - rejestr r0, pełniący w obliczeniach specjalną
rolę.
Syn wierzchołka - węzeł w dla wierzchołka v w krawędzi (v, w) є E w drzewie zorientowanym. W drzewie niezorientowanym, węzeł v jest węzłem położonym o jeden poziom wyżej w strukturze drzewa, niż węzeł w.
Ścieżka (droga) w grafie - ciąg kolejnych wierzchołkow, przez ktore przechodzimy, kierując się od wierzchołka początkowego do wierzchołka końcowego.
Taśma wejściowa - ciąg klatek, z ktorych każda może
zawierać liczbę całkowitą. Każdorazowo, kiedy z taśmy
wejściowej zostanie odczytana liczba, głowica czytająca
jest przesuwana o jedną pozycję w prawo.
Taśma wyjściowa - ciąg klatek (na początku pustych), do ktorych maszyna może tylko zapisywać. Po zapisie do kolejnej klatki głowica zapisująca jest przesuwana o
jedną klatkę w prawo.
Węzeł - wierzchołek drzewa.
Wysokość drzewa - wysokość jego korzenia.
Wysokość węzła - maksymalna długość drogi od tego
węzła do liścia.
Złożoność czasowa - czas potrzebny na wykonanie
algorytmu jako funkcja rozmiaru zadania, za jednostkę
przyjmuje się wykonanie jednej operacji dominującej.
Złożoność czasowa asymptotyczna - charakter złożoności czasowej przy dążeniu do wartości granicznej wraz ze wzrostem rozmiaru zadania.
Złożoność oczekiwana - pewna „średnia” złożoność dla wszystkich możliwych wejść danego rozmiaru.
Złożoność pamięciowa - pamięć potrzebna do wykonania algorytmu jako funkcja rozmiaru zadania, za jednostkę przyjmuje się słowo pamięci maszyny.
Złożoność pamięciowa asymptotyczna - charakter
złożoności pamięciowej przy dążeniu do wartości
granicznej wraz ze wzrostem rozmiaru zadania.
Złożoność pesymistyczna - największa ze złożoności dla wszystkich możliwych wejść danego rozmiaru.
Typy operandów:
=i - liczba całkowita i; operand tego typu nazywamy
literałem; v(=i) = i,
i - zawartość rejestru o numerze i (i powinno być
nieujemne); v(i) = c(i),
*i - wartością operandu jest zawartość rejestru j, gdzie j
jest liczbą nieujemną przechowywaną w rejestrze i
(adresacja pośrednia); v(*i) = c(c(i)).
Opis poleceń maszyny RAM:
LOAD a - c(0) ← v(a), co oznacza zapis wartości operandu
a do rejestru 0 (sumatora),
STORE i - c(i) ← c(0),
STORE *i - c(c(i)) ← c(0),
ADD a - c(0) ← c(0) + v(a),
SUB a - c(0) ← c(0) - v(a),
MULT a - c(0) ← c(0) × v(a),
DIV a - c(0) ← c(0) / v(a),
READ i - c(i) ← kolejny symbol wejściowy,
READ *i - c(c(i)) ← kolejny symbol wejściowy,
WRITE a - v(a) jest zapisywane do tej klatki taśmy
wyjściowej, przy ktorej aktualnie znajduje się głowica,
JUMP b - licznik rozkazow jest ustawiany na komendę z etykietą b,
JGTZ b - jeśli c(0) > 0, to licznik rozkazow jest ustawiany na komendę z etykietą b; w przeciwnym razie na komendę następną,
JZERO b - jeśli c(0) = 0, to licznik rozkazow jest ustawiany na komendę z etykietą b; w przeciwnym razie na komendę następną,
HALT - zatrzymanie programu.
Podstawowe operatory pseudokodu:
Nadawanie wartości: zmienna ← wyrażenie,
Operator warunkowy: jeśli warunek to operator(y)
inaczej operator(y),
Operator pętli „dopoki”: dopóki warunek wykonuj
operator(y),
Operator pętli „powtarzaj”: powtarzaj operator(y) aż_do warunek,
Operator pętli „dla”: dla zmienna ← wartość_początkowa
[w_dół_]do wartość_końcowa wykonuj operator(y).
Wagi logarytmiczne operandów:
=i - l(i),
i - l(i) + l(c(i)),
*i - l(i) + l(c(i)) + l(c(c(i))).
Wagi logarytmiczne komend:
LOAD a - t(a),
STORE i - l(c(0)) + l(i),
STORE *i - l(c(0)) + l(i) + l(c(i)),
ADD a - l(c(0)) + t(a),
SUB a - l(c(0)) + t(a),
MULT a - l(c(0)) + t(a),
DIV a - l(c(0)) + t(a),
READ i - l(wejście) + l(i),
READ *i - l(wejście) + l(i) + l(c(i)),
WRITE a - t(a),
JUMP b - 1,
JGTZ b - l(c(0)),
JZERO b - l(c(0)),
HALT - 1.
Umieszczanie elementu x na stosie S :
PUSH(S,x)
1 top[S] ← top[S] + 1
2 S[top[S]] ← x
Zdejmowanie elementu x ze stosu S :
POP(S)
1 jeśli STOS-PUSTY(S)
2 to błąd „niedomiar”
3 inaczej { top[S] ← top[S] - 1
4 zwróć S[top[S] + 1] }