COMPUTER ALGEBRA
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2019/2020
- Teacher
- FABIO STUMBO
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- MAT/02
Training objectives
- The goal of the course is to deepen theoretical aspects which are the basis of some important algebraic algorithms commonly used in applications with particular reference to Groebner bases and Coding Theory.
i
Main acquired knowledges are:
* Structure of finite fields;
* Berlekamp's algorithm;
* Buchberger's algorithm;
* Coding algorithms and error correction for message transmission.
Main acquired skills are:
* Knowing how to factor polynomials with coefficients in the rational field or in a finite field;
* Knowing how to perform division between polynomials in more than one variable;
* Knowing how to encode and decode a message and ability to recognize and correct errors occurred during transmission according to the studied algorithms. Prerequisites
- Elementary algebra knowledge as acquired in a first year undergraduate Algebra course. In particular:
* Notions about groups, rings and fields;
* Structure of finite fields;
* Calculation of the GCD and the Euclidean algorithm. Course programme
- The course forecasts 48 hours of standard lessons with both theory and exercises, approximately shared in the following way:
1. Algebraic prerequisites (4 hours):
* Euclidean algorithm
* Finite fields.
* Primitive elements.
* Roots of unity and cyclotomic classes
2. Factorization of polynomials in one variable (4 hours):
* Berlekamp's algorithm.
* Hensel Lemma.
* Factorization in Q[x].
3. Groebner basis (20 hours):
* Monomial ideals.
* Division for multivariate polynomials.
* Dickson lemma.
* Hilbert basis theorem.
* Syzygies.
* Groebner basis.
* Buchberger's algorithm.
4. Error correcting codes (20 hours):
* Hamming's distance.
* Bounds: Hamming, Singleton e Gilbert-Varshamov.
* Linear odes, Hamming codes.
* Cyclic codes, BCH codes and Reed-Solomon codes.
* Coding and decoding.
* Syndrome decoding, Slepian decoding.
* Meggitt decoding in cyclic codes.
* Decoding algorithms in BCH codes: PGZ, Forney, Sugyiama, Berlekamp-Massey. Didactic methods
- The course is organized in conventional lectures, usually 2 hours each.
Learning assessment procedures
- Examination test consists in verifying the achievement of expected skills.
This verification is through a written test lasting
3 hours and consisting in exercises related to the topics of the course lectures.
The written test consists of questions and/or exercises with
variable score for a total of not less than 30.
The total number of points obtained in the test (limited to 30 if greater) is
the student's grade.
The examination is passed if the grade is at least 18.
Oral session is optional, at student's request.
Any oral session contributes to the final mark with a score
between -3 and 3. Reference texts
- 1) Fabio Stumbo, Basi di Groebner
2) Fabio Stumbo, Teoria dei Codici
