Misplaced Pages

#978021

68-421: The input to the algorithm is an undirected graph G = ( V , E ) with vertex set V , edge set E , and (optionally) numerical weights on the edges in E . The goal of the algorithm is to partition V into two disjoint subsets A and B of equal (or nearly equal) size, in a way that minimizes the sum T of the weights of the subset of edges that cross from A to B . If the graph is unweighted, then instead

136-491: A and other nodes in A , and let E a {\displaystyle E_{a}} be the external cost of a , that is, the sum of the costs of edges between a and nodes in B . Similarly, define I b {\displaystyle I_{b}} , E b {\displaystyle E_{b}} for each b ∈ B {\displaystyle b\in B} . Furthermore, let be

204-457: A connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees. A polytree (or directed tree or oriented tree or singly connected network ) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest )

272-437: A directed simple graph permitting loops and a directed multigraph permitting loops (or a quiver ) respectively. The edges of a directed simple graph permitting loops G is a homogeneous relation ~ on the vertices of G that is called the adjacency relation of G . Specifically, for each edge ( x , y ) , its endpoints x and y are said to be adjacent to one another, which is denoted x ~ y . A mixed graph

340-446: A network is a graph in which a number (the weight) is assigned to each edge. Such weights might represent for example costs, lengths or capacities, depending on the problem at hand. Such graphs arise in many contexts, for example in shortest path problems such as the traveling salesman problem . One definition of an oriented graph is that it is a directed graph in which at most one of ( x , y ) and ( y , x ) may be edges of

408-770: A recurrence relation or difference equation . Difference equations are similar to differential equations , but replace differentiation by taking the difference between adjacent terms; they can be used to approximate differential equations or (more often) studied in their own right. Many questions and methods concerning differential equations have counterparts for difference equations. For instance, where there are integral transforms in harmonic analysis for studying continuous functions or analogue signals, there are discrete transforms for discrete functions or digital signals. As well as discrete metric spaces , there are more general discrete topological spaces , finite metric spaces , finite topological spaces . The time scale calculus

476-440: A chemico-graphical image). Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures . A graph (sometimes called an undirected graph to distinguish it from a directed graph , or a simple graph to distinguish it from a multigraph ) is a pair G = ( V , E ) , where V is a set whose elements are called vertices (singular: vertex), and E

544-407: A course that is basically intended to develop mathematical maturity in first-year students; therefore, it is nowadays a prerequisite for mathematics majors in some universities as well. Some high-school-level discrete mathematics textbooks have appeared as well. At this level, discrete mathematics is sometimes seen as a preparatory course, like precalculus in this respect. The Fulkerson Prize

612-442: A loop contributes 2 to the degree), and the maximum number of edges is n ( n − 1)/2 (or n ( n + 1)/2 if loops are allowed). The edges of a graph define a symmetric relation on the vertices, called the adjacency relation . Specifically, two vertices x and y are adjacent if { x , y } is an edge. A graph is fully determined by its adjacency matrix A , which is an n × n square matrix, with A ij specifying

680-405: A number of challenging problems which have focused attention within areas of the field. In graph theory, much research was motivated by attempts to prove the four color theorem , first stated in 1852, but not proved until 1976 (by Kenneth Appel and Wolfgang Haken, using substantial computer assistance). In logic , the second problem on David Hilbert 's list of open problems presented in 1900

748-402: A part of number theory and analysis , partition theory is now considered a part of combinatorics or an independent field. Order theory is the study of partially ordered sets , both finite and infinite. Graph theory, the study of graphs and networks , is often considered part of combinatorics, but has grown large enough and distinct enough, with its own kind of problems, to be regarded as

SECTION 10

#1732798532979

