Randomized algorithmA randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.
Sorting algorithmIn computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.
Carathéodory's theorem (convex hull)Carathéodory's theorem is a theorem in convex geometry. It states that if a point lies in the convex hull of a set , then can be written as the convex combination of at most points in . More sharply, can be written as the convex combination of at most extremal points in , as non-extremal points can be removed from without changing the membership of in the convex hull. Its equivalent theorem for conical combinations states that if a point lies in the conical hull of a set , then can be written as the conical combination of at most points in .
Convex hull algorithmsAlgorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities. Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and sometimes also in terms of h, the number of points on the convex hull.
Ordered fieldIn mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. The basic example of an ordered field is the field of real numbers, and every Dedekind-complete ordered field is isomorphic to the reals. Every subfield of an ordered field is also an ordered field in the inherited order. Every ordered field contains an ordered subfield that is isomorphic to the rational numbers. Squares are necessarily non-negative in an ordered field.
Filter (mathematics)In mathematics, a filter or order filter is a special subset of a partially ordered set (poset), describing "large" or "eventual" elements. Filters appear in order and lattice theory, but also topology, whence they originate. The notion dual to a filter is an order ideal. Special cases of filters include ultrafilters, which are filters that cannot be enlarged, and describe nonconstructive techniques in mathematical logic. Filters on sets were introduced by Henri Cartan in 1937.
Archimedean ordered vector spaceIn mathematics, specifically in order theory, a binary relation on a vector space over the real or complex numbers is called Archimedean if for all whenever there exists some such that for all positive integers then necessarily An Archimedean (pre)ordered vector space is a (pre)ordered vector space whose order is Archimedean. A preordered vector space is called almost Archimedean if for all whenever there exists a such that for all positive integers then A preordered vector space with an order unit is Archimedean preordered if and only if for all non-negative integers implies Let be an ordered vector space over the reals that is finite-dimensional.
