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

Codul	Disciplina	
MML1012	Teoria codurilor	

Specializarea	Sem.	Ore: C+S+L	Categoria	Statutul	
Matematică Computaţională - în limba maghiară	1	2+1+0	specialitate	obligatorie	
Optimizarea modelelor informatice - în limba magh.	1	2+1+0	specialitate	obligatorie	

Titularii de disciplină	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.
	
Conţinutul	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%)