816-443: A person B only if B also shakes hands with A . In contrast, if an edge from a person A to a person B means that A owes money to B , then this graph is directed, because owing money is not necessarily reciprocated. Graphs are the basic subject studied by graph theory. The word "graph" was first used in this sense by J. J. Sylvester in 1878 due to a direct relation between mathematics and chemical structure (what he called

884-538: A point, or as the spectrum Spec ⁡ K [ x ] ( x − c ) {\displaystyle \operatorname {Spec} K[x]_{(x-c)}} of the local ring at (x-c) , a point together with a neighborhood around it. Algebraic varieties also have a well-defined notion of tangent space called the Zariski tangent space , making many features of calculus applicable even in finite settings. In applied mathematics , discrete modelling

952-406: A positive integer. Undirected graphs will have a symmetric adjacency matrix (meaning A ij = A ji ). A directed graph or digraph is a graph in which edges have orientations. In one restricted but very common sense of the term, a directed graph is a pair G = ( V , E ) comprising: To avoid ambiguity, this type of object may be called precisely a directed simple graph . In

1020-449: A single conclusion). The truth values of logical formulas usually form a finite set, generally restricted to two values: true and false , but logic can also be continuous-valued, e.g., fuzzy logic . Concepts such as infinite proof trees or infinite derivation trees have also been studied, e.g. infinitary logic . Set theory is the branch of mathematics that studies sets , which are collections of objects, such as {blue, white, red} or

1088-486: A special kind of binary relation , because most results on finite graphs either do not extend to the infinite case or need a rather different proof. An empty graph is a graph that has an empty set of vertices (and thus an empty set of edges). The order of a graph is its number | V | of vertices, usually denoted by n . The size of a graph is its number | E | of edges, typically denoted by m . However, in some contexts, such as for expressing

1156-693: A subject in its own right. Graphs are one of the prime objects of study in discrete mathematics. They are among the most ubiquitous models of both natural and human-made structures. They can model many types of relations and process dynamics in physical, biological and social systems. In computer science, they can represent networks of communication, data organization, computational devices, the flow of computation, etc. In mathematics, they are useful in geometry and certain parts of topology , e.g. knot theory . Algebraic graph theory has close links with group theory and topological graph theory has close links to topology . There are also continuous graphs ; however, for

1224-472: A subset of the pairs chosen to have the best overall effect on the solution quality T . Given a graph with n vertices, each pass of the algorithm runs in time O ( n log n ) . In more detail, for each a ∈ A {\displaystyle a\in A} , let I a {\displaystyle I_{a}} be the internal cost of a , that is, the sum of the costs of edges between

1292-491: A unified framework for counting permutations , combinations and partitions . Analytic combinatorics concerns the enumeration (i.e., determining the number) of combinatorial structures using tools from complex analysis and probability theory . In contrast with enumerative combinatorics which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae . Topological combinatorics concerns

1360-425: A vertex to itself. To allow loops, the pairs of vertices in E must be allowed to have the same node twice. Such generalized graphs are called graphs with loops or simply graphs when it is clear from the context that loops are allowed. Generally, the vertex set V is taken to be finite (which implies that the edge set E is also finite). Sometimes infinite graphs are considered, but they are usually viewed as

1428-407: Is tiling of the plane . In algebraic geometry , the concept of a curve can be extended to discrete geometries by taking the spectra of polynomial rings over finite fields to be models of the affine spaces over that field, and letting subvarieties or spectra of other rings provide the curves that lie in that space. Although the space in which the curves appear has a finite number of points,

SECTION 20

#1732798532979

1496-408: Is a directed acyclic graph whose underlying undirected graph is a forest. More advanced kinds of graphs are: Two edges of a graph are called adjacent if they share a common vertex. Two edges of a directed graph are called consecutive if the head of the first one is the tail of the second one. Similarly, two vertices are called adjacent if they share a common edge ( consecutive if the first one

1564-434: Is a directed graph in which every ordered pair of vertices in the graph is strongly connected. Otherwise, it is called a weakly connected graph if every ordered pair of vertices in the graph is weakly connected. Otherwise it is called a disconnected graph . A k-vertex-connected graph or k-edge-connected graph is a graph in which no set of k − 1 vertices (respectively, edges) exists that, when removed, disconnects

1632-400: Is a graph in which some edges may be directed and some may be undirected. It is an ordered triple G = ( V , E , A ) for a mixed simple graph and G = ( V , E , A , ϕ E , ϕ A ) for a mixed multigraph with V , E (the undirected edges), A (the directed edges), ϕ E and ϕ A defined as above. Directed and undirected graphs are special cases. A weighted graph or

1700-417: Is a set of unordered pairs { v 1 , v 2 } {\displaystyle \{v_{1},v_{2}\}} of vertices, whose elements are called edges (sometimes links or lines ). The vertices u and v of an edge { u , v } are called the edge's endpoints . The edge is said to join u and v and to be incident on them. A vertex may belong to no edge, in which case it

1768-467: Is a theorem. For classical logic, it can be easily verified with a truth table . The study of mathematical proof is particularly important in logic, and has accumulated to automated theorem proving and formal verification of software. Logical formulas are discrete structures, as are proofs , which form finite trees or, more generally, directed acyclic graph structures (with each inference step combining one or more premise branches to give

1836-457: Is a unification of the theory of difference equations with that of differential equations , which has applications to fields requiring simultaneous modelling of discrete and continuous data. Another way of modeling such a situation is the notion of hybrid dynamical systems . Discrete geometry and combinatorial geometry are about combinatorial properties of discrete collections of geometrical objects. A long-standing topic in discrete geometry

1904-418: Is awarded for outstanding papers in discrete mathematics. Theoretical computer science includes areas of discrete mathematics relevant to computing. It draws heavily on graph theory and mathematical logic . Included within theoretical computer science is the study of algorithms and data structures. Computability studies what can be computed in principle, and has close ties to logic, while complexity studies

1972-420: Is called a disconnected graph . In a directed graph, an ordered pair of vertices ( x , y ) is called strongly connected if a directed path leads from x to y . Otherwise, the ordered pair is called weakly connected if an undirected path leads from x to y after replacing all of its directed edges with undirected edges. Otherwise, the ordered pair is called disconnected . A strongly connected graph

2040-429: Is called an edge (also called link or line ). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with

2108-421: Is implied that the graphs discussed are finite. If the graphs are infinite, that is usually specifically stated. In an undirected graph, an unordered pair of vertices { x , y } is called connected if a path leads from x to y . Otherwise, the unordered pair is called disconnected . A connected graph is an undirected graph in which every unordered pair of vertices in the graph is connected. Otherwise, it

Kernighan–Lin algorithm - Misplaced Pages Continue

2176-435: Is not joined to any other vertex and is called isolated . When an edge { u , v } {\displaystyle \{u,v\}} exists, the vertices u and v are called adjacent . A multigraph is a generalization that allows multiple edges to have the same pair of endpoints. In some texts, multigraphs are simply called graphs. Sometimes, graphs are allowed to contain loops , which are edges that join

2244-590: Is the comma category Set ↓ D where D : Set → Set is the functor taking a set s to s × s . There are several operations that produce new graphs from initial ones, which might be classified into the following categories: In a hypergraph , an edge can join any positive number of vertices. An undirected graph can be seen as a simplicial complex consisting of 1- simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices. Discrete mathematics Discrete mathematics

2312-481: Is the discrete analogue of continuous modelling . In discrete modelling, discrete formulae are fit to data . A common method in this form of modelling is to use recurrence relation . Discretization concerns the process of transferring continuous models and equations into discrete counterparts, often for the purposes of making calculations easier by using approximations. Numerical analysis provides an important example. The history of discrete mathematics has involved

2380-602: Is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables , having a bijection with the set of natural numbers ) rather than "continuous" (analogously to continuous functions ). Objects studied in discrete mathematics include integers , graphs , and statements in logic . By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers , calculus or Euclidean geometry . Discrete objects can often be enumerated by integers ; more formally, discrete mathematics has been characterized as

2448-429: Is the tail and the second one is the head of an edge), in which case the common edge is said to join the two vertices. An edge and a vertex on that edge are called incident . The graph with only one vertex and no edges is called the trivial graph . A graph with only vertices and no edges is known as an edgeless graph . The graph with no vertices and no edges is sometimes called the null graph or empty graph , but

2516-448: Is the union of two disjoint sets, W and X , so that every vertex in W is adjacent to every vertex in X but there are no edges within W or X . A path graph or linear graph of order n ≥ 2 is a graph in which the vertices can be listed in an order v 1 , v 2 , …, v n such that the edges are the { v i , v i +1 } where i = 1, 2, …, n − 1. Path graphs can be characterized as connected graphs in which

2584-403: The calculus of finite differences , a function defined on an interval of the integers is usually called a sequence . A sequence could be a finite sequence from a data source or an infinite sequence from a discrete dynamical system . Such a discrete function could be defined explicitly by a list (if its domain is finite), or by a formula for its general term, or it could be given implicitly by

2652-430: The computational complexity of algorithms, the term size is used for the quantity | V | + | E | (otherwise, a non-empty graph could have size 0). The degree or valency of a vertex is the number of edges that are incident to it; for graphs with loops, a loop is counted twice. In a graph of order n , the maximum degree of each vertex is n − 1 (or n + 1 if loops are allowed, because

2720-420: The computer graphics incorporated into modern video games and computer-aided design tools. Several fields of discrete mathematics, particularly theoretical computer science, graph theory, and combinatorics , are important in addressing the challenging bioinformatics problems associated with understanding the tree of life . Currently, one of the most famous open problems in theoretical computer science

2788-735: The first programmable digital electronic computer being developed at England's Bletchley Park with the guidance of Alan Turing and his seminal work, On Computable Numbers. The Cold War meant that cryptography remained important, with fundamental advances such as public-key cryptography being developed in the following decades. The telecommunications industry has also motivated advances in discrete mathematics, particularly in graph theory and information theory . Formal verification of statements in logic has been necessary for software development of safety-critical systems , and advances in automated theorem proving have been driven by this need. Computational geometry has been an important part of

Kernighan–Lin algorithm - Misplaced Pages Continue

2856-456: The (infinite) set of all prime numbers . Partially ordered sets and sets with other relations have applications in several areas. In discrete mathematics, countable sets (including finite sets ) are the main focus. The beginning of set theory as a branch of mathematics is usually marked by Georg Cantor 's work distinguishing between different kinds of infinite set , motivated by the study of trigonometric series, and further development of

2924-506: The branch of mathematics dealing with countable sets (finite sets or sets with the same cardinality as the natural numbers). However, there is no exact definition of the term "discrete mathematics". The set of objects studied in discrete mathematics can be finite or infinite. The term finite mathematics is sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business. Research in discrete mathematics increased in

2992-645: The curves are not so much sets of points as analogues of curves in continuous settings. For example, every point of the form V ( x − c ) ⊂ Spec ⁡ K [ x ] = A 1 {\displaystyle V(x-c)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}} for K {\displaystyle K} a field can be studied either as Spec ⁡ K [ x ] / ( x − c ) ≅ Spec ⁡ K {\displaystyle \operatorname {Spec} K[x]/(x-c)\cong \operatorname {Spec} K} ,

3060-426: The definition above, are two or more edges with both the same tail and the same head. In one more general sense of the term allowing multiple edges, a directed graph is sometimes defined to be an ordered triple G = ( V , E , ϕ ) comprising: To avoid ambiguity, this type of object may be called precisely a directed multigraph . A loop is an edge that joins a vertex to itself. Directed graphs as defined in

3128-811: The definitions must be expanded. For directed simple graphs, the definition of E {\displaystyle E} should be modified to E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } {\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}} . For directed multigraphs, the definition of ϕ {\displaystyle \phi } should be modified to ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } {\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}} . To avoid ambiguity, these types of objects may be called precisely

3196-457: The degree of all but two vertices is 2 and the degree of the two remaining vertices is 1. If a path graph occurs as a subgraph of another graph, it is a path in that graph. A planar graph is a graph whose vertices and edges can be drawn in a plane such that no two of the edges intersect. A cycle graph or circular graph of order n ≥ 3 is a graph in which the vertices can be listed in an order v 1 , v 2 , …, v n such that

3264-613: The difference between the external and internal costs of s . If a and b are interchanged, then the reduction in cost is where c a , b {\displaystyle c_{a,b}} is the cost of the possible edge between a and b . The algorithm attempts to find an optimal series of interchange operations between elements of A {\displaystyle A} and B {\displaystyle B} which maximizes T o l d − T n e w {\displaystyle T_{old}-T_{new}} and then executes

3332-414: The edge ( x , y ) directed from x to y , the vertices x and y are called the endpoints of the edge, x the tail of the edge and y the head of the edge. The edge is said to join x and y and to be incident on x and on y . A vertex may exist in a graph and not belong to an edge. The edge ( y , x ) is called the inverted edge of ( x , y ) . Multiple edges , not allowed under

3400-425: The edges are the { v i , v i +1 } where i = 1, 2, …, n − 1, plus the edge { v n , v 1 } . Cycle graphs can be characterized as connected graphs in which the degree of all vertices is 2. If a cycle graph occurs as a subgraph of another graph, it is a cycle or circuit in that graph. A tree is an undirected graph in which any two vertices are connected by exactly one path , or equivalently

3468-402: The goal is to minimize the number of crossing edges; this is equivalent to assigning weight one to each edge. The algorithm maintains and improves a partition, in each pass using a greedy algorithm to pair up vertices of A with vertices of B , so that moving the paired vertices from one side of the partition to the other will improve the partition. After matching the vertices, it then performs

SECTION 50

#1732798532979

3536-410: The graph. A k -vertex-connected graph is often called simply a k-connected graph . A bipartite graph is a simple graph in which the vertex set can be partitioned into two sets, W and X , so that no two vertices in W share a common edge and no two vertices in X share a common edge. Alternatively, it is a graph with a chromatic number of 2. In a complete bipartite graph , the vertex set

3604-401: The graph. That is, it is a directed graph that can be formed as an orientation of an undirected (simple) graph. Some authors use "oriented graph" to mean the same as "directed graph". Some authors use "oriented graph" to mean any orientation of a given undirected graph or multigraph. A regular graph is a graph in which each vertex has the same number of neighbours, i.e., every vertex has

3672-566: The latter half of the twentieth century partly due to the development of digital computers which operate in "discrete" steps and store data in "discrete" bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science , such as computer algorithms , programming languages , cryptography , automated theorem proving , and software development . Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems. Although

3740-409: The main objects of study in discrete mathematics are discrete objects, analytic methods from "continuous" mathematics are often employed as well. In university curricula, discrete mathematics appeared in the 1980s, initially as a computer science support course; its contents were somewhat haphazard at the time. The curriculum has thereafter developed in conjunction with efforts by ACM and MAA into

3808-1050: The most part, research in graph theory falls within the domain of discrete mathematics. Number theory is concerned with the properties of numbers in general, particularly integers . It has applications to cryptography and cryptanalysis , particularly with regard to modular arithmetic , diophantine equations , linear and quadratic congruences, prime numbers and primality testing . Other discrete aspects of number theory include geometry of numbers . In analytic number theory , techniques from continuous mathematics are also used. Topics that go beyond discrete objects include transcendental numbers , diophantine approximation , p-adic analysis and function fields . Algebraic structures occur as both discrete examples and continuous examples. Discrete algebras include: Boolean algebra used in logic gates and programming; relational algebra used in databases ; discrete and finite versions of groups , rings and fields are important in algebraic coding theory ; discrete semigroups and monoids appear in

3876-478: The number of connections from vertex i to vertex j . For a simple graph, A ij is either 0, indicating disconnection, or 1, indicating connection; moreover A ii = 0 because an edge in a simple graph cannot start and end at the same vertex. Graphs with self-loops will be characterized by some or all A ii being equal to a positive integer, and multigraphs (with multiple edges between vertices) will be characterized by some or all A ij being equal to

