ALGORITHMS OF INFORMATICS
   Next

ALGORITHMS OF INFORMATICS

Volume 3

Új Széchenyi Terv logó.

Table of Contents

Introduction
24. The Branch and Bound Method
24.1. 24.1 An example: the Knapsack Problem
24.1.1. 24.1.1 The Knapsack Problem
24.1.2. 24.1.2 A numerical example
24.1.3. 24.1.3 Properties in the calculation of the numerical example
24.1.4. 24.1.4 How to accelerate the method
24.2. 24.2 The general frame of the B&B method
24.2.1. 24.2.1 Relaxation
24.2.2. 24.2.2 The general frame of the B&B method
24.3. 24.3 Mixed integer programming with bounded variables
24.3.1. 24.3.1 The geometric analysis of a numerical example
24.3.2. 24.3.2 The linear programming background of the method
24.3.3. 24.3.3 Fast bounds on lower and upper branches
24.3.4. 24.3.4 Branching strategies
24.3.5. 24.3.5 The selection of the branching variable
24.3.6. 24.3.6 The numerical example is revisited
24.4. 24.4 On the enumeration tree
24.5. 24.5 The use of information obtained from other sources
24.5.1. 24.5.1 Application of heuristic methods
24.5.2. 24.5.2 Preprocessing
24.6. 24.6 Branch and Cut
24.7. 24.7 Branch and Price
25. Comparison Based Ranking
25.1. 25.1 Introduction to supertournaments
25.2. 25.2 Introduction to -tournaments
25.3. 25.3 Existence of -tournaments with prescribed score sequence
25.4. 25.4 Existence of an -tournament with prescribed score sequence
25.5. 25.5 Existence of an -tournament with prescribed score sequence
25.5.1. 25.5.1 Existence of a tournament with arbitrary degree sequence
25.5.2. 25.5.2 Description of a naive reconstructing algorithm
25.5.3. 25.5.3 Computation of
25.5.4. 25.5.4 Description of a construction algorithm
25.5.5. 25.5.5 Computation of and
25.5.6. 25.5.6 Description of a testing algorithm
25.5.7. 25.5.7 Description of an algorithm computing and
25.5.8. 25.5.8 Computing of and in linear time
25.5.9. 25.5.9 Tournament with and
25.5.10. 25.5.10 Description of the score slicing algorithm
25.5.11. 25.5.11 Analysis of the minimax reconstruction algorithm
25.6. 25.6 Imbalances in -tournaments
25.6.1. 25.6.1 Imbalances in -tournaments
25.6.2. 25.6.2 Imbalances in -tournaments
25.7. 25.7 Supertournaments
25.7.1. 25.7.1 Hypertournaments
25.7.2. 25.7.2 Supertournaments
25.8. 25.8 Football tournaments
25.8.1. 25.8.1 Testing algorithms
25.8.2. 25.8.2 Polynomial testing algorithms of the draw sequences
25.9. 25.9 Reconstruction of the tested sequences
26. Complexity of Words
26.1. 26.1 Simple complexity measures
26.1.1. 26.1.1 Finite words
26.1.2. 26.1.2 Infinite words
26.1.3. 26.1.3 Word graphs
26.1.4. 26.1.4 Complexity of words
26.2. 26.2 Generalized complexity measures
26.2.1. 26.2.1 Rainbow words
26.2.2. 26.2.2 General words
26.3. 26.3 Palindrome complexity
26.3.1. 26.3.1 Palindromes in finite words
26.3.2. 26.3.2 Palindromes in infinite words
27. Conflict Situations
27.1. 27.1 The basics of multi-objective programming
27.1.1. 27.1.1 Applications of utility functions
27.1.2. 27.1.2 Weighting method
27.1.3. 27.1.3 Distance-dependent methods
27.1.4. 27.1.4 Direction-dependent methods
27.2. 27.2 Method of equilibrium
27.3. 27.3 Methods of cooperative games
27.4. 27.4 Collective decision-making
27.5. 27.5 Applications of Pareto games
27.6. 27.6 Axiomatic methods
28. General Purpose Computing on Graphics Processing Units
28.1. 28.1 The graphics pipeline model
28.1.1. 28.1.1 GPU as the implementation of incremental image synthesis
28.2. 28.2 GPGPU with the graphics pipeline model
28.2.1. 28.2.1 Output
28.2.2. 28.2.2 Input
28.2.3. 28.2.3 Functions and parameters
28.3. 28.3 GPU as a vector processor
28.3.1. 28.3.1 Implementing the SAXPY BLAS function
28.3.2. 28.3.2 Image filtering
28.4. 28.4 Beyond vector processing
28.4.1. 28.4.1 SIMD or MIMD
28.4.2. 28.4.2 Reduction
28.4.3. 28.4.3 Implementing scatter
28.4.4. 28.4.4 Parallelism versus reuse
28.5. 28.5 GPGPU programming model: CUDA and OpenCL
28.6. 28.6 Matrix-vector multiplication
28.6.1. 28.6.1 Making matrix-vector multiplication more parallel
28.7. 28.7 Case study: computational fluid dynamics
28.7.1. 28.7.1 Eulerian solver for fluid dynamics
28.7.2. 28.7.2 Lagrangian solver for differential equations
29. Perfect Arrays
29.1. 29.1 Basic concepts
29.2. 29.2 Necessary condition and earlier results
29.3. 29.3 One-dimensional perfect arrays
29.3.1. 29.3.1 Pseudocode of the algorithm Quick-Martin
29.3.2. 29.3.2 Pseudocode of the algorithm Optimal-Martin
29.3.3. 29.3.3 Pseudocode of the algorithm Shift
29.3.4. 29.3.4 Pseudocode of the algorithm Even
29.4. 29.4 Two-dimensional perfect arrays
29.4.1. 29.4.1 Pseudocode of the algorithm Mesh
29.4.2. 29.4.2 Pseudocode of the algorithm Cellular
29.5. 29.5 Three-dimensional perfect arrays
29.5.1. 29.5.1 Pseudocode of the algorithm Colour
29.5.2. 29.5.2 Pseudocode of the algorithm Growing
29.6. 29.6 Construction of growing arrays using colouring
29.6.1. 29.6.1 Construction of growing sequences
29.6.2. 29.6.2 Construction of growing squares
29.6.3. 29.6.3 Construction of growing cubes
29.6.4. 29.6.4 Construction of a four-dimensional double hypercube
29.7. 29.7 The existence theorem of perfect arrays
29.8. 29.8 Superperfect arrays
29.9. 29.9 -complexity of one-dimensional arrays
29.9.1. 29.9.1 Definitions
29.9.2. 29.9.2 Bounds of complexity measures
29.9.3. 29.9.3 Recurrence relations
29.9.4. 29.9.4 Pseudocode of the algorithm Quick-Martin
29.9.5. 29.9.5 Pseudocode of algorithm - Complexity
29.9.6. 29.9.6 Pseudocode of algorithm Super
29.9.7. 29.9.7 Pseudocode of algorithm MaxSub
29.9.8. 29.9.8 Construction and complexity of extremal words
29.10. 29.10 Finite two-dimensional arrays with maximal complexity
29.10.1. 29.10.1 Definitions
29.10.2. 29.10.2 Bounds of complexity functions
29.10.3. 29.10.3 Properties of the maximal complexity function
29.10.4. 29.10.4 On the existence of maximal arrays
30. Score Sets and Kings
30.1. 30.1 Score sets in 1-tournaments
30.1.1. 30.1.1 Determining the score set
30.1.2. 30.1.2 Tournaments with prescribed score set
30.2. 30.2 Score sets in oriented graphs
30.2.1. 30.2.1 Oriented graphs with prescribed scoresets
30.3. 30.3 Unicity of score sets
30.3.1. 30.3.1 1-unique score sets
30.3.2. 30.3.2 2-unique score sets
30.4. 30.4 Kings and serfs in tournaments
30.5. 30.5 Weak kings in oriented graphs
Bibliography

