结构化程序定理

来自计算思维百科
跳转至: 导航搜索

结构化程序定理(Structured Program Theorem)认为任何一个可计算的算法都可以只用顺序、分支选择和循环这三种基本结构来表达。上述的三种结构可以完全描述CPU中的机器指令,也可以完全描述图灵机的运作,因此,虽然整个程序可能不是结构化的,但CPU所执行的指令可视为是某种“结构化程序”。鉴于迪杰斯特拉1968年的论文引用了鲍姆和贾可皮尼1966年的论文,一般都认为结构化程序理论是由鲍姆和贾可皮尼的1966年论文提出的。

结构化程序理论未提及如何编写结构化程序,也没有提到结构化程序的分析,后来1960至1970年代时,迪杰斯特拉、美国计算机学家罗伯特·弗洛伊德(Robert W Floyd)(图 2)和英国计算机学家东尼·霍尔(Sir Charles Antony Richard Hoare)(图 3)等计算机科学家在此领域作出了许多贡献,因此,迪杰斯特拉获得了1972年图灵奖,弗洛伊德获得了1978年图灵奖,霍尔获得了1980年图灵奖。此外,迪杰斯特拉还设计了著名最短路径算法和银行家算法等;弗洛伊德设计了求图中所有最短路径的弗洛伊德算法并且开创性地在程序验证中使用了逻辑断言,而且他还是1974年图灵奖得主唐纳德·克努斯(Donald Ervin Knuth)(图 4)的传世著作《计算机程序设计艺术》(The Art of Computer Programming)[4]的主要评审;霍尔则提出了著名的快速排序算法和霍尔逻辑。有趣的是,弗洛伊德和霍尔的本科主修专业都是文科,并且都有一个辅修的理科专业。

10.3.2.png

图2 罗伯特•弗洛伊德(Robert W Floyd)(来源于图灵奖官方网站)

10.3.3.png

图3 东尼•霍尔(Sir Charles Antony Richard Hoare)(来源于维基百科)

10.3.4.png

图4 唐纳德•克努斯(Donald Ervin Knuth)(来源于维基百科)

结构化程序设计禁止goto语句的使用,这是存在争议的。克努斯在1974年发表的论文“Structured Programming with Goto Statements”,提出了一些使用goto语句可以使得程序更清楚有效的反例。目前,绝大多数的计算机科学学者均已同意使用结构化程式设计的好处。

常见的结构化程序设计语言包括FORTRAN、ALGOL、COBOL、PASCAL、BASIC和C等。以下分别介绍。