Algo-Helper; (06) 컴퓨터가 가능한 연산은 무엇일까? (연산; Python 코딩)

[문교식]

(06) 컴퓨터가 가능한 연산은 무엇일까? (연산; Python 코딩) 

생각해 보기;
 [1] 컴퓨터의 기본연산에는 어떠한 것들이 있을까?
      '기본연산'은 다른 연산들의 조합이 아닌 독립적으로 실행가능한 연산이다.
      음식의 예를 들면, 그것은 음식의 재료에 해당한다.
      재료는 '기본연산'에 해당하고, 
      재료가 합쳐진 음식은 기본연산이 모여서 이루어진 코드와 같다.

 [2] 디지털 컴퓨터가 계산할 수 없는 문제가 존재할까?
      현재에 그러한 것이 있다면,

      미래에 디지털 컴퓨터의 성능이 획기적으로 향상되면

      그러한 문제가 해결될 수 있을까? 논리적 근거는?

--------------------------------------------------- 

컴퓨터에 의한 연산이란 결국 CPU의 연산 기능을 말한다.

아무리 복잡한 프로그램이라도 CPU의 기본 연산을 조합한 것이다.

아래의 내용은 CPU의 기본연산을 정리한 것이다.

CPU가 할 수 있는 연산의 종류를 공부해 보자.

(연산자, 연산 표기 방법 등 연산 표현은 C 스타일을 따른다) 

 [1] 사칙연산; 가감승제

     사칙연산자; + - * /

     문제의 예; 두 분수의 덧셈; A/B + C/D를 계산하라.
        풀이; A/B + C/D; (A*D + C*B) / B*D 
        이 계산은 사칙연산에 의해 계산이 가능함을 보여준다.

  [Q] (9/5)와 (9/5.0)의 결과는 어떤 차이가 있는지 설명하시오.

  [Q] 세 수 a, b, c의 평균을 계산하는 연산식을 작성하시오.

  [Q] C언어의 조건문 표현에서 잘못된 부분을 바로 잡으시오.

        (의도; Y가 X보다 크고, Z가 Y보다 크면, Z를 출력한다)
        if (X<Y<Z) { Z를 출력한다; }

[2] 비교연산; 두 수의 대소비교
    비교연산자; >       <         >=         <=         ==        != 

                 (크다, 작다, 크거나 같다, 작거나 같다, 같다, 다르다)

      예; X > Y,   X <= Y,   X != Y

 
    문제의 예; 두 수 X, Y에서 X는 Y보다 큰가?
               (크면, True를 산출하고, 그렇지 않으면, False를 산출한다)
    풀이; (X > Y)

      예; X=2, Y=3이면?  
          X=3, Y=3이면?  
          X=4, Y=3이면?  

  [Q] 두 수 a, b에서 a와 b가 같은지를 검사하는 비교연산식을 표현하시오.

  [Q] 두 수 a, b에서 a와 b가 다른지를 검사하는 비교연산식을 표현하시오.

  [Q] 두 수 a, b에서 a가 b보다 크지 않은지를 검사하는 비교연산식을 표현하시오.
     

[3] 논리연산; True, False, And, Or, Not
    논리연산자; &&(And), ||(Or), !(Not)

    분기, 조건분기; Jump 명령 (다음 실행할 명령을 지정한다)

    (참고; 본 사이트의 C-Helper/조건문)

    기타의 논리연산은 위의 세 연산자의 조합으로 표현가능하다.
    예(XOR;배타적-Or,Exclusive-Or); X XOR Y = ((!X && Y) || (X && !Y))

  
    문제의 예; 두 수 X, Y의 최대수는 무엇인가?
    풀이; if (X > Y) { X를 출력한다; }
           else { Y를 출력한다; }
    조건문(if문); if (조건식) { 실행문1; }
                    else { 실행문2; }
                    의 뜻은 '조건식'이 True이면, '실행문1'을 실행한다. 
                    그렇지 않으면, '실행문2'를 실행한다. 

   
    예; X=3, Y=5이면, (X>Y)가 False이므로 else문을 실행한다; 5를 출력한다.

    조건식; 결과가 True 또는 False이고, 둘 중 하나만 가능하다.

             결과값이 0이면, False이다. 그 외의 다른 값은 모두 True이다.

     예;  if (a-b) { printf("\n True"); }
           else { printf("\n False"); }

           ; a=7, b=8의 결과는?

    여러 개의 실행문이 가능하다.

       예; if (조건식) { 실행문1; 실행문2; 실행문3; }
           else { 실행문4; 실행문5; }

[4] 비트 연산

   정보를 비트로 표현하여 비트 단위의 연산을 한다.

   비트 연산에는 여러 가지의 종류의 연산이 있다.

   예를 들면, 원래의 비트에 왼쪽에서 0 (또는 1)을 넣고 오른쪽으로 한자리씩 이동하는

   오른쪽 쉬프트(right-shift)가 있다.

   예를 들어, 원래의 데이터가 8비트이며 다음과 같다면,

         01011101

   왼쪽에서 0을 넣는 오른쪽 쉬프트를 하면,

             00101110

   이 된다.

   이 외에도 다양한 형태의 비트 연산이 있다.

   프로그래밍에 빈번하지는 않지만 필요한 경우가 있으므로 비트 연산을 다룰 수 있어야 한다.

   비트 연산; left-shift, masking, XOR 등  

[5] 데이터 전송

   Store(CPU에서 메모리로 자료를 보내기),

   Load(메모리에서 CPU로 자료를 가져오기)와 같은 명령을 비롯하여,

   블록(block) 단위로 데이터를 이동하는 Move (또는 Transfer) 명령,

   두 장소의 내용을 맞 바꾸는 Exchange 등의 명령이 있다.

   스택을 사용하는 Push, Pop 명령도 사용한다.

[6] 입력, 출력

외부로부터 데이터를 읽고(INPUT), 계산 결과를 출력(OUTPUT)하는 명령이다.

이와 같은 명령은 범용의 CPU에서 일반적으로 사용하고 있다.

이러한 명령들을 기반으로 하는 프로그래밍 언어가 나오게 되었고,

사용자들은 프로그래밍 언어를 활용하여 풀고자 하는 문제를 풀 수 있게 되었다.

      ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠

이와 같이 CPU가 처리할 수 있는 몇 가지의 기본 연산에 대해 알아 보았다.

잘 지은 집을 분해해 보면 벽돌과 모래, 돌, 등과 같은 재료로 만들어지듯이

복잡한 컴퓨터 프로그램도 위와 같은 단순한 연산들의 조합으로 이루어져 있다.

어떻게 그러한 연산의 조합을 만들어 내느냐 하는 것이 알고리즘의 핵심이다.

컴퓨터 알고리즘이란 어떤 문제의 해결을 위한 절차인데, 

반드시 컴퓨터에 의해 계산가능(computable)해야 한다는 조건을 전제로 하고 있다.

다른 말로 하면, 아무리 어떤 문제를 풀 수 있는 절차와 방법이라 하더라도

그것이 컴퓨터에 의해 실행될 수 없다면 컴퓨터 알고리즘이 아니라는 뜻이다.

(이 분야를 computability theory라고 한다. Alan Turing이 이 분야를 최초로 개척하였다.

Computability에 대한 최초의 논문; Alan Turing(1936) "On Computable Numbers, with an Application to the Entscheidungsproblem in the Proceedings of the London Mathematical Society journal)

지금까지 컴퓨터 알고리즘의 여러 측면을 알아 보았다.

앞으로는 특별한 언급이 없으면, '알고리즘'은 '컴퓨터 알고리즘'을 말한다.

【문제1】세 수 a,b,c의 최대수를 찾는 논리연산식을 표현하시오.

    예;  29 39 55  -> 55

         38 38 19  ->  38

         25 25 25  -> 25
 

【문제2】화씨 온도를 섭씨로 변환하는 계산은 아래와 같은 수식으로 표현된다.

     F는 화씨, C는 섭씨를 나타내는 변수이다.

     예를 들어, F가 100도이면, C=(100-32)*5./9. ~= 37.78

     이 계산은 컴퓨터로 계산가능하다. 왜 그러한가?

【문제3】아래는 비만도 계산이다. 실행파일을 열어 비만도를 계산해 보자.

     이 계산은 컴퓨터로 계산가능하다. 왜 그러한가?

     비만도(BMI, Body Mass Index) 계산 ; WHO(세계보건기구)에 따르면,

     인종이나 개인에 따라 약간의 차이가 있지만,

     계산하기 쉬운 비만도 측정이라는 장점이 있다.

     BMI = 몸무게(Kg) / 키(m)*키(m)

       18.5미만; 저체중

       18.5-22.99; 정상

       23-24.99; 과체중

       25-29.99; 비만

       30-34.99; 중증비만

       35이상; 고도비만

     키보드 입력; 키(height; float), 몸무게(weight; float)

     예: 50Kg, 1.5m ⇒ 50 / (1.5*1.5) = 22.22 (정상)

         60.5Kg, 1.53m ⇒ 60.5 / (1.53*1.53) = 25.84 (비만)

【문제4】다음은 윤년을 판별하는 규칙이다. 조건식으로 표현해 보자.

             (a) Y가 4로 나누어지면서 100으로는 나누어지지 않으면, Y는 윤년이다.

             (b) Y가 400으로 나누어지면, Y는 윤년이다.

             (c) 그 외에는 윤년이 아니다.

      이것은 컴퓨터에서 계산가능한가? 왜?

      (도움말; %는 나머지 연산자이다. 예; 5%3 = 2)

//