컴퓨터과학이 여는 세계_8.2 알고리즘과 언어_이광근

강좌 동영상

 소프트웨어는 튜링기계다. 튜링기계는 어떤일을 하고 그 일은 문제를 푸는 것이다. 컴퓨터는 소프트웨어(튜링기계)를 실행하면서 문제풀이를 자동적으로 진행한다. 컴퓨터로 문제를 푼다는 것이 이 뜻이다.

 알고리즘이란 소프트웨어로 만드는 문제푸는 방도이다. 따라서 컴퓨터로 문제를 풀려면 알고리즘을 찾아야 한다. 그 해법이 맞는지 확인한 후 소프트웨어로 구현한다.

-컴퓨터 과학이 여는 세계 中 

 문제를 풀기 위해선 알고리즘을 찾아야한다. 찾았다 하더라도 더 빠른 방법은 없는지 그 알고리즘이 현실적으로 가능한지 살펴야한다. 만약 알고리즘이 현실적으로 불가능하다면, 우주가 끝날 때까지 답을 찾지 못할 수 있다.

 또, 어떤 알고리즘의 시간적 비용이 120년이라고 해서 같은 문제를 푸는 다른 방법을 찾았더니 똑같이 120년이라 하자. 심지어 전 세계 사람들이 그 문제를 푸는 방법을 생각해 낸 알고리즘의 시간적 비용이 120년이라고 하자. 그렇지만 그 문제를 푸는데 드는 비용은 120년인지 아닌지는 알 수 있는 방법이 없다. 지금 생각해낸 알고리즘 보다 더 좋은 알고리즘이 나올 수 있기 때문이다.