Computer Science: The systematic study of computing systems and computation. The body of knowledge resulting from this discipline contains theories for understanding computing systems and methods; design methodology, algorithms, and tools; methods for the testing of concepts; methods of analysis and verification; and knowledge representation and implementation.
Graph: A graph is a pair <V, E> where V is the set of all vertexes (nodes) and E is the set of all edges.
A geometric diagram consisting of a finite number of dots called vertices joined by a finite number of curved or straight line segments called edges.
Link: edge, node, acyclic graph, cyclic graph, Graph Depth, Combinatorial Circuits.
Trees: (on site)
Link: Spanning Tree, Parent Node, Child Node, Leaf Node, Root Node, Parse Tree, Binary Tree, Balanced Binary Tree, and Tree Search.
Algorithm: An explicit step-by-step procedure for producing a solution to a given problem. Specifically, a mathematical equation typically executed using a computer program (or set of programs) that is designed to systematically solve a certain kind of problem.
Spanning Tree:A subgraph that is a tree containing all nodes. The max weight spanning tree problem is to find a spanning tree such that the sum of (given, positive) weights of the edges is a maximum.
home.eunet.cz/berka/o/English/lp/glossary/S.html
Link: Tree, Node, Vertex
Axiom: A basic assumption about a mathematical system from which theorems can be deduced. For example, the system could be the points and lines in the plane. Then an axiom would be that given any two distinct points in the plane, there is a unique line through them.
Theorem: A theorem is a statement which has been proved to be true.
ddi.cs.uni-potsdam.de/Lehre/TuringLectures/MathNotions.htm
Link: Domino Theorem, Deduction Theorem, Entailment Theorem
Natural Numbers: set of counting numbers; typically denoted as N = {1,2,3,...}
Link: Unary Numbers
Unary Numbers:consisting of or involving a single element or component; "in a unary operation in a mathematical system one element is used to yield a single result"
wordnet.princeton.edu/perl/webwn
Link: Unary System
Domino Theorem: (on site)
Link: Theorem
Sets: (on site)
Link: Data, Set Operations
Math Statements: (on site)
Link: AND, OR, NOT gates, LOGIC Gates.
Relations: (on site)
Link: binary, composition
Set Operations: (on site)
Link: Sets, Cartesian Product.
Composition: (on site)
Link: Relation
Function: In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). The concept of a function is fundamental to virtually every branch of mathematics and every quantitative science.
en.wikipedia.org/wiki/Function_(math)
Link: Set, Computer Science
Lambda Calculus: The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. It was introduced by AlonzoChurch and Stephen Cole Kleene in the 1930s; Church used the lambda calculus in 1936 to give a negative answer to the Entscheidungsproblem. The calculus can be used to cleanly define what a computable function is.
en.wikipedia.org/wiki/Lambda_calculus
Link: Function, Calculi, Turing Computable Function.
Binary Relations: (on site)
Link: Relation, Binary System, Equivalence.
SML:
Greek Alphabet: (on site)
Peano Axioms: (on site)
Lists:In computer science, a list is an abstract concept denoting an ordered collection of fixed-length entities. In practice, any list is either an array or a linked list of some sort. The use of the concept allows to treat them regardless of implementation. For this reason, lists have properties that arrays and linked lists share. Informally, the term list is used synonymously with linked list. A sequence is another name, emphasizing the ordering and suggesting that it may not be a linked list.
Link: Computer Science
Data Types: The characteristic of columns and variables that defines what types of data values they can store. Examples include character, floating point and integer.
Abstract Data Types: Abstract data types or ADTs are a mathematical specification of a set of data and the set of operations that can be performed on the data. They are abstract in the sense that the focus is on the definitions of the constructor that returns an abstract handle that represents the data, and the various operations with their arguments. The actual implementation is not defined, and does not affect the use of the ADT.
Link: Sets
Fibonacci Numbers: In mathematics, the Fibonacci numbers form a sequence defined by the following recurrence relation:(+ PICTURE)
That is, after two starting values, each number is the sum of the two preceding numbers. The first Fibonacci numbers (sequence A000045 in OEIS), also denoted as Fn, for n = 0, 1, …, are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811…
Link: Numbers
Mutual Recursion: Mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other.
For instance, consider two functions A(x) and B(x) defined as follows:(+ PICTURE)
Programming with Effects: (Exceptions) Exceptions are generalized error codes. They abort evaluation of a program by signaling an exceptional condition.
Exceptions can be predefined or user-defined.
Formal Languages: In mathematics, logic and computer science, a formal language is a set of finite-length words (i.e. character strings) drawn from some finite alphabet, and the scientific theory that deals with these entities is known as formal language theory. Note that we can talk about formal language in many contexts (scientific, legal, linguistic and so on), meaning a mode of expression more careful and accurate, or more mannered than everyday speech.
Link: logic, computer science, word, alphabet, string
Pic: formal_language.png
Alphabet: An alphabet is a character set that includes letters and is used to write a language.
wordnet.princeton.edu/perl/webwn
Link: Formal languages, word, string
String: (comment for links: a string for some alphabet can be referenced as a word in some language over this alphabet).
Pic: string.png
Link: Formal languages, word, alphabet,
Word: In computer programming and some branches of mathematics, strings are sequences of various simple objects. These are selected from a predetermined set (language) each entry of which is usually allocated a code. The symbol are contained in a finite set that is called an alphabet.
Link: Formal Language, alphabet.
Concatenation:
Pic: concatenation.png
Link: string
Prefix
Pic: prefix.png
Link: string, word.
Lexical Order: Ordering two sequences of values by comparing their elements in order. The first two elements that differ determine the order.
Link: String, word,
Pic: lexical_order.png
Character Codes:
Pic: character_code.png
Link: Alphabet, Binary System
Extension of Codes:
Pic: code_extension.png
Link: string, functions
Morse Code:
Pic: morse_code.png
Syntax: In logic, syntax is a systematic statement of the rules governing the properly formed formulas of a logical system.
In computer science, the term syntax is used to denote the literal text of something written in a formal language or programming language, as opposed to its semantics or meaning.
Link: Computer Science, Formal Languages, Logic, Semantics
Semantics: The science of describing what words mean, the opposite of syntax.
Link: Word, Syntax
Pic: semantics.png
Boolean Expressions: An expression that evaluates to either True or False.
Link: Properties of Boolean Expressions
Landau Notation:
Pic: landau_notation.png
Quine – McCluskey Algorithm: The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of boolean functions which was developed by Willard Van Orman Quine and Edward J. McCluskey. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.
The method involves two steps:
1. Finding all prime implicants of the function.
2. Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.
Pic: quine_mccluskey.png
Constructing Minimal Polynomials: Prime Implicants
Pic: prime_implicants.png
Properties of Boolean Expressions: Boolean expressions can have the following properties:
Pic: properties_of_boolean_expressions.png
Link: Boolean Expressions
Entailment: In logic, entailment (or logical implication) is a relation between sets of formulae such that, if A and B are sets of formulae of a formal language, then A entails B if and only if every model (or interpretation) that makes all the members of A true, makes at least one of the members of B true. Alternatively, we can say that A entails B if and only if, for every subset B' of B, the class of models of A is a subclass of the union of the classes of each B'.
Pic: entailment.png
Link: Entailment Theorem, Logic, Formal Languages, Sets
Logic: Mathematical logic is a subfield of mathematics. It is often divided into the subfields of model theory, proof theory, set theory, and recursion theory.At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems. The system of first-order logic is the most widely studied because of its applicability to foundations of mathematics and because of its desirable properties. Stronger classical logics such as second-order logic or infinitary logic are also studied, along with nonclassical logics such as intuitionistic logic.There are many connections between mathematical logic and computer science.Many early pioneers in computer science, such as Alan Turing, were also mathematicians and logicians.The study of computability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however. Computer scientists often focus on concrete programming languages and feasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability.
The study of programming language semantics is related to model theory, as is program verification (in particular, model checking). The Curry-Howard isomorphism between proofs and programs relates to proof theory; intuitionistic logic and linear logic are significant here. Calculi such as the lambda calculus and combinatory logic are nowadays studied mainly as idealized programming languages.
Link: Computer Science, Turing Machine, Sets, Computation, Calculi, Lambda Calculus, Combinatorial Circuits
Calculus:
Pic: calculus.png
Link: Hilbert Calculus, Resolution Calculus, Leibniz Notation
Completeness and Correctness:
Pic: completeness_and_correctness.png
Hilbert Calculus:
Pic: hilbert_calculus.png
Link: Calculus, Boolean Expressions, Resolution Calculus
Entailment Theorem:
Pic: entailment_theorem.png
Link: Tntailment, Theorem
Deduction Theorem:
Pic: deduction_theorem.png
Link: Theorem
Atoms and Literals:
Pic: atoms_and_literals.png
Tableau Method: In proof theory, the semantic tableau is a decision procedure for sentential and related logics, and a proof procedure for formulas of first order logic. The tableau method can also determine the satisfiability of finite sets of formulas of various logics. It is the most popular proof procedure for modal logics (Girle 2000).
An analytic tableau has for each node a subformula of the formula at the origin. In other words, it is a tableau satisfying the subformula property.
Pic: tableau_method.png
Link: logic, sets, node
Termination for Tableau:
Pic: termination_for_tableau.png
Resolution Calculus:
Pic: resolution_calculus.png
Link: calculus
Sort: Sorting is basically “ordering” records or citations by the contents of a particular field.
Link: Sets, Lists
Leibniz Notation: In calculus, Leibniz's notation, named in honor of the 17th century German philosopher and mathematician Gottfried Wilhelm Leibniz, was originally the use of expressions such as dx and dy and to represent "infinitely small" (or infinitesimal) increments of quantities x and y, just as Δx and Δy represent finite increments of x and y respectively. According to Leibniz, the derivative of y with respect to x, was the quotient of an infinitesimal increment of y by an infinitesimal increment of x.
Link: Calculus