ДМиТИ Зяблицева Лекции

Lecture Notes on Discrete Mathematics and Theoretical Computer Science

Page 1

• Course Title: Discrete Mathematics and Theoretical Computer Science

• Instructor: Lyudmila Vladimirovna Zablitskaya

Page 2

Lecture 1: Abstract Algebraic Structures

• Key Concepts:

  • Abstract algebraic structures consist of a set and operations defined on that set.

  • Let A be a non-empty set; it includes ordered pairs defined as A² = A × A.

  • General formula: Aⁿ = (a₁; a₂; ...; aₙ) where aᵢ ∈ A.

Operations on Sets

• Operations: Defined on the set A, denoted by symbols like ◦ and *.

• Algebraic Operations: Each pair of elements a, b from A can be mapped to a unique element of A by a operation defined as a ◦ b.

• Algebra Structure: If ◦ is an operation on A, the structure (A; ◦) is called an algebra.

Properties of Algebraic Operations

1. Commutativity: An operation is commutative if a ◦ b = b ◦ a for all a, b ∈ A.

2. Associativity: An operation is associative if a ◦ (b ◦ c) = (a ◦ b) ◦ c.

3. Identity Element: An element e ∈ A such that e ◦ a = a ◦ e = a for all a ∈ A.

4. Inverses: An element b is said to be the inverse of a with respect to an operation ◦ if a ◦ b = e.

5. Distributive Property: An operation * is distributive over ◦ if a * (b ◦ c) = (a * b) ◦ (a * c).

Page 3

Properties Continued

• Exercise: Confirm whether an operation defined in a Cayley table is algebraic, commutative, or associative; find neutral elements.

• Commutative Cayley Table: If symmetric across the diagonal, then the operation is commutative.

• Neutral Element: Must equal the original rows and columns for all elements.

• Associativity Testing: More complex, involving the associativity test algorithm.

Page 4

Algebra Classification with Binary Operations

1. Semigroup: An algebra with an associative operation.

2. Monoid: An associative algebra with a neutral element.

3. Group: An algebra where:

   • The operation is associative.

   • There exists a neutral element.

   • Every element has an inverse.

4. Abelian Group: A group where the operation is also commutative.

Page 5

Examples of Groups and Algebras

• Integers with Addition: (ℤ, +) is an abelian group.

• Natural Numbers with Addition: (ℕ, +) is a commutative semigroup (no neutral element).

• Multiplication of Natural Numbers: (ℕ, ×) is a commutative monoid.

• Difference in Integers: (ℤ, −) is algebraic but not associative.

Page 6

Divisibility and Division Theorem of Integers

• Definition: An integer a is divisible by b if there exists an integer q such that a = bq.

• Notation: a|b and a is called divisible (b is the divisor).

• Key Properties: 0|a for a ≠ 0; a|(±a); a|1 implies a must be ±1.

• Linear Combinations: r = x₁a₁ + x₂a₂ + ... + xₙaₙ.

Page 7

Integrating Divisibility in Integer Arithmetic

• Remainder Definition: a is divided with remainder b if there are integers q and r satisfying: a = bq + r where 0 ≤ r < |b|.

• Properties: Unique division with remainder.

Page 8

Division with Remainder Theorem

• Existence of Division: Every integer can be divided by another non-zero integer with remainder.

• Proof Sketch: Using inequalities to establish bounds for q and r.

Page 9

GCD and LCM of Integers

• Definition: The greatest common divisor (GCD) of a set of integers is the largest positive integer that divides them all.

• Properties: Notation (a, b) denotes GCD. Certain rules apply to GCD like commutativity, associativity, distributed over addition.

• Examples: Calculation examples showing applications of GCD.

Page 10

Factorization and the Euclidean Algorithm

• Greatest Common Divisor: Exists by definition of non-empty sets of integers.

• Calculation of GCD: Via division method, tracking remainders until no remainder remains.

Page 11

Field Construction and Galois Theory

• Fields with Polynomial Rings: Concepts such as irreducibility in fields, normalization of polynomials, canonic representation, etc.

• Galois Field Fq defined over prime fields Q = Zp.

Page 12

Error Detection and Correction in Coding Theory

• Channel Coding Theory: Concepts of binary, systematic codes, Hamming Codes, Reed Solomon, etc.

• Noise Reduction Techniques: Detection methods, syndrome calculations, and error corrections.

Page 13

Huffman Coding and Gray Code

• Huffman Algorithm: Process for forming optimal codes and analyzing average lengths.

• Gray Code: Explains the significance of binary transformations preserving single-bit differences which is crucial in minimizing errors in digital systems.