sicp ch2 3 - andstudy/forge GitHub Wiki

SICP/2.3 글자데이터

발표내용

• SICP/2.3 글자데이터
  • 2.3.1 따옴표 연산
  • 2.3.2 연습: 글자 식의 미분
  • 2.3.3 연습 : 집합을 나타내는 방법
  • 2.3.4 연습 : 허프만 인코딩 나무 (각자)

2.3.1 따옴표 연산

• lisp은 문자를 데이터로 사용할 수 있다.

    (define a 1)
    (define b 2)
    (list a b)
    >> (1 2)
    (list `a `b)
    >> (a b)
    (list `a b)
    >> (a 2)
    (car `(a b c))
    >> a
    (cdr `(a b c))
    >> (b c)
  

• p186 memq 설명

• p187(2.53) 설명

• p187(2.54) 설명 (2.3.2에서 사용되는 프로시저)

2.3.2 연습 글자 식의 미분

• 글자로 이루어진 대수식의 미분 프로시저를 설계해 보자.

• 대수식과 변수를 인자로 받아서 그 변수로 미분한 대수식을 내놓는다.

  • =>수식과 변수. 2개의 인자를 받는 미분 프로시저를 만들어보자.
  • 입력:ax^2+bx+c, x
  • 출력:2ax+b

• 2.2.1절에서 사용했던 유리수 시스템 개발할 때와 마찬가지로 “데이터 요약”을 이용하여 우선 알맞게 문제를 간추리는 것에 초점을 둡니다. =>문제 간추리기

• 미분 공식을 알아보자

  • dc/dx = 0

  • dx/dx = 1

  • d(u+v)/dx = du/dx+dv/dx 합의 공식

  • d(uv)/dx = u(dv/dx)+v(du/dx)곱의 공식

  • f(x)=c =>f’(x) = 0 c=상수

  • y=f(x) =>y’ = f’(x) = 1

  • y=f(x)+g(x) =>y’ = f’(x)+g’(x) 합의공식

  • y=f(x)g(x) =>y’ = f’(x)g(x)+f(x)g’(x) 곱의공식

  • 필요한 기능을 알아 보자

  • 미분공식(규칙)을 이용하여 식(입력)을 넣어 미분된 식(출력)을 구하는 프로시저로 표현하려면 식이 덧셈 식인지 곱셈 식인지 상수인지 변수인지 알아 보는 기능(어떤 규칙을 적용 시킬지)이 필요하고, 또 덧셈 식이라면 더하임 수와 덧수 곱셈식이라면 곱하임 수와 곱 수를 뽑는 기능(규칙을 적용시켜 나온 미분 수식을 어떻게 표현 할지)이 필요합니다.

  • 기능을 간추려 보자.

    • 미분식의 변수는 글자로 나타낸다.
    • 어떤 값이 기호인지 아닌지 알아보는 기본 프로시저는 symbol?이다.
    • 변수를 나타내는 두 기회가 eq?하다면, 두 변수는 같다.
    • 덧셈 식과 곱셈 식은 리스트를 써서 짜맞춘다.
    • 덧셈 식은 첫 번째 원소가 +기호로 시작되는 리스트이다.
    • 더하임수는 리스트의 2번째 원소이다.
    • 덧수는 덧셈 리스트이 3번째 원소이다.
    • 곱셈 식은 첫 번째 원소가 *기호로 시작되는 리스트이다.
    • 곱하임수는 곱셈 리스트의 2번째 원소이다.
    • 곱수는 곱셈 리스트의 3번째 원소이다.

• p190 deriv 설명

• 발전된 deiv 프로시저를 만들자

  • => derive 프로시저를 이용하여 x+3을 미분하면 (+ 1 0)을 출력한다.

  • => 답은 맞지만, 알아 보기가 힘드므로 좀더 알아보기 쉽게 출력되도록 수정 해 보자.

  • => deriv프로시저는 그대로 사용하고 make-sum과 make-product 프로시저를 수정하도록 한다.

  • 덧셈의 경우

    • 더하임 수 혹은 덧수가 0인 경우 없어져도 무방하다.
    • 더하임 수와 덧수가 둘 다 숫자일 경우 덧셈 연산을 진행한다.
    • 그외의 경우엔 예전처럼 출력시킨다.

  • 곱셈의 경우

    • 곱하임 수 혹은 곱수가 0인경우 해당 항이 없어진다.
    • 곱하임 수 혹은 곱수가 1인 경우 나머지항만 출력한다.(x*1=x)
    • 곱하임 수와 곱수가 모두 숫자일 경우 곱셈 연산을 진행한다.
    • 그외의 경우엔 예전처럼 출력시킨다.

• p194 advanced deriv 설명

• p194(2.56) 설명

• p195(2.57) 설명(2마디 이상 연산 가능)

2.3.3 연습 : 집합을 나타내는 방법

• 알고리즘의 복잡도에 관련된 내용을 집합을 통해서 살펴본 챕터이다.

• 차례 없는 리스트로 표현한 집합(unordered list)

• 차례 매긴 리스트로 표현한 집합(ordered list)

• 두 갈래 나무로 표현한 집합(binary tree)

  • 아래와 같은 집합이 존재 할 때 두 집합의 교집합을 구해 보자.

  • 리스트1= 4 2 1 9

  • 리스트2= 6 8 2 4

  • unordered list의 경우

  • 총 16번의 비교 연산이 필요 O(n^2)

• p197(2.59) 설명

  • orderde list의 경우

  • 리스트1= 1 2 3 9

  • 리스트2= 2 4 6 8

  • 1-2,2-2,3-2,3-4,9-2,9-4,9-6,9-8

  • 총 8번의 비교 연산이 필요 O(n)

  • 1|2,2|2,3|4,9|4,9|6,9|8

  • 2|4,3|4,9|6,0|6,0|8

  • 3|6,9|6,0|8,0|8,

  • 9|8,0|8,

  • 총 6번의 비교 연산이 필요 O(n/2) = O(n)

• p200 설명

  • binary tree의 경우
  • 설명 Olog(n)

• p201(2.61)설명

  • 집합에서 정보 찾아내기
  • unordered list 같은 단순한 방법으로 빨리 작업한 후, 점차 개선해 나간다.