Pojęcia:

Algorytm - pewien przepis (sposob postępowania), który ma prowadzić do rozwiązania określonego zadania.

Algorytm wewnętrzny - dane są przechowywane

wyłącznie w pamięci wewnętrznej.

Algorytm zewnętrzny - dane w przeważającej części

znajdują się poza pamięcią wewnętrzną.

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.

Analiza algorytmów: Dziedzina zajmująca się algorytmami a jej zasadnicze kierunki dotyczą jego poprawności i złożoności obliczeniowej

Antysymetryczność - dla dowolnych a,b є S zachodzi: jeśli aRb i bRa, to a = b (S to zbior, R to relacja).

Asymptotyczna złożoność czasowa:

Czas potrzebny na wykonanie algorytmu jako funkcja rozmiary zadania jest nazywany złożonością czasową tego algorytmu. Charakter tej złożoności przy dążeniu do wartości granicznej wraz ze wzrostem rozmiarów zadania jest określany jako asymptotyczna złożoność czasowa co zapisujemy O(n)

Asymptotycznej granica dolna: Pewna nieujemna funkcja f(n)=(g(n)) jeśli istnieje taka stała c , że zachodzi 0cg(n)f(n) dla wszystkich n oprócz pewnego zbioru nieujemnych wartości n. Notacja ta ogranicza funkcję z dołu.

asymptotyczna granica górna: Pewna nieujemna funkcja f(n)=O(g(n)) jeśli istnieje taka stała c , że zachodzi 0f(n)cg(n) dla wszystkich n oprócz pewnego zbioru nieujemnych wartości n. Istnieją dodatnie stałe c i n takie, że na prawo od tego n wartość f(n) jest zawsze niewiększa od cg(n).

Cechy algorytmu: posiada wejście i wyjście, jest wykonalny jest określony, dochodzi do punktu końcowego

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.

Częściowym porządkiem na zbiorze S nazywamy relację R, która posiada następujące właściwości:

Zwrotność. Dla dowolnego a  S zachodzi aRa.

Przechodniość. Dla dowolnych a, b, c  S zachodzi: jeśli aRb i bRc to aRc.

Antysymetryczność. Jeśli aRb i bRa to a = b.

Przykładami częściowych porządków są:  w zbiorze Z oraz  dla zbiorów.

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.

Liniowym (całkowitym) porządkiem na zbiorze S nazywamy częściowy porządek R na S, taki, że dla dowolnych a, b  S zachodzi aRb albo bRa.

Relacja  jest przykładem porządku liniowego w zbiorze liczb Z, natomiast  dla zbiorów nie jest porządkiem liniowym.

Logarytmiczne kryterium wagowe - jest oparte na założeniu, że cena wykonania każdej komendy (jej waga) jest proporcjonalna do długości operandów.

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.

Poprawność algorytmu: Dotyczy głównie metod i pojęć związanych z dowodzeniem poprawności algorytmów, takich jak: własność stopu, częściowa poprawność, metoda niezmienników itd.

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 i potomek wierzchołka:

Jeżeli istnieje droga prowadząca od wierzchołka v do w , to wierzchołek w nazywamy potomkiem v, a v przodkiem w.

Przechodniość - dla dowolnych a,b,c є S, zachodzi: jeśli aRb i bRc, to aRc (S to zbior, R to relacja).

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.

Równomierne kryterium wagowe - zakłada się, że każda komenda RAM potrzebuje na jej wykonanie jednej jednostki czasu, a każdy rejestr wykorzystuje 1 jednostkę pamięci

Rozmiar zadania (wejścia) - konkretna liczba

charakteryzująca objętość danych wejściowych.

rząd drzewa-najwyższy stopień węzła w drzewie

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.

sortowanie wewnętrzne-dane są przechowywane wyłącznie w pamięci wewnętrznej.

sortowanie zewnętrzne-w przeważającej części dane znajdują się poza pamięcia wewnętrzną.

Sterowanie - zmiana kolejności elementow pewnego

ciągu tak, aby zostały one ustawione w porządku

niemalejącym lub nierosnącym.

stopień węzła-to liczba jego synów.

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ł”.

struktury z ograniczonym dostępem-struktury posiadające z góry ustalony i charakterystyczny dla nich tryb dodawania i usuwania elementów.

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.

zadanie sortowania oraz charakterystyka dwóch klas algorytmów sortowania: Jeśli S jest zbiorem w którym jest określony porządek  a (a₁, a₂, ... , a_n ) ciągiem elementów z S to zadaniem sortowania jest wyznaczenie permutacji tj. pewnej kolejności (a₁, a₂, ... , a_n ) , zadanych n elementów takiej, że: a₁  a₂  ...  a_n .

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ść obliczeniowa algorytmu: Polega na określaniu zasobów jakie są potrzebne do wykonania algorytmu tzn. czasu obliczeń i pamięci. Często stosowana jest metoda polegająca na badaniu jak zwiększa się czas lub wielkość pamięci potrzebnej do wykonania algorytmu w miarę wzrostu rozmiaru danych wejściowych

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.

Zwrotność - dla dowolnego a є S, zachodzi aRa (S to zbior, R to relacja).

---