프로그래밍 철학

논리적 사고 === 좋은 소프트웨어

프로그래밍은 새로운 문해력입니다. 하지만 좋은 프로그램을 어떻게 작성합니까? 해결해야 할 반복되는 질문은 다음과 같습니다.

  • 문제에 대한 알고리즘 솔루션을 어떻게 생각해 낼까요?
  • 그렇다면 솔루션이 실제로 작동하는지 어떻게 알 수 있습니까?
  • 작동한다고 확신하더라도 컴퓨터에 어떻게 실행하도록 지시합니까?

재미있는 사실입니다. 이러한 질문 중 하나라도 해결하는 데 어려움이 있다면 실제로 철학을 수행하고있는 것입니다.

그 이유를 알아보기 위해 프로그래밍과 철학적 추론 사이의 흥미로운 유사점을 살펴 보겠습니다.

첫 번째 원칙 : 열심히 생각해야합니다.

컴퓨터는 우리가 할 수있는 것보다 더 똑똑한 일을하지 않습니다. 차이점은 더 빠른 속도로 수행한다는 것입니다.

그러나 그들은“집에서 사무실까지 어떻게 가야합니까?”와 같은 실제 문제를 해결할 수 없습니다.

효과적인 방법은 (원칙적으로) 종이와 연필을 제외한 모든 기계의 도움없이 인간이 수행 할 수 있습니다.-The Church-Turing Thesis

프로그래밍의 장점은 여전히 ​​추론 부분에 있습니다. 즉, 실제 문제를 컴퓨터가 실행할 수있는 간단한 명령으로 변환하는 것입니다.

물론, 프로그래밍 언어마다 의미 론적 추상화 수준이 다릅니다. Python 프로그램은 C 프로그램보다 짧을 수 있습니다. 그러나 그것은 단지 번역의 양을 바꿉니다. 번역 작업을 없앨 수는 없습니다. 그러나 우리는 나중에이 토론을 떠날 것입니다.

프로그래머의 추론 흐름

이제 우리는 몇 가지 문제 설명을보고 있습니다. 먼저 문제를 이해하기 위해 소규모 입출력 예제를 찾을 수 있습니다.

유도. 그러한 예를 다룰 수있는 알고리즘이 필요합니다. 이제 당신은 귀납법을하고 있습니다 : 경험으로부터 원리를 일반화합니다.

공제. 다른 알려지지 않은 입력에 대해 작동하는지 어떻게 알 수 있습니까? 우리는 알고리즘의 정확성을 증명하기 위해 추론을합니다.

온톨로지 . 우리는 컴퓨터 메모리에 데이터를 유지해야합니다. 목표는 컴퓨터가 효율적으로 처리하도록 만드는 것입니다. 즉, 내 정보의 동적 흐름을 가장 잘 포착 할 수있는 데이터 구조는 무엇입니까?

다시 유도 . 그런 다음 마지막 단계 인 디버깅입니다. 예상치 못한 출력을 분석하여 프로그램의 버그가있는 부분을 유도합니다.

이제 정점 A에서 정점 E까지의 최단 경로를 찾는 실제 예제를 따라 위의 프로세스를 살펴 보겠습니다.

소규모 문제의 경우 본능으로 해결할 수 있습니다. 마찬가지로, 우리가보기만으로 솔루션 ACE를 인식하는 것은 매우 간단합니다.

하지만 더 복잡한 토폴로지는 어떻습니까? 다른 가장자리 가중치는 어떻습니까?

컴퓨터의 도움이 필요합니다. 그러나 컴퓨터에게 무엇을해야하는지 말하는 것은 간단하지 않습니다. 인간의 사고 방식과 컴퓨터 작동 방식 사이에는 차이가 있습니다.

과정

1. 경험으로부터 원칙을 일반화 : 알고리즘

컴퓨터에게 무엇을해야하는지 알려주려면 먼저 알고리즘 절차를 마련해야합니다.

