진법(Positional notation)

이 개념 위에 세워진 것

이 개념을 언급하는 페이지

• 중간값 정리

  … 겹겹이 포개지면 정확히 한 점으로 모입니다. 이 사실도 실수에 빈틈이 없기 때문에 성립합니다. 이 구조는진법 전개와 같습니다. 처음 구간을 [0, 1]로 보고, 이분법의 매 단계에서 왼쪽 반을 남기면 0, 오른쪽 반을 …

• 칸토어의 대각선 논법

  … 수열)로 시작합니다. 0과 1 사이의 실수는 이진 소수 0.b_1b_2b_3\ldots 로 쓸 수 있으니(진법), 이진 수열의 목록은 실수의 목록과 거의 같습니다. '거의'인 까닭은 아래에서 다룹니다. 이제 이진 …

• 멱집합

  … 증명됩니다. "넣는다"를 1, "뺀다"를 0으로 적으면 부분집합 하나가 n 자리 이진수 하나가 됩니다(진법). 같은 말로, 부분집합은 원소마다 참이나 거짓을 정하는 함수 A \to \{0, 1\} 이고, 함수 …

• 칸토어 집합

  … 점이 이 집합에 들어갈 확률은 0입니다. 그런데 남은 점은 결코 적지 않습니다. 점을 3진법으로 쓰면(진법), 가운데 3분의 1을 지우는 것은 "어떤 자리에 1이 있는 수"를 지우는 것입니다. ( 1/3 = …

• 무리수

  … 이유로 q 도 짝수입니다. 분자와 분모가 모두 2로 나누어떨어지니 기약분수라는 가정에 어긋납니다. 무리수를소수 전개로 쓰면 끝나지도 순환하지도 않고 이어집니다. 흔히 √2 = 1.41421356…처럼 소수점 아래가 끝없이 …

• 파스칼의 삼각형

  … 그대로 성립하기 때문입니다. 정확한 규칙도 있습니다. \binom nk 가 홀수일 필요충분조건은 k 를2진법으로 썼을 때 1인 자리가 모두 n 에서도 1인 것입니다(뤼카의 정리). m 이 소수 p 이면 p 번째 …

• 모듈러 연산

  … \cdot \omega^b = \omega^{a+b} , 곧 회전의 합성입니다. 우리가 수를진법으로 쓸 때 마지막 자리는 10으로 나눈 나머지입니다. 오른쪽 곱셈표에서 가로줄 a (노란 테두리)를 …

• 등비급수

  … 1/10인 등비급수라 합이 \tfrac{9}{10} / (1 - \tfrac{1}{10}) = 1 입니다(진법 전개). 칸토어 집합을 만들며 잘라 낸 길이 \tfrac13 + \tfrac29 + …

• 연속체 가설

  … 크기를 2^{\aleph_0} ('2의 알레프 0 제곱')라 적습니다. 0과 1 사이의 실수를이진 전개로 적고 1이 있는 자리들을 모으면 자연수의 부분집합 하나가 나옵니다. 예를 들어 0.101_2 는 {1, …

• 대수적 수와 초월수

  … 흔히 드는 예는 1이 1!, 2!, 3!, \dots 번째(1, 2, 6, 24, … 번째) 자리에만 있는십진 전개0.110001000\ldots 입니다. 1이 나오는 자리가 급격히 멀어져서, 앞부분에서 끊은 분수가 …

• 칸토어 함수

  … 0인 집합 속으로 숨어 버립니다. 값을 직접 구할 수도 있습니다. 노란 점 x 를 끌어 보세요. x 를3진법으로 쓰면 입니다. 처음 나오는 1까지만 읽고(그 1은 그대로 둡니다), 그 앞의 2를 모두 1로 바꿔 …

• 로지스틱 사상

  … 한 걸음이 각도 θ를 두 배로 만드는 일이고, 정수 부분은 결과에 영향이 없으니 버려도 됩니다. θ를이진법으로 적으면 두 배는 소수점을 한 칸 옮기는 일입니다. θ = 0.1011…₂이면 두 배는 …

• 오일러 경로

  … 000, 001, 010, 101, 011, 111, 110, 100이 차례로 나타나며, 모두 3자리이진수입니다. 네덜란드의 수학자 니콜라스 드 브라위언의 이름을 따 드 브라위언 수열이라 부르는데, 오일러 …

• 4색 정리

  … 나라가 n개일 때 규칙을 따지지 않고 네 가지 색을 나눠 주는 방법은 모두 4^n 가지, 곧 n자리4진수의 개수이지만, 되추적은 막힌 가지를 일찍 잘라 냅니다. 이 지도에서 다 칠하고 나면 같은 색 나라들의 …

• 해밍 거리

  … 1001001은 셋째와 다섯째 자리가 달라 해밍 거리가 2입니다. 0과 1로 된 비트열이라면, 두 수를이진수로 적어 자리마다 비교하는 셈입니다. 비트열을 '1이 있는 자리들의 집합'으로 보면, 해밍 거리는 둘 중 …

• 불 대수

  … 넘어갑니다. 반가산기 둘과 OR 하나로 올림까지 받는 전가산기를 만들고, 이를 줄줄이 이으면 여러 자리이진수의 덧셈기가 됩니다. 여러 비트를 XOR로 이어 붙이면 1의 개수가 홀수일 때 1, 짝수일 때 0이 …

• 튜링 기계

  … 간 다음, 1을 0으로 바꾸며 받아올림을 왼쪽으로 넘기다가 0이나 빈칸을 만나면 1을 쓰고 멈춥니다.이진법의 받아올림 그대로입니다. 회문 검사 는 abba처럼 앞에서 읽으나 뒤에서 읽으나 같은 문자열(회문)인지 …

• 람다 계산

  … 'n번 적용하기를 m번 되풀이'입니다. 막대를 세는 1진법과 같아서 큰 수일수록 길어집니다. 실제 계산기는이진법을 쓰지만, 원리를 보는 데는 이것으로 충분합니다. 노란 부분이 다음에 적용될 함수, 분홍 부분이 그 …

• 처치–튜링 논제

  … 양옆, 세 칸만 보고 다음 값을 정하는 세포 자동자에서 규칙 번호는 여덟 가지 이웃 모양에 대한 답을이진수로 읽은 수입니다. 규칙 은 이고, 처음 줄은 입니다. 규칙 110은 보편 계산이 가능합니다. 끝없이 …

• P 대 NP 문제

  … 수 있는 부분집합은 멱집합의 크기인 2^n 개입니다. 탐색은 부분집합에 0부터 2^n - 1 까지의이진수번호를 붙여 차례로 셉니다. n이 하나 늘 때마다 시도할 것이 두 배가 됩니다. 요령을 부리면 조금 줄일 …

• 유한 오토마톤

  … 나머지만 기억합니다. 지금까지 읽은 이진수가 m이면 다음 비트 b를 읽은 뒤의 수는 2m + b 입니다(진법). 그러니 m을 3으로 나눈 나머지 r만 알면 다음 나머지 (2r + b) \bmod 3 을 알 수 …

• 정보 엔트로피

  … 2의 거듭제곱이면 이 값은 n가지 중 하나를 이진법으로 적는 데 필요한 자릿수와 같습니다(8가지면 3자리,자릿값 기수법). 확률이 치우칠수록 엔트로피는 작아집니다. 엔트로피는 압축의 한계이기도 합니다. 여섯 글자의 확률을 …

• n-그램 언어 모델

  … 것의 비율입니다. 가능한 n-그램은 기호가 V가지일 때 V^n 개로, V진법 n자리 수만큼 늘어나지만(자릿값 기수법), 말뭉치는 그 가운데 극히 일부만 담습니다. 차원의 저주와 닮은 현상이고, 지프의 법칙의 긴 …

• 알고리즘

  … 따라 해도 같은 결과가 나와야 합니다. 이름은 9세기 바그다드의 학자 알콰리즈미에서 왔습니다. 인도식자리값 기수법으로 계산하는 법을 다룬 그의 책이 라틴어로 옮겨지면서, 그의 이름이 '계산 규칙'을 뜻하는 말이 …

• 이진 탐색

  … 빼면, 비교 한 번의 답은 '앞' 아니면 '뒤', 곧 1비트입니다. 그래서 이진 탐색은 찾는 자리의 번호를이진수로 한 자리씩 알아내는 것과 같습니다. 거꾸로, n개 가운데 하나를 가리키려면 적어도 \log_2 n …

• 정렬 알고리즘

  … 안에서는 들어온 순서를 그대로 지켜야 앞 단계에서 맞춰 둔 아랫자리 순서가 망가지지 않습니다. 비교 대신진법의 자릿수를 이용하므로 비교 정렬의 하한을 비켜 가고, 자릿수 k가 정해져 있으면 k(n + 10) 번 …

• 비교 정렬의 하한

  … 가장 많이 줄이는 것을 욕심껏 고릅니다. 비교 말고 다른 연산을 쓰면 한계를 넘을 수 있습니다. 수를자릿수별로 칸에 나눠 담는 기수 정렬은 자릿수가 정해져 있으면 O(n) 입니다.

• 욕심쟁이 알고리즘

  … 최적화에서 경사 하강법이 빠지는 함정도 같은 모양입니다. 이어지는 곳. 1, b, b², …처럼진법의 자릿값으로 된 동전이라면 욕심쟁이가 언제나 최적이고, 그 답은 금액을 b진법으로 쓴 각 자리의 …

• 힙과 우선순위 큐

  … 다음에 일어날 사건을 시각순으로 꺼내는 데 씁니다. 배열 번호를 1부터 매기면 i번 칸의 부모는 i를이진법으로 쓰고 마지막 자리를 지운 수입니다. 예를 들어 6은 이진법으로 110이고, 마지막 자리를 지운 11은 …

• 허프만 부호

  … 줄입니다. 이어지는 곳. 고정 길이 부호는 k가지 글자에 \lceil \log_2 k \rceil 자리의이진수를 주는 것입니다. '고른 글'처럼 8가지 글자가 똑같이 흔하면 허프만 부호도 글자마다 3비트라 둘이 …

• 원천 부호화 정리

  … 될 수 없습니다. 이 몫을 수로 재 봅시다. 0과 1이 끝없이 이어지는 비트열 앞에 '0.'을 붙여이진 소수로 읽으면 0 이상 1 미만의 수가 됩니다. 이 범위를 [0, 1)로 씁니다. 10으로 시작하는 비트열은 …

• 산술 부호화

  … [0, 1) 안의 수 하나로 적습니다. 씨앗은 1948년 섀넌의 논문에 이미 있었습니다. 누적 확률을이진 소수로 적어 부호어로 쓰는 방법입니다. 이것을 기호마다 구간을 좁혀 가는 방식으로 이어 쓰자는 생각은 …

• 수 체계: 자연수에서 실수까지

  … 사람이 만들었다'는 이 사다리를 아래에서 본 말입니다. 이어지는 곳. 실수를 유리수로 다가가는 방법으로는진법의 소수 전개와 연분수가 있고, 황금비는 연분수의 항이 모두 1이어서 분수로 가장 다가가기 어려운 …

• 정수론

  … 생성함수이고, 1의 거듭제곱근은 나머지 계산을 원 위의 회전으로 바꿉니다. 수를 적는 방법은자리값 기수법에, 자연수에서 실수까지의 전체 그림은 수 체계에, 새 수 체계의 대수는 군과 다항식에 …

• 위치 인코딩의 변천

  … 47,100토큰). 이진수로 수를 셀 때 맨 끝 자리는 매번, 그 앞자리는 두 번에 한 번 바뀌는 것처럼(자릿값 기수법), 빠른 짝과 느린 짝을 함께 보면 위치를 읽을 수 있다는 생각입니다. 다만 이진수와 달리 주기는 짝마다 …

• 님과 스프라그–그런디 정리

  … 따르면 미국의 대학과 장터에서 여러 형태로 놀던 게임이었습니다. 그의 규칙은 이렇습니다. 무더기의 크기를이진법으로 적어 자리를 맞추고, 모든 자리에서 1의 개수가 짝수이면 차례인 사람이 집니다. 1, 2, 3은 …

• 배타적 논리합

  … \lor b) \land \lnot(a \land b) , 곧 'OR이면서 둘 다는 아님'입니다. 수를이진법으로 적으면 XOR을 자리마다 따로 할 수 있습니다. 컴퓨터의 비트 연산 XOR이 이것입니다. …

이 페이지가 가리키는 개념