게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

[숙제 4] 공지사항 및 보충 스펙 (4월 11일 수정)

 
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.310 Programming Languages (Spring 2022)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
김훈



가입: 2021년 4월 17일
올린 글: 9

올리기올려짐: 2022년4월8일 18:11    주제: [숙제 4] 공지사항 및 보충 스펙 (4월 11일 수정) 인용과 함께 답변

안녕하세요, 수강생 여러분.

숙제 4가 올라왔음을 알려드립니다.

내용: http://ropas.snu.ac.kr/~kwang/4190.310/22/hw4.pdf
제출: http://ropas.snu.ac.kr/~ta/4190.310/22/submit/index.pl
기한: 4/18 밤 12시

* K- 언어 문법 및 의미구조
http://ropas.snu.ac.kr/~ta/4190.310/22/show/K-.pdf

* 뼈대코드
- http://ropas.snu.ac.kr/~ta/4190.310/22/show/K_skel.zip (링크 클릭으로 다운이 진행되지 않을시 브라우저 새 탭에 주소를 입력해 주시기 바랍니다)
- 뼈대코드에는 K- 언어로 짜여진 프로그램을 읽어들이는 파서, K- 언어의 정의 및 실행기의 뼈대가 들어있습니다. k.ml 파일에서 TODO 로 표시해 둔 부분을 완성하여 실행기를 완성하시기 바랍니다.
- 뼈대코드에는 여러분이 숙제를 쉽게 하실 수 있도록 보조 모듈과 보조 함수들에 제공됩니다.
- 뼈대코드 디렉토리에서 make 명령을 실행하시면 숙제 전체가 컴파일되고, 'run' 이라는 실행파일이 생성됩니다. run 파일을 다음과 같이 실행하시면 examples 디렉토리에 제공해 드린 예제를 실행기로 돌려볼 수 있습니다. 채점에 사용될 테스트케이스도 이 예제들의 범위를 크게 벗어나지 않을 것입니다. (다소 응용한 케이스는 있을 수 있습니다.)
코드:

make
./run examples/test1.k-


* 과제 관련 주의 사항
과제를 하고 제출하기에 앞서 꼭 제출시 주의사항 공지를 확인해 주세요.

* 숙제 스펙 보충사항
(질문은 이 글에 답글로 달지 마시고, 별도의 글로 질문해 주시기 바랍니다)

Exercise 1 "K- 실행기"

- 제출시에는 뼈대코드 중 k.ml 파일을 제출합니다. 꼭 주의해 주세요, 엉뚱한 ml 파일을 잘못 제출하시면 조교팀이 해결해 드릴 방법이 없습니다.

- read의 실행의미 구현에는 read_int 를, write의 구현에는 "print_endline (string_of_int n)"을 사용하는 것으로 합니다.
즉, hw3.pdf 에 설명된 대로 정수를 출력한 다음에 개행 문자(newline)를 출력해야 합니다.
마침 숙제의 감을 잡으실 수 있도록 뼈대 코드에 read와 write의 실행 의미를 정의해 두었으므로, 이 정의를 그대로 두시면 되겠습니다.

- K.run 의 결과는 출력 대상이 아닙니다. 입출력은 read/write 로만 이루어집니다.

- 실행 의미 규칙이 정의되지 않은 경우 Error 예외를 발생시킵니다. 몇몇 구체적인 상황과, 각각의 경우 Error 예외의 문자열은 다음과 같이 정하겠습니다.

(1) 타입 에러 - 정수 값이 와야 하는 곳에 하는데 참/거짓(bool) 값이 나오거나, Addr이 나와야 하는데 Procedure가 나온 경우
코드:
raise (Error "TypeError ...")


TypeError 뒤에 추가적인 정보를 더 붙이셔도 됩니다. 예를 들어 아래와 같이 쓸 수 있습니다. 채점시에는 스트링의 앞글자들만 매칭할 것이므로 모두 정답으로 인정됩니다.
코드:
Error "TypeError : not int"
Error "TypeError : boolean is expected"


(2) Bind되지 않은 변수나 함수가 사용되는 경우
코드:
raise (Error "Unbound")



(3) callv, callr에서 함수에 넘겨준 인자 개수와 함수 정의에서 받는 인자 개수가 다른 경우 :
코드:
raise (Error "InvalidArg")



그 외에 실행의미가 정의되지 않은 경우에 대해서는, Error 예외의 문자열은 자유롭게 사용하시면 됩니다.

-어느 예외가 먼저 발생해야 하는지 모호한 경우는 테스트하지 않겠습니다. 예를 들어
코드:
let proc f (x) = x in
f (1, 2 + true)



