ALGORITHMS OF INFORMATICS
		Next

ALGORITHMS OF INFORMATICS

Volume 1

Új Széchenyi Terv logó.

Table of Contents

Preface

Introduction

I. AUTOMATA

1. Automata and Formal Languages

1.1. 1.1 Languages and grammars

1.1.1. 1.1.1 Operations on languages
1.1.2. 1.1.2 Specifying languages
1.1.3. 1.1.3 Chomsky hierarchy of grammars and languages
1.1.4. 1.1.4 Extended grammars
1.1.5. 1.1.5 Closure properties in the Chomsky-classes

1.2. 1.2 Finite automata and regular languages

1.2.1. 1.2.1 Transforming nondeterministic finite automata
1.2.2. 1.2.2 Equivalence of deterministic finite automata
1.2.3. 1.2.3 Equivalence of finite automata and regular languages.
1.2.4. 1.2.4 Finite automata with special moves
1.2.5. 1.2.5 Minimization of finite automata
1.2.6. 1.2.6 Pumping lemma for regular languages
1.2.7. 1.2.7 Regular expressions

1.3. 1.3 Pushdown automata and context-free languages

1.3.1. 1.3.1 Pushdown automata
1.3.2. 1.3.2 Context-free languages
1.3.3. 1.3.3 Pumping lemma for context-free languages
1.3.4. 1.3.4 Normal forms of the context-free languages

2. Compilers

2.1. 2.1 The structure of compilers

2.2. 2.2 Lexical analysis

2.2.1. 2.2.1 The automaton of the scanner
2.2.2. 2.2.2 Special problems

2.3. 2.3 Syntactic analysis

2.3.1. 2.3.1 parser
2.3.2. 2.3.2 parsing

3. Compression and Decompression

3.1. 3.1 Facts from information theory

3.1.1. 3.1.1 The Discrete Memoryless Source
3.1.2. 3.1.2 Prefix codes
3.1.3. 3.1.3 Kraft's inequality and noiseless coding theorem
3.1.4. 3.1.4 Shannon-Fano-Elias-codes
3.1.5. 3.1.5 The Huffman coding algorithm

3.2. 3.2 Arithmetic coding and modelling

3.2.1. 3.2.1 Arithmetic coding
3.2.2. 3.2.2 Modelling

3.3. 3.3 Ziv-Lempel-coding

3.3.1. 3.3.1 LZ77
3.3.2. 3.3.2 LZ78

3.4. 3.4 The Burrows-Wheeler-transform

3.5. 3.5 Image compression

3.5.1. 3.5.1 Representation of data
3.5.2. 3.5.2 The discrete cosine transform
3.5.3. 3.5.3 Quantisation
3.5.4. 3.5.4 Coding

4. Reliable Computation

4.1. 4.1 Probability theory

4.1.1. 4.1.1 Terminology
4.1.2. 4.1.2 The law of large numbers (with “large deviations”)

4.2. 4.2 Logic circuits

4.2.1. 4.2.1 Boolean functions and expressions
4.2.2. 4.2.2 Circuits
4.2.3. 4.2.3 Fast addition by a Boolean circuit

4.3. 4.3 Expensive fault-tolerance in Boolean circuits

4.4. 4.4 Safeguarding intermediate results

4.4.1. 4.4.1 Cables
4.4.2. 4.4.2 Compressors
4.4.3. 4.4.3 Propagating safety
4.4.4. 4.4.4 Endgame
4.4.5. 4.4.5 The construction of compressors

4.5. 4.5 The reliable storage problem

4.5.1. 4.5.1 Clocked circuits
4.5.2. 4.5.2 Storage
4.5.3. 4.5.3 Error-correcting codes
4.5.4. 4.5.4 Refreshers

II. COMPUTER ALGEBRA

5. Algebra

5.1. 5.1 Fields, vector spaces, and polynomials

5.1.1. 5.1.1 Ring theoretic concepts
5.1.2. 5.1.2 Polynomials

5.2. 5.2 Finite fields

5.3. 5.3 Factoring polynomials over finite fields

5.3.1. 5.3.1 Square-free factorisation
5.3.2. 5.3.2 Distinct degree factorisation
5.3.3. 5.3.3 The Cantor-Zassenhaus algorithm
5.3.4. 5.3.4 Berlekamp's algorithm

