Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat

FISA DISCIPLINEI

Codul
Denumirea disciplinei
MML1012 Teoria codurilor
Specializarea
Semestrul
Ore: C+S+L
Categoria
Statutul
Matematică Computatională - în limba maghiară
1
2+2+0
obligatorie
Matematică Computaţională - în limba maghiară
1
2+2+0
specialitate
obligatorie
Optimizarea modelelor informatice - în limba magh.
1
2+2+0
specialitate
obligatorie
Titularii de disciplina
Prof. Dr. MARCUS Andrei,  marcusmath.ubbcluj.ro
Obiective
Acest curs este o introducere in teoria codurilor corectoare de erori,
insistand asupra codurilor liniare. Se introduc notiunile si rezultatele din
algebra privind in special polinoamele peste corpuri finite, si se prezinta
algoritmi pentru manipularea acestora.
Continutul
1. Polinoame
1.1. Preliminarii asupra polinoamelor
1.2. Evaluarea polinoamelor
1.2.1. Schema lui Horner
1.2.2. Metoda Cooley-Tukey
1.3. Formula de interpolare Lagrange
1.4. Transformarea Fourier Discreta
1.4.1. Metoda Schoenhage-Strassen pentru multiplicarea rapida a intregilor

2. Extensions of fields
2.1. Finite and algebraic extensions
2.2. Simple extensions. Splitting fields
2.3. Multiple roots, separable polynomials
2.4. Adjunction of an element. Minimal polynomial

3. Corpuri finite
3.1. Constructii de corpuri finite si proprietati de baza
3.2. Logaritmul discret
3.3. Subcorpuri ale corpurilor finite
3.4. Algoritmul Silver-Pohlig-Hellman pentru calculul logaritmului discret
3.5. O aplicatie a teoremei Chineze a resturilor: adunarea rapida a intregilor

4. Polinoame peste corpuri finite
4.1. Polinoame ciclotomice
4.2. Formula de inversiune Moebius
4.3. Polinoame ireductibile
4.4. Calculul polinoamelor minimale
4.5. Numarul polinoame ireductibile
4.6. Ordinul unui polinom. Polinoame primitive
4.6.1. Polinoame primitive
4.6.2. Metode de determinare ale polinoamelor primitive

5. Factorizarea polinoamelor peste corpuri finite
5.1. Teorema chineza a resturilor pentru polinoame
5.2. Algoritmul lui Berlekamp
5.3. Aplicatii ale corpurilor finite in criptologie
5.3.1. AES (Advanced Encryption Standard)
5.3.2. Sistemul Diffie-Hellmann de schimbare a cheii

6. Teoria codurilor
6.1. Introducere
6.2. Concepte de baza
6.3. Coduri liniare
6.3.1. Distanta minima a unui cod liniar
6.3.2. Dual unui cod liniar
6.3.3. Algoritm de decodare pentru coduri liniare
6.3.4. Coduri Hamming
6.4. Coduri ciclice
6.4.1. Dualul unui cod ciclic
6.4.2. Algoritm de decodare pentru coduri ciclice
6.4.3. Coduri ciclice speciale. Coduri BCH
6.5. Coduri convolutionale
6.5. Pachete GAP pentru calcule in teoria codurilor



Bibliografie
1. Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT 1990.
2. Knuth, D.E.: The Art of Computer Programming. Addison Wesley Longman 1998.
3. Koblitz, N.: Introduction to Number Theory and Cryptography.
Springer-Verlag New York 1987.
4. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications.
Cambridge University Press 1994.
5. Lidl, R., Pilz, G.: Applied Abstract Algebra. 2nd edition.
Springer-Verlag New York 1998.
6. Marcus, A.: Algebra. Notes (in Hungarian) available at http://math.ubbcluj.ro/~marcus.
7. van Lint, J.H.: Introduction to Coding Theory. Springer-Verlag New York 1992.
8. The GAP Group: GAP -- Groups, Algorithms, and Programming. Version 4.4.3.
http://www.gap-system.org
9. Wicker S., Kim S.: Fundamentals of codes, graphs and iterative decoding
Kluwer, 2002
Evaluare
Teme de casa (50%). Examen. (50%)
Legaturi: Syllabus-urile tuturor disciplinelor
Versiunea in limba engleza a acestei discipline
Versiunea in format rtf a acestei discipline