Reference library
Foundations
Explore concepts, laws, equations and methods, with clear explanations of their use and sources. Choose an area of study or find a specific entry.
More filters
Reference entries
Showing 1–30 of 204 reference entries
Build an inspectable physics record, test and revise a bounded cart model, preserve processing history, and plan findable data with appropriate sharing conditions.
MethodMathematics & logic · InformationClassical propositions and connectivesClassical logic combines truth-valued propositions using defined connectives.
DefinitionMathematics & logic · InformationSets, membership and basic operationsA set specifies membership without counting duplicate listings.
DefinitionMathematics & logic · InformationFunctions, domain and codomainA function assigns exactly one output to each input in its domain.
DefinitionMathematics & logic · InformationMathematical inductionA base case and general successor step establish a predicate on all nonnegative integers.
MethodMathematics & logic · InformationComplex numbersA complex number has real coordinates a and b and an imaginary unit satisfying i²=−1.
DefinitionMathematics & logic · Information · PhysicsLinear maps and matrix representationA linear map preserves linear combinations and has a matrix once bases are chosen.
DefinitionMathematics & logic · InformationProbability space and axiomsA probability assigns nonnegative, normalised, countably additive weights to events.
DefinitionMathematics & logic · InformationConditional probability and independenceConditioning restricts attention to an event of positive probability.
DefinitionMathematics & logic · InformationExpected value of a discrete random variableExpected value weights possible values by their probabilities.
DefinitionInformation · Mathematics & logicBits and unsigned binary encodingA bit has two possible states; a fixed-width unsigned binary word encodes an integer.
DefinitionInformation · Mathematics & logicShannon entropy of a discrete distributionShannon entropy measures uncertainty in a specified probability distribution.
DefinitionInformationAlgorithm and decision procedureAn algorithm specifies effective steps; a decision procedure must terminate on every permitted input.
MethodInformation · Mathematics & logicUndecidability of the halting problemNo total algorithm decides halting for every program and input in a general computation model.
Mathematical statementInformation · Mathematics & logicAsymptotic upper bounds and big OBig O bounds eventual growth up to a fixed constant factor.
DefinitionInformationFinite-alphabet mutual informationMutual information measures statistical dependence in bits.
DefinitionInformationNear-lossless source coding thresholdEntropy bounds asymptotic compression for an iid source.
Mathematical statementInformationDiscrete memoryless channel capacityCapacity is the maximal asymptotically reliable rate.
Mathematical statementInformationHamming distance and error correctionSeparated codewords permit bounded symbol-error recovery.
Mathematical statementInformationInternet protocol layersProtocol layers divide communication responsibilities.
DefinitionInformationTCP reliable byte-stream transportTCP orders bytes and retransmits detected losses.
MethodInformationEncryption, hashes and message authenticationCryptographic primitives serve distinct security properties.
DefinitionInformationPublic-key digital signaturesA signing key and a verification key have different roles.
DefinitionInformationComputable reductions and undecidabilityReduction direction determines which impossibility transfers.
Mathematical statementInformationDecision classes P and NPPolynomial solving and polynomial verification differ.
DefinitionInformationNP-hardness and NP-completenessNP-completeness combines verification and reduction hardness.
DefinitionInformationBounded-error randomized computationRandom choices permit a stated probability of error.
DefinitionInformationFinite graphs and treesGraphs represent pairwise connections; trees impose acyclicity.
DefinitionInformationData-structure interfaces and operation costsAn interface defines operations; an implementation determines costs.
MethodInformationLoop invariants and total correctnessAn invariant establishes correctness only with its proof obligations.
Method