욕심 많은 전략은 자연스러운 진행 방법입니다. 즉, 소스 정점 A에서 시작하여 알려진 최단 경로를 따라 이동합니다. 목적지 E에 도달 할 때까지 새로운 정점을 계속 탐색하십시오. 실제로이 접근 방식은 우리의 예를 만족시킵니다.

직관은 목적지까지의 최단 경로를 따라 모든 중간 노드가 최단 경로에서도 방문된다는 것입니다. (물론이 직관은 모든 모서리에 양의 가중치가 있다고 가정합니다. 이는 응용 프로그램에 따라 사실이 아닐 수도 있습니다. 나중에 자세히 설명하겠습니다).

알고리즘 절차는 다음과 같습니다.

  1. 일부 설정 : (1) 우리가 방문한 정점을 기록합니다 : 집합 ( visited), (2) 발견 된 정점 만 사용 하는 각 정점에 대해 알려진 최단 거리를 기억합니다 : 다른 집합 distance(u). 소스 정점이 0 인 것을 제외하고 모든 정점의 거리는 초기에 무한대입니다.
  2. 이제 탐색을 시작합니다. 먼저 지금까지 알려진 최단 경로가있는 정점을 방문 합니다 u. (처음에는 소스 정점입니다).
  3. vertex에 서있을 때 u나가는 가장자리를 둘러 봅니다. 예를 들어 각 모서리 는 정점 을 마지막 단계로 사용하는 정점 (u,v)경로를 제공합니다 . 그들 중 어떤 것이 실제로 , 또는 우리가 찾은 첫 번째 경로 인 경우 , 만세 우리는 지금 우리의 최단 경로 세트를 업데이트 할 수 있습니다. 그렇지 않으면 무시하고 계속하십시오.vuvv
  4. vertex로 끝났 u으므로 visited세트에 추가합니다 .
  5. 2 단계로 돌아가서 모든 정점을 방문 할 때까지 계속 탐색합니다.

distance방문한 노드 만 사용하여 최단 거리를 유지하는 데 사용되기 때문에 이제 전역 최단 거리를 알려줄 수 있습니다. 그리고 알고리즘이 완료되면 모든 정점을 방문합니다.

우리는 방금 Dijkstra의 알고리즘을 재창조했습니다. 물론 최단 경로를 찾기위한 다른 많은 알고리즘이 있습니다. 그러나 요점은 문제를 해결하기위한 알고리즘 절차가 필요하다는 것입니다.

2. 공제를 통한 일반 원칙 검증

알고리즘의 원리가 올바른지 어떻게 확인합니까? 더 많은 입력 예제에 대해 원리를 테스트하여 신뢰도를 높이거나보다 효과적으로 엄격한 수학적 증명을 찾을 수 있습니다.

철학의 선험적 명제처럼 알고리즘의 정확성은 실행과 무관합니다. 즉, 테스트는 알고리즘의 정확성을 보장 할 수 없습니다. 우리는 그것을 증명해야합니다.

증명의 기본 흐름은 다음과 같습니다.

1. 방문한 모든 정점에 대해 최단 경로를 찾습니다.

2. 목적지를 방문합니다.

3. 따라서 목적지까지의 최단 경로를 찾습니다.

낯 익지 않나요? 이렇게 :

1. 모든 사람은 필사자입니다.

2. Socrate는 남자 다.

3. 그러므로 Socrate는 필사자입니다.

사실 이것은 연역적 추론의 고전적인 형태 인 Syllogism입니다. 이것은 논리 학자들이하는 일입니다.

또 다른 흥미로운 역사적 사실 : 계산의 공식적인 개념은 1930 년대 논리 학자에 의해 처음 등장했습니다. 그들은 특정 논리적 문제가 실제로 해결 가능한지 여부를 알아야했습니다 (해결할 수없는 문제를 해결하는 데 시간을 낭비하지 않을 수 있음). 이에 답하기 위해 그들은 계산 가능성이라는 개념을 제시합니다.

1936 년 말에 Alonzo Church와 Alan Turing은 동시에 독립적으로 계산 가능성의 공식적인 정의를 개발했습니다. 이 백서는 계산에 대한 역사적 검토를 제공합니다.