5.4. 5.4 Lattice reduction

5.4.1. 5.4.1 Lattices
5.4.2. 5.4.2 Short lattice vectors
5.4.3. 5.4.3 Gauss' algorithm for two-dimensional lattices
5.4.4. 5.4.4 A Gram-Schmidt orthogonalisation and weak reduction
5.4.5. 5.4.5 Lovász-reduction
5.4.6. 5.4.6 Properties of reduced bases

5.5. 5.5 Factoring polynomials in

5.5.1. 5.5.1 Preparations
5.5.2. 5.5.2 The Berlekamp-Zassenhaus algorithm
5.5.3. 5.5.3 The LLL algorithm

6. Computer Algebra

6.1. 6.1 Data representation

6.2. 6.2 Common roots of polynomials

6.2.1. 6.2.1 Classical and extended Euclidean algorithm
6.2.2. 6.2.2 Primitive Euclidean algorithm
6.2.3. 6.2.3 The resultant
6.2.4. 6.2.4 Modular greatest common divisor

6.3. 6.3 Gröbner basis

6.3.1. 6.3.1 Monomial order
6.3.2. 6.3.2 Multivariate division with remainder
6.3.3. 6.3.3 Monomial ideals and Hilbert's basis theorem
6.3.4. 6.3.4 Buchberger's algorithm
6.3.5. 6.3.5 Reduced Gröbner basis
6.3.6. 6.3.6 The complexity of computing Gröbner bases

6.4. 6.4 Symbolic integration

6.4.1. 6.4.1 Integration of rational functions
6.4.2. 6.4.2 The Risch integration algorithm

6.5. 6.5 Theory and practice

6.5.1. 6.5.1 Other symbolic algorithms
6.5.2. 6.5.2 An overview of computer algebra systems

7. Cryptology

7.1. 7.1 Foundations

7.1.1. 7.1.1 Cryptography
7.1.2. 7.1.2 Cryptanalysis
7.1.3. 7.1.3 Algebra, number theory, and graph theory

7.2. 7.2 Diffie and Hellman's secret-key agreement protocol

7.3. 7.3 RSA and factoring

7.3.1. 7.3.1 RSA
7.3.2. 7.3.2 Digital RSA signatures
7.3.3. 7.3.3 Security of RSA

7.4. 7.4 The protocols of Rivest, Rabi, and Sherman

7.5. 7.5 Interactive proof systems and zero-knowledge

7.5.1. 7.5.1 Interactive proof systems and Arthur-Merlin games
7.5.2. 7.5.2 Zero-knowledge protocol for graph isomorphism

8. Complexity Theory

8.1. 8.1 Foundations

8.2. 8.2 NP-completeness

8.3. 8.3 Algorithms for the satisfiability problem

8.3.1. 8.3.1 A deterministic algorithm
8.3.2. 8.3.2 A randomised algorithm

8.4. 8.4 Graph isomorphism and lowness

8.4.1. 8.4.1 Reducibilities and complexity hierarchies
8.4.2. 8.4.2 Graph isomorphism is in the low hierarchy
8.4.3. 8.4.3 Graph isomorphism is in SPP

III. NUMERICAL METHODS

9. Competitive Analysis

9.1. 9.1 Notions, definitions

9.2. 9.2 The -server problem

9.3. 9.3 Models related to computer networks

9.3.1. 9.3.1 The data acknowledgement problem
9.3.2. 9.3.2 The file caching problem
9.3.3. 9.3.3 On-line routing

9.4. 9.4 On-line bin packing models

9.4.1. 9.4.1 On-line bin packing
9.4.2. 9.4.2 Multidimensional models

9.5. 9.5 On-line scheduling

9.5.1. 9.5.1 On-line scheduling models
9.5.2. 9.5.2 LIST model
9.5.3. 9.5.3 TIME model

10. Game Theory

10.1. 10.1 Finite games

10.1.1. 10.1.1 Enumeration
10.1.2. 10.1.2 Games represented by finite trees

10.2. 10.2 Continuous games

10.2.1. 10.2.1 Fixed-point methods based on best responses
10.2.2. 10.2.2 Applying Fan's inequality
10.2.3. 10.2.3 Solving the Kuhn-Tucker conditions
10.2.4. 10.2.4 Reduction to optimization problems
10.2.5. 10.2.5 Method of fictitious play
10.2.6. 10.2.6 Symmetric matrix games
10.2.7. 10.2.7 Linear programming and matrix games
10.2.8. 10.2.8 The method of von Neumann
10.2.9. 10.2.9 Diagonally strictly concave games

