# 1.0. Computational Thinking

# Definition of computational thinking

The thought processes involved in (i) formulating a problem and (ii) expressing its solutions in such a way that a computer --human or machine- can effectively carry out.

1. Problem formulation (abstraction)
2. Solution expression (automation)
3. Solution execution & evaluation (analyses)

# Characteristics of computational thinking

• Formulating problems in a way that enables us to use a computer and other tools to help solve them
• Logically organizing and analyzing data → Data structure
• Representing data though abstractions such as models and simulations → Data Structure
• Automating solutions through algorithmic thinking (a series of ordered steps) → Algorithm
• Identifying, analyzing, and implementing possible solutions with the goal of achieving the most efficient and effective combination of steps and resources → time and space complexity
• Generalizing and transferring the problem solving process to a wide variety of problems

# Problem Solving in Computer Science and Engineering

문 제 (Problem) \rightarrow 해 (Solution)

• Problem : 가상 현실, 문서작성, 홈뱅킹, 인터넷 신문, 문서 번역, 회로 설계, 유전자 분석, 무인 자동차, 온라인 게임, 비디오 편집, 자료 검색, 영화 제작, 음성 인식, 가상 수술, 건축 설계, 기상 예측, 주가 예측, 인공 지능, 대용량 과학 계산, …

# Problem Solving Pipeline

# 도강 문제

한 어부(M)가 늑대(W), 염소(G), 양배추(C)를 강 한 쪽에서 다른 쪽으로 옮기려 한다. 어부가 배를 타고 강을 건널 때 어부 자신 외에 늑대, 염 소, 양배추 중 하나만 배에 가지고 갈 수가 있는데, 문제는 어부가 늑대 를 싣고 가는 동안, 염소가 양배추를 같은 쪽에 남겨두면 염소가 양배 추를 먹어버리게 되고, 양배추를 싣고 갈 때 늑대와 염소를 같은 쪽에 남겨둘 경우 늑대가 염소를 잡아 먹게 된다. 과연 어떻게 하면 어부가 가장 적은 회수로 강을 건너면서 세 가지를 모두 안전하게 옮길 수 있을까?

# 문제 분석

# 해법 고안

• Graph, search, and so on → Which data structures and algorithms?
• Cost, time, space, and so on → What complexities?

[연습] 이 문제에 대한 알고리즘과 시간/공간 복잡도를 컴퓨터학의 용 어를 써서 기술한다면, ???

• 무슨 말인지 전혀 모르겠으면 [43-080 자료구조]를 재수강한 후 이 과목을 들을 것!

# 구현 : ✓ Programming is an art!

• 어떻게 하면 주어진 알고리즘을 가장 효과적으로 구현을 할 수 있을까?

• 어떻게 하면 C/C++를 사용하여 주어진 알고리즘을 가장 최적으로 구현할 수 있을까?

  • 원시 코드 레벨의 측면
  • 어셈블러 레벨의 측면
  • 시스템 레벨의 측면
  • 기타

• ✓ 과연 내가 http://acm.uva.es/problemset/에 있는 문제들을 스스로 “문제 분석 \rightarrow 해법 고안 \rightarrow 구현” 과정을 통하여 효과적으로 해결할 수 있을까???

  • Programming Challenges by S. Skiena and M. Revilla, Springer, 2003.

• 어떻게 하면 좋은 구현 결과를 얻을 수 있는가?

  • 동일한 프로세서 상에서 더 빠르게
  • 적은 메모리만 사용하게
  • 안정적이게

• 구현 예

19 0.265968초 4.862961초 3.4GHz Intel Core i7 CPU

# Data Structure → Algorithm → Theory of Computation

• 어떻게 하면 주어진 복잡한 문제를 이진수 형태의 낮은 수준의 명령어만 이해하는 ‘단순한’ 컴퓨터 상에서 효율적으로 해결할 수 있을까?

1. [Data Structure] 주어진 추상적인 문제를 어떠한 자료 구조를 사용하여 컴 퓨터의 구조에 최적화된 형태로 표현할 수 있을까?
2. [Algorithm] 주어진 추상적인 문제를 어떠한 알고리즘을 사용하여 컴퓨터를 사용하여 가장 효율적으로 해결할 수 있을까?
3. [Complexity] 과연 컴퓨터가 주어진 문제를 효율적으로 해결할 수 있을까 ?
4. [Computability] 과연 컴퓨터가 세상의 모든 문제를 해결할 수 있을까?

• ✓ 이 과목에서는 [CSE3080 자료구조] 과목에 이어, 1번과 2번을 집중적으로 살펴보 고, 3번 문제에 대하여 어느 정도 살펴볼 예정임.
• 4번 문제는 [CSE3085 자동장치이론] 과목에서 다룸.