결론의 정확성은 처음 두 전제에 따라 다릅니다. 우리의 증명에서 두 번째 전제는 우리 알고리즘이 말 그대로 모든 노드를 방문하기 때문에 사소한 것입니다. 그러나 우리가 노드를 방문 할 때까지 최단 경로를 찾는다는 첫 번째 전제를 증명하려면 약간의 작업이 필요합니다.

수학적 귀납법 이 도움이 될 수 있습니다. 실제로 다른 많은 알고리즘의 정확성을 증명하는 가장 유용한 기술 중 하나입니다.

일반적인 흐름은 다음과 같습니다. 첫째, 알고리즘이 input 0에서 작동 하고 두 번째로 입력 에서 작동 한다는 사실이 n입력 n+1 에서도 작동한다는 것을 의미하면 모든 입력에서 0. 이 시점에서 알고리즘의 정확성을 보장 할 수 있습니다.

단순함을 위해이 경로 찾기 알고리즘의 완전한 증거를 위해이 강의 노트를 참조 할 것입니다.

수학적 귀납법과 철학적 귀납법을 혼동해서는 안됩니다. 철학적 정의에 따르면, 수학적 귀납법은 외부 관찰없이 정확성 자체가 포함되어 있기 때문에 연역적 추론 과정입니다.

교훈은 알고리즘을 만들 때 가능한 모든 실행 사례를 처리 할 수 ​​있어야한다는 것입니다.

실제로, 엄격한 수학적 증명을 거치는 것은 가장 효율적인 전략이 아닐 수 있습니다. 그러나 적어도 우리는 가능한 한 많은 실행 사례, 특히 적대적인 사례를 고려하고 싶습니다. 이 관행은 우리 코드의 견고성을 향상시킬 것입니다.

예제 경로 찾기 알고리즘에서 에지 가중치가 음수이면 작동하지 않는다는 것을 알 수 있습니다. 이 강의 노트에서 그 이유를 찾을 수 있습니다. 음의 가중치 그래프를 처리하기 위해 Bellman-Ford 알고리즘을 사용할 수 있습니다.

3. 온톨로지 문제 : 데이터 구조

지금까지 우리는 올바른 알고리즘을 가지고 있다고 확신했습니다. 그러나 이것은 전투의 절반에 불과합니다.

다음 질문은 정보를 컴퓨터에 어떻게 공급합니까? 인간은 그래프 나 히스토그램과 같은 시각화 된 정보를 좋아합니다. 그러나 오늘날의 컴퓨터는 바이너리 비트 만 처리합니다.

우리는 필수 정보를 담고있는 데이터 구조를 생각해 내야합니다. 그리고 프로그램이 동시에 처리하는 것이 효율적이어야합니다.

경로 찾기 예제를 계속해 보겠습니다. 경로는 정렬 된 목록입니다. 그러나 정수에 비해 처리하기가 짜증납니다. 알고리즘에서 발견 된 경로 세트에서 최단 경로를 찾아야합니다. 그리고 끝까지 반복합니다. 각 경로를 저장하기 위해 배열이나 메모리를 전용해야하는 것 같습니다.

우리가 더 잘할 수 있을까요? 유효한 경로에서 요소의 연속적인 모양은 그래프의 모서리와 일치해야합니다. 그러나 우리는 이미 에지 정보를 가지고 있으며 모든 경로에 대해 동일합니다. 이 중복 정보를 제거 할 수없는 이유는 무엇입니까?

글쎄, 우리는 목록을 제거 할 수 있습니다. 최단 경로를 수집하기 위해 중간 단계는 이동해야 할 다음 홉이 무엇인지 결정하는 것입니다. 소스 A에서 대상 노드까지의 최단 경로를 검색하는 데 필요한 것은 그래프 자체와 A에서 모든 노드까지의 최단 거리뿐입니다.

위 그림은 시각적 표현입니다. 이 표현은 메모리 효율적입니다. 또한 프로그램이 처리하는 것이 더 효율적입니다.

