Course Identification

Finite algebraic structures for Computer Scientists
20194202

Lecturers and Teaching Assistants

Dr. Josephine Shamash
N/A

Course Schedule and Location

2019
Second Semester
Wednesday, 11:15 - 13:00, Ziskind, Rm 155
27/03/2019

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; 2.00 points

N/A

No

20

English

Attendance and participation

Expected and Recommended

Numerical (out of 100)

20%
80%

Take-home exam

09/08/2019
N/A
-
N/A

N/A

Syllabus

This course is intended for computer science students who have not taken advanced algebra courses as part of their first degree. The course focuses on the theory of finite structures which are important in applications of algebra to computer science, especially for error-correcting codes. Detailed examples will be investigated.

1.         Basics: Fields, rings, groups, vector spaces and their substructures. Homomorphisms of rings, ideals, quotient rings.

2.         Polynomial rings over fields and their properties. The Chinese remainder Theorem and its corollary for the structure of Z/mZ,

3.         Finite Group theory: Introduction, finite cyclic groups and their properties, the fundamental theorem of finite abelian groups.

4.         Sylow's theorems and applications to examples.

5.         The symmetric groups: their conjugacy classes and structure. Simplicity of the alternating group  for .

6.         Finite Simple groups and the classification theorem – survey.

7.         Introduction to complex characters and representations of finite groups

8.         Finite Field theory: Basic extension theorem, Finite fields, their structure and properties. Existence and uniqueness of finite fields of order q for any prime power q. Detailed examples and arithmetic in finite fields.

9.         Wedderburn's theorem that finite division rings are finite fields.

10.       Factorization of polynomials over finite fields.

11.       Counting irreducible polynomials over finite fields. Finding irreducible polynomials for error-correcting codes over finite fields using the Berlekamp algorithm.

12.       The structure of some classical matrix groups over finite fields, conjugacy classes in finite matrix groups, detailed examples.

13.       Vector spaces over finite fields and error-correcting codes: Bilinear forms and orthogonality in finite dimensional vector spaces over fields of characteristic 2.

14.       The theory of linear codes over finite fields of characteristic 2.

Examples: Hamming codes, using the structure of the field of 16 elements to define the BCH double-error correcting code.

Learning Outcomes

Computer science students should acquire a knowledge of finite algebraic structures relevant to their research.

Nathan Jacobson: Basic Algebra I & II

I. Martin Isaacs: Algebra: A Graduate Course (Chapter 21 on finite fields)

Serge Lang: Algebra

Vera Pless.: Error-correcting Codes

N/A