Edsger W. Dijkstra
(네덜란드 컴퓨터과학자 1930 ~ 2002)
.......... Dijkstra 는 University of Leiden 에서 이론물리학을 전공했다. 1970 년대에 Burroughs Corporation 에서 일했고 네덜란드 Eindhoven University of Technology 에 재직하다가 University of Texas at Austin 컴퓨터과학과에서 2000 년 은퇴할때 까지 재직했다. 그는 프로그래밍 언어연구에 몰두하여 1950 년대말에 고급언어인 ALGOL 의 주요개발자중 한명이었다. 그는 그래프이론에 관한 이론서 뿐만아니라 프로그래밍 언어분야의 수많은 텍스트와 철학적 숙고에 이르기까지 많은 저술을 남겼다. 그는 Dijkstra's algorithm 라고 알려진 shortest path-algorithm 를 연구하여 유명해졌고 1972 년에 Turing Award 를 받았다. ..............
간단히 다이크스트라의 알고리즘이라 불리고 있는 최단 경로의 알고리즘 은 그동안 철도 건설, 통신 네트워크의 경로 설계, 항공기 운항 계획 등 모두 목적지에 이르는 최선의 길을 찾아 내야 하는 응용 분야에서 사용되어 왔다 ..... 이것은 나 자신이 제기하고, 또 그 답을 얻어 낸 최초의 그래프 문제였습니다. 놀라운 일은 내가 그것을 공식적으로 발표하지 않았다는 사실입니다. 하지만 그 땐 그것이 전혀 놀랄만한 일이 아니었지요. 당시엔 알고리즘이라는 것이 좀처럼 과학적 주제로 여겨지지 않았으니까요 ....
다이크스트라는 다시 열차에 대해 생각해 보았다. 이번엔 신호기 (semaphore) 라고 부르는 열차의 신호 체계에 관한 것이었다. X 도시와 Y 도시 사이에 따로 설치된 두 줄의 트랙이 있다고 가정해 보자. 하나는 X 에서 Y 로 가는 것이고 다른 하나는 Y 에서 X 로 향하는 것이다. 두 트랙이 그 노선의 일정 구역에서 하나로 좁혀진다면, 양 방향에서 달리고 있던 열차들이 같은 구획의 트랙을 사용해야만 한다. 충돌을 피하기 위해 엔지니어들은 신호기를 사용하여 그 공유된 트랙 위에 반드시 한 번에 한 대의 열차만 있도록 만든다. 신호기는 한 번에 오직 한 방향으로만 녹색등이 켜지고, 어느 한 대의 열차가 트랙의 그 결정적인 구획 위에 머무는 동안에는 절대로 그 신호의 색이 변하지 않도록 해 준다. 따라서, 신호기의 사용은 주어진 시간동안 그 결정적인 트랙 위에는 오직 한 대의 열차만이 있게 되는 것을 보장해 준다. 이것을 상호 배제라고 한다 ....... 다이크스트라는 상호 배제의 개념을 컴퓨터와 이에 접속된 키보드 사이의 통신에 적용시켰다. 이들 두 장치는 버퍼 (buffer) 라고 알려져 있는 기억 장치 내의 통신 영역을 통해 정보를 교환한다. 기본 원칙은 이 두 가지 장치가 버퍼를 읽거나 쓰는 행동이 한 번에 하나씩만 이루어져야 한다는 것이다 .......
컴퓨터 네트워크에서는 만찬의 철학자들 문제의 다양한 변형들을 종종 볼 수 있다. 예를 들어, 근거리 통신망 내의 컴퓨터들은 흔히 한 번에 단 하나의 메시지만 보낼 수 있는 선이나 방송 채널을 공유한다. 만일 모든 사이트들이 동시에 전송을 시도할 경우 모두 실패하게 된다. 그리고 나서 곧바로 재시도를 하면 또 다시 실패하게 된다. 이것은 교착과 유사하다. 만일, 어느 하나의 사이트가 항상 우선권을 가진다면, 다른 사이트가 기아 상태에 놓이거나 혹은 프로토콜이 불공평하게 될 것이다 .......... (Dennis Shasha 1998)
다이크스트라의 연구 방법들을 간파해 보려고 하는 젊은 과학자들에게 그는 세 가지 황금률을 권한다.
term :
컴퓨터 (Computer) 그래프 이론 (Graph Theory) 최단경로 찾기 문제 (Shortest Path Finding Problem) Edsger W. Dijkstra A.M. Turing Award
site :
Edsger W. Dijkstra : 약력 : 단순함을 찾아서... (In Pursuit of Simplicity)
다익스트라의 `프로그래밍의 수련(修練)' 해역(解譯) : 김도형 : A Discipline of Programming 의 일부 번역
컴퓨터 과학의 황제 서거하다 : News.com
paper :
Edsger W. Dijkstra : Dennis Shasha