이것이 거리 벡터만을 사용하여 최단 경로를 구성하는 방법입니다. 대상 정점 및 빈 경로에서 시작합니다. 들어오는 가장자리를 통해 중간 정점을 찾습니다. 에서 가장 낮은 값을 가진 것을 선택하십시오 distance. 경로의 머리에 추가하십시오. 소스에 도달 할 때까지 반복하십시오. 이 트릭에는 실제로 역 추적이라고하는 공식 표기법이 있습니다.

철학자들은 영원한 진리를 추구합니다. 프로그래머는 정보의 역학을 가장 잘 포착하는 정확한 데이터 구조를 찾고 싶어합니다. 경로 찾기 예제에서 볼 수 있듯이 최단 경로를 제공하는 데 필요한 것은 각 정점까지의 최단 거리를 알려주는 벡터뿐입니다. 이것은 꼭지점이나 모서리의 수에 관계없이 모든 그래프에 적용됩니다.

4. 사후 제안 : 디버깅

대부분의 프로그래머는 이러한 추론을 수없이 겪었습니다. 이것은 모든 프로그래밍 작업에서 가장 어렵고 시간이 많이 걸리는 부분 중 하나라고 확신합니다.

예를 들어, C 프로그램의 분할 오류는 종종 널 포인터 참조로 인해 발생합니다. 저는 수많은 C / C ++ 세분화 오류를 처리 한 후에 이것을 배웠습니다. 물론 개인 프로그래밍 습관과 관련된 더 미묘한 경우가 있습니다.

다음 예제는 프로그래머가 만든 구문 실수입니다. if 조건은 그래야 is_float==1했지만 프로그래머는 논리 동등 연산자 ==를 평가 연산자로 착각했습니다 =. 둘 중 하나가 올바른 구문이기 때문에 여전히 컴파일러의 검사를 통과합니다.

if (is_float = 1) { // do something}

이것은 귀납적 추론 과정입니다. 디버깅 진단은 프로그램 실행을 충분히 관찰 한 경우에만 의미가 있습니다.

연습의 가치는 여기에 있습니다. 어떤 기술을 배우 든 충분한 실용적인 데이터를 수집해야합니다. 그렇지 않으면 귀납법을 수행하기에 충분한 경험이 없을 것입니다.

버그가있는 코드에서 반복되는 패턴을 주시해야합니다. 버그를 발견하면 고치는 것만으로는 충분하지 않습니다. 자신의 프로그래밍 실습에 대한 추가 인과 관계 분석이 필요합니다. 스스로에게 물어보십시오.이 부분이 내 프로그래밍 습관의 일부가 이러한 종류의 버그에 특히 취약합니까?

그렇다면 왜 중요할까요?

프로그래밍은 단순히 코드를 작성하는 것이 아니라 체계적인 추론 방법입니다. 코드 또는 지침은 목적을위한 수단 일뿐입니다. 프로그램 합성 기술의 개발로 인해 코드 작성과 디버깅에 신경 쓰지 않아도됩니다. 중요한 것은 컴퓨터에게 무엇을해야할지 말할 수 있는지 여부입니다.

프로그래밍 기술을 향상시키기위한 첫 번째 단계로,이 기사는 우리가 프로그래밍 할 때조차 인식하지 못할 수있는 근본적인 추론 패턴을 보여줍니다. 우리 대부분은 일상 업무의 대부분을 완료하기 위해 무의식적 인 자동 반사에 의존합니다. 그러나 개선은 어디에서 오는 것일까 요? 먼저 추론 과정에서 우리가 저지른 오류나 실수를 알아 차리기 때문입니다.

실용적인 조언을 위해 저는 프로그래머처럼 생각하는 방법에 대한이 기사와 같은 주제에 대한이 책을 더 자세히 추천합니다.

참고 문헌

  • 계산, 철학적 문제에 대해. Matthias Scheutz.
  • Church-Turing 논문.
  • 프로그래머처럼 생각하십시오 : 창의적인 문제 해결에 대한 소개. V. Anton Spraul.