힘들고 짜증난다

ㅈ씀

 

왜 이렇게 사는 게 힘들고 짜증날까

 

 

[이산수학]Group Code (군코드)

N이 group code인지 아닌지 확인하는 방법은 다음과 같다.

 

1. Identity 00....0 ∈ N (항등원이 N에 속한다)

2. x + y (mod 2 sum) ∈ N for x, y ∈ N

   (x와 y가 N의 원소이면 x+y도 N에 속해야 한다.)

 

 

 

 

[이산수학]Message Transmission (정보 전송)

컴퓨터에서 정보를 전송할 때는 0과 1로 구성된 코드를 보내게 되므로

노이즈라는 장애를 받아 0을 1로, 1을 0으로 수신하는 경우가 종종 생긴다.

이런 경우를 Transmission Error 라고 부른다.

 

이런 에러를 줄이기 위해 정보를 그대로 보내지 않고 encoding하여 보낸다. 특정한 encoding function을 이용해 b를 e(b)라는 code word로 바꾸어 보내는 것이다.

즉, b라는 word가 B^m에 속할 때,

x = e(b) ∈ B^m 인 encoded word로 바꾸어 보내게 된다.

이 때 B^n이 (m,n) encoding function이며 일대일 함수이다.

만약 이렇게 인코딩된 정보가 에러가 나면 도착 후에 에러를 검출할 수 있다.

 

보낸 정보와 받은 정보가 다르면 틀림없이 에러가 난 것이다. 이 때 한 자리 이상 k자리 이하만큼 다른 경우, k개 이하의 에러로 전송되었다고 말한다.

 

parity check code

e : B^m → B^m+1 와 같은 암호 함수를 parity check code라고 한다.

즉 단어의 끝에 한자리를 더 추가해서 보내는 것이다.

이 때 마지막 자리수는 단어의 1의 개수가 짝수이면 0, 홀수이면 1로 보낸다.

(x에 있는 1의 개수를 x의 무게(weight)라고 부르고 |x|로 표시한다.)

만약 짝수의 무게를 가진 수가 하나의 에러가 났다면 수신되는 단어는 홀수의 무게를 가지게 되므로 에러가 났음을 알 수 있게 된다.

 

(m, 3m) encoding function

m자리의 단어를 3번 반복해서 보낸다.

b = 011이라 가정하면 e(011) = 011011011이다. 만약 여기서 에러를 일으켜

한 개 또는 두 개의 에러가 났다면 검출이 가능하다.

 

Hamming distance

Hamming distance는 x와 y의 mod 2 연산을 한 결과의 무게이다.

mod 2 연산에 의하면 0과 1을 연산할 때만 1이 된다.

결과적으로 x와 y의 자리수가 얼마나 다른지를 알 수 있는 척도가 된다.

 

minimum distance

Hamming distance 중에거 무게가 가장 작은 것을 말한다.

(m,n) encoding function e : B^m → B^n이 k개 이하의 에러를 검출할 수 있는 필요 충분 조건은 minimum distance가 적어도 k+1이 되는 것이다.

 

 

[기독교]하나님은 변두리 인생을 택했다

ㅈ씀

 

  하나님은 항상 변두리 인생을 택해 일생 동안 주변인간으로 살았다고 한다. 또한 희망이 없는 사람들을 제자로 삼았으며 주님의 일을 도모하도록 맡겼다고 한다. 우리 주위에는 변두리 인생을 사는 사람들을 하찮게 여기는 사람들이 있다. 그리고 많은 사람들은 주류가 되고 싶어한다. 그런데 하나님은 변두리 인생을 일부러 택하고 일생 동안 마이너리티의 삶을 살았던 것이다. 이것은 오늘날 우리에게 시사하는 바가 크다.

 

  주류를 따르기보다는 변두리에서 희망을 잃어버린 채로 살아가고 있는 사람들과 어울리며 그들을 돕는 일은 매우 중요한 일이 아닐 수 없다. 이것을 교회로 확대하여 생각해보자. 교회는 지역사회에 전도를 하는 것도 하나의 중요한 목표이다. 그러나 전도에서 그치는 것이 아니라 지역사회에 관심을 가지고 일련의 활동에 참여하는 것 또한 매우 중요하다. 교회도 엄연히 지역사회 공동체의 일원이기 때문이다.

 

 

 

[이산수학]+ "mod 2" 덧셈

+ "mod 2" 덧셈은 이항 덧셈을 한 결과를 2로 나눈 나머지를 말한다.

그래서 그 나머지는 항상 0 또는 1이며, 이것은 컴퓨터에서 유용하게 쓰인다.

 

+  │  0     1

─┼────

0  │  0     1

1  │  1     0

 

mod 2 덧셈으로 0과 1을 연산한 결과는 위와 같다.

 

[이산수학]재귀 관계(Recurrence Relations)

전에 수열에 대한 내용을 다룰 때 formula에는 두 가지가 있다고 했다.

바로 재귀적(recursive) 공식과 명시된(explicit) 공식이 그것인데,

재귀 관계 (Recurrence Relation) 은 recursive를 explicit으로 변환하는 문제에 관한 내용이다.

recursive formula를 사용하려면 initial condition (초기 조건)이 꼭 있어야 하는데, 이 초기 조건과 공식을 이용해 어떤 열을 나타내는 게 바로 재귀 관계이다.

 

───────────────────────────────────

 

백트래킹 (backtracking)은 recurrence relation으로 정의된 sequence의

explicit formula를 찾기 위해 사용되는 기술로, 이전 항목의 정의로 대치함으로써 거꾸로 패턴을 찾아가는 것이다.

 

───────────────────────────────────

 

그러나 백트래킹으로 패턴을 찾지 못하는 경우가 있다.

만약 recurrence relation이 Homogeneous relation of degree k 인 경우에는

이차방정식을 푸는 방법으로 해결할 수 있다.

 

 

[이산수학]비둘기 집 원리 (Pigeonhole principle)

비둘기 집 원리 (Pigeonhole principle)

 

m < n 일 때 n 마리의 비둘기를 m 개의 비둘기 집에 배당하면,

최소 하나 이상의 비둘기 집에 둘 이상의 비둘기가 배당된다.

 

: 집이 4개밖에 없는데 비둘기가 5마리라면,

  적어도 한 집에는 2마리 이상이 있어야 한다.

 

언뜻보면 당연해보이는 비둘기 집 원리(Pigeonhole principle)는 실제로

강력한 증명 기술로 사용될 수 있다.

 

Pigeonhole principle의 원리를 확장해보자.

n 마리의 비둘기가 m 개의 비둘기 집에 배당될 때,

하나 이상의 비둘기집은 최소 [(n-1)/m]+1 마리의 비둘기가 배당되어야 한다.

이 식을 가지고서 여러 가지를 증명할 수 있다.