List of Figures

24.1. The first seven steps of the solution.
24.2. The geometry of linear programming relaxation of Problem (24.36) including the feasible region (triangle The geometry of linear programming relaxation of Problem (24.36) including the feasible region (triangle \overline{{\bf \mbox{OAB}}} ), the optimal solution (x_{1}=2.5,\, x_{2}=1.5 ), and the optimal level of the objective function represented by the line 2x_{1}+x_{2}=\frac{13}{2} .), the optimal solution (The geometry of linear programming relaxation of Problem (24.36) including the feasible region (triangle \overline{{\bf \mbox{OAB}}} ), the optimal solution (x_{1}=2.5,\, x_{2}=1.5 ), and the optimal level of the objective function represented by the line 2x_{1}+x_{2}=\frac{13}{2} .), and the optimal level of the objective function represented by the line The geometry of linear programming relaxation of Problem (24.36) including the feasible region (triangle \overline{{\bf \mbox{OAB}}} ), the optimal solution (x_{1}=2.5,\, x_{2}=1.5 ), and the optimal level of the objective function represented by the line 2x_{1}+x_{2}=\frac{13}{2} ..
24.3. The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(\frac{5}{3} ,2), F=(0,2), G=(\frac{5}{3} ,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: \overline{OAB} , Branch 2: \overline{OACD} , Branch 3: empty set, Branch 4: \overline{OHG} , Branch 5: \overline{AEF} , Branch 6: \overline{AIJF} , Branch 7: empty set (not on the figure). Point J is the optimal solution.,2), F=(0,2), G=(The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(\frac{5}{3} ,2), F=(0,2), G=(\frac{5}{3} ,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: \overline{OAB} , Branch 2: \overline{OACD} , Branch 3: empty set, Branch 4: \overline{OHG} , Branch 5: \overline{AEF} , Branch 6: \overline{AIJF} , Branch 7: empty set (not on the figure). Point J is the optimal solution.,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(\frac{5}{3} ,2), F=(0,2), G=(\frac{5}{3} ,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: \overline{OAB} , Branch 2: \overline{OACD} , Branch 3: empty set, Branch 4: \overline{OHG} , Branch 5: \overline{AEF} , Branch 6: \overline{AIJF} , Branch 7: empty set (not on the figure). Point J is the optimal solution., Branch 2: The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(\frac{5}{3} ,2), F=(0,2), G=(\frac{5}{3} ,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: \overline{OAB} , Branch 2: \overline{OACD} , Branch 3: empty set, Branch 4: \overline{OHG} , Branch 5: \overline{AEF} , Branch 6: \overline{AIJF} , Branch 7: empty set (not on the figure). Point J is the optimal solution., Branch 3: empty set, Branch 4: The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(\frac{5}{3} ,2), F=(0,2), G=(\frac{5}{3} ,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: \overline{OAB} , Branch 2: \overline{OACD} , Branch 3: empty set, Branch 4: \overline{OHG} , Branch 5: \overline{AEF} , Branch 6: \overline{AIJF} , Branch 7: empty set (not on the figure). Point J is the optimal solution., Branch 5: The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(\frac{5}{3} ,2), F=(0,2), G=(\frac{5}{3} ,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: \overline{OAB} , Branch 2: \overline{OACD} , Branch 3: empty set, Branch 4: \overline{OHG} , Branch 5: \overline{AEF} , Branch 6: \overline{AIJF} , Branch 7: empty set (not on the figure). Point J is the optimal solution., Branch 6: The geometry of the course of the solution. The co-ordinates of the points are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=(\frac{5}{3} ,2), F=(0,2), G=(\frac{5}{3} ,1), H=(0,1), I=(1,2.4), and J=(1,2). The feasible regions of the relaxation are as follows. Branch 1: \overline{OAB} , Branch 2: \overline{OACD} , Branch 3: empty set, Branch 4: \overline{OHG} , Branch 5: \overline{AEF} , Branch 6: \overline{AIJF} , Branch 7: empty set (not on the figure). Point J is the optimal solution., Branch 7: empty set (not on the figure). Point J is the optimal solution.
24.4. The course of the solution of Problem (24.36). The upper numbers in the circuits are explained in subsection 24.3.2. They are the corrections of the previous bounds obtained from the first pivoting step of the simplex method. The lower numbers are the (continuous) upper bounds obtained in the branch.
24.5. The elements of the dual simplex tableau.
25.1. Point matrix of a chess+last trick-bridge tournament with Point matrix of a chess+last trick-bridge tournament with n=4 players. players.
25.2. Point matrix of a Point matrix of a (0,10,6) -tournament with f=10 for \mathbf{q}=(0,0,0,40,40,40) .-tournament with Point matrix of a (0,10,6) -tournament with f=10 for \mathbf{q}=(0,0,0,40,40,40) . for Point matrix of a (0,10,6) -tournament with f=10 for \mathbf{q}=(0,0,0,40,40,40) ..
25.3. The point table of a The point table of a (2,10,6) -tournament T .-tournament The point table of a (2,10,6) -tournament T ..
25.4. The point table of The point table of T reconstructed by Score-Slicing . reconstructed by Score-Slicing .
25.5. The point table of The point table of T reconstructed by Mini-Max . reconstructed by Mini-Max .
25.6. Number of binomial, head halfing and good sequences, further the ratio of the numbers of good sequences for neighbouring values of Number of binomial, head halfing and good sequences, further the ratio of the numbers of good sequences for neighbouring values of n ..
25.7. Sport table belonging to the sequence Sport table belonging to the sequence q=(2,3,3,9) ..
26.1. The De Bruijn graph The De Bruijn graph B(2,3) ..
26.2. The De Bruijn graph The De Bruijn graph B(3,2) ..
26.3. The De Bruijn tree The De Bruijn tree T(2,010) ..
26.4. Rauzy graphs for the infinite Fibonacci word.
26.5. Rauzy graphs for the power word.
26.6. Complexity of several binary words.
26.7. Complexity of all 3-length binary words.
26.8. Complexity of all 4-length binary words.
26.9. Values of Values of G(n) , R(n) , and M(n) ., Values of G(n) , R(n) , and M(n) ., and Values of G(n) , R(n) , and M(n) ..
26.10. Frequency of words with given total complexity.
26.11. Graph for Graph for (2,4) -subwords when n=6 .-subwords when Graph for (2,4) -subwords when n=6 ..
26.12. (d_{1},d_{2}) -complexity for rainbow words of length 6 and 7.-complexity for rainbow words of length 6 and 7.
26.13. The The (1,d) -complexity of words of length n .-complexity of words of length The (1,d) -complexity of words of length n ..
26.14. Values of Values of K(n,d) ..
27.1. Planning of a sewage plant.
27.2. The image of set The image of set X ..
27.3. The image of set The image of set H ..
27.4. Minimizing distance.
27.5. Maximizing distance.
27.6. The image of the normalized set The image of the normalized set H ..
27.7. Direction-dependent methods.
27.8. The graphical solution of Example 27.6.
27.9. The graphical solution of Example 27.7.
27.10. Game with no equilibrium.
27.11. Group decision-making table.
27.12. The database of Example 27.17.
27.13. The preference graph of Example 27.17.
27.14. Group decision-making table.
27.15. Group decision-making table.
27.16. The database of Example 27.18.
27.17.
27.18. Kalai–Smorodinsky solution.
27.19. Solution of Example 27.20.
27.20. The method of monotonous area.
28.1. GPU programming models for shader APIs and for CUDA. We depict here a Shader Model 4 compatible GPU. The programmable stages of the shader API model are red, the fixed-function stages are green.
28.2. Incremental image synthesis process.
28.3. Blending unit that computes the new pixel color of the frame buffer as a function of its old color (destination) and the new fragment color (source).
28.4. GPU as a vector processor.
28.5. An example for parallel reduction that sums the elements of the input vector.
28.6. Implementation of scatter.
28.7. Caustics rendering is a practical use of histogram generation. The illumination intensity of the target will be proportional to the number of photons it receives (images courtesy of Dávid Balambér).
28.8. Finite element representations of functions. The texture filtering of the GPU directly supports finite element representations using regularly placed samples in one-, two-, and three-dimensions and interpolating with piece-wise constant and piece-wise linear basis functions.
28.9. A time step of the Eulerian solver updates textures encoding the velocity field.
28.10. Computation of the simulation steps by updating three-dimensional textures. Advection utilizes the texture filtering hardware. The linear equations of the viscosity damping and projection are solved by Jacobi iteration, where a texel (i.e. voxel) is updated with the weighted sum of its neighbors, making a single Jacobi iteration step equivalent to an image filtering operation.
28.11. Flattened 3D velocity (left) and display variable (right) textures of a simulation.
28.12. Snapshots from an animation rendered with Eulerian fluid dynamics.
28.13. Data structures stored in arrays or textures. One-dimensional float3 arrays store the particles' position and velocity. A one-dimensional float2 texture stores the computed density and pressure. Finally, a two-dimensional texture identifies nearby particles for each particle.
28.14. A time step of the Lagrangian solver. The considered particle is the red one, and its neighbors are yellow.
28.15. Animations obtained with a Lagrangian solver rendering particles with spheres (upper image) and generating the isosurface (lower image) [ 114 ].
29.1. a) A (2,2,4,4)-square;           b) Indexing scheme a) A (2,2,4,4)-square;           b) Indexing scheme I of size 4\times4 of size a) A (2,2,4,4)-square;           b) Indexing scheme I of size 4\times4
29.2. Binary colouring matrix Binary colouring matrix C of size 8\times8 of size Binary colouring matrix C of size 8\times8
29.3. A (4,2,2,16)-square generated by colouring
29.4. A (2,2,4,4)-square
29.5. Sixteen layers of the Sixteen layers of the (2,3,2,16) -perfect output of Shift-perfect output of Shift
29.6. Values of jumping function of rainbow words of length Values of jumping function of rainbow words of length 1,2,\ldots,10 ..
30.1. A round-robin competition involving 4 players.
30.2. A tournament with score set A tournament with score set \{0,2\} ..
30.3. Out-degree matrix of the tournament represented in Figure 30.2.
30.4. Construction of tournament Construction of tournament T with odd number of distinct scores. with odd number of distinct scores.
30.5. Construction of tournament Construction of tournament T with even number of distinct scores. with even number of distinct scores.
30.6. Out-degree matrix of the tournament Out-degree matrix of the tournament T_{5}^{(3)} ..
30.7. Out-degree matrix of the tournament Out-degree matrix of the tournament T_{5}^{(3)} ..
30.8. Out-degree matrix of the tournament Out-degree matrix of the tournament T_{5} ..
30.9. An oriented graph with score sequence An oriented graph with score sequence [1,3,3,5] and score set \{1,3,5\} . and score set An oriented graph with score sequence [1,3,3,5] and score set \{1,3,5\} ..
30.10. A tournament with three kings A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs. and three serfs A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs.. Note that A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs. is neither a king nor a serf and A tournament with three kings \{u,v,y\} and three serfs \{u,v,x\} . Note that z is neither a king nor a serf and \{u.v\} are both kings and serfs. are both kings and serfs.
30.11. A tournament with three kings and two strong kings
30.12. Construction of an Construction of an (n,k) -tournament with even k .-tournament with even Construction of an (n,k) -tournament with even k ..
30.13. Six vertices and six weak kings.
30.14. Six vertices and five weak kings.
30.15. Six vertices and four weak kings.
30.16. Six vertices and three weak kings.
30.17. Six vertices and two weak kings.
30.18. Vertex of maximum score is not a king.
30.19. Construction of an Construction of an (n,k,s,b) -oriented graph.-oriented graph.
   Next