Untitled

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

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

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ą

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ść,

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,

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ą

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

Węzeł - wierzchołek drzewa.

Wysokość drzewa - wysokość jego korzenia.

Wysokość węzła - maksymalna długość drogi od tego

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.

=i - liczba całkowita i; operand tego typu nazywamy

i - zawartość rejestru o numerze i (i powinno być

*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

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)

Operator pętli „dopoki”: dopóki warunek wykonuj

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) + l(c(i)) + l(c(c(i))).

Wagi logarytmiczne komend:

STORE i - l(c(0)) + l(i),

STORE *i - l(c(0)) + l(i) + l(c(i)),

MULT a - l(c(0)) + t(a),

READ i - l(wejście) + l(i),

READ *i - l(wejście) + l(i) + l(c(i)),

Umieszczanie elementu x na stosie S :

Zdejmowanie elementu x ze stosu S :

3 inaczej { top[S] ← top[S] - 1

4 zwróć S[top[S] + 1] }