제 2 부

컴퓨터를 동작시키기 — 알고리즘

• 전함 (battleship)—검색 알고리즘
  
• 가장 가벼운 것과 가장 무것운 것—정렬 알고리즘
  
• 시간내 일을 마치기—정렬 네트워크(Sorting Network)
  
• 진흙도시 프로젝트—최소생성나무(Minimal Spanning Trees)
  
• 오렌지 게임—네트워크 라우팅(Routing)과 교착상태(Deadlock)
  
• 돌명판(Tablets of Stone) — 네트워크 통신 프로토콜

컴퓨터를 동작시키기

컴퓨터는 미리 준비된 명령어 목록에 따라 동작합니다. 명령어는 컴퓨터로 하여금 정보를 정렬하고, 찾고, 전송할 수 있게 합니다. 이러한 작업들을 가능하면 빨리 수행할 수 있도록, 대용량 데이터 속에서 원하는 정보를 찾고, 네트워크를 통해서 정보를 송신하기 위해서 좋은 방법이 필요합니다.

알고리즘(algorithm)은 작업을 수행하기 위한 명령어 집합입니다. 알고리즘 아이디어는 컴퓨터 과학의 핵심입니다. 알고리즘은 컴퓨터로 하여금 어떻게 문제를 해결해야 하는지 지정합니다. 어떤 알고리즘은 다른 알고리즘보다 빠릅니다. 새로이 발견된 많은 알고리즘은 이전에 상대적으로 너무 오랜 시간 걸려 실행불가능하다고 생각되었던 문제를 풀 수 있도록 합니다. 예를 들어, 원주율(pi)의 백만 자리를 찾는다거나 월드와이드웹(World-Wide Web)에 여러분의 이름이 포함된 모든 페이지를 찾는다거나, 컨테이너에 짐을 넣는 가장 좋은 방법을 찾는다거나, 100자리 소수를 찾는다던가 하는 것입니다.

알고리즘(algorithm) 어원은 Mohammed ibn Musa Al-Khowarizmi 이름에서 나왔는데, Khowarizm 출신 모세의 아들 모하메드(Mohammed)는 기원후 800년경 바그다드의 지혜의 집(House of Wisdom)으로 알려진 학교에서 일하게 되었다. 모하메드의 저작은 아랍의 힌두예술에 전해졌고, 유럽으로 전파되었다. 1120년 라틴어로 변역되었고, 첫 단어가 “Dixit Algorismi”이다.