| [ QuizWit ] in KIDS 글 쓴 이(By): guest (roro) 날 짜 (Date): 1998년 4월 15일 수요일 오후 03시 52분 33초 제 목(Title): [답[ 위의 알고리듬 학부때 이런비슷한 문제에 대해 한참 생각해본적이 있습니다. 그당시 페이퍼좀 들쳐봤는데 생각보다 쉽습니다. 크크.... 제가 이보드 초창기에 비슷한문제 (knapsack problem & coin exchange problem generalized to fraction) 에 대한 대충의 풀이를 올려논기억이 있는데 참조하기 바랍니다. 못찾으시겠으면 카이스트 메뜨비비라고 있었던것같던데 누가 캡쳐해서 올려놨던걸로 기억하고 있습니다. 아직도 있나모르겠군요. 대충 이런 유사 알고리듬에 대해 저널에서 찾고싶으면 다음의 키워드를 이용하세요. 1. egyptian fraction 이집시안 스펠이 맞나? 2. erdos 유명한 헝가리 수학자. 이분이 80년대에 journal of computation에 그래햄이던가(가물가물..) 하고 같이 비슷한 문제에 대한 알고리듬을 퍼블리쉬했습니다. 3. 이문제는 뉴메리칼 아날리스스랑은 전혀 상관이 없습니다. exact 하게 유한스텝안에 풀리니까요. 4. solution (x1,x2,x3..xn) 에 ordering을 줄수 있습니다. 어떠한 콘디션에서 이 ordering 은 unique하게 표현될것입니다. 제가 구했던 해법은 분모 (a1,a2,...) 이 aj mod a(j-1) = 0 일경우 degenerate case를 빼고 unique 한 표현으로 나타납니다. 증명은 생각보다 그렇게 쉽지 않습니다. 5. 위의 4를 이용해서 위의문제를 정수 Z 에서 유리수의 집합 Q로 확장할수 있습니다. 유리수로의 확장은 trivial 합니다. 그러나 더욱 놀라운건 Q 에서 실수 R로 확장할수있습니다. 확장의 엄밀성을 위해서는 알고리듬적 해법에서 벗어나 수열의 convergence에 대해 증명을 해야합니다. 하지만 R이 complete space 이기 때문에 이런 확장역시 trivial하게 됩니다. 실수계로 이문제를 확장하게 되면 unique representation of real number 라는 중요한 문제에 도달하는데 이건 위의 4가 유일한 representation이 됩니다. ( continued fration representation 같은게 아닌 field에서의 addition & subtraction으로만 오퍼레이션을 한정할때에 한해서) 6. 위의 5에대해서는 아직 페이퍼가 거의 없습니다. ^^ 석사 논문수준으로는 좋은 리써치 페이퍼 토픽입니다. 7. 한가지 예로 데시말이나 바이나리가 바로 위의 4의 special solution 입니다. 굳이 데시말 representation을 쓰고싶지 않다면 다음과같은 unique knapsack solution에의한 factorial representatin이나 prime factorization representation이 있습니다. example. 임의의 실수 x = sum ( x_j/ (j!)) 위의 조건을 만족하는 정수해는 degenerate한경우를 빼고 unique합니다. 혹은 펙토리알 대신 프라임 펙토라이제이션을 써도 됩니다. 모두 4의 special 케이스입니다. 8. 유닉하다는 의미는 ordering을 주었을때한한거죠. total ordering 을 안주면 뭐 아무 의미가 없죠. 특수한 ordering을 줄경우 재미있는 토픽으로 들어갑니다. example: shur partial ordering= majorization 위의 정리에 이름이 붙어있습니다. 환상정리 (1994) 낄낄...94년도에 발견했거든요. |