10.3. 10.3 The oligopoly problem

11. Recurrences

11.1. 11.1 Linear recurrence equations

11.1.1. 11.1.1 Linear homogeneous equations with constant coefficients
11.1.2. 11.1.2 Linear nonhomogeneous recurrence equations

11.2. 11.2 Generating functions and recurrence equations

11.2.1. 11.2.1 Definition and operations
11.2.2. 11.2.2 Solving recurrence equations by generating functions
11.2.3. 11.2.3 The Z-transform method

11.3. 11.3 Numerical solution

12. Scientific Computing

12.1. 12.1 Floating point arithmetic and error analysis

12.1.1. 12.1.1 Classical error analysis
12.1.2. 12.1.2 Forward and backward errors
12.1.3. 12.1.3 Rounding errors and floating point arithmetic
12.1.4. 12.1.4 The floating point arithmetic standard

12.2. 12.2 Linear systems of equations

12.2.1. 12.2.1 Direct methods for solving linear systems
12.2.2. 12.2.2 Iterative methods for linear systems
12.2.3. 12.2.3 Error analysis of linear algebraic systems

12.3. 12.3 Eigenvalue problems

12.3.1. 12.3.1 Iterative solutions of the eigenvalue problem

12.4. 12.4 Numerical program libraries and software tools

12.4.1. 12.4.1 Standard linear algebra subroutines
12.4.2. 12.4.2 Mathematical software

Bibliography

List of Figures

