Content deleted Content added
→See also: sai.net Tag: Reverted |
m Reverted 4 edits by 182.232.208.183 (talk) to last revision by Mox Eden |
||
Line 91:
=== Structured programming ===
Per the [[Church–Turing thesis]], any algorithm can be computed by any [[Turing complete]] model. Turing completeness only requires four instruction types—conditional GOTO, unconditional GOTO, assignment, HALT. However, Kemeny and Kurtz observe that, while "undisciplined" use of unconditional GOTOs and conditional IF-THEN GOTOs can result in "[[spaghetti code]]", a programmer can write structured programs using only these instructions; on the other hand "it is also possible, and not too hard, to write badly structured programs in a structured language".<ref>[[John G. Kemeny]] and [[Thomas E. Kurtz]] 1985 ''Back to Basic: The History, Corruption, and Future of the Language'', Addison-Wesley Publishing Company, Inc. Reading, MA, {{ISBN|0-201-13433-0}}.</ref> Tausworthe augments the three [[Structured program theorem|Böhm-Jacopini canonical structures]]:<ref>Tausworthe 1977:101</ref> SEQUENCE, IF-THEN-ELSE, and WHILE-DO, with two more: DO-WHILE and CASE.<ref>Tausworthe 1977:142</ref> An additional benefit of a structured program is that it lends itself to [[proof of correctness|proofs of correctnes]]s using [[mathematical induction]].<ref>Knuth 1973 section 1.2.1, expanded by Tausworthe 1977 at pages 100ff and Chapter 9.1</ref>
== Legal status ==
Line 97 ⟶ 96:
By themselves, algorithms are not usually patentable. In the United States, a claim consisting solely of simple manipulations of abstract concepts, numbers, or signals does not constitute "processes" (USPTO 2006), so algorithms are not patentable (as in ''[[Gottschalk v. Benson]]''). However practical applications of algorithms are sometimes patentable. For example, in ''[[Diamond v. Diehr]]'', the application of a simple [[feedback]] algorithm to aid in the curing of [[synthetic rubber]] was deemed patentable. The [[Software patent debate|patenting of software]] is controversial,<ref>{{Cite news |date=2013-05-16 |title=The Experts: Does the Patent System Encourage Innovation? |url=https://www.wsj.com/articles/SB10001424127887323582904578487200821421958 |access-date=2017-03-29 |work=[[The Wall Street Journal]] |issn=0099-9660}}</ref> and there are criticized patents involving algorithms, especially [[data compression]] algorithms, such as [[Unisys]]'s [[Graphics Interchange Format#Unisys and LZW patent enforcement|LZW patent]]. Additionally, some cryptographic algorithms have export restrictions (see [[export of cryptography]]).
== Classification ==
Line 140 ⟶ 138:
; [[Back tracking]]
: In this approach, multiple solutions are built incrementally and abandoned when it is determined that they cannot lead to a valid full solution.
=== Optimization problems ===
Line 207 ⟶ 204:
** [[Computational complexity theory]]
{{div col end}}
== Notes ==
| |||