Theoretical computer science is a subfield of

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

and

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

that focuses on the abstract and mathematical foundations of

computation A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms. Mechanical or electronic devices (or, hist ...

. It is difficult to circumscribe the theoretical areas precisely. The ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description:

History

While logical inference and mathematical proof had existed previously, in 1931

Kurt Gödel Kurt Friedrich Gödel ( ; ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel profoundly ...

proved with his

incompleteness theorem Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies ...

that there are fundamental limitations on what statements could be proved or disproved.

Information theory Information theory is the mathematical study of the quantification (science), quantification, Data storage, storage, and telecommunications, communication of information. The field was established and formalized by Claude Shannon in the 1940s, ...

was added to the field with a 1948 mathematical theory of communication by

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, computer scientist, cryptographer and inventor known as the "father of information theory" and the man who laid the foundations of th ...

. In the same decade, Donald Hebb introduced a mathematical model of

learning Learning is the process of acquiring new understanding, knowledge, behaviors, skills, value (personal and cultural), values, Attitude (psychology), attitudes, and preferences. The ability to learn is possessed by humans, non-human animals, and ...

in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of

neural network A neural network is a group of interconnected units called neurons that send signals to one another. Neurons can be either biological cells or signal pathways. While individual neurons are simple, many of them together in a network can perfor ...

s and parallel distributed processing were established. In 1971, Stephen Cook and, working independently,

Leonid Levin Leonid Anatolievich Levin ( ; ; ; born November 2, 1948) is a Soviet-American mathematician and computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, fou ...

, proved that there exist practically relevant problems that are

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

– a landmark result in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

. 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:

Topics

Algorithms

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

is a step-by-step procedure for calculations. Algorithms are used for

calculation A calculation is a deliberate mathematical process that transforms a plurality of inputs into a singular or plurality of outputs, known also as a result or results. The term is used in a variety of senses, from the very definite arithmetical ...

data processing Data processing is the collection and manipulation of digital data to produce meaningful information. Data processing is a form of ''information processing'', which is the modification (processing) of information in any manner detectable by an o ...

, and

automated reasoning In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer progr ...

. An algorithm is an

effective method In metalogic, mathematical logic, and computability theory, an effective method or effective procedure is a finite-time, deterministic procedure for solving a problem from a specific class. An effective method is sometimes also called a mechani ...

expressed as a

finite Finite may refer to: * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marked for person and/or tense or aspect * "Finite", a song by Sara Gr ...

list of well-defined instructions for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a

that, when

executed Capital punishment, also known as the death penalty and formerly called judicial homicide, is the state-sanctioned killing of a person as punishment for actual or supposed misconduct. The sentence (law), sentence ordering that an offender b ...

, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily

deterministic Determinism is the metaphysical view that all events within the universe (or multiverse) can occur only in one possible way. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping mo ...

; some algorithms, known as

randomized algorithms A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses Uniform distribution (discrete), uniformly random bits as an auxiliary input to guide its behavior, in the ...

, incorporate random input.

Automata theory

Automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to cognitive science and mathematical l ...

is the study of ''

abstract machine In computer science, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is similar to a mathematical function in that it receives inputs and produces outputs based on p ...

s'' and ''

automata An automaton (; : automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions. Some automata, such as bellstrikers i ...

'', as well as the computational problems that can be solved using them. It is a theory in theoretical computer science, under

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

(a section of

and also of

). ''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) of

(or any function/process).

Coding theory

Coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...

is the study of the properties of codes and their fitness for a specific application. Codes are used for

data compression In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressi ...

cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

error correction In information theory and coding theory with applications in computer science and telecommunications, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communi ...

and more recently also for

network coding In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations. Linear network coding may be used to improve a network's throughput, efficiency, ...

. Codes are studied by various scientific disciplines – such as

information theory Information theory is the mathematical study of the quantification (science), quantification, Data storage, storage, and telecommunications, communication of information. The field was established and formalized by Claude Shannon in the 1940s, ...

electrical engineering Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems that use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...

, and

– for the purpose of designing efficient and reliable

data transmission Data communication, including data transmission and data reception, is the transfer of data, signal transmission, transmitted and received over a Point-to-point (telecommunications), point-to-point or point-to-multipoint communication chann ...

methods. This typically involves the removal of redundancy and the correction (or detection) of errors in the transmitted data.

Computational complexity theory

Computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

is a branch of the

theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., app ...

that focuses on classifying

computational problems In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computatio ...

according to their inherent difficulty, and relating those classes 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 an

. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the

used. The theory formalizes this intuition, by introducing mathematical

models of computation In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...

to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Other

complexity Complexity characterizes the behavior of a system or model whose components interact in multiple ways and follow local rules, leading to non-linearity, randomness, collective dynamics, hierarchy, and emergence. The term is generally used to c ...

measures are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in

circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...

) and the number of processors (used in

parallel computing Parallel computing is a type of computing, computation in which many calculations or Process (computing), processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. ...

). One of the roles of computational complexity theory is to determine the practical limits on what

computer A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...

s can and cannot do.

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms that can be stated in terms of

geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...

. 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 in

computer graphics Computer graphics deals with generating images and art with the aid of computers. Computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and computer displays, and many specialized applications. ...

and computer-aided design and manufacturing ( CAD/

CAM Cam or CAM may refer to: Science and technology * Cam (mechanism), a mechanical linkage which translates motion * Camshaft, a shaft with a cam * Camera or webcam, a device that records images or video In computing * Computer-aided manufacturin ...

), but many problems in computational geometry are classical in nature, and may come from

mathematical visualization Mathematics, Mathematical phenomena can be understood and explored via Visualization (graphic), visualization. Classically, this consisted of two-dimensional drawings or building three-dimensional models (particularly plaster models in the 19th a ...

. Other important applications of computational geometry include

robotics Robotics is the interdisciplinary study and practice of the design, construction, operation, and use of robots. Within mechanical engineering, robotics is the design and construction of the physical structures of robots, while in computer s ...

(motion planning and visibility problems),

geographic information system A geographic information system (GIS) consists of integrated computer hardware and Geographic information system software, software that store, manage, Spatial analysis, analyze, edit, output, and Cartographic design, visualize Geographic data ...

s (GIS) (geometrical location and search, route planning),

integrated circuit An integrated circuit (IC), also known as a microchip or simply chip, is a set of electronic circuits, consisting of various electronic components (such as transistors, resistors, and capacitors) and their interconnections. These components a ...

design (IC geometry design and verification),

computer-aided engineering Computer-aided engineering (CAE) is the general usage of technology to aid in tasks related to engineering analysis. Any use of technology to solve or assist engineering issues falls under this umbrella. Overview Following alongside the con ...

(CAE) (mesh generation),

computer vision Computer vision tasks include methods for image sensor, acquiring, Image processing, processing, Image analysis, analyzing, and understanding digital images, and extraction of high-dimensional data from the real world in order to produce numerical ...

(3D reconstruction).

Computational learning theory

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

Computational number theory In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithm ...

, also known as algorithmic number theory, is the study of

s for performing number theoretic

s. The best known problem in the field is

integer factorization In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...

Cryptography

Cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

is the practice and study of techniques for

secure communication Secure communication is when two entities are communicating and do not want a third party to listen in. For this to be the case, the entities need to communicate in a way that is unsusceptible to eavesdropping or interception. Secure communication ...

in the presence of third parties (called adversaries). More generally, it is about constructing and analyzing protocols that overcome the influence of adversaries and that are related to various aspects in

information security Information security is the practice of protecting information by mitigating information risks. It is part of information risk management. It typically involves preventing or reducing the probability of unauthorized or inappropriate access to data ...

such as data

confidentiality Confidentiality involves a set of rules or a promise sometimes executed through confidentiality agreements that limits the access to or places restrictions on the distribution of certain types of information. Legal confidentiality By law, la ...

data integrity Data integrity is the maintenance of, and the assurance of, data accuracy and consistency over its entire Information Lifecycle Management, life-cycle. It is a critical aspect to the design, implementation, and usage of any system that stores, proc ...

authentication Authentication (from ''authentikos'', "real, genuine", from αὐθέντης ''authentes'', "author") is the act of proving an Logical assertion, assertion, such as the Digital identity, identity of a computer system user. In contrast with iden ...

, and non-repudiation. Modern cryptography intersects the disciplines of

, and

. Applications of cryptography include ATM cards, computer passwords, and

electronic commerce E-commerce (electronic commerce) refers to Commerce, commercial activities including the electronic buying or selling Goods and services, products and services which are conducted on online platforms or over the Internet. E-commerce draws on tec ...

. Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around

computational hardness assumption In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (unconditi ...

s, 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 in

algorithms, and faster computing technology require these solutions to be continually adapted. There exist

information-theoretically secure A cryptosystem is considered to have information-theoretic security (also called unconditional security) if the system is secure against adversaries with unlimited computing resources and time. In contrast, a system which depends on the computatio ...

schemes that cannot be broken even with unlimited computing power—an example is the

one-time pad The one-time pad (OTP) is an encryption technique that cannot be Cryptanalysis, cracked in cryptography. It requires the use of a single-use pre-shared key that is larger than or equal to the size of the message being sent. In this technique, ...

—but these schemes are more difficult to implement than the best theoretically breakable but computationally secure mechanisms.

Data structures

data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

is a particular way of organizing

data Data ( , ) are a collection of discrete or continuous values that convey information, describing the quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted for ...

in a computer so that it can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, databases use

B-tree In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing fo ...

indexes for small percentages of data retrieval and

compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...

s and databases use dynamic

hash table In computer science, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps Unique key, keys to Value (computer science), values. ...

s as look up tables. Data structures provide a means to manage large amounts of data efficiently for uses such as large

database In computing, a database is an organized collection of data or a type of data store based on the use of a database management system (DBMS), the software that interacts with end users, applications, and the database itself to capture and a ...

s and internet indexing services. Usually, efficient data structures are key to designing efficient

s. Some formal design methods and

programming language A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...

s 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 both

main memory Computer data storage or digital data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers. The central processin ...

and in secondary memory.

Distributed computation

Distributed computing Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers. The components of a distributed system commu ...

studies distributed systems. A distributed system is a software system in which components located on networked computers communicate and coordinate their actions by passing messages. 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. Examples of distributed systems vary from SOA-based systems to

massively multiplayer online game A massively multiplayer online game (MMOG or more commonly MMO) is an online video game with a large number of players to interact in the same online game world. MMOs usually feature a huge, persistent world, persistent open world, although t ...

s to peer-to-peer applications, and blockchain networks like

Bitcoin Bitcoin (abbreviation: BTC; Currency symbol, sign: ₿) is the first Decentralized application, decentralized cryptocurrency. Based on a free-market ideology, bitcoin was invented in 2008 when an unknown entity published a white paper under ...

. A

computer program A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. It is one component of software, which also includes software documentation, documentation and other intangibl ...

that runs in a distributed system is called a distributed program, and distributed programming is the process of writing such programs. There are many alternatives for the message passing mechanism, including RPC-like connectors and message queues. An important goal and challenge of distributed systems is

location transparency In computer networks, location transparency is the use of names to identify network resources, rather than their actual location. For example, files are accessed by a unique file name, but the actual data is stored in physical sectors scattered aro ...

Information-based complexity

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

Formal methods In computer science, formal methods are mathematics, mathematically rigorous techniques for the formal specification, specification, development, Program analysis, analysis, and formal verification, verification of software and computer hardware, ...

are a particular kind of

based techniques for the

specification A specification often refers to a set of documented requirements to be satisfied by a material, design, product, or service. A specification is often a type of technical standard. There are different types of technical or engineering specificati ...

, development and verification of

software Software consists of computer programs that instruct the Execution (computing), execution of a computer. Software also includes design documents and specifications. The history of software is closely tied to the development of digital comput ...

and hardware systems. 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. Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particular

logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...

calculi,

formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to cognitive science and mathematical l ...

, and

program semantics In programming language theory, semantics is the rigorous mathematical study of the meaning of programming languages. Semantics assigns computational meaning to valid strings in a programming language syntax. It is closely related to, and oft ...

, but also

type systems In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a ''type'' (for example, integer, floating point, string) to every '' term'' (a word, phrase, or other set of symbols). Usual ...

and algebraic data types to problems in software and hardware specification and verification.

Information theory

is a branch of applied mathematics,

, and

involving the Quantification (science), quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as data compression, compressing data and on reliably Computer data storage, storing and Telecommunications, communicating data. Since its inception it has broadened to find applications in many other areas, including statistical inference, natural language processing,

, neurobiology, the evolution and function of molecular codes, model selection in statistics, thermal physics, quantum computing, linguistics, plagiarism detection, pattern recognition, anomaly detection and other forms of data analysis. Applications of fundamental topics of information theory include lossless data compression (e.g. ZIP (file format), ZIP files), lossy data compression (e.g. MP3s and JPEGs), and channel capacity, channel coding (e.g. for DSL, Digital Subscriber Line (DSL)). The field is at the intersection of

, statistics,

, physics, neurobiology, and

. Its impact has been crucial to the success of the Voyager program, Voyager missions to deep space, the invention of the compact disc, the feasibility of mobile phones, the development of the Internet, the study of linguistics and of human perception, the understanding of black holes, and numerous other fields. Important sub-fields of information theory are source coding, channel coding, algorithmic complexity theory, algorithmic information theory, information-theoretic security, and measures of information.

Machine learning

Machine learning is a academic disciplines, scientific discipline that deals with the construction and study of

s that can learning, learn from data. Such algorithms operate by building a Statistical model, model based on inputs 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 and statistics. It has strong ties to artificial intelligence and mathematical optimization, optimization, 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-based

s is infeasible. Example applications include spam filtering, optical character recognition (OCR),Wernick, Yang, Brankov, Yourganov and Strother, Machine Learning in Medical Imaging, ''IEEE Signal Processing Society, IEEE Signal Processing Magazine'', vol. 27, no. 4, July 2010, pp. 25–38 Learning to rank, search engines and

. Machine learning is sometimes conflated with data mining, although that focuses more on exploratory data analysis. Machine learning and pattern recognition "can be viewed as two facets of the same field."

Natural computation

Parallel computation

Parallel computing is a form of computing, computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved Parallelism (computing), "in parallel". There are several different forms of parallel computing: bit-level parallelism, bit-level, instruction level parallelism, instruction level, data parallelism, data, and task parallelism. Parallelism has been employed for many years, mainly in high performance computing, high-performance computing, but interest in it has grown lately due to the physical constraints preventing frequency scaling. As power consumption (and consequently heat generation) by computers has become a concern in recent years, parallel computing has become the dominant paradigm in computer architecture, mainly in the form of multi-core processors.Asanovic, Krste et al. (December 18, 2006)
"The Landscape of Parallel Computing Research: A View from Berkeley"
(PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit." Parallel algorithm, Parallel computer programs are more difficult to write than sequential ones, because concurrency introduces several new classes of potential software bugs, of which race conditions are the most common. Computer networking, Communication and Synchronization (computer science), synchronization between the different subtasks are typically some of the greatest obstacles to getting good parallel program performance. The maximum possible speedup, speed-up of a single program as a result of parallelization is known as Amdahl's law.

Programming language theory and program semantics

Programming language theory is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of

s and their individual Programming language#Elements, features. It falls within the discipline of theoretical computer science, both depending on and affecting

, software engineering, and linguistics. It is an active research area, with numerous dedicated academic journals. In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of

s. It does so by evaluating the meaning of programming language syntax, syntactically legal String (computer science), strings 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 certain computer platform, platform, hence creating a model of computation.

Quantum computation

A quantum computer is a

system that makes direct use of quantum mechanics, quantum-mechanical phenomena, such as quantum superposition, superposition and quantum entanglement, entanglement, to perform Instruction (computer science), operations on data. Quantum computers are different from digital computers based on transistors. 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 uses qubits (quantum bits), which can be in quantum superposition, superpositions of states. A theoretical model is the quantum Turing machine, also known as the universal quantum computer. Quantum computers share theoretical similarities with Non-deterministic Turing machine, non-deterministic and probabilistic automaton, probabilistic computers; one example is the ability to be in more than one state simultaneously. The field of quantum computing was first introduced by Yuri Manin in 1980 and Richard Feynman in 1982. A quantum computer with spins as quantum bits was also formulated for use as a quantum space–time in 1968. Experiments have been carried out in which quantum computational operations were executed on a very small number of qubits. Both practical and theoretical research continues, and many national governments and military funding agencies support quantum computing research to develop quantum

s for both civilian and national security purposes, such as cryptanalysis.

Symbolic computation

Computer algebra, also called symbolic computation or algebraic computation is a scientific area that refers to the study and development of

s and

for manipulating expression (mathematics), mathematical expressions and other mathematical objects. Although, properly speaking, computer algebra should be a subfield of scientific computing, they are generally considered as distinct fields because scientific computing is usually based on numerical computation with approximate floating point numbers, while symbolic computation emphasizes ''exact'' computation with expressions containing variable (mathematics), variables that have not any given value and are thus manipulated as symbols (therefore the name of ''symbolic computation''). Software applications that perform symbolic calculations are called ''computer algebra systems'', with the term ''system'' 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, a user interface for the input/output of mathematical expressions, a large set of function (computer science), routines to perform usual operations, like simplification of expressions, differentiation (mathematics), differentiation using chain rule, polynomial factorization, indefinite integration, etc.

Very-large-scale integration

Very-large-scale integration (VLSI) is the process of creating an

(IC) by combining thousands of transistors into a single chip. VLSI began in the 1970s when complex semiconductor and communication technologies were being developed. The microprocessor is a VLSI device. Before the introduction of VLSI technology most ICs had a limited set of functions they could perform. An electronic circuit might consist of a central processing unit, CPU, Read-only memory, ROM, Random Access Memory, RAM and other glue logic. VLSI allows IC makers to add all of these circuits into one chip.

Organizations

* European Association for Theoretical Computer Science * SIGACT * Simons Institute for the Theory of Computing

Journals and newsletters

* Discrete Mathematics and Theoretical Computer Science * ''Information and Computation'' * ''Theory of Computing (journal), Theory of Computing'' (Open access (publishing), open access journal) * ''Formal Aspects of Computing'' * ''Journal of the ACM'' * ''SIAM Journal on Computing'' (SICOMP) * ''SIGACT News'' * ''Theoretical Computer Science (journal), Theoretical Computer Science'' * ''Theory of Computing Systems''
TheoretiCS
(Open access (publishing), open access journal) * ''International Journal of Foundations of Computer Science'' * ''Chicago Journal of Theoretical Computer Science'' (Open access (publishing), open access journal) * ''Foundations and Trends in Theoretical Computer Science'' * ''Journal of Automata, Languages and Combinatorics'' * ''Acta Informatica'' * ''Fundamenta Informaticae'' * ''ACM Transactions on Computation Theory'' * ''Computational Complexity (journal), Computational Complexity'' * ''Journal of Complexity (journal), Journal of Complexity'' * ACM Transactions on Algorithms * Information Processing Letters
Open Computer Science
(Open access (publishing), open access journal)

Conferences

* Annual ACM Symposium on Theory of Computing (STOC)Th
2007 Australian Ranking of ICT Conferences
: tier A+. * Annual IEEE Symposium on Foundations of Computer Science (FOCS) * Innovations in Theoretical Computer Science (ITCS) * Mathematical Foundations of Computer Science (MFCS) * International Computer Science Symposium in Russia (CSR) * ACM–SIAM Symposium on Discrete Algorithms (SODA) * IEEE Symposium on Logic in Computer Science (LICS) * Computational Complexity Conference (CCC) * International Colloquium on Automata, Languages and Programming (ICALP) * Annual Symposium on Computational Geometry (SoCG)Th
2007 Australian Ranking of ICT Conferences
: tier A. * ACM Symposium on Principles of Distributed Computing (PODC) * ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) * Annual Conference on Learning Theory (COLT) * International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) * Symposium on Theoretical Aspects of Computer Science (STACS) * European Symposium on Algorithms (ESA) * Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) * Workshop on Randomization and Computation (RANDOM) * International Symposium on Algorithms and Computation (ISAAC) * International Symposium on Fundamentals of Computation Theory (FCT)FCT 2011
(retrieved 2013-06-03) * International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

Notes

External links

SIGACT directory of additional theory links
(archived 15 July 2017)
Theory Matters Wiki
Theoretical Computer Science (TCS) Advocacy Wiki
List of academic conferences in the area of theoretical computer science
a
confsearch

Theoretical Computer Science – StackExchange
a Question and Answer site for researchers in theoretical computer science
Computer Science Animated

Theory of computation
at the Massachusetts Institute of Technology {{Authority control Theoretical computer science, Formal sciences

History

Topics

Algorithms

Automata theory

Coding theory

Computational complexity theory

Computational geometry

Computational learning theory

Computational number theory

Cryptography

Data structures

Distributed computation

Information-based complexity

Formal methods

Information theory

Machine learning

Natural computation

Parallel computation

Programming language theory and program semantics

Quantum computation

Symbolic computation

Very-large-scale integration

Organizations

Journals and newsletters

Conferences

See also

Notes

Further reading

External links