User:Ott0/sandbox

ChineseRemainder open bracket open curly Subscript of r and 1 and Subscript of r and 2 Ellipsis close bracket close curly {Subscript[m, 1],Subscript[m, 2],\[Ellipsis]}] gives the smallest x with x greater than or equal to 0 that satisfies all the integer congruences x mod Subscript[m, i] double equals Subscript[r, i]mod Subscript[m, i].

If no solution for x exists, ChineseRemainder returns unevaluated.

If all 0 less than or equal to Subscript[r, i] less than Subscript[m, i], then the result satisfies x mod Subscript[m, i] double equals Subscript[r, i].

ChineseRemainder[{Subscript[r, 1],Subscript[r, 2],\[Ellipsis]},{Subscript[m, 1],Subscript[m, 2],\[Ellipsis]}] gives a solution x with 0<=x<lcm(Subscript[m, 1],Subscript[m, 2],\[Ellipsis]).

ChineseRemainder[{Subscript[r, 1],Subscript[r, 2],\[Ellipsis]},{Subscript[m, 1],Subscript[m, 2],\[Ellipsis]},d] gives a solution x with d<=x<d+lcm(Subscript[m, 1],Subscript[m, 2],\[Ellipsis]).

Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.

The ideal form for a layered drawing would be an upward planar drawing, in which all edges are oriented in a consistent direction and no pairs of edges cross. However, graphs often contain cycles, minimizing the number of inconsistently-oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard, so layered graph drawing systems typically apply a sequence of heuristics that reduce these types of flaws in the drawing without guaranteeing to find a drawing with the minimum number of flaws.

Layout algorithm The construction of a layered graph drawing proceeds in a sequences of steps:

If the input graph is not already a directed acyclic graph, a set of edges is identified the reversal of which will make it acyclic. Finding the smallest possible set of edges is the NP-complete feedback arc set problem, so often greedy heuristics are used here in place of exact optimization algorithms. The exact solution to this problem can be formulated using integer programming.[3] Alternatively, if the number of reversed edges is very small, these edges can be found by a fixed-parameter-tractable algorithm. The vertices of the directed acyclic graph resulting from the first step are assigned to layers, such that each edge goes from a higher layer to a lower layer. The goals of this stage are to simultaneously produce a small number of layers, few edges that span large numbers of layers, and a balanced assignment of vertices to layers. For instance, by Mirsky's theorem, assigning vertices by layers according to the length of the longest path starting from each vertex produces an assignment with the minimum possible number of layers. The Coffman–Graham algorithm may be used to find a layering with a predetermined limit on the number of vertices per layer and approximately minimizing the number of layers subject to that constraint. Minimizing the width of the widest layer is NP-hard but may be solved by branch-and-cut or approximated heuristically. Alternatively, the problem of minimizing the total number of layers spanned by the edges (without any limits on the number of vertices per layer) may be solved using linear programming. Integer programming procedures, although more time-consuming, may be used to combine edge length minimization with limits on the number of vertices per level. Edges that span multiple layers are replaced by paths of dummy vertices so that, after this step, each edge in the expanded graph connects two vertices on adjacent layers of the drawing. As an optional step, a layer of edge concentrator vertices (or confluent junctions) may be imposed between two existing vertex layers, reducing the edge density by replacing complete bipartite subgraphs by stars through these edge concentrators. The vertices within each layer are permuted in an attempt to reduce the number of crossings among the edges connecting it to the previous layer. Finding the minimum number of crossings or finding a maximum crossing-free set of edges is NP-complete, even when ordering a single layer at a time in this way, so again it is typical to resort to heuristics, such as placing each vertex at a position determined by finding the average or median of the positions of its neighbors on the previous level and then swapping adjacent pairs as long as that improves the number of crossings. Alternatively, the ordering of the vertices in one layer at a time may be chosen using an algorithm that is fixed-parameter tractable in the number of crossings between it and the previous layer. Each vertex is assigned a coordinate within its layer, consistent with the permutation calculated in the previous step. Considerations in this step include placing dummy nodes on a line between their two neighbors to prevent unnecessary bends, and placing each vertex in a centered position with respect to its neighbors. Sugiyama's original work proposed a quadratic programming formulation of this step; a later method of Brandes and Köpf takes linear time and guarantees at most two bends per edge. The edges reversed in the first step of the algorithm are returned to their original orientations, the dummy vertices are removed from the graph and the vertices and edges are drawn. To avoid intersections between vertices and edges, edges that span multiple layers of the drawing may be drawn as polygonal chains or spline curves passing through each of the positions assigned to the dummy vertices along the edge.

5 paydays in a month

Representation as a set

The conventional representation of decision problems is the set of objects possessing the property in question. The halting set

K defined as set of ordered pairs i x such that program i halts when run on input x

represents the halting problem.

This set is recursively enumerable, which means there is a computable function that lists all of the pairs i x it contains. However, the complement of this set is not recursively enumerable.

There are many equivalent formulations of the halting problem; any set whose Turing degree equals that of the halting problem is such a formulation. Examples of such sets include:

set of i such that program i eventually halts when run with input 0 and set of i such that there is an input x such that program i eventually halts when run with input x

Proof concept

The proof that the halting problem is not solvable is a proof by contradiction. To illustrate the concept of the proof, suppose that there exists a total computable function halts(f) that returns true if the subroutine f halts (when run with no inputs) and returns false otherwise. Now consider the following subroutine:

def g

   if halts g
       loop forever

halts g must either return true or false, because halts was assumed to be total. If halts(g) returns true, then g will call loop_forever and never halt, which is a contradiction. If halts(g) returns false, then g will halt, because it will not call loop_forever; this is also a contradiction. Overall, halts(g) can not return a truth value that is consistent with whether g halts. Therefore, the initial assumption that halts is a total computable function must be false.

The method used in the proof is called diagonalization - g does the opposite of what halts says g should do. The difference between this sketch and the actual proof is that in the actual proof, the computable function halts does not directly take a subroutine as an argument; instead it takes the source code of a program. The actual proof requires additional work to handle this issue. Moreover, the actual proof avoids the direct use of recursion shown in the definition of g.

If the initial term of an arithmetic progression is a sub 1 and the common difference of successive members is d, then the nth term of the sequence a sub n is given by:

a sub n equals a sub 1 plus quantity n minus 1 times d

and in general

a sub n equals a sub m plus quantity n minus m times d.