[jaewooklee]

0. 1번 문제의 출력 리스트는 정렬되어야 하나요?

1. 1번 문제의 코멘트는 어느정도로 상세해야 하나요? 저는 코멘트를 쓰다보니 코드 자체보다 증명이 더 길어지는 것 같네요..

2. 2번 문제에서 달성해야 할 정밀도는 얼마가 되어야 하나요?

3. 2번 문제에, '주어진 행렬이 Markov 행렬이고 그 극한이 유일하게 존재하도록 변환시킨 후 그 극한을 계산하는 함수 markov_limit을 작성하라.'고 쓰여져 있는데요. 이는 어떤 특정한 방식으로 극한을 구해야 한다는 것을 의미하나요? 단순히 극한의 정의를 사용하여 극한을 계산하는 것은 금지되나요?

4. 2번 문제에서 극한이 유일하게 존재하지 않는 경우도 있을 수 있다는 것인가요? 초기 벡터가 [1/N;1/N;...] 또는 [1;1;..]인 경우에도 그런 것이 가능한가요? markov_limit 함수가 위와 달리 [1;0;0;..] 모양인 초기 벡터에 대해서도 잘 작동해야 하나요? 극한이 유일하게 존재하지 않는 경우에는 무엇을 반환해야 하나요?

5. 3번 문제에서 '변환전 확인사항'이 모두 만족되었는지를 확인하기 위해 check_exp라는 함수를 구현하여야 하는데요.

만일 repeat (read 1)과 같은 프로그램이 입력으로 들어왔을 경우, read의 값이 음수가 될 수도 있으므로 음수인 경우에는 repeat이 불가능하지만, 양수라면 repeat이 가능합니다.

이런 경우에 check_exp는 false를 반환해야 하나요? 그러니까 프로그램이 올바른지의 여부를 가능한 한 보수적으로 체크해야 하는 것인가요?

한편, 위와 비슷하지만 repeat ((read+100) 1)과 같은 입력은 read로 입력받을 수 있는 수의 범위가 -100부터 100까지이므로 항상 유효한 프로그램입니다. 이 경우에는 check_exp는 true를 반환해야 하나요?

비슷하게, if 1 0 (repeat -1 1) 과 같은 입력은 유효한가요? 즉, if의 true statement만 taken 되어서 repeat 자체를 무시해도 되는 경우에는 check_exp가 어떻게 출력해야 하나요.

6. 위의 질문에 이어서, if를 구현할 때, short-circuit evaluation으로 만들어야 하나요? 아니면 그냥 모두 계산하게 만들어도 되나요?

7. 3번 문제에서 repeat(곱하기)을 구현할 때, 단순하게 더하기를 여러번 하는 것으로 구현하였다고 하면, 혹시 큰 수를 곱할 때 실행속도가 느려지는 문제가 있지 않을까 걱정되는데요. 3번 문제에서 실행속도는 고려하지 않아도 되나요?

8. 3번 문제를 풀때 OCaml의 imperative feature를 사용하여도 되나요?

감사합니다.

[김윤승]

0. 채점은 정렬 관계없이 할 것이고, 문제나 뼈대코드에 정렬하라는 지시가 없다면 안 해도 됩니다.

1. 여러 가지 가능한 증명들이 있을텐데, 제가 기대하는 분량은 3~4줄 이하입니다.
엄밀한 증명이 아니라 정확한 논리만 밝히면 됩니다.

2. 오차는 대략 0.0001정도 이하로 수렴하면 됩니다. 안전하게 하시려면 이보다 더 오차를 작게 설정하시면 될 것입니다.

3. 저 문장의 의미는, 임의의 Markov 행렬이 다 유일한 평형점 (수렴하는 극한점)을 가지는 것이 아니기 때문에 유일하게 가지도록 변환해서 극한을 구하라는 의미입니다. 수렴할 때까지 단순히 극한을 계산해도 됩니다.

4. 3번 질문과 관련 있는 것 같은데, 단순히 1,2,3 노드가 있을 때, 1이 2와 3을 가리키고, 2는 1만, 3도 1만 가리킨다고 했을 때 (1/3,1/3,1/3)이 수렴하지 않고 진동하는 것 같습니다. 한 번 확인해보세요.

3번 문제와 관련된 5, 6, 7, 8번 문제는 저도 정확한 스펙 파악이 안 되어서, 빠른 시일 내에 다시 답변드리겠습니다.

[김윤승]

2번 문제에 대해서, 행렬이 극한이 존재하도록 변환할 때, 학생들께서 임의로 선택하실 수 있는 자유도가 있습니다. 적절하다고 생각되시는 선에서 적당히 선택해주세요. 완전히 이상한 선택만 아니면 이로 인해 불이익을 보시는 일은 없을 것입니다.

[jaewooklee]

답변 감사드립니다.

그런데 3.에 대한 답변에서 행렬을 변환한다는 것이 어떤 의미인지 잘 모르겠습니다.
저희가 임의로 행렬에 쓰여진 값을 바꾸게 된다면 그건 그냥 다른 문제를 풀게 되는 것이 아닌가요?

예를 들어, 조교님이 말씀하신 경우에서,

행렬 A=
0. 1. 1.
.5 0. 0.
.5 0. 0.

b=[1/3;1/3;1/3]
로 주어진다면
markov_limit A b 는 무엇을 출력해야 하나요?

가장 그럴듯한 평형점은 진동하는 두 값의 평균인 [1/2;1/4;1/4]이 될 것 같은데요.
그렇다고 markov_limit 함수를 무조건 (b에 상관없이) A의 평형점을 찾는 함수로 만들게 된다면, b라는 초기값을 넣어주는 의미가 사라지는 것이 아닌지 궁금합니다.

모든 Markov 행렬이 nonzero인 평형점을 적어도 1개는 가지기 때문에, 그것을 계산하는 프로그램을 찾아내는 것은 별로 어렵지 않을 것 같습니다.

그렇지만 만일 단순하게 A의 평형점을 찾아내는 프로그램을 작성한다면, 평형점이 여러개 있는 경우, 예를 들어 A=I_3(identity matrix)로 주어질 경우에는 임의의 분포벡터가 모두 평형점이 되는데요. 이러한 경우에 markov_limit I_3 b가 무엇을 출력해야 하는 것인지 궁금합니다.

[김윤승]

실제 Pagerank 알고리즘이 어떻게 동작하는지를 생각해보면 이해가 되실 것 같은데요,

Pagerank 알고리즘에서도 입력된 자료인 페이지들간의 링크 말고도 임의로 우리가 정해야 하는 상수가 있습니다.

혹시 자료가 필요하신 분들은 작년 게시판에도 링크되어있는 자료를 읽어보시면 도움이 될 수 있을 것 같습니다.

http://www.cs.berkeley.edu/~sinclair/cs294/n2.pdf

채점은 "변환시킨 행렬에 대해서" 극한을 제대로 구했는지만 체크할것입니다.

변환을 할 때 사용하는 상수 등은 자유롭게 정하실 수 있습니다.

[김윤승]

5. repeat read .. 의 경우에는 false를 반환해야 합니다. 하나라도 틀린 실행이 있다면 false를 반환해야 합니다.
반대로, 모든 실행이 올바르다면 최대한 true를 반환하도록 해야 합니다.

이를 완전하게 정확히 아는 것은 쉽지 않기 때문에, 할 수 있는 선에서 true를 반환하도록 해보세요.

너무 어려운 예시는 테스트하지 않습니다.

이 다음에 들으신 예시 2개는 true를 반환할 수 있습니다.

6. 조건이 있는 것은 아닙니다. 만약 if 1 0 (repeat -1 1)과 같은 경우를 올바른 식으로 인정하면서 모양 그대로 변환하는 경우에는 repeat -1 1을 계산하지 않는 게 좋을 것 같습니다.

7. 프로젝트의 실행 시간 제한은 이후 공지하겠습니다.

8. 네 괜찮습니다.

[jaewooklee]

좋은 자료 감사드립니다.

그렇지만 사실 아직도 '행렬을 변환시킨다'는 것이 어떤 의미인지는 아직 잘 모르겠습니다.

올려주신 자료에 따르면, 주어진 행렬을 irreducible이고 aperiodic인 것으로 바꾸어주면 극한이 유일하게 존재하게 되는 것 같은데요.

어떻게 해야 주어진 행렬이 자연스럽게 위의 조건을 만족하게 변환시킬 수 있는지가 명확하지 않은 것 같습니다. 예를 들어, 원래 주어진 행렬을 P에서 Q로 변환시킨다고 할때, P와 Q의 차이가 너무 크면 P 대신 Q에 대해 문제를 푼 답이 테스트를 통과하지 못할 것이 염려되고, P와 Q의 차이가 너무 작다면 Qⁿx가 Pⁿx와 다를것이 없어서 극한이 유일하지 않은 문제가 생기지 않을까 걱정됩니다. P에서 Q로 행렬을 변환시킬때 어느 정도의 변환이 허용되는 것인지 잘 모르겠습니다.

아직 프로젝트는 제출 기한이 많이 남았으니 제가 PageRank에 대해서 더 공부를 해보고 나중에 다시 질문을 드리도록 하겠습니다.