는 Error "TypeError : ... "를 발생시켜야 하는 케이스에 해당하기도 하고, Error "InvalidArg"를 발생시켜야 하는 케이스에 해당하기도 합니다.
숙제 문서의 실행 의미 정의만으로는 어떤 예외가 우선시되는지 판단하기 애매하므로, 이런 경우는 테스트하지 않을 것입니다.

---

Exercise 2 "K-프로그래밍: 거스름 방법의 수"

- K- 언어로 프로그램을 작성하신 후, 확장자를 .txt로 하여 제출해 주세요. 중앙전산원에서 .k- 확장자 파일 제출을 차단하기 때문입니다.

- 제공해 드린 뼈대 코드로 실행했을 때 파싱 에러가 발생하지 않도록 해 주세요

- numch 함수 작성 후 in 안에서 정수를 하나 입력으로 받고(input), numch(input) 을 출력하는 코드까지 작성해 주세요.
즉 다음과 같은 형태가 되면 됩니다.
코드:
...
let proc numch (x) =
  ...
in
let input := 0 in
read input;
write (numch(input))



- numch 함수의 인자로는 양의 정수만 들어온다고 가정하셔도 됩니다.
양의 정수 아닌 값이 인자로 들어올 경우 자유롭게 처리하시기 바랍니다.

- 우리나라에는 50원 동전이 있지만, 본 숙제에서는 hw4.pdf 의 스펙을 따라 50원 동전은 없는 것으로 간주합니다.

---

Exercise 3 "K- 프로그래밍: 구조물 데이터"

- K- 언어로 프로그램을 작성하신 후, 확장자를 .txt로 하여 제출해 주세요. 중앙전산원에서 .k- 확장자 파일 제출을 차단하기 때문입니다.

- 제공해 드린 뼈대 코드로 실행했을 때 파싱 에러가 발생하지 않도록 해 주세요

- 구현해야 하는 모든 함수 작성 후 마지막에 ... in 2019 로 끝내주세요. 마지막에 숫자 2019로 끝내는 것은 파싱 에러를 피하기 위해서입니다.

즉 다음과 같은 형태가 되면 됩니다.
코드:
let proc leaf(i) =
  ...
in
...
...
let proc bft (t) =
  ...
in
2019



