System liczb jednoargumentowych - Unary numeral system
| Systemy liczbowe |
|---|
| System liczb hindusko-arabskich |
| Azji Wschodniej |
| amerykański |
| Alfabetyczny |
| Dawny |
| Systemy pozycyjne według bazy |
| Niestandardowe pozycyjne systemy liczbowe |
| Lista systemów liczbowych |
Jednoargumentowy systemie liczbowym jest najprostszym systemie liczbowym do reprezentacji liczby naturalne : reprezentować numer N , symbol reprezentujący 1 jest powtarzany N razy.
W systemie jednoargumentowym liczba 0 (zero) jest reprezentowana przez pusty ciąg , czyli brak symbolu. Liczby 1, 2, 3, 4, 5, 6, ... są reprezentowane w liczbach jednoargumentowych jako 1, 11, 111, 1111, 11111, 111111, ...
W położenia ramy notacji , jednoargumentowa jest bijective baza - 1 systemie liczbowym . Ponieważ jednak wartość cyfry nie zależy od jej pozycji, można argumentować, że jednoargumentowy nie jest systemem pozycyjnym.
Użycie znaków zliczania w liczeniu jest zastosowaniem jednoargumentowego systemu liczbowego. Na przykład, używając znaku sumy | , liczba 3 jest reprezentowana jako ||| . W Azji Wschodniej kultur, liczba 3 jest reprezentowany jako三, znak narysowany z trzech uderzeń. (Jeden i dwa są reprezentowane podobnie.) W Chinach i Japonii znak 正, narysowany 5 kreskami, jest czasami używany do reprezentowania 5 jako sumy.
Liczby jednoargumentowe należy odróżnić od powtórzeń , które są również zapisywane jako sekwencje jedynek, ale mają swoją zwykłą dziesiętną interpretację liczbową.
Operacje
Dodawanie i odejmowanie są szczególnie proste w systemie jednoargumentowym, ponieważ obejmują niewiele więcej niż łączenie ciągów . Operacja wagi Hamminga lub liczenia populacji, która zlicza liczbę niezerowych bitów w sekwencji wartości binarnych, może być również interpretowana jako konwersja z liczb jednoargumentowych na binarne . Jednak mnożenie jest bardziej kłopotliwe i często jest używane jako przypadek testowy przy projektowaniu maszyn Turinga .
Złożoność
W porównaniu ze standardowymi pozycyjnymi systemami liczbowymi , system jednoargumentowy jest niewygodny i dlatego nie jest stosowany w praktyce do dużych obliczeń. Występuje w niektórych opisach problemów decyzyjnych w informatyce teoretycznej (np. w niektórych problemach P-zupełnych ), gdzie jest używany do „sztucznego” zmniejszania wymagań czasowych lub przestrzennych problemu. Na przykład podejrzewa się , że problem faktoryzacji liczb całkowitych wymaga więcej niż funkcji wielomianowej długości wejścia jako czasu wykonywania, jeśli dane wejściowe są podane w postaci binarnej , ale wymaga tylko liniowego czasu działania, jeśli dane wejściowe są prezentowane w postaci jednoargumentowej. Jest to jednak potencjalnie mylące. Użycie jednoargumentowych danych wejściowych jest wolniejsze dla dowolnej liczby, a nie szybsze; różnica polega na tym, że wejście binarne (lub o większej podstawie) jest proporcjonalne do logarytmu o podstawie 2 (lub większej podstawie) liczby, podczas gdy wejście jednoargumentowe jest proporcjonalne do samej liczby. W związku z tym, chociaż wymagania dotyczące czasu wykonywania i miejsca w trybie jednoargumentowym wyglądają lepiej w funkcji rozmiaru danych wejściowych, nie stanowią one bardziej wydajnego rozwiązania.
W teorii złożoności obliczeniowej numeracja jednoargumentowa jest używana do odróżnienia problemów silnie NP-zupełnych od problemów, które są NP-zupełne, ale nie silnie NP-zupełne. Problem, w którym dane wejściowe zawierają pewne parametry numeryczne, jest silnie NP-zupełny, jeśli pozostaje NP-zupełny, nawet jeśli wielkość danych wejściowych jest sztucznie zwiększona przez przedstawienie parametrów w postaci jednoargumentowej. W przypadku takiego problemu istnieją twarde przypadki, w których wszystkie wartości parametrów są co najwyżej wielomianowo duże.
Aplikacje
Numeracja jednoargumentowa jest używana jako część niektórych algorytmów kompresji danych, takich jak kodowanie Golomba . Stanowi również podstawę aksjomatów Peano do formalizowania arytmetyki w logice matematycznej . Forma notacji jednoargumentowej zwana kodowaniem Church jest używana do reprezentowania liczb w rachunku lambda .