배요한
Site Admin
가입: 2018년 3월 6일
올린 글: 107
|
 올려짐: 2018년9월11일 1:30 주제: [숙제 2] 공지사항 (0911 추가) |
 |
|
안녕하세요, 수강생 여러분.
숙제 2가 올라왔습니다.
내용 : http://ropas.snu.ac.kr/~kwang/4190.310/18/hw2.pdf
제출 : http://ropas.snu.ac.kr/~ta/4190.310/18/submit/index.pl
기한 : 9/21 밤 11시 59분 59초
제출 페이지에서 학번을 아이디로 하여 가입(register)하신 다음 해당 계정으로 로그인하여 숙제를 제출하시면 됩니다. 가입 기간은 10/29 일까지입니다.
* 과제 관련 주의 사항
과제를 제출하기 전에 꼭 주의사항(https://ropas.snu.ac.kr/phpbb/viewtopic.php?t=6525)을 확인해 주세요.
* 뼈대코드
숙제 2은 뼈대코드가 없습니다
* 숙제 스펙 세부사항
(이 글에 답글로 질문하지 말아 주세요. 별도의 게시글로 질문해 주시기 바랍니다!)
Exercise 1 "계산기"
- 계산 식의 SIGMA, INTEGRAL 등의 의미는 우리가 수학적으로 알고 있는 그것과 동일합니다. 헷갈리기 쉬운 몇몇 경우에 대해서는 다음과 같이 정하겠습니다.
(1) SIGMA 계산시 시작 값이 끝 값보다 클 경우 0을 리턴합니다.
(2) INTEGRAL(a, b, f)에서 a>b인 경우, -INTEGRAL(b,a, f) 의 값을 계산하시면 됩니다.
(3) INTEGRAL 계산시 시작과 끝 값의 차가 0.1 미만인 경우 0을 리턴합니다.
(4) SIGMA, INTEGRAL 는 구간을 정의하는 첨자로 어떤 exp든 받을 수 있습니다.
SIGMA에서 이 첨자로 실수(float)가 들어올 경우, 이를 정수로 바꾸어 계산합니다.
실수 -> 정수 변환에는 OCaml 내장 함수인 int_of_float 을 사용하는 것으로 하겠습니다.
(5) INTEGRAL 계산시 구분구적법 형태로 계산하게 되는데, 이 때 고려하는 직사각형의 높이는 왼쪽 함수값을 기준으로 합니다.
즉, f 함수의 적분 계산시 구분구적법에서 구간 [a, b]를 만나면 해당하는 직사각형의 높이는 f(a) 가 됩니다.
(6) SIGMA(1.9, 1.1, f)와 같은 식의 경우 위의 (1)과 (4) 중에 어떤 것을 먼저 적용하는지에 따라 결과값이 0이 될 수도 있고 f(1)이 될 수도 있습니다.
이런 경우는 테스트하지 않겠습니다. 즉, 어떻게 구현해도 무방합니다.
- OCaml floating-point arithmetic 의 불확실성에 의해 발생할 수 있는 계산 오차는 무시하셔도 됩니다.
(예를 들어, 1.1 -. 1.0 > 0.1 식이 true 가 리턴되는 현상)
결과로 계산된 값에 오차 범위를 주어 채점할 예정이며, 테스트 케이스 또한 논란의 여지가 없는 식을 사용할 예정입니다.
- 변수로 주어지는 X는 항상 변수를 감싸고 있는 가장 안쪽의 SIGMA 또는 INTEGRAL 에 묶이는 것으로 합니다.
가장 안쪽의 어떤 SIGMA, INTEGRAL 도 없다면 FreeVariable 예외 예외를 내시면 됩니다.
FreeVariable예외를 아래 코드처럼 정의하시고, 숙제 제출시 포함해 주세요.
| 코드: | | exception FreeVariable |
- 사칙 연산에는 OCaml의 실수(float) 연산을 사용하도록 합니다.
float 의 infinity/neg_infinity/nan 을 그대로 계산에 사용하며, 정수 -> 실수 변환에는 OCaml 내장 함수인 float_of_int 를 사용하도록 하겠습니다.
--
Exercise 2 "Mathemadiga"
- SUM 혹은 TIMES 의 인자로 빈 리스트가 들어올 경우 InvalidArgument 예외를 냅니다.
아래 코드를 참고하시고, 숙제 제출시 포함해 주세요.
| 코드: | | exception InvalidArgument |
--
Exercise 3 "우선큐"
문제에서 주어진 뼈대코드 중 rank 함수를 아래와 같이 수정합니다.
| 코드: |
let rank = function EMPTY -> -1
| NODE (r, _, _, _) -> r
|
이는, 다음과 같은 힙도 왼쏠힙이라고 인정하는 꼴이 되기 때문입니다.
(1)
\
(2)
이 트리의 경우, 왼쪽 자식노드의 급수는 rank EMPTY = 0, 오른쪽 자식노드의 급수는 0 입니다. 또한, 오른쪽 척추에 붙은 노드 수도 └ log(2 + 1) ┘ = 1이 되어 왼쏠힙의 조건을 만족하는 상황이기 때문이죠.
그 외, 문제에 나와있는 식들을 ocaml로 번역하면 다음과 같이 표현 됩니다.
| 코드: |
exception EmptyHeap
let rank h = match h with
| EMPTY -> -1
| NODE(r,_,_,_) -> r
let shake (x,lh,rh) =
if (rank lh) >= (rank rh)
then NODE(rank rh+1, x, lh, rh)
else NODE(rank lh+1, x, rh, lh)
let findMin h = match h with
| EMPTY -> raise EmptyHeap
| NODE(_,x,_,_) -> x
let insert(x,h) = merge(h, NODE(0,x,EMPTY,EMPTY))
let deleteMin h = match h with
| EMPTY -> raise EmptyHeap
| NODE(_,x,lh,rh) -> merge (lh,rh)
|
(0911 추가)
rank값을 계산하는 함수에서 -1 양옆으로 쌓여있던 오타들([color] 마크)을 제거했습니다.
--
[b] Exercise 4 "Queue = 2 Stacks"
- 어떤 코드를 작성해야 하는지에 대해서 : 숙제의 템플릿을 그대로 따라가는 IntListQ 모듈을 구현하는 것으로 하겠습니다.
숙제 문서에 정의된 module type Queue를 숙제 파일에 포함하시고, 제시된 IntListQ 모듈을 완성하세요.
- 여러분이 구현한 IntListQ가 Queue 모듈 타입을 만족하는지 꼭 확인 해 주세요. 확인해 보는 방법은, 끝에 아래와 같이 한 줄을 추가하고 제대로 컴파일되는지 확인해 보시면 됩니다. 물론 제출하실 때에는 이 라인은 지워주셔야 합니다.
| 코드: | | module ValidIntListQ = (IntListQ : Queue) |
감사합니다.
TA 이동권
e-mail: dklee@ropas.snu.ac.kr
TA 배요한
e-mail: yhbae@ropas.snu.ac.kr |
|
FAQ
검색
멤버리스트
사용자 그룹
사용자 등록하기
개인 정보
비공개 메시지를 확인하려면 로그인하십시오
로그인