- dft 함수는 preorder로 방문하도록 작성해 주세요(https://en.wikipedia.org/wiki/Tree_traversal#Pre-order).
bft 함수를 작성할 때는 왼편 자식 트리를 먼저 방문하도록 작성하시기 바랍니다.
예를 들어, 아래 트리의 dft 방문 순서, bft 방문 순서는 모두 1->2->3 이 됩니다.
코드:
  1
 /  \
2    3



- makeLtree/makeRtree에 의해 만들어져서 한쪽에만 subtree를 가지고 있는 tree의 경우, 반대편에 empty tree가 매달려 있는 것으로 하겠습니다.
Leaf 양쪽에도 빈 트리가 달려있다고 볼 수도 있겠지만, 이 과제에서는 그렇지 않은 것으로 정의합니다.

즉, 다음과 같이 계산되어야 합니다
isEmpty(rTree(makeLtree (1, leaf (2)))) = true
isEmpty(ltree(makeRtree (1, leaf (2)))) = true

- Empty tree는 dft/bft 함수로 방문할 때 아무것도 출력하지 않아야 합니다.

- rTree/lTree의 인자로 empty tree나 leaf가 들어오는 경우, 그리고 nodeVal의 인자로 empty tree가 들어오는 경우는 테스트하지 않겠으니 자유롭게 구현하시면 됩니다.

-숙제에서 제시된 함수들은 모두 call by value로 호출될 때 올바르게 동작하도록 작성해주세요.
(예를들어 채점시에는 if isEmpty (lTree (tr)) then write (1) else write (0) 이러한 코드의 실행결과가 올바른지 채점할 예정입니다.)

---

Exercise 4 "즐거운 고민"

-별도의 뼈대코드는 없으며, 문제에 제시된 타입들을 파일에 포함한 상태에서 shoppingList 함수를 구현한 .ml 파일을 제출해주시면 됩니다.

-shoppingList의 계산결과를 list로 작성할 때, 조카의 이름 ABC 순서대로 리스트의 원소를 정렬해주세요. 숙제 파일에 제시된 답안 예시처럼 구현해주시면 됩니다.

- 각 조카가 받게 될 선물 리스트들도 오름차순으로 정렬해주세요. 마찬가지로 숙제 파일에 제시된 답안 예시처럼 구현해주시면 됩니다.

(* 4월 11일 추가 *)

아래의 사항들은 수강생 분들의 구현 편의를 위한 입력에 대한 가정들입니다. 일반적으로 저런 가정들이 없어도 올바른 답안을 항상 낸다는 것을 보장할 수는 있지만, 구현이 더 간편해질 여지가 있기 때문에 이러한 가정을 추가합니다.

- require list에서 한명의 조카가 여러번 등장하지 않습니다.(즉 한명의 조카당 하나의 cond list로 한꺼번에 요구합니다. 예를 들어 require list에는 [(A, ...); (A, ...); ... ] 이런 꼴이 등장하지 않습니다.)

- 아무 요청도 하지 않는 조카는 (A, []) 와 같이 cond list 자리에 빈 리스트가 온 형태로 require list에 입력으로 포함됩니다. 이에 따라 아무 요청도 하지 않은 조카가 있을 때 출력 상으로도 그 조카가 아무 선물을 못 받는다는 것을 명시해주셔야 합니다. (위와 같이 A가 아무 요청도 하지 않았다면 출력은 [(A, []); (B, [...]); ...] 처럼 될 것입니다.)

- 조카의 순서가 섞여 들어오지 않다고 생각하셔도 좋습니다.

---

Exercise 5 "탐사 준비"

- 별도의 뼈대코드는 없으며, 문제에 제시된 타입들을 파일에 포함한 상태에서 getReady 함수를 구현한 .ml 파일을 제출해주시면 됩니다.

- 탐험이 불가능할 때는 아래의 IMPOSSIBLE 예외를 발생시킵니다.
코드:
exception IMPOSSIBLE



- Guide ("x", e1) 에 대해 다음과 같이 설명되어 있습니다.
인용:
e1 안에서 만날 보물상자 x의 열쇠가 α이고 ...



이때 e1 안에는 반드시 x 가 존재한다고 가정하겠습니다.

- getReady 가 내놓는 키 리스트에서 원소들의 순서는 상관 없습니다. 다만 리스트에 겹치는 원소는 없어야 합니다.

아래는 전년도의 문제의 이해를 돕기 위한 보충 설명입니다.
인용:
'보물지도에서 암시하는 열쇠모양'이라는 것은, 실제로 보물상자를 열 때 필요한 열쇠모양이 아니라고 보셔도 됩니다. 단, 이 보물지도에서 암시하는 열쇠모양을 제대로 알아낼 수 있다면 그 정보를 통해 실제 보물상자들을 여는 열쇠모양을 모두 알아낼 수 있다고 생각하시면 됩니다.

숙제문서의 두번째 예제를 보면서 생각해보겠습니다. 각 보물지도가 암시하는 열쇠의 모양에 대한 표를 참고하시면, (안내판x|x) 꼴의 보물지도가 암시하는 모양은 (-,-) 라고 볼 수 있습니다. 실제로는 ((-,-), (-,-)) 등 여러가지 경우가 있을수 있겠지만, 열쇠꾸러미 크기를 최소로 한다고 하였으니 (-,-)라고 보시면 됩니다.

이제 이 보물지도가 암시하는 열쇠모양을 제대로 알아냈으니, 실제로 보물상자를 열기위해 필요한 열쇠 모양을 생각해봅시다. 지도의 시작지점이 암시하는 열쇠모양이 (-,-)라는 걸 알아냈고, 안내판에 x가 쓰여있었으니, x라는 보물상자는 -로 열수있다고 생각할 수 있을 것이고, 실제로 만나게 되는 보물상자도 x뿐이니 숙제문서의 두번째 예제는 - 하나로도 탐사를 마칠 수 있는 것입니다.

세번째 예제도 간단하게 설명드리자면, ((안내판x | x) | star) 꼴의 보물지도에서 뒤쪽의 star부분이 암시하는 열쇠모양은 -입니다. 여기서 전체가 암시하는 열쇠모양을 판별해야 하는데, (안내판 x | x)가 암시하는 열쇠모양은 (-,-) 혹은 ((-,-) , (-,-))와 같이 여러가지 모양이 있을 수 있습니다. 하지만 보물지도 암시 규칙표의 마지막 부분을 보시면, 앞선 (안내판 x | x) 부분이 암시하는 열쇠모양이 (-,-)가 되어야만 전체 보물지도가 암시하는 열쇠모양이 -로 제대로 나오게 됩니다. (star의 -와 모양을 맞춰야 하기때문이죠.)

위와 같이 보물지도의 열쇠모양 암시에 성공했으므로, 그 정보들을 가지고 보물상자를 열기위한 열쇠모양을 찾아보면, 전체 보물지도에서 보물상자는 x와 star입니다. star는 -로 열수있는 것이 자명하며, x또한 위의 열쇠모양 암시를 보면 -로 열 수 있다는 것을 알수있습니다.

이런식으로 열쇠모양에 대한 암시와 실제 필요한 열쇠꾸러미를 구분하시면 됩니다.


감사합니다.

조교 드림

TA 조승한
e-mail: shjo@ropas.snu.ac.kr

TA 김훈
e-mail: hkim@ropas.snu.ac.kr
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.310 Programming Languages (Spring 2022) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay