Theoretical computer science is a subfield ofcomputer science andmathematics that focuses on theabstract and mathematical foundations ofcomputation.
It is difficult to circumscribe the theoretical areas precisely. TheACM'sSpecial Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description:[1]
TCS covers a wide variety of topics includingalgorithms,data structures,computational complexity,parallel anddistributed computation,probabilistic computation,quantum computation,automata theory,information theory,cryptography,program semantics andverification,algorithmic game theory,machine learning,computational biology,computational economics,computational geometry, andcomputational number theory andalgebra. Work in this field is often distinguished by its emphasis on mathematical technique andrigor.
While logical inference and mathematical proof had existed previously, in 1931Kurt Gödel proved with hisincompleteness theorem that there are fundamental limitations on what statements could be proved or disproved.
Information theory was added to the field witha 1948 mathematical theory of communication byClaude Shannon. In the same decade,Donald Herb introduced a mathematical model oflearning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields ofneural networks andparallel distributed processing were established. In 1971,Stephen Cook and, workingindependently,Leonid Levin, proved that there exist practically relevant problems that areNP-complete – a landmark result incomputational complexity theory.[2]
Modern theoretical computer science research is based on these basic developments, but includes many other mathematical and interdisciplinary problems that have been posed, as shown below:
Analgorithm is a step-by-step procedure for calculations. Algorithms are used forcalculation,data processing, andautomated reasoning.
An algorithm is aneffective method expressed as afinite list[3] of well-defined instructions[4] for calculating afunction.[5] Starting from an initial state and initial input (perhapsempty),[6] the instructions describe acomputation that, whenexecuted, proceeds through a finite[7] number of well-defined successive states, eventually producing "output"[8] and terminating at a final ending state. The transition from one state to the next is not necessarilydeterministic; some algorithms, known asrandomized algorithms, incorporate random input.[9]
Automata theory is the study ofabstract machines andautomata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science, underdiscrete mathematics (a section ofmathematics and also ofcomputer science).Automata comes from the Greek word αὐτόματα, meaning "self-acting".
Automata Theory is the study of self-operating virtual machines to help in the logical understanding of input and output process, without or with intermediate stage(s) ofcomputation (or anyfunction/process).
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used fordata compression,cryptography,error correction and more recently also fornetwork coding. Codes are studied by various scientific disciplines – such asinformation theory,electrical engineering,mathematics, andcomputer science – for the purpose of designing efficient and reliabledata transmission methods. This typically involves the removal of redundancy and the correction (or detection) of errors in the transmitted data.
Computational complexity theory is a branch of thetheory of computation that focuses on classifyingcomputational problems according to their inherent difficulty, and relating thoseclasses to each other. A computational problem is understood to be a task that is in principle amenable to being solved by a computer, which is equivalent to stating that the problem may be solved by mechanical application of mathematical steps, such as analgorithm.
A problem is regarded as inherently difficult if its solution requires significant resources, whatever thealgorithm used. The theory formalizes this intuition, by introducing mathematicalmodels of computation to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Othercomplexity measures are also used, such as the amount of communication (used incommunication complexity), the number ofgates in a circuit (used incircuit complexity) and the number of processors (used inparallel computing). One of the roles of computational complexity theory is to determine the practical limits on whatcomputers can and cannot do.
Computational geometry is a branch of computer science devoted to the study of algorithms that can be stated in terms ofgeometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry.
The main impetus for the development of computational geometry as a discipline was progress incomputer graphics and computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature, and may come frommathematical visualization.
Other important applications of computational geometry includerobotics (motion planning and visibility problems),geographic information systems (GIS) (geometrical location and search, route planning),integrated circuit design (IC geometry design and verification),computer-aided engineering (CAE) (mesh generation),computer vision (3D reconstruction).
Theoretical results in machine learning mainly deal with a type of inductive learning called supervised learning. In supervised learning, an algorithm is given samples that are labeled in some useful way. For example, the samples might be descriptions of mushrooms, and the labels could be whether or not the mushrooms are edible. The algorithm takes these previously labeled samples and uses them to induce a classifier. This classifier is a function that assigns labels to samples including the samples that have never been previously seen by the algorithm. The goal of the supervised learning algorithm is to optimize some measure of performance such as minimizing the number of mistakes made on new samples.
Computational number theory, also known asalgorithmic number theory, is the study ofalgorithms for performingnumber theoreticcomputations. The best known problem in the field isinteger factorization.
Cryptography is the practice and study of techniques forsecure communication in the presence of third parties (calledadversaries).[10] More generally, it is about constructing and analyzingprotocols that overcome the influence of adversaries[11] and that are related to various aspects ininformation security such as dataconfidentiality,data integrity,authentication, andnon-repudiation.[12] Modern cryptography intersects the disciplines ofmathematics,computer science, andelectrical engineering. Applications of cryptography includeATM cards,computer passwords, andelectronic commerce.
Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed aroundcomputational hardness assumptions, making such algorithms hard to break in practice by any adversary. It is theoretically possible to break such a system, but it is infeasible to do so by any known practical means. These schemes are therefore termed computationally secure; theoretical advances, e.g., improvements ininteger factorization algorithms, and faster computing technology require these solutions to be continually adapted. There existinformation-theoretically secure schemes that provably cannot be broken even with unlimited computing power—an example is theone-time pad—but these schemes are more difficult to implement than the best theoretically breakable but computationally secure mechanisms.
Adata structure is a particular way of organizingdata in a computer so that it can be usedefficiently.[13][14]
Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, databases useB-tree indexes for small percentages of data retrieval andcompilers and databases use dynamichash tables as look up tables.
Data structures provide a means to manage large amounts of data efficiently for uses such as largedatabases andinternet indexing services. Usually, efficient data structures are key to designing efficientalgorithms. Some formal design methods andprogramming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design. Storing and retrieving can be carried out on data stored in bothmain memory and insecondary memory.
Distributed computing studies distributed systems. A distributed system is a software system in which components located onnetworked computers communicate and coordinate their actions bypassing messages.[15] The components interact with each other in order to achieve a common goal. Three significant characteristics of distributed systems are: concurrency of components, lack of a global clock, and independent failure of components.[15] Examples of distributed systems vary fromSOA-based systems tomassively multiplayer online games to peer-to-peer applications, and blockchain networks likeBitcoin.
Acomputer program that runs in a distributed system is called adistributed program, and distributed programming is the process of writing such programs.[16] There are many alternatives for the message passing mechanism, includingRPC-like connectors andmessage queues. An important goal and challenge of distributed systems islocation transparency.
Information-based complexity (IBC) studies optimal algorithms and computational complexity for continuous problems. IBC has studied continuous problems as path integration, partial differential equations, systems of ordinary differential equations, nonlinear equations, integral equations, fixed points, and very-high-dimensional integration.
Formal methods are a particular kind ofmathematics based techniques for thespecification, development andverification ofsoftware andhardware systems.[17] 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.[18]
Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particularlogic calculi,formal languages,automata theory, andprogram semantics, but alsotype systems andalgebraic data types to problems in software and hardware specification and verification.[19]
Information theory is a branch ofapplied mathematics,electrical engineering, andcomputer science involving thequantification ofinformation. Information theory was developed byClaude E. Shannon to find fundamental limits onsignal processing operations such ascompressing data and on reliablystoring andcommunicating data. Since its inception it has broadened to find applications in many other areas, includingstatistical inference,natural language processing,cryptography,neurobiology,[20] the evolution[21] and function[22] of molecular codes,model selection in statistics,[23] thermal physics,[24]quantum computing,linguistics, plagiarism detection,[25]pattern recognition,anomaly detection and other forms ofdata analysis.[26]
Applications of fundamental topics of information theory includelossless data compression (e.g.ZIP files),lossy data compression (e.g.MP3s andJPEGs), andchannel coding (e.g. forDigital Subscriber Line (DSL)). The field is at the intersection ofmathematics,statistics,computer science,physics,neurobiology, andelectrical engineering. Its impact has been crucial to the success of theVoyager missions to deep space, the invention of the compact disc, the feasibility of mobile phones, the development of theInternet, the study oflinguistics and of human perception, the understanding ofblack holes, and numerous other fields. Important sub-fields of information theory aresource coding,channel coding,algorithmic complexity theory,algorithmic information theory,information-theoretic security, and measures of information.
Machine learning is ascientific discipline that deals with the construction and study ofalgorithms that canlearn from data.[27] Such algorithms operate by building amodel based on inputs[28]: 2 and using that to make predictions or decisions, rather than following only explicitly programmed instructions.
Machine learning can be considered a subfield of computer science andstatistics. It has strong ties toartificial intelligence andoptimization, which deliver methods, theory and application domains to the field. Machine learning is employed in a range of computing tasks where designing and programming explicit, rule-basedalgorithms is infeasible. Example applications includespam filtering,optical character recognition (OCR),[29]search engines andcomputer vision. Machine learning is sometimes conflated withdata mining,[30] although that focuses more on exploratory data analysis.[31] Machine learning andpattern recognition "can be viewed as two facets of the same field."[28]: vii
Natural computing,[32][33] also called natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of novel problem-solving techniques; 2) those that are based on the use of computers to synthesize natural phenomena; and 3) those that employ natural materials (e.g., molecules) to compute. The main fields of research that compose these three branches areartificial neural networks,evolutionary algorithms,swarm intelligence,artificial immune systems, fractal geometry,artificial life,DNA computing, andquantum computing, among others. However, the field is more related tobiological computation.
Computational paradigms studied by natural computing are abstracted from natural phenomena as diverse asself-replication, the functioning of thebrain,Darwinian evolution,group behavior, theimmune system, the defining properties of life forms,cell membranes, andmorphogenesis. Besides traditionalelectronic hardware, these computational paradigms can be implemented on alternative physical media such as biomolecules (DNA, RNA), or trapped-ionquantum computing devices.
Dually, one can view processes occurring in nature as information processing. Such processes includeself-assembly,developmental processes,gene regulation networks,protein–protein interaction networks, biological transport (active transport,passive transport) networks, andgene assembly inunicellular organisms. Efforts tounderstand biological systems also include engineering of semi-synthetic organisms, and understanding the universe itself from the point of view of information processing. Indeed, the idea was even advanced that information is more fundamental than matter or energy. The Zuse-Fredkin thesis, dating back to the 1960s, states that the entire universe is a hugecellular automaton which continuously updates its rules.[34][35]Recently it has been suggested that the whole universe is aquantum computer that computes its own behaviour.[36]The universe/nature as computational mechanism is addressed by,[37] exploring nature with help the ideas of computability, and[38] studying natural processes as computations (information processing).
Parallel computing is a form ofcomputation in which many calculations are carried out simultaneously,[40] operating on the principle that large problems can often be divided into smaller ones, which are then solved"in parallel". There are several different forms of parallel computing:bit-level,instruction level,data, andtask parallelism. Parallelism has been employed for many years, mainly inhigh-performance computing, but interest in it has grown lately due to the physical constraints preventingfrequency scaling.[41] As power consumption (and consequently heat generation) by computers has become a concern in recent years,[42] parallel computing has become the dominant paradigm incomputer architecture, mainly in the form ofmulti-core processors.[43]
Parallel computer programs are more difficult to write than sequential ones,[44] because concurrency introduces several new classes of potentialsoftware bugs, of whichrace conditions are the most common.Communication andsynchronization between the different subtasks are typically some of the greatest obstacles to getting good parallel program performance.
The maximum possiblespeed-up of a single program as a result of parallelization is known asAmdahl's law.
Programming language theory is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification ofprogramming languages and their individualfeatures. It falls within the discipline of theoretical computer science, both depending on and affectingmathematics, software engineering, andlinguistics. It is an active research area, with numerous dedicated academic journals.
Inprogramming language theory,semantics is the field concerned with the rigorous mathematical study of the meaning ofprogramming languages. It does so by evaluating the meaning ofsyntactically legalstrings defined by a specific programming language, showing the computation involved. In such a case that the evaluation would be of syntactically illegal strings, the result would be non-computation. Semantics describes the processes a computer follows when executing a program in that specific language. This can be shown by describing the relationship between the input and output of a program, or an explanation of how the program will execute on a certainplatform, hence creating amodel of computation.
Aquantum computer is acomputation system that makes direct use ofquantum-mechanicalphenomena, such assuperposition andentanglement, to performoperations ondata.[45] Quantum computers are different from digital computers based ontransistors. Whereas digital computers require data to be encoded into binary digits (bits), each of which is always in one of two definite states (0 or 1), quantum computation usesqubits (quantum bits), which can be insuperpositions of states. A theoretical model is thequantum Turing machine, also known as the universal quantum computer. Quantum computers share theoretical similarities withnon-deterministic andprobabilistic computers; one example is the ability to be in more than one state simultaneously. The field of quantum computing was first introduced byYuri Manin in 1980[46] andRichard Feynman in 1982.[47][48] A quantum computer with spins as quantum bits was also formulated for use as a quantumspace–time in 1968.[49]
Experiments have been carried out in which quantum computational operations were executed on a very small number of qubits.[50] Both practical and theoretical research continues, and many national governments and military funding agencies support quantum computing research to develop quantumcomputers for both civilian and national security purposes, such ascryptanalysis.[51]
Computer algebra, also called symbolic computation or algebraic computation is a scientific area that refers to the study and development ofalgorithms andsoftware for manipulatingmathematical expressions and othermathematical objects. Although, properly speaking, computer algebra should be a subfield ofscientific computing, they are generally considered as distinct fields because scientific computing is usually based onnumerical computation with approximatefloating point numbers, while symbolic computation emphasizesexact computation with expressions containingvariables that have not any given value and are thus manipulated as symbols (therefore the name ofsymbolic computation).
Software applications that perform symbolic calculations are calledcomputer algebra systems, with the termsystem alluding to the complexity of the main applications that include, at least, a method to represent mathematical data in a computer, a user programming language (usually different from the language used for the implementation), a dedicated memory manager, auser interface for the input/output of mathematical expressions, a large set ofroutines to perform usual operations, like simplification of expressions,differentiation usingchain rule,polynomial factorization,indefinite integration, etc.
Very-large-scale integration (VLSI) is the process of creating anintegrated circuit (IC) by combining thousands oftransistors into a single chip. VLSI began in the 1970s when complexsemiconductor andcommunication technologies were being developed. Themicroprocessor is a VLSI device. Before the introduction of VLSI technology, most ICs had a limited set of functions they could perform. Anelectronic circuit might consist of aCPU,ROM,RAM and otherglue logic. VLSI allows IC makers to add all of these circuits into one chip.
