 | | | This article is within the scope of the following WikiProjects: |  | This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of Computing on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. | |  GA | This article has been rated as GA-Class on the project's quality scale. | | Top | This article has been rated as Top-importance on the project's importance scale. | | | | This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. | | Mathematics rating: | GA Class | Top Priority | Field: Basics | | One of the 500 most frequently viewed mathematics articles. | | Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. | | Please add to or update the comments to suggest improvements to the article. | | History and references have improved since de-featuring, gets messier towards the end Salix alba 17:41, 30 September 2006 (UTC) | |  | This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. | | | GA | This article has been rated as GA-Class on the project's quality scale. | | Top | This article has been rated as Top-importance on the project's importance scale. | | | | | | e · h · w · r  To-do: | | | -- moved to section in talk page -- - Rewrite the history section
- Ancient algorithms (Babylonians, Euclid, Sieve)
- Formalization -- done -- (Godel's and Herbrand's λ-calculus (cf footnote in Church's paper, p. 90 in Undecidable ), Church's theorem (1936) (p. 88ff in Undecidable), Post's "process" (1936) (p. 289ff in Undecidable), Turing's machine (1936-1937) (p. 116ff in Undecidable), J.B. Rosser's definition of "effective method" in terms of "a machine" (1939)(on p. 225-226 in Undecidable), Kleene proposing the "Church-Turing thesis" based on the papers of Church and Turing cited here (1943) (p. 273-274 in Undecidable)
| [edit] Link to AllMathWords.org Encyclopedia. I feel it is appropriate to include a link to http://www.allmathwords.org/algorithm.html in the Wikipedia article. The Wikipedia guidelines state: What should be linked 3. Sites that contain neutral and accurate material that cannot be integrated into the Wikipedia article due to copyright issues, amount of detail (such as professional athlete statistics, movie or television credits, interview transcripts, or online textbooks) or other reasons. The reason the linked article should be perpemitted is that it is intended for a different audience that the Wikipedia article. The Wikipedia article is written at a college level. The All Math Words Encyclopedia is written for U.S. grades 7-10. The Wikipedia ariticle will be confusing to most 12-14 year olds. The All Math Words Encyclopedia article keeps the information and examples reachable by the target audience. —Preceding unsigned comment added by 76.27.81.30 (talk) 14:00, 5 October 2008 (UTC) - I don't have a problem with the content of this link (altho it does refer, circularly, back to the wikipedia article). I would not have a problem with creating a sub-section of "References" with a title such as "For younger readers" and this link entered. Maybe Silly Rabbit would be willing to state its objections and its reversion. Bill Wvbailey (talk) 21:49, 5 October 2008 (UTC)
The subject is also covered in the Simple English Wikipedia. See here. pgr94 (talk) 16:30, 6 December 2008 (UTC) - I was totally unaware of it. What a nice addition to wikipedia! Do you have an opinion about putting a link to this simple english version and/or to the All Math Words Encyclopedia? Bill Wvbailey (talk) 18:31, 7 December 2008 (UTC)
-
- I reverted the addition of the AllMathWords link because it appeared to be spammed across many articles in a short period of time, and the entries do not seem to provide a resource beyond that of a well-written article. (The link under discussion has virtually no content at all.) So I don't feel the link belongs here, but I'm not going to argue about it if you think it should be added back here. As for the simple English, note that there is already an interwiki. siℓℓy rabbit (talk) 18:57, 7 December 2008 (UTC)
[edit] Algorithm equivalence and normal forms Is it possible to determine if two programs code for the same algorithm? For example, if an algorithm is expressed in two different languages can they be mapped back the same algorithm? More concretely, given implementations of quicksort in C, Java, Lisp and Prolog is it possible to determine (automatically) that the programs represent the same algorithm? This, I suppose, is the same as asking if there is a canonical form for expressing algorithms. It seems like a fundamental question that I didn't see covered in the article. pgr94 (talk) 12:25, 26 October 2008 (UTC) - A really interesting question. My guess is: formally, the matter is intractable in the same manner as the Busy beaver problem. But some thoughts: (I'm just a assembly-language coder (8085 and MC68HC), wrote a "universal program" for a home-built Post-Turing machine as well as a zillion little counter machine algorithms etc.) What I've observed is that the front-end "specification", if it is precise enough, usually sets up the task of "coding" which thereafter you just crank out. It is in the specification that we'd find the similarities -- the code will be unique for the instance but fall into a general classification or classifications. I'm thinking here of when I use a "state machine" design (but this devolves into the busy-beaver problem), for example, as opposed to "random code". Or a parsing table+indirect addressing rather than just a bunch of "case" tests (I've done both). This gets into the notion of a "toolbox" of generalized algorithms -- Knuth's cookbooks of algorithms, for example. There must be some oneone working on this sort of thing. The name E. J. McClusky at Stanford comes to mind. Bill Wvbailey (talk) 15:23, 26 October 2008 (UTC)
- There is a very general theorem, Rice's theorem, that says that there is no nontrivial property of a partial computable function, such that the set of programs that compute a function with that property is decidable. In particular, there is no way to decide in general if the function computed by a given program is equal to some predetermined function known in advance. — Carl (CBM · talk) 22:57, 26 October 2008 (UTC)
-
- Ok, the wording in Rice's theorem should talk about "the set of programs that compute a function with that property" rather than given/one (I reverted your last edit and it looks like you are the person to write better wording). Derek farn (talk) 01:36, 27 October 2008 (UTC)
- Correct me if I'm wrong, but Rice's theorem doesn't rule out the use of "heuristics" on specific instances of programs; Rice's theorem has to do with a generalized mechanical procedure extended to all possible programs-as-inputs. It would be quite possible for a Carnivore-like monster program to crunch through an instance of "a program" looking for "pattern matches", perhaps simulating it; sometimes it would succeed, sometimes not, and if not it would "time out." All of these programs are finite in nature, and their inputs are finite as well -- so they are finite state machines and hence theoretically "tractable", but in practicality "intractable" in the sense of the busy beaver problem. Rice's theorem is really only applicable to a infinite-tape Turing machine . . . isn't this correct? Bill Wvbailey (talk) 14:42, 27 October 2008 (UTC)
-
- You're morally right, but that solution is very impractical. If you specify a fixed finite amount of memory that the program in question can work with, then it is possible to analyze a program by "brute force", testing its execution on every possible input as if it were a finite state machine. Then you could assign the program a standard form as some other finite state machine. However, you can't do the analysis via any method that does not make use of an assumption of a fixed memory bound, because any general method would also apply in the case of unlimited memory, which is what Rice's theorem prevents. So apart from some limited heuristics, the "normal form" would not be obtained by direct syntactic manipulation of the original program; it would just be some more-or-less arbitrarily selected program that happens to have the same behavior.
-
- For a quantitative estimate, suppose that the program takes a single 32 bit integer as input and uses no other external state information at all. Then there are 2^32 instances of the program that have to be brute-force tested in order to create a normal form. That would take about 50 days to do at 1000 instances/second. If there is any other external information that the program uses that could change, you have to run all those possibilities as well, which would increase the number of possibilities exponentially. — Carl (CBM · talk) 15:15, 27 October 2008 (UTC)
I'm not familiar with Rice's theorem and it does appear very general. Google led me to this article doi:10.1016/j.tcs.2006.07.021 which strikes me as quite relevant: - Prime normal form and equivalence of simple grammars
- A prefix-free language is prime if it cannot be decomposed into a concatenation of two prefix-free languages. We show that we can check in polynomial time if a language generated by a simple context-free grammar is prime. Our algorithm computes a canonical representation of a simple language, converting its arbitrary simple grammar into prime normal form (PNF); a simple grammar is in PNF if all its nonterminals define primes. We also improve the complexity of testing the equivalence of simple grammars. The best previously known algorithm for this problem worked in O(n13) time. We improve it to View the MathML source and View the MathML source time, where n is the total size of the grammars involved, and v is the length of a shortest string derivable from a nonterminal, maximized over all nonterminals.
If we can establish a normal form for context-free grammars then wouldn't it suggest Rice's theorem is not a problem? pgr94 (talk) 15:59, 12 November 2008 (UTC) - Context-free languages are only a small subset of all decidable languages. So even if there is a normal form for context-free grammars, this does not imply a normal form for arbitrary grammars. — Carl (CBM · talk) 17:54, 12 November 2008 (UTC)
- True, but aren't context-free grammars a good start: "Context free languages are the theoretical basis for the syntax of most programming languages."[1] pgr94 (talk) 18:17, 12 November 2008 (UTC)
- Yes, they are a good start. — Carl (CBM · talk) 03:05, 13 November 2008 (UTC)
[edit] Can an algorithm truly result in non-deterministic behavior? I disagree with the idea that some algorythms are non-determinist with the only example being a randon( acually pseudo random) number generator. Randomness is a property of physical systems not mathmatical ones. In the actual implementation of these algorythms for random number generation, the variables are set before running there for if the same inputs were applied they would produce the same random number. More properly its a hueristic. Linuxguru1968 (talk) 00:32, 25 February 2009 (UTC) -
- This is an interesting question, with an interesting rebutal of the conventional P.O.V.. I believe it deserves a response. My first response is to agree with Linuxguru1968 -- all random number generators that I know of use a non-algorithmic process (e.g. time of day, zener-diode shot noise, etc) to "seed" the generator, but the generator itself is deterministic (i.e. it uses computational (integer) processes in a finite mechanism). Does anybody (hopefufully more knowledgable than myself) have an opinion? Bill Wvbailey (talk) 03:39, 25 February 2009 (UTC)
-
- I don't see how random number generators are related here. We are not talking about randomized algorithms, but about non-deterministic algorithms. Or are we? The better way to think of nondeterministic algorithms is that they run all the possible paths in parallel, not that they pick a random path to follow.
-
- About "non-deterministic algorithms" it's really a matter of language. The recursion theory definition of algorithm requires them to be deterministic. However in computer science the term algorithm is used slightly more broadly than that. In the context of Turing computability there is no gain to non-determinism, but in some weaker classes of languages it makes a difference (see pushdown automaton and NP). — Carl (CBM · talk) 04:50, 25 February 2009 (UTC)
-
- See also Deterministic_algorithm#What_makes_algorithms_non-deterministic.3F. pgr94 (talk) 15:05, 26 February 2009 (UTC)
[edit] GA Reassessment - This discussion is transcluded from Talk:Algorithm/GA1. The edit link for this section can be used to add comments to the reassessment.
I'm reassessing this article for GA sweeps, to double-check all old GAs. This is the first part where i do a skim-check, then part two, the full review, may occur later. There's one major thing I notice with this article: The references are all in MLA format. They need to be converted to wiki format. I'll give you five days to fix this. If it is, I'll do a full review of the article. If not, I'll delist it. Wizardman 22:14, 18 August 2009 (UTC) - I'm not entirely sure what this means. Could you explain what you mean by MLA vs wiki? And also, could you point to which GA guideline the current referencing style infringes? Thanks. RobHar (talk) 22:44, 18 August 2009 (UTC)
- I mean right now all the references are (Name: #-#) format, when they really should not be. They should be in either Harvard referencing style or in a style where clocking it can bring the viewer straight to the reference. Wizardman 22:48, 18 August 2009 (UTC)
- WP:CITE says that any consistently-used format is acceptable. Moreover, choice of style alone is not a sufficient reason for changing an established referencing style. However, I would rather see this article delisted if it will prevent this sort of discussion in the future. — Carl (CBM · talk) 00:10, 19 August 2009 (UTC)
-
- It's also true that the refs in this article are not consistent, although "(Kleene 1967:45)" seems to be the predominant style. They should be consistent, at least. — Carl (CBM · talk) 01:15, 19 August 2009 (UTC)
- Wizardman, the GA criteria do not specify any particular style of citation formatting. You are supposed to be assessing this article against the GA criteria, not your own personal preferences. --Malleus Fatuorum 00:18, 19 August 2009 (UTC)
- Actually, I do favor delisting this article at this time, due to concerns about the content, especially in the lower sections. Having a review underway makes it harder to do significant editing. Once the content is improved, we can always have the article reviewed again. — Carl (CBM · talk) 00:32, 19 August 2009 (UTC)
- Unless I've missed something in WP:CITE, there's nothing wrong with MLA format (although I personally find it a pain). The only minor issue is that it is a bit inconvenient to see an inline reference and then have to scroll down to the bibliography to search for the proper full citation (no linking function as with the ref tags). Again, though, it's a minor issue, and should not be used to pre-empt a proper review, especially at the GA level. Dabomb87 (talk) 01:13, 19 August 2009 (UTC)
The GA requirements require that citations exist, not that be Harvard, Turabian, APA, MLA, or any specific style. This is not a reason to delist the article. -- Avi (talk) 19:57, 19 August 2009 (UTC) - Someone else review the article then. I still think the way the cites are is an issue but i don't care enough about this to fight it. Wizardman 03:42, 20 August 2009 (UTC)
WP:CITE#HOW says that "Any of these styles is acceptable on Wikipedia so long as articles are internally consistent." I think the current article is not internally consistent. For example, references with page numbers have been formatted using at least six different styles: (Smith 2008:1), (Smith 2008, p. 1), (Smith 2008, p. 1) with hyperlink, (Smith:1), (Smith, p. 1), and (Smith, p.1). I do not agree with the original verdict that the MLA style is bad – besides, I didn't even notice a single example of pure MLA style, which would be (Smith 1). However, I agree that mixing up all these different styles is not appropriate for a GA. — Miym (talk) 22:07, 20 August 2009 (UTC) - The history section is way long and full of not incredibly important stuff. Please move it to a separate article and summarize its main points. Pcap ping 01:26, 22 August 2009 (UTC)
- There already is a split-out article called Algorithm characterizations that deals with much of the history. The history section in the article is appropriate length (and was added to address an article-improvement suggestion a number of years ago). I'm going to revert this silly banner above the page. Bill Wvbailey (talk) 03:33, 22 August 2009 (UTC)
- Some footnotes do not correspond to any discernible reference, for instance "Valley News, p. 13". Pcap ping 18:09, 22 August 2009 (UTC)
-
- Fixed.Wvbailey (talk) 14:52, 7 September 2009 (UTC)
- The very 1st reference, "al-Daffa 1977" that's supposed to cover the etymology is also non present. I can't be bothered with much more checking, except to say that I find the prose really convoluted: the repeated direct references to the sources become very distracting. You already know my opinion about the marginal value of much of the information in this article, which only serves to dilute important stuff. Computability is not mentioned anywhere except in references for instance. The article does not introduce itself as chiefly an etymological or historical treatise, but that's what it is... I would delist it, but I'm irrelevant around here. Pcap ping 18:52, 22 August 2009 (UTC)
-
- The spelling of the al-Kwhowârizmi's name, and the exact historical details (i.e. scholarship, truth) has been a matter of great contention in this article; what the reader sees now has been reverted, altered and messed with probably 100 times; all that I can do is quote this from Knuth (The Art of Computer Programmeing, Vol. 1 2nd Edition: Fundamental Algorithms 1968, 1973:1-2); he gives no source for this that I can find: "Finally, historians of mathematics found the true origin of the word algorism: it comes from the name of a famous Persion textbook author, Abu Ja'far Mohammed ibn Mûsâ al-Kwhowârizmi (c. 825) -- literlly, "Father of Ja'far, Mohammed, son of Moses, native of Kwhowârizm." Khowârizm is today the small Soviet city of Khiva. Al-Khowârizmi wrote the celebrated book Kitab al jabr w'al-mugabala ("Rules of restoration and reduction"); another word, "algebra," stems from the title of his book, although the book wasn't really very algebraic. ¶ Gradually the form and meaning of "algorism" became corrupted; as explained by the Oxford English Dictionary, the word was "erroneously refashioned by "learned confusion" with the word arithmetic. The change from "algorism" to "algorithm" is not hard to understand in view of the fact that people had forgotten the original derivation of the word. An early German mathematical dictionary, Vollstandiges Mathematishes Lexicon (Leipzig, 1747), gives the following definition for the word Algorithmus: "Under this designation are combined the notions of the four types of arithmetic calculations, namely addition, multiplication, subtraction, and division." The latin phrase algorithmus infinitesimalis was at that time used to denote "ways of calculation with infinitely small quantities, as invented by Leibnitz." ¶ "By 1950, the word algorithm was most frequenty associated with "Euclid's algorithm,", a process for finding the greatest common divisior of two numbers which appears in Euclid's Elements (Book 7, Propositions 1 and 2.) It will be instructive to exhibits Euclid's algorithm here: [etc]." Knuth (pages 225-227) offers an interesting history of various computational notions such as "subroutines", "coroutines", "interpretive routine", "buffering", "semaphores" and "concurrent process". Wvbailey (talk) 15:30, 7 September 2009 (UTC)
While the various type of alogorithms such as linear programming, dynamic programming, etc. cetrainly exist, the taxonomical division in "by implementation" and "by design paradigm" appears WP:OR to me. Please provide a citation that someone uses those two categories containing the classes listed in this wiki article. Pcap ping 14:20, 7 September 2009 (UTC) [edit] Dubious How is classification by "computing power" different that the complexity classes? Pcap ping 14:25, 7 September 2009 (UTC) - Good question, I vote remove this. Ben1220 (talk) 10:39, 1 December 2009 (UTC)
[edit] Missing topics This article makes no mention randomized algorithms or of quantum computing/quantum_algorithm so it's stuck in the 1980s or so. Rather unacceptable for a GA. Pcap ping 14:42, 7 September 2009 (UTC) - Randomized algorithms were barely mentioned as "probabilistic algorithms", a terminology that is not commonly found in publications after 1990; I've added some basic details as well. Pcap ping 15:14, 7 September 2009 (UTC)
[edit] Algorithms + Data Structures = Programs I'm surprized, there is a very famous equation missing: - Algorithms + Data Structures = Programs
author = {Wirth, Niklaus}, title = {Algorithms + Data Structures = Programs}, year = {1978}, isbn = {0130224189}, publisher = {Prentice Hall PTR}, more: a paragraph about "Data Structures" should be written (variable, array, list, graph, ...), and some short description of the main "Control Structures" (sequence, if-then-else, loop, ...) —Preceding unsigned comment added by 86.200.233.182 (talk) 09:17, 28 December 2009 (UTC) |
.svg){kind=small}
