Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 25

Alfabet – skończony, niepusty zbiór obiektów nazywanych symbolami

Alternatywa – operacja boolowska OR

Argument – wartość wejściowa (dana) funkcji

Ciąg – uporządkowana lista obiektów

Cykl – ścieżka zaczynająca się i kończąca w tym samym wierzchołku

Dopełnienie – operacja zwracająca zbiór wszystkich elementów nienależących do danego zbioru

Drzewo – spójny graf niezawierający prostych cykli

Dwuargumentowa relacja – relacja, której dziedziną jest zbiór par uporządkowanych

Dziedzina – zbiór wszystkich możliwych wartości wejściowych (argumentów) funkcji

Element – obiekt należący do zbioru

Funkcja – operacja przekształcająca wartości wejściowe na wartości wyjściowe

Graf – zbiór punktów i linii łączących niektóre pary tych punktów

Iloczyn kartezjański – operacja na zbiorach tworząca zbiór wszystkich krotek złożonych z elementów odpowiednich zbiorów

Język – zbiór słów nad pewnym alfabetem

k-krotka – ciąg k obiektów

Koniunkcja – operacja boolowska AND

Konkatenacja – operacja łączenia ze sobą słów

Krawędź – linia łącząca wierzchołki grafu

Nieuporządkowana para – zbiór o dwóch elementach

Operacja boolowska – operacja na wartościach boolowskich

Predykat – funkcja, której przeciwdziedziną jest zbiór {TRUE, FALSE}

Prosta ścieżka – ścieżka bez powtarzających się wierzchołków

Przeciwdziedzina – zbiór, z którego pochodzą wartości wyjściowe funkcji

Przecięcie (iloczyn zbiorów) – operacja na zbiorach tworząca zbiór elementów wspólnych dla tych zbiorów

Relacja równoważności – relacja dwuargumentowa, która jest zwrotna, symetryczna i przechodnia

Relacja – predykat, którego dziedziną jest zbiór k-krotek

Singletonowy zbiór – zbiór jednoelementowy

Skierowany graf – zbiór punktów i strzałek (par uporządkowanych) łączących wybrane pary tych punktów

Spójny graf – graf zawierający ścieżki łączący dowolne dwa wierzchołki

Suma zbiorów – operacja na zbiorach łącząca wszystkie elementy uczestniczących zbiorów w jeden zbiór

Symbol – element alfabetu

Słowo puste – słowo o długości zero

Słowo – skończona lista symboli z pewnego alfabetu

Ścieżka – sekwencja wierzchołków grafu połączonych krawędziami

Uporządkowana para – lista o dwóch elementach, ciąg dwuelementowy

Wartość boolowska – wartości TRUE (prawda) lub FALSE (fałsz), często reprezentowane przez 1 lub 0

Wierzchołek – punkt w grafie

Węzeł (inaczej wierzchołek) – punkt w grafie

Własność – inaczej predykat

Zbiór pusty – zbiór, który nie ma żadnych elementów

Zbiór – grupa obiektów