3944-514: The numbers of incident edges.) The same remarks apply to edges, so graphs with labeled edges are called edge-labeled . Graphs with labels attached to edges or vertices are more generally designated as labeled . Consequently, graphs in which vertices are indistinguishable and edges are indistinguishable are called unlabeled . (In the literature, the term labeled may apply to other kinds of labeling, besides that which serves only to distinguish different vertices or edges.) The category of all graphs

4012-423: The operations, producing a partition of the graph to A and B . Source: Undirected graph In discrete mathematics , particularly in graph theory , a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices (also called nodes or points ) and each of the related pairs of vertices

4080-423: The same degree. A regular graph with vertices of degree k is called a k ‑regular graph or regular graph of degree k . A complete graph is a graph in which each pair of vertices is joined by an edge. A complete graph contains all possible edges. A finite graph is a graph in which the vertex set and the edge set are finite sets . Otherwise, it is called an infinite graph . Most commonly in graph theory it

4148-605: The study of various continuous computational topics. Information theory involves the quantification of information . Closely related is coding theory which is used to design efficient and reliable data transmission and storage methods. Information theory also includes continuous topics such as: analog signals , analog coding , analog encryption . Logic is the study of the principles of valid reasoning and inference , as well as of consistency , soundness , and completeness . For example, in most systems of logic (but not in intuitionistic logic ) Peirce's law ((( P → Q )→ P )→ P )

SECTION 60

#1732798532979

4216-409: The terminology is not consistent and not all mathematicians allow this object. Normally, the vertices of a graph, by their nature as elements of a set, are distinguishable. This kind of graph may be called vertex-labeled . However, for many questions it is better to treat vertices as indistinguishable. (Of course, the vertices may be still distinguishable by the properties of the graph itself, e.g., by

4284-534: The theory of formal languages . There are many concepts and theories in continuous mathematics which have discrete versions, such as discrete calculus , discrete Fourier transforms , discrete geometry , discrete logarithms , discrete differential geometry , discrete exterior calculus , discrete Morse theory , discrete optimization , discrete probability theory , discrete probability distribution , difference equations , discrete dynamical systems , and discrete vector measures . In discrete calculus and

4352-411: The theory of infinite sets is outside the scope of discrete mathematics. Indeed, contemporary work in descriptive set theory makes extensive use of traditional continuous mathematics. Combinatorics studies the ways in which discrete structures can be combined or arranged. Enumerative combinatorics concentrates on counting the number of certain combinatorial objects - e.g. the twelvefold way provides

4420-536: The time, space, and other resources taken by computations. Automata theory and formal language theory are closely related to computability. Petri nets and process algebras are used to model computer systems, and methods from discrete mathematics are used in analyzing VLSI electronic circuits. Computational geometry applies algorithms to geometrical problems and representations of geometrical objects, while computer image analysis applies them to representations of images. Theoretical computer science also includes

4488-616: The two definitions above cannot have loops, because a loop joining a vertex x {\displaystyle x} to itself is the edge (for a directed simple graph) or is incident on (for a directed multigraph) ( x , x ) {\displaystyle (x,x)} which is not in { ( x , y ) ∣ ( x , y ) ∈ V 2 and x ≠ y } {\displaystyle \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}} . So to allow loops

4556-436: The use of techniques from topology and algebraic topology / combinatorial topology in combinatorics . Design theory is a study of combinatorial designs , which are collections of subsets with certain intersection properties. Partition theory studies various enumeration and asymptotic problems related to integer partitions , and is closely related to q-series , special functions and orthogonal polynomials . Originally

4624-595: Was to prove that the axioms of arithmetic are consistent . Gödel's second incompleteness theorem , proved in 1931, showed that this was not possible – at least not within arithmetic itself. Hilbert's tenth problem was to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution. In 1970, Yuri Matiyasevich proved that this could not be done . The need to break German codes in World War II led to advances in cryptography and theoretical computer science , with

#978021