1.1. Finite automaton.
1.2. The finite automaton of Example 1.9.
1.3. Nondeterministic finite automata.
1.4. Transition tables of the NFA in Fig. 1.3
1.5. The equivalent DFA with NFA $The equivalent DFA with NFA \mathrm{A} in Fig. 1.3.$ in Fig. 1.3.
1.6. Equivalent DFA's (Example 1.11).
1.7. Non equivalent DFA's (Example 1.12).
1.8. DFA of the Example 1.13.
1.9. NFA associated to grammar in Example 1.14.
1.10. Relations between regular grammars and finite automata. To any regular grammar one may construct an NFA which accepts the language generated by that grammar. Any NFA can be transformed in an equivalent DFA. To any DFA one may construct a regular grammar which generates the language accepted by that DFA.
1.11. Finite automata with $Finite automata with \epsilon -moves.$ -moves.
1.12. NFA equivalent to FA with $NFA equivalent to FA with \varepsilon -moves given in Fig. 1.11.$ -moves given in Fig. 1.11.
1.13. (a) Representation of an NFA. Initial states are represented by a circle with an arrow, final states by a double circle. (b) Union of two NFA's.
1.14. (a) Product of two FA. (b) Iteration of an FA.
1.15. Minimization of DFA.
1.16. Minimum automaton equivalent with DFA in Fig. 1.15.
1.17. Sketch of DFA used in the proof of the pumping lemma.
1.18. Properties of regular expressions.
1.19. DFA from Example 1.20, to which regular expression is associated by Method 1.
1.20. DFA in Example 1.21 to which a regular expression is associated by Method 1. The computation are in Figure 1.21.
1.21. Determining a regular expression associated to DFA in Figure 1.20 using sets $Determining a regular expression associated to DFA in Figure 1.20 using sets R_{ij}^{k} .$ .
1.22. Possible equivalent transformations for finding regular expression associated to an automaton.
1.23. Transformation of the finite automaton in Fig. 1.19.
1.24. Steps of Example 1.23.
1.25. Possible transformations to obtain finite automaton associated to a regular expression.
1.26. Associating finite automaton to regular expression $Associating finite automaton to regular expression \varepsilon+(0+1)^{*}1 .$ .
1.27. Finite automaton associated to regular expression $Finite automaton associated to regular expression \varepsilon+(0+1)^{*}1 .$ .
1.28. DFA's to minimize for Exercise 1.2-5
1.29. Finite automata for Exercises 1.2-6 and 1.2-7.
1.30. DFA for Exercise1.2-9.
1.31. Pushdown automaton.
1.32. Example of pushdown automaton.
1.33. Transition graph of the Example 1.27
1.34. Computation tree to show acceptance of the word $Computation tree to show acceptance of the word 1001 (see Example 1.27).$ (see Example 1.27).
1.35. Computation tree to show that the pushdown automaton in Example 1.27 does not accept word $Computation tree to show that the pushdown automaton in Example 1.27 does not accept word 101 .$ .
1.36. Recognising a word by empty stack (see Example 1.28).
1.37. Derivation (or syntax) tree of word $Derivation (or syntax) tree of word aaaabb .$ .
1.38. Decomposition of tree in the proof of pumping lemma.
2.1. The translator.
2.2. The structure of compilers.
2.3. The programs of the analysis and the synthesis.
2.4. The positive integer and real number.
2.5. The identifier.
2.6. A comment.
2.7. The character string.
2.8. $LL(k) grammar.$ grammar.
2.9. The sentential form and the analysed text.
2.10. The structure of the $The structure of the LL(1) parser.$ parser.
2.11. The syntax tree of the sentence $The syntax tree of the sentence i+i*i .$ .
2.12. The $The LR(k) grammar.$ grammar.
2.13. The $The \left[A\rightarrow\alpha.\beta,a\right] LR(1) -item.$ $The \left[A\rightarrow\alpha.\beta,a\right] LR(1) -item.$ -item.
2.14. The function $The function closure(\left[A\rightarrow\alpha.B\beta,a\right]) .$ .
2.15. The automaton of the Example 2.15.
2.16. The structure of the $The structure of the LR(1) parser.$ parser.
2.17. The syntax tree of the sentence $The syntax tree of the sentence aab .$ .
2.18. The automaton of the Example 2.22.
3.1. Frequency of letters in $Frequency of letters in 1000 characters of English.$ characters of English.
3.2. Example of a code tree.
3.3. Example of Shannon code and Shannon-Fano-Elias-code.
3.4. Example of the Shannon-Fano-algorithm.
3.5. Example of a Huffman code.
3.6. Example of arithmetic encoding with interval expansion.
3.7. Table of the first values for the Krichevsky-Trofimov-estimator.
3.8. An example for a tree source.
3.9. Weighted context tree for source sequence ' $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ ' with past $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ . The pair $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ denotes $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ zeros and $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ ones preceded by the corresponding context $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ . For the contexts $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ it is $Weighted context tree for source sequence ' 0100111 ' with past \dots010 . The pair (a_{s},b_{s}) denotes a_{s} zeros and b_{s} ones preceded by the corresponding context s . For the contexts s=111,101,110,000 it is P_{w}^{s}=P_{e}(0,0)=1 .$ .
4.1. AND, OR and NOT gate.
4.2. The assignment (values on nodes, configuration) gets propagated through all the gates. This is the “computation”.
4.3. Naive parallel addition.
4.4. Failure at a gate.
4.5. An executive organ.
4.6. A restoring organ.
4.7. An executive organ followed by a restoring organ.
4.8. Reliable circuit from a fault-free circuit.
4.9. A shift register.
4.10. Part of a circuit which computes the sum of two binary numbers $Part of a circuit which computes the sum of two binary numbers x,y . We feed the digits of x and y beginning with the lowest-order ones, at the input nodes. The digits of the sum come out on the output edge. A shift register holds the carry.$ . We feed the digits of $Part of a circuit which computes the sum of two binary numbers x,y . We feed the digits of x and y beginning with the lowest-order ones, at the input nodes. The digits of the sum come out on the output edge. A shift register holds the carry.$ and $Part of a circuit which computes the sum of two binary numbers x,y . We feed the digits of x and y beginning with the lowest-order ones, at the input nodes. The digits of the sum come out on the output edge. A shift register holds the carry.$ beginning with the lowest-order ones, at the input nodes. The digits of the sum come out on the output edge. A shift register holds the carry.
4.11. A “computer” consists of some memory (shift registers) and a Boolean circuit operating on it. We can define the size of computation as the size of the computer times the number of steps.
4.12. Transmission through a noisy channel.
4.13. Using a refresher.
4.14. A regular expander.
6.1. The general scheme of modular computations.
6.2. Illustration of the operation of the Classical-Euclidean algorithm in $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ and $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ . In case (a), the input is $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ and $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ is executed four times, values $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ , $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ and $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ in these iterations are shown in the table. The Classical-Euclidean( $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ , $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ ) algorithm outputs $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ as result. In case (b), the input parameters are $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial $Illustration of the operation of the Classical-Euclidean algorithm in \mathbb{Z} and \mathbb{Q}[x] . In case (a), the input is a=-18,b=30,a,b\in\mathbb{Z} . The first two lines of the pseudocode compute the absolute values of the input numbers. The loop between lines 3 and 6 is executed four times, values r , c and d in these iterations are shown in the table. The Classical-Euclidean( -18 , 30 ) algorithm outputs 6 as result. In case (b), the input parameters are a=12x^{4}-68x^{3}+52x^{2}-92x+56,b=-12x^{3}+80x^{2}-84x+24\in\mathbb{Q}[x] . The first two lines compute the normal form of the polynomials, and the while loop is executed three times. The output of the algorithm is the polynomial \textrm{normal}(c)=x-2/3 .$ .
6.3. The illustration of the operation of the Primitive-Euclidean algorithm with input $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ and $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ is executed three times, the table shows the values of $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ , $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ and $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ in the iterations. In line $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ , variable $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ equals $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ . The Primitive-Euclidean( $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ ) algorithm returns $The illustration of the operation of the Primitive-Euclidean algorithm with input a(x)=12x^{4}-68x^{3}+52x^{2}-92x+56,\ b(x)=-12x^{3}+80x^{2}-84x+24\in\mathbb{Z}[x] . The first two lines of the program compute the primitive parts of the polynomials. The loop between lines 3 and 6 is executed three times, the table shows the values of r , c and d in the iterations. In line 7 , variable \gamma equals \textrm{gcd}(4,4)=4 . The Primitive-Euclidean( a,b ) algorithm returns 4\cdot(3x-2) as result.$ as result.
7.1. A typical scenario in cryptography.
7.2. Example of an encryption by the shift cipher.
7.3. Vigenére square: Plaintext “H” is encrypted as “A” by key “T”.
7.4. Example of an encryption by the Vigenére cipher.
7.5. Three graphs: $Three graphs: G is isomorphic to H , but not to F .$ is isomorphic to $Three graphs: G is isomorphic to H , but not to F .$ , but not to $Three graphs: G is isomorphic to H , but not to F .$ .
7.6. Two ciphertexts encrypting the same plaintext, see Exercise 7.1-1.
7.7. The Diffie-Hellman secret-key agreement protocol.
7.8. The RSA protocol.
7.9. Example of an RSA encryption (M = Message).
7.10. Digital RSA signatures.
7.11. The Rivest-Sherman protocol for secret-key agreement, based on $The Rivest-Sherman protocol for secret-key agreement, based on \sigma$
7.12. Goldreich, Micali, and Wigderson's zero-knowledge protocol for $Goldreich, Micali, and Wigderson's zero-knowledge protocol for \mathtt{GI} .$ .
7.13. Simulation of the zero-knowledge protocol for $Simulation of the zero-knowledge protocol for \mathtt{GI} without knowing \pi .$ without knowing $Simulation of the zero-knowledge protocol for \mathtt{GI} without knowing \pi .$ .
8.1. A Turing machine with one input and two work tapes.
8.2. Transition function $Transition function \delta of M for L=\{a^{n}b^{n}c^{n}\mid n\geq1\} .$ of $Transition function \delta of M for L=\{a^{n}b^{n}c^{n}\mid n\geq1\} .$ for $Transition function \delta of M for L=\{a^{n}b^{n}c^{n}\mid n\geq1\} .$ .
8.3. $M 's states, their meaning and their intention.$ 's states, their meaning and their intention.
8.4. Comparison of some polynomial and exponential time functions.
8.5. What happens when the computers get faster?
8.6. Transition graph of a stochastic automaton for describing Random-SAT .
8.7. Runtimes of some algorithms for the satisfiability problem.
10.1. Prisoner's dilemma.
10.2. Game with no equilibrium.
10.3. Finite tree of Example 10.3.
10.4. Tree for Exercise 10.1-5.
10.5. The graph of function $The graph of function g(\lambda) .$ .
11.1. The form of particular solutions.
11.2. Binary trees with two and three vertices.
12.1. Forward and backward error.
12.2. Gaussian elimination.