GetWiki
theoretical computer science
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
theoretical computer science
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{about|the branch of computer science and mathematics|the journal|Theoretical Computer Science (journal)}}- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
missing image!
- Maquina.png -
An artistic representation of a Turing machine. Turing machines are used to model general computing devices.
Theoretical computer science, or TCS, is a subset of general computer science and mathematics that focuses on more mathematical topics of computing and includes the theory of computation.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:WEB, SIGACT,weblink 2017-01-19, {{"|TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.}}In this list, the ACM's journal Transactions on Computation Theory includes coding theory and computational learning theory, as well as theoretical computer science aspects of areas such as databases, information retrieval, economic models, and networks.WEB, ToCT,weblink 2010-06-09, yes,weblink" title="web.archive.org/web/20101104004846weblink">weblink 2010-11-04, Despite this broad scope, the "theory people" in computer science self-identify as different from the "applied people"{{Citation needed|date=September 2017}}. Some characterize themselves as doing the "(more fundamental) 'science(s)' underlying the field of computing."WEB, Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing,weblink 2009-03-29, Other "theory-applied people" suggest that it is impossible to separate theory and application. This means that the so-called "theory people" regularly use experimental science(s) done in less-theoretical areas such as software system research{{Citation needed|date=September 2017}}. It also means that there is more cooperation than mutually exclusive competition between theory and application{{Citation needed|date=September 2017}}.- Maquina.png -
An artistic representation of a Turing machine. Turing machines are used to model general computing devices.
History
While logical inference and mathematical proof had existed previously, in 1931 Kurt GÃ¶del proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved.These developments have led to the modern study of logic and computability, and indeed the field of theoretical computer science as a whole{{Citation needed|date=September 2017}}. Information theory was added to the field{{by whom|date=September 2017}} with a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of neural networks and parallel distributed processing were established. In 1971, Stephen Cook and, working independently, Leonid Levin, proved that there exist practically relevant problems that are NP-complete – a landmark result in computational complexity theory{{Citation needed|date=September 2017}}.With the development of quantum mechanics in the beginning of the 20th century came the concept that mathematical operations could be performed on an entire particle wavefunction. In other words, one could compute functions on multiple states simultaneously. This led to the concept of a quantum computer in the latter half of the 20th century that took off in the 1990s when Peter Shor showed that such methods could be used to factor large numbers in polynomial time, which, if implemented, would render most modern public key cryptography systems uselessly insecure.{{citation needed|reason=Your explanation here|date=October 2014}}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:{| style="border:1px solid #ddd; text-align:center; margin: 0 auto;" cellspacing="15"| P rightarrow Q ,| Mathematical logic| Automata theory| Number theory| Graph theory| Computability theory| Computational complexity theory| GNITIRW-TERCES| Gammavdash x: text{Int}| Cryptography| Type theory| Category theory| Computational geometry| Combinatorial optimization96px) | 96px) | 96px) | 96px)| P = NP ? |
96px) | 96px) | 96px) | 96px) |
Quantum computer>Quantum computing theory |
Topics
Algorithms
An algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.An algorithm is an effective method expressed as a (wikt:finite|finite) list"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2). of well-defined instructionsWell defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2). for calculating a function."an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1). Starting from an initial state and initial input (perhaps empty),"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5). the instructions describe a computation that, when executed, proceeds through a finite"A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5). number of well-defined successive states, eventually producing "output""An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5). and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2.Data structures
A data structure is a particular way of organizing data in a computer so that it can be used efficiently.Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 15 December 2004. Online version Accessed May 21, 2009.Entry data structure in the EncyclopÃ¦dia Britannica (2009) Online entry accessed on May 21, 2009.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 indexes for small percentages of data retrieval and compilers and databases use dynamic hash tables as look up tables.Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms. Some formal design methods and programming 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 both main memory and in secondary memory.Computational complexity theory
Computational complexity theory is a branch of the theory of computation that focuses on classifying computational problems 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 algorithm.A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Other complexity 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) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do.Distributed computation
Distributed computing 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.BOOK, Coulouris, George, Jean Dollimore, Tim Kindberg, Gordon Blair, Distributed Systems: Concepts and Design (5th Edition), Addison-Wesley, 2011, Boston, 0-132-14301-1, 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 games to peer-to-peer applications.A computer program that runs in a distributed system is called a distributed program, and distributed programming is the process of writing such programs.{{harvtxt|Andrews|2000}}. {{harvtxt|Dolev|2000}}. {{harvtxt|Ghosh|2007}}, p. 10. 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.Parallel computation
Parallel computing is a form of computation in which many calculations are carried out simultaneously,BOOK, Gottlieb, Allan, Highly parallel computing, 1989, Benjamin/Cummings, Redwood City, Calif., 0-8053-0177-1,weblink Almasi, George S., 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, and task parallelism. Parallelism has been employed for many years, mainly in high-performance computing, but interest in it has grown lately due to the physical constraints preventing frequency scaling.S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" {{Webarchive|url=https://web.archive.org/web/20081209154000weblink |date=2008-12-09 }} (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits â€“ increased clock frequency and smarter but increasingly complex architectures â€“ are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster." As power consumption (and consequently heat generation) by computers has become a concern in recent years,Asanovic et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free". 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 computer programs are more difficult to write than sequential ones,BOOK, Hennessy, John L., Computer organization and design : the hardware/software interface, 1999, Kaufmann, San Francisco, 1-55860-428-6, 2. ed., 3rd print., Patterson, David A., Larus, James R., because concurrency introduces several new classes of potential software bugs, of which race conditions are the most common. Communication and synchronization between the different subtasks are typically some of the greatest obstacles to getting good parallel program performance.The maximum possible speed-up of a single program as a result of parallelization is known as Amdahl's law.Very-large-scale integration
Very-large-scale integration (VLSI) is the process of creating an integrated circuit (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 CPU, ROM, RAM and other glue logic. VLSI allows IC makers to add all of these circuits into one chip.Machine learning
Machine learning is a scientific discipline that deals with the construction and study of algorithms that can learn from data.JOURNAL, Glossary of terms, Ron Kovahi, Foster Provost, Machine Learning (journal), Machine Learning, 30, 271â€“274, 1998,weblink Such algorithms operate by building a model based on inputsBOOK, C. M. Bishop, Christopher M. Bishop, 2006, Pattern Recognition and Machine Learning, Springer, 0-387-31073-8, {{rp|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 and statistics. It has strong ties to artificial intelligence and 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 algorithms 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 Magazine, vol. 27, no. 4, July 2010, pp. 25-38 search engines and computer vision. Machine learning is sometimes conflated with data mining,CONFERENCE, Mannila, Heikki, Data mining: machine learning, statistics, and databases, Int'l Conf. Scientific and Statistical Database Management, IEEE Computer Society, 1996, although that focuses more on exploratory data analysis.JOURNAL, Friedman, Jerome H., Jerome H. Friedman, Data Mining and Statistics: What's the connection?, Computing Science and Statistics, 29, 1, 1998, 3â€“9, Machine learning and pattern recognition "can be viewed as two facets ofthe same field."{{rp|vii}}Computational biology
Computational biology involves the development and application of data-analytical and theoretical methods, mathematical modeling and computational simulation techniques to the study of biological, behavioral, and social systems.WEB,weblink
, NIH working definition of bioinformatics and computational biology
, 17 July 2000
, 18 August 2012
, Biomedical Information Science and Technology Initiative
, yes
,weblink" title="web.archive.org/web/20120905155331weblink">weblink
, 5 September 2012
,
, , NIH working definition of bioinformatics and computational biology
, 17 July 2000
, 18 August 2012
, Biomedical Information Science and Technology Initiative
, yes
,weblink" title="web.archive.org/web/20120905155331weblink">weblink
, 5 September 2012
,
The field is broadly defined and includes foundations in computer science, applied mathematics, animation, statistics, biochemistry, chemistry, biophysics, molecular biology, genetics, genomics, ecology, evolution, anatomy, neuroscience, and visualization.
WEB,weblink About the CCMB, 18 August 2012, Center for Computational Molecular Biology, Computational biology is different from biological computation, which is a subfield of computer science and computer engineering using bioengineering and biology to build computers, but is similar to bioinformatics, which is an interdisciplinary science using computers to store and process biological data.Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms that can be stated in terms of geometry. 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. While modern computational geometry is a recent development, it is one of the oldest fields of computing with history stretching back to antiquity. An ancient precursor is the Sanskrit treatise Shulba Sutras, or "Rules of the Chord", that is a book of algorithms written in 800 BCE. The book prescribes step-by-step procedures for constructing geometric objects like altars using a peg and chord.The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature, and may come from mathematical visualization.Other important applications of computational geometry include robotics (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).Information theory
Information theory is a branch of applied mathematics, electrical engineering, and computer science involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and communicating data. Since its inception it has broadened to find applications in many other areas, including statistical inference, natural language processing, cryptography, neurobiology,BOOK, F. Rieke, D. Warland, R Ruyter van Steveninck, W Bialek, Spikes: Exploring the Neural Code, The MIT press, 1997, 978-0262681087, the evolutioncf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science 294:2310-2314 and functionRando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. Schneider, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene 215:1, 111-122 of molecular codes, model selection in statistics,Burnham, K. P. and Anderson D. R. (2002) Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition (Springer Science, New York) {{isbn|978-0-387-95364-9}}. thermal physics,Jaynes, E. T. (1957) Information Theory and Statistical Mechanics, Phys. Rev. 106:620 quantum computing, linguistics, plagiarism detection,Charles H. Bennett, Ming Li, and Bin Ma (2003) Chain Letters and Evolutionary Histories, Scientific American 288:6, 76-81 pattern recognition, anomaly detection and other forms of data analysis.WEB, David R. Anderson
, Some background on why people in the empirical sciences may want to better understand the information-theoretic methods
, November 1, 2003
,weblink
, pdf
, 2010-06-23
, yes
,weblink" title="web.archive.org/web/20110723045720weblink">weblink
, July 23, 2011
,
, Applications of fundamental topics of information theory include lossless data compression (e.g. ZIP files), lossy data compression (e.g. MP3s and JPEGs), and channel coding (e.g. for Digital Subscriber Line (DSL)). The field is at the intersection of mathematics, statistics, computer science, physics, neurobiology, and electrical engineering. Its impact has been crucial to the success of the 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., Some background on why people in the empirical sciences may want to better understand the information-theoretic methods
, November 1, 2003
,weblink
, 2010-06-23
, yes
,weblink" title="web.archive.org/web/20110723045720weblink">weblink
, July 23, 2011
,
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties (called adversaries).BOOK, Ronald L., Rivest, Ron Rivest, J. Van Leeuwen, Handbook of Theoretical Computer Science, Cryptology, 1, Elsevier, 1990, More generally, it is about constructing and analyzing protocols that overcome the influence of adversariesBOOK, Mihir, Bellare, Phillip, Rogaway, Introduction to Modern Cryptography, Introduction, 10, 21 September 2005, and that are related to various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation.BOOK, A. J., Menezes, P. C., van Oorschot, S. A., Vanstone,weblink Handbook of Applied Cryptography, 0-8493-8523-7, bot: unknown,weblink" title="web.archive.org/web/20050307081354weblink">weblink 2005-03-07, Modern cryptography intersects the disciplines of mathematics, computer science, and electrical engineering. Applications of cryptography include ATM cards, computer passwords, and electronic commerce.Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around computational 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 in integer factorization algorithms, and faster computing technology require these solutions to be continually adapted. There exist information-theoretically secure schemes that {{not a typo|provably}} cannot be broken even with unlimited computing powerâ€”an example is the one-time padâ€”but these schemes are more difficult to implement than the best theoretically breakable but computationally secure mechanisms.Quantum computation
A quantum computer is a computation system that makes direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data."Quantum Computing with Molecules" article in Scientific American by Neil Gershenfeld and Isaac L. Chuang 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 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 and 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 1980BOOK, Manin, Yu. I., Vychislimoe i nevychislimoe, Computable and Noncomputable, 1980, Sov.Radio,weblink 13â€“15, Russian, 4 March 2013, yes,weblink" title="web.archive.org/web/20130510173823weblink">weblink 10 May 2013, and Richard Feynman in 1982.JOURNAL, Feynman, R. P., Simulating physics with computers, International Journal of Theoretical Physics, 1982, 21, 6, 467â€“488, 10.1007/BF02650179, JOURNAL, Quantum computation, David Deutsch, David, Deutsch, Physics World, 1992-01-06, A quantum computer with spins as quantum bits was also formulated for use as a quantum spaceâ€“time in 1968.BOOK, David, Finkelstein, Space-Time Structure in High Energy Interactions, Fundamental Interactions at High Energy, T., Gudehus, G., Kaiser, New York, Gordon & Breach, 1968, {{as of|2014}}, quantum computing is still in its infancy but experiments have been carried out in which quantum computational operations were executed on a very small number of qubits.WEB,weblink New qubit control bodes well for future of quantum computing, 26 October 2014, Both practical and theoretical research continues, and many national governments and military funding agencies support quantum computing research to develop quantum computers for both civilian and national security purposes, such as cryptanalysis.Quantum Information Science and Technology Roadmap for a sense of where the research is heading.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.Computational number theory
Computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations. The best known problem in the field is integer factorization.Symbolic computation
Computer algebra, also called symbolic computation or algebraic computation is a scientific area that refers to the study and development of algorithms and software for manipulating 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 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 routines to perform usual operations, like simplification of expressions, differentiation using chain rule, polynomial factorization, indefinite integration, etc.Program semantics
In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages. It does so by evaluating the meaning of syntactically legal 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 platform, hence creating a model of computation.Formal methods
Formal methods are a particular kind of mathematics based techniques for the specification, development and verification of software and hardware systems.WEB, R. W. Butler, What is Formal Methods?,weblink 2001-08-06, 2006-11-16, 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.JOURNAL, C. Michael Holloway, Why Engineers Should Consider Formal Methods,weblink 16th Digital Avionics Systems Conference (27â€“30 October 1997), 2006-11-16, yes,weblink" title="web.archive.org/web/20061116210448weblink">weblink 16 November 2006, Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particular logic calculi, formal languages, automata theory, and program semantics, but also type systems and algebraic data types to problems in software and hardware specification and verification.Monin, pp.3-4Automata 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, under Discrete mathematics (a section of Mathematics and also of Computer Science). Automata comes from the Greek word Î±á½Ï„ÏŒÎ¼Î±Ï„Î± meaning "self-acting".Automata Theory is the study of self-operating virtual machines to help in logical understanding of input and output process, without or with intermediate stage(s) of computation (or any function / process).Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding. Codes are studied by various scientific disciplinesâ€”such as information theory, electrical engineering, mathematics, and computer scienceâ€”for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction (or detection) of errors in the transmitted data.Computational learning theory
Theoretical results in machine learning mainly deal with a type ofinductive learning called supervised learning. In supervisedlearning, an algorithm is given samples that are labeled in someuseful way. For example, the samples might be descriptions ofmushrooms, and the labels could be whether or not the mushrooms areedible. The algorithm takes these previously labeled samples anduses them to induce a classifier. This classifier is a function thatassigns labels to samples including the samples that have never beenpreviously seen by the algorithm. The goal of the supervised learningalgorithm is to optimize some measure of performance such asminimizing the number of mistakes made on new samples.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 (open access journal)
- Formal Aspects of Computing
- Journal of the ACM
- SIAM Journal on Computing (SICOMP)
- SIGACT News
- Theoretical Computer Science
- Theory of Computing Systems
- International Journal of Foundations of Computer Science
- Chicago Journal of Theoretical Computer Science (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 of Complexity
- ACM Transactions on Algorithms
- Information Processing Letters
- Open Computer Science (open access journal)
Conferences
- Annual ACM Symposium on Theory of Computing (STOC)The 2007 Australian Ranking of ICT Conferences {{Webarchive|url=https://web.archive.org/web/20091002002344weblink |date=2009-10-02 }}: tier A+.
- Annual IEEE Symposium on Foundations of Computer Science (FOCS)
- Innovations in Theoretical Computer Science (ITCS)
- Mathematical Foundations of Computer Science (MFCS)MFCS 2017
- International Computer Science Symposium in Russia (CSR)CSR 2018
- 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)The 2007 Australian Ranking of ICT Conferences {{Webarchive|url=https://web.archive.org/web/20091002002344weblink |date=2009-10-02 }}: 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)
- 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)
See also
- Formal science
- Unsolved problems in computer science
- List of important publications in theoretical computer science
Notes
Further reading
- Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, {{isbn|0-12-206382-1}}. Covers theory of computation, but also program semantics and quantification theory. Aimed at graduate students.
External links
- SIGACT directory of additional theory links
- Theory Matters Wiki Theoretical Computer Science (TCS) Advocacy Wiki
- [news://comp.theory Usenet comp.theory]{{Dead link|date=June 2018 |bot=InternetArchiveBot |fix-attempted=no }}
- List of academic conferences in the area of theoretical computer science at confsearch
- Theoretical Computer Science - StackExchange, a Question and Answer site for researchers in theoretical computer science
- Computer Science Animated
- weblink @ Massachusetts Institute of Technology
- content above as imported from Wikipedia
- "theoretical computer science" does not exist on GetWiki (yet)
- time: 2:23am EDT - Sat, Aug 18 2018
- "theoretical computer science" does not exist on GetWiki (yet)
- time: 2:23am EDT - Sat, Aug 18 2018
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
Culture
© 2018 M.R.M. PARROTT | ALL RIGHTS RESERVED