Bal

Front 1

drzewo

Back 1

Front 2

korzeń

Back 2

Rekord w strukturze drzewa, który

ma w polu wskaźnikowym na rodzica adres pusty NIL.

Front 3

pola wskaźnikowe rekordu w drzewie

Back 3

Mogą wskazywać na wiele rekordów potomnych

oddalonych od pierwszego (korzenia) o taką samą liczbę wskazań, które należy odczytać np. w celu poznania zawartości ich pola kluczowego,

Front 4

węzeł/wierzchołek drzewa

Back 4

każdy rekord w strukturze drzewiastej nazywany

Front 5

liść

Back 5

Rekord, w którym wszystkie pola wskaźnikowe

przeznaczone do wskazywania rekordów potomnych zawierają adres pusty (NIL) .

Front 6

gałąź

Back 6

Oba wskazania razem, które występują

pomiędzy dwoma rekordami będącymi
dla siebie bezpośrednim rodzicem
i potomkiem.

Front 7

poziom drzewa

Back 7

Określa dla danego rekordu liczba wskazań (adresów), które należy odczytać poczynając od wskaźnika na korzeń drzewa np. w celu poznania zawartości jego pola kluczowego.

Front 8

rząd drzewa

Back 8

Największa liczba wierzchołków potomnych jaką można znaleźć wśród wszystkich jego wierzchołków (jest to zatem największa

liczba pól w tym samym rekordzie, które wskazując na rekordy potomne nie zawierają pustego adresu).

Front 9

drzewo binarne

Back 9

Drzewo, w którym żaden wierzchołek nie ma więcej niż 2 wierzchołki potomne.

Front 10

drzewo pełne

Back 10

Drzewo, w którym wszystkie wierzchołki poza liśćmi mają jednakową liczbę potomków i wszystkie liście są na tym samym poziomie.

Front 11

Drzewo BST

Back 11

Drzewo binarne, w którym dla dowolnie

wskazanego wierzchołka spełnione są dwa warunki: żaden z elementów zapisanych w wierzchołkach jego lewego poddrzewa nie jest większy od elementu zapisanego w tym wierzchołku i żaden z elementów zapisanych w wierzchołkach jego prawego poddrzewa nie jest mniejszy od tego elementu .

Front 12

programownie dynamiczne

Back 12

Dwuetapowa metoda polegająca najpierw na stopniowym gromadzeniu dodatkowej wiedzy o wszystkich możliwych cząstkowych rozwiązaniach zadania, a potem na wykorzystaniu tej wiedzy do wybrania najlepszego rozwiązania.

Przykładem zastosowania metody jest algorytm wyznaczania
najkrótszej drogi w grafie skierowanym

Front 13

Algorytm całkowicie poprawny

Back 13

Algorytm, dla którego udowodniono, że nie zawiera on ani błędów

logicznych, ani algorytmicznych.

„Dany algorytm dla każdego zestawu dopuszczalnych danych wejściowych samoistnie przestaje działać po wykonaniu skończonej liczby operacji elementarnych, dając oprawny (spełniający założone warunki) wynik końcowy”

Front 14

Algorytm częściowo poprawny

Back 14

Dla każdego zestawu dopuszczalnych danych wejściowych z faktu, że dany algorytm samoistnie przestał działać po wykonaniu skończonej liczby operacji elementarnych wynika, że dał poprawny (spełniający założone warunki) wynik końcowy.

Front 15

Metoda niezmienników (częściowa poprawność)

Back 15

- wybraniu w schemacie algorytmu punktów kontrolnych,
- związaniu z każdym punktem kontrolnym tzw. asercji, czyli warunku logicznego zależnego od stanu realizacji procesu wyznaczania założonego wyniku końcowego,

- ustaleniu w obrębie każdej z iteracji takiej asercji, której prawdziwość będzie można wykazać po dowolnej liczbie powtórzeń tej iteracji (tzw. niezmiennik iteracji),
- wykazaniu, że z prawdziwość jednej asercji wynika prawdziwość następnej, że niezmienniki pozostają prawdziwe po kolejnych iteracjach i pociągają za sobą prawdziwość ostatniej asercji, która oznacza osiągnięcie założonego wyniku.

Front 16

metoda zbieżników (całkowita poprawność algorytmu)

Back 16

- ustaleniu dla każdej iteracji zbieżnika, czyli takiej zmiennej, której wartości zależą od stanu realizacji algorytmu po wykonaniu kolejnych powtórzeń tej iteracji i tworzą ograniczony ciąg

monotoniczny,
- wykazaniu, że każdy ze zbieżników nie może zmieniać się nieskończoną liczbę razy i algorytm po wykonaniu skończonej liczby powtórzeń w każdej z iteracji zatrzyma się w ostatnim

punkcie kontrolnym.