Editing Computer science (section)

===Theoretical computer science===
{{main|Theoretical computer science}}
''Theoretical computer science'' is mathematical and abstract in spirit, but it derives its motivation from practical and everyday computation. It aims to understand the nature of computation and, as a consequence of this understanding, provide more efficient methodologies.

====Theory of computation====

{{main|Theory of computation}}

According to Peter Denning, the fundamental question underlying computer science is, "What can be automated?"<ref name=DenningAutomated/> Theory of computation is focused on answering fundamental questions about what can be computed and what amount of resources are required to perform those computations. In an effort to answer the first question, [[computability theory]] examines which computational problems are solvable on various theoretical [[models of computation]]. The second question is addressed by [[computational complexity theory]], which studies the time and space costs associated with different approaches to solving a multitude of computational problems.

The famous [[P = NP?]] problem, one of the [[Millennium Prize Problems]],<ref>[http://www.claymath.org/millennium/P_vs_NP/ Clay Mathematics Institute] P = NP {{webarchive |url=https://web.archive.org/web/20131014194456/http://www.claymath.org/millennium/P_vs_NP/ |date=October 14, 2013 }}</ref> is an open problem in the theory of computation.

{| style="border:1px solid #ccc; text-align:center; margin:auto;" cellspacing="15"
|-
| [[File:DFAexample.svg|130px]]
| [[File:Syntax tree.svg|96px]]
| <math>M= \{ X : X \not\in X \}</math>
| [[File:Complexity classes.svg|120px]]
|-
| [[Automata theory]]
| [[Formal language]]s
| [[Computability theory]]
| [[Computational complexity theory]]
|-
| [[File:Interaction Net as Configuration.png|96px]]
| [[File:Blochsphere.svg|96px]]
| [[File:XNOR ANSI Labelled.svg]]
| [[File:Kellerautomat.svg|96px]]
|-
| [[Models of computation]]
| [[Quantum computer|Quantum computing theory]]
| [[Circuit (computer science)|Logic circuit theory]]
| [[Cellular automata]]
|}

====Information and coding theory====

{{main|Information theory|Coding theory}}

Information theory, closely related to [[probability]] and [[statistics]], is related to the quantification of information. This was developed by [[Claude Shannon]] to find fundamental limits on [[signal processing]] operations such as compressing data and on reliably storing and communicating data.<ref>{{cite web |date=October 14, 2002 |last=P. Collins |first=Graham |title=Claude E. Shannon: Founder of Information Theory |url=http://www.scientificamerican.com/article.cfm?id=claude-e-shannon-founder |work=Scientific American |access-date=December 12, 2014 |archive-date=January 16, 2014 |archive-url=https://web.archive.org/web/20140116183558/http://www.scientificamerican.com/article.cfm?id=claude-e-shannon-founder |url-status=live }}</ref>
Coding theory is the study of the properties of [[code]]s (systems for converting information from one form to another) and their fitness for a specific application. Codes are used for [[data compression]], [[cryptography]], [[error detection and correction]], and more recently also for [[network coding]]. Codes are studied for the purpose of designing efficient and reliable [[data transmission]] methods.
<ref>Van-Nam Huynh; Vladik Kreinovich; Songsak Sriboonchitta; 2012. ''Uncertainty Analysis in Econometrics with Applications''. Springer Science & Business Media. p. 63. {{ISBN|978-3-642-35443-4}}.</ref>

{| style="border:1px solid #ccc; text-align:center; margin:auto;" cellspacing="15"
|-
| [[File:Hamming.jpg|96px]]
| [[File:Binary symmetric channel.svg|96px]]
| [[File:Digitalteilchen.svg|96px]]
| [[File:H0 h1 fehler.jpg|96px]]
| [[File:Mandelpart2 red.png|96px]]
|-
| [[Coding theory]]
| [[Channel capacity]]
| [[Algorithmic information theory]]
| [[Signal detection theory]]
| [[Kolmogorov complexity]]
|}

====Data structures and algorithms====

{{main|Data structure|Algorithm}}Data structures and algorithms are the studies of commonly used computational methods and their computational efficiency.

{| style="border:1px solid #ccc; text-align:center; margin:auto;" cellspacing="15"
|-
| {{math|''O''(''n''<sup>2</sup>)}}
| [[File:Sorting quicksort anim.gif|96px]]
| [[File:Tree (computer science).svg|96px]]
| [[File:TSP Deutschland 3.png|96px]]
| [[File:SimplexRangeSearching.svg|96px]]
| [[File:Contraction vertices.jpg|96px]]
|-
| [[Analysis of algorithms]]
| [[Algorithmics|Algorithm design]]
| [[Data structures]]
| [[Combinatorial optimization]]
| [[Computational geometry]]
| [[Randomized algorithms]]
|}

====Programming language theory and formal methods====
{{main|Programming language theory|Formal methods}}
Programming language theory is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of [[programming language]]s and their individual [[Programming language#Elements|features]]. It falls within the discipline of computer science, both depending on and affecting mathematics, software engineering, and [[linguistics]]. It is an active research area, with numerous dedicated academic journals.

Formal methods are a particular kind of mathematically based technique for the [[formal specification|specification]], development and [[formal verification|verification]] of software and [[computer hardware|hardware]] systems.<ref>Phillip A. Laplante, (2010). ''Encyclopedia of Software Engineering'' Three-Volume Set (Print). CRC Press. p. 309. {{ISBN|978-1-351-24926-3}}.</ref> The use of formal methods for software and hardware design is motivated by the expectation that, as in other engineering disciplines, performing appropriate mathematical analysis can contribute to the reliability and robustness of a design. They form an important theoretical underpinning for software engineering, especially where safety or security is involved. Formal methods are a useful adjunct to software testing since they help avoid errors and can also give a framework for testing. For industrial use, tool support is required. However, the high cost of using formal methods means that they are usually only used in the development of high-integrity and [[life-critical system]]s, where safety or [[computer security|security]] is of utmost importance. Formal methods are best described as the application of a fairly broad variety of [[theoretical computer science]] fundamentals, in particular [[logic in computer science|logic]] calculi, [[formal language]]s, [[automata theory]], and [[program semantics]], but also [[type systems]] and [[algebraic data types]] to problems in software and hardware specification and verification.

{| style="border:1px solid #ccc; text-align:center; margin:auto;" cellspacing="15"
|-
| [[File:IF-THEN-ELSE-END flowchart.svg|96px]]
| <math>\Gamma\vdash x: \text{Int}</math>
| [[File:Compiler.svg|96px]]
| [[File:Python add5 syntax.svg|96px]]
| [[File:Prop-tableau-1.svg|96px]]
| [[File:Coq plus comm screenshot.jpg|96px]]
|-
| [[Semantics (computer science)|Formal semantics]]
| [[Type theory]]
| [[Compiler design]]
| [[Programming language]]s
| [[Formal verification]]
| [[Automated theorem proving]]
|}