구조화 정리
보이기
구조화 정리, 구조화 프로그램 정리(Structured program theorem) 또는 뵘-야코피니 정리(Böhm–Jacopini theorem)[1][2]는 프로그래밍 언어 이론의 결과이다. 이는 제어 흐름 그래프 클래스(이 맥락에서 역사적으로 순서도라고 함)가 세 가지 특정 방식(제어 구조)으로만 하위 프로그램을 결합하는 경우 계산 가능한 모든 함수를 계산할 수 있다고 명시한다. 이것들은
- 하나의 서브프로그램을 실행한 후 다른 서브프로그램(시퀀스) 실행
- 불리언 식의 값에 따라 두 하위 프로그램 중 하나 실행(선택)
- 불리언 식이 참인 동안 서브프로그램을 반복적으로 실행(반복)
이러한 제약 조건이 적용되는 구조화된 차트, 특히 단일 종료를 암시하는 루프 제약 조건(이 문서의 뒷부분에 설명됨)은 비트 형식의 추가 변수(원래 증명의 추가 정수 변수에 저장됨)를 사용하여 다음을 수행할 수 있다. 원본 프로그램이 프로그램 위치로 나타내는 정보를 추적한다. 구성은 뵘의 프로그래밍 언어 P''를 기반으로 했다.
이 정리는 goto 명령을 피하고 서브루틴, 시퀀스, 선택 및 반복을 독점적으로 사용하는 프로그래밍 패러다임인 구조적 프로그래밍의 기초를 형성한다.

같이 보기
[편집]각주
[편집]- ↑ Dexter Kozen and Wei-Lung Dustin Tseng (2008). 〈The Böhm–Jacopini Theorem is False, Propositionally〉. 《Mathematics of Program Construction》 (PDF). 《MPC 2008》. Lecture Notes in Computer Science 5133. 177–192쪽. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2.
- ↑ “CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM”. Cse.buffalo.edu. 2004년 11월 22일. 2013년 8월 24일에 확인함.
더 읽기
[편집]위에서 아직 다루지 않은 자료:
- DeMillo, Richard A. (1980). “Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem”. 《Journal of the ACM》 27 (1): 123–127. doi:10.1145/322169.322180. S2CID 15669719.
- Devienne, Philippe (1994). 〈One binary horn clause is enough〉. 《Stacs 94》. Lecture Notes in Computer Science 775. 19–32쪽. CiteSeerX 10.1.1.14.537. doi:10.1007/3-540-57785-8_128. ISBN 978-3-540-57785-0.