Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
FISA DISCIPLINEI
| MML1012 | Teoria codurilor |
| Titularii de disciplina |
Prof. Dr. MARCUS Andrei, marcus math.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 |