1-1.0 PP Project 1 Test Program

bpy

SNU Principles of Programming Fall 2014

Duststorm test program

Download Link : pp_prj1_test

 

Author : KINETC_ (Jhoo Ho Young / [email protected]) 2014/11/22
Developed with Qt, PySide, PyDev, cx_freeze
Available for Windows
Released as open source under LGPL license

——— how to use ———–
in ocaml
1. move prj1_test.ml to project 1 folder
2. ocamlc prj1.ml
3. ocaml prj1.cmo prj1_test.ml
4. copy results (robots, shelters, results)

in windows
5. run build/prj1_test.exe
6. paste results in each text browser
7. click assign button
8. …
9. PROFIT!

 

—————————–

pp 플젝 1번 테스트를 하려고 했더니 답이 없어서

그냥 프로그램을 만들어버렸다.

한번도 안써본 Qt를 다뤄보려니…

역시 비주얼 베이직 써볼걸 그랬군

Read More

1-0. 1/3-2/3 Conjecture

순서론에서의 한 추론이다. 무려 50년이 되도록 미증명상태

 

0. 기본 지식

어떤 유한한 set이 있다고 하자. 대충 A = {a, b, c} 의 부분집합들의 집합

B = {{}, {a}, {b}, {c}, {a, b}, {a, c}. {b, c}, {a, b, c}}

를 가정하자.

이 때, B의 각 원소를 원소의 갯수에 따라 정렬한다고 하면 {}, {a} 같이 대소 비교가 되지만 {a}, {b} 같이 대소 비교가 안되는 놈이 존재한다.

그래도 어쨌든 대소비교가 되는것 끼리 모일 수 있으므로 대충 저 위의 꼴과 비슷하게

{} -> {a},{b},{c} -> {a, b}, {b, c}, {c, a} -> {a, b, c} 순으로 정렬 된다. (각 step의 내부의 순서는 무시하고)

요런 놈을 partially ordered set, 줄여서 poset이라고 한다. (원소간에 대소비교가 불가능한게 있어도 된다. 만약 임의의 원소 두개에 대해 전부 가능하면 totally ordered set이라고 한다.)

대소 비교를 할때는 반드시 대소 비교를 하는 부등호가 존재하므로 위에서 정렬 할 때 사용한 부등호를 <= 라고 하자.

그러면 한 집합을 <=에 대해 poset이 되게 정렬하려면 <= 는 다음의 성질을 만족해야 한다.

(1) a<=a

(2) a<=b, b<=a -> a=b

(3) a<=b. b<=c -> a<=c

3가지 모두 당연한 성질이지만, (2)번 때문에 대소 비교가 되지 않는 두 원소는 대소가 같은것이 아니라 그냥 대소 비교 자체가 정의가 되지 않은것으로 처리된다.

그러면 자연히 그 두 원소의 비교가 가능하게 만드는 부등호로 위의 <=를 확장 시킬 방법이 있는지 찾게 될텐데 (예를 들면 위의 A를 알파벳 순으로 정렬한다던가)

그놈을 <=*라 하면 <=*는 <=의 linear extension 이라고 한다.

 

1. Conjecture의 내용

이 때, partially ordered set이면서 totally ordered가 되지 않은 유한집합 P가 있다고 하자. 정렬은 부등호 <=로 한다.

그러면 p가 totally ordered가 아니므로 <=의 linear extension들이 여러개 존재하게 된다.

이 <=의 linear extension들의 집합을 L이라고 하자. (P가 유한집합이기 때문에 L도 당연히 유한집합이다.)

그러면

“P의 어떤 두 원소 x, y에 대해

|L| * 1/3  <= { x(<=”)y | (<=*)는 L의 원소} <= |L| * 2/3

이 되는 x, y가 항상 존재한다.”

가 Conjecture의 내용이다.

 

세줄로 요약하면

“대소비교를 정의하는 도중에

어떤 두 원소의 대소를 정의해버리면

남은 정렬 방법의 수가 1/3이상 2/3이하가 되는 두 원소가 존재한다.”

 

좀 더 실용적으로 말하자면

a<b<c<d

1<2<3<4

현재까지 이렇게 정렬되어있다고 할 때,

a<4를 정의하는 것 보다 d<1을 정의 하는 것이 남은 정렬 방법의 수가 훨씬 적어지게 된다.

문제는 이걸 임의의 집합에서 임의의 정렬 상태와 step에 대해 정렬 방법의 수를 언제나 2/3 이하로 줄일 수 있는 두 원소를 찾을 수 있냐는 것이다.

 

2.

대충 생각하면 정렬 방법의 갯수는 n!개고 항상 찾을 수 있다면 알고리즘을 잘 짜면

정렬 시간이 log_(2/3) n! ~ O(n logn)이 된다는 소린데

수많은 O(n logn) 알고리즘들이 있는걸 보면 말이 되는것 같기도 하고…

문제는 이게 증명도 반증도 안되어있다는 걸 보면 또 그렇게 간단한것도 아닌것 같다.

 

이런 conjecture가 나온 배경에는

a<=b 가 정의되어 있고 거기에 c를 끼워 넣을때

a<=b<=c, a<=c<=b, c<=a<=b, 3가지 경우가 존재하는데

a<=c를 정의하면 남는건 왼쪽 2개밖에 없고, b<=c를 정의하면 왼쪽 1개밖에 안 남아서

딱 남은 정렬의 갯수가 1/3-2/3 사이에 놓이게 된다.

이게 원소가 n개일때도 가능하냐는 말이지.. (이렇게 보니 되게 제한이 빡빡하군)

 

가능 할것 같은데…

 

 

 

Read More