컴퓨팅 사고 I: WEEK 3-3, 4-1

*POSTECH 청년 AI · Big Data 아카데미(https://pabi.smartlearn.io/)의
 'Computational Thinking (컴퓨팅 사고) Ⅰ' 코스 강의를 듣고 정리한 글입니다

*모든 이미지의 출처는 https://pabi.smartlearn.io/ 입니다

 

 

3-3. 컴퓨팅으로 풀 수 있는 문제

1) 컴퓨팅의 한계를 묻는 질문

(1) 어떤 문제를 컴퓨팅으로 풀 수 있는가

=> '컴퓨터로 풀 수 있는 문제'라고만 답할 수 있음 (계산 시간을 고려하지 않고, 이론상 답이 나오는지만 따짐)

 

(2) 시간을 아무리 쏟아도 컴퓨팅으로 풀 수 없는 문제가 있는가?

=> 하드웨어 컴퓨터와 학문 '컴퓨터과학'은 모두 계산의 한계를 묻는 질문들에서 시작됨

      1-계산이란 무엇인가?

      2-계산으로 풀 수 없는 문제가 있는가?

 

2) 계산이란 무엇인가?

=> '컴퓨팅으로 할 수 있는 일 (컴퓨터로 프로그램을 실행해서 할 수 있는 일)'을 의미함

=> 앨런 튜링과 알론조 처치가 발견한 계산 개념을 넘어서는 새로운 계산 개념을 아직까지 인류가 찾지 못함..

 

(1) 앨런 튜링-튜링 기계(=매우 간단한 컴퓨터)

- 간단한 연산과 명령을 처리할 수 있고 쪽수가 무한한 공책을 갖춘 계산 수행 주체라고 생각하면 됨

- 문제를 푸는 튜링 기계가 존재하면, 계산으로 문제를 푸는 것 (튜링 기계가 할 수 있는 일을 '계산'으로 정함)

 

(2) 알론조 처치-람다 계산법(=매우 간단한 프로그래밍 언어)

- 람다는 그리스 문자 람다를 지칭

- 함수 기반의 연산만 있는, 매우 간단한 계산 언어로 생각하면 됨

- 람다 계산법으로 설명할 수 있는 과정을 '계산'으로 정의

 

*위의 두 계산 개념은 사실 동등함!

- 컴퓨터는 튜링 기계의 일종인 만능 기계를 실제 하드웨어로 구현한 것

- 범용 소프트웨어를 구현하는 데 쓰는 프로그래밍 언어는 전부 람다 계산법과 표현력이 동등함.

 

3) 계산으로 풀 수 없는 문제가 있는가?

=> 이론적으로 무수히 많음

 

* 실제 예시 (아무리 시간을 쏟아도 계산으로 풀 수 없음)

- 프로그램을 입력으로 받아서 실행이 끝나는지 판별

- 프로그램 두 개를 입력으로 받아서 동등한 프로그램인지, 즉 같은 조건에서 항상 실행 결과가 같은지 판별

 

4-1. 계산 자료

1) 기본 자료 = 더 이상 쪼갤 수 없는 계산 자료

• 성적 총합은 1729이다
• 생활기록부가 아직 남아 있다 생활기록부가 이제 남아 있지 않다
• 가장 가까운 도시는 부산이다
• 시험이 끝나는 날을 수요일이다

 

2) Python 언어의 기본 자료

• 정수 - 예시: (-2), (-1), 0, 1, 2 등
• 논리값 - 예시: True, False
• 문자열 - 예시: ‘1456’, ‘컴퓨팅 사고’ 등

* 문자열이 표현하는 단어와 문장의 뜻을 해석하지 않음

• ‘1729’: 글자 1, 7, 2, 9로 이루어진 단어로, 정수 1729(천 칠백 이십 구)와 무관
• ‘True’: 글자 T, r, u, e로 이루어진 단어로, 논리값 True와 무관

 

3) 기본 자료 = 프로그램 = 계산 결과

• 예시: “정수 1729를 계산한다”는 1729를 넣고 프로그램을 실행하는 것인데, 이 경우 당연히 그대로 1729가 출력됨
• 기본 자료 계산 = 기본 자료 기억하기