Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu română
Limba de predare: Română

SYLLABUS

I. Date generale
Codul	Disciplina	
MML0007	Algebră computaţională	

Semestrul	Ore: C+S+L	Categoria	Statutul	
4	2+2+0	specialitate	opţională	

II. Cadre didactice cu norma de bază în Universitate
Numele şi	Titlul	Gradul	Catedra	Tipul activităţii	
prenumele	ştiinţific	didactic		C	S	L	
SACAREA Christian	Dr.	Lect.	Algebră	*			

Cadre didactice asociate
Numele şi	Titlul	Instituţia	Tipul	Tipul activităţii	
prenumele	ştiinţific		postului	C	S	L	

III. Obiectivele disciplinei
O introducere in algebra computationala, prin prezentarea aplicatiilor algoritmilor algebrici in criptografie, teoria codurilor si procesarea conceptuala a informatiei.

•	Prezentarea metodelor şi aplicaţiilor algebrei superioare în criptografie, teoria codurilor şi procesarea conceptuală a informaţiei
•	Cunoaşterea algoritmilor  de generare şi testare de numere prime
•	Prezentarea şi utilizarea metodelor de factorizare
•	Schimb de chei Diffie-Hellman, determinarea logaritmilor discreţi
•	Prezentarea şi familiarizarea cu noţiuni şi algoritmi de teoria codurilor
•	Aplicaţii ale metodelor de procesare conceptuală a informaţiei.

	

IV. Conţinutul disciplinei
1. Notiuni de complexitatea algoritmilor. Notatia O, clase de complexitate.
2. Congruente si clase de resturi. Algoritmul lui Euclid, functia lui Euler, teorema chineza a restului, protocoale de criptare cu cheie publica: RSA, ElGamal. Semnaturi electronice. Algoritmi fundamentali. 
3. Teste de primalitate. Resturi patratice, simbolul lui Legendre si Jacobi.
4. Sisteme de codare si decodare. Coduri liniare, coduri ciclice, coduri Reed-Muller. Algoritmi de factorizare a polinoamelor si aplicatii in constructia decodoarelor.
5. Metode de procesare conceptuala a informatiei, investigarea rationala a bazelor de date, aplicatii in economie. Algoritmi de trasare grafica. Navigarea conceptuala in baze de date.	

V. Bibliografie
1.	S. Crivei, A. Mărcuş, C. Săcărea, C. Szanto, Computational Algebra with applications to cryptography and coding theory, Efes 2006.
2.	W. Bosma, A. van der Porten, Computational Algebra and Number Theory, Kluwer 1995. 
3.	D. Bressoud, S. Wagon, A Course in Computational Number Theory, Springer-Verlag 2000. 
4.	H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 2000.
5.	H. Cohen, A.M. Cuypers, H. Sterk, Some Tapas of Computer Algebra, Springer-Verlag,  1999. 
6.	R. Crandall, C. Pomerance, Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.
7.	K. Ireland, M. Rosen, A Classical Introduction to Number Theory, Springer-Verlag, 1990.
8.	N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, 1994.
9.	R. Lidl, G. Pilz, Applied Abstract Algebra, Springer-Verlag, 1998.
10.	H.S. Wilf, Algorithmes et complexite, Masson, Paris, 1989.
11.	B. Ganter, R. Wille, Formal Concept Analysis, Springer 2000.	

VI. Tematica activităţilor didactice pe săptămâni
1.	Introducere în Algebra Computaţională (1 curs + 1 seminar)
•	Ce este Algebra Computaţională?
•	Domenii de aplicabilitate: Grafică, Optimizare, Criptografie, Teoria Codurilor
•	Introducere în Criptografie. Cifrul monoalfabetic de substituţie.

2.	De la criptografia clasică la criptografia cu cheie publică (1 curs + 1 seminar)
•	Cifruri polialfabetice
•	Maşina ENIGMA
•	Probleme ce apar la utilizarea maşinilor de criptare
•	Schimbul de chei
•	Schema Diffie – Hellman
•	Problema logaritmilor discreţi

3.	De la criptografia cu cheie publică la complexitatea algoritmilor (1 curs + 1 seminar)
•	Criptografia cu cheie publică
•	Funcţii de sens unic. Probleme computaţionale
•	RSA
•	Securitatea algoritmului RSA
•	Exemple

4.	Complexitatea algoritmilor (1 curs + 1 seminar)
•	Aspecte computaţionale
•	Complexitatea calculului
•	Eficienţa algoritmilor
•	Exemple: fractali
•	Timpi de rulare. Exemple
•	Notaţia O
•	Clase de complexitate.

•	Numere prime  (1 curs + 1 seminar)
•	Numere prime.
•	Mistere ale numerelor prime
•	Determinarea numerelor prime
•	Distribuţia numerelor prime
•	Numere Mersenne
•	Teste de primalitate: ciurul lui Eratostene, ciurul lui Atkins

     6.  Teste de primalitate (1 curs + 1 seminar)
•	Numere Fermat probabil prime
•	Testul de primalitate Fermat
•	Numerele Carmichael
•	Numere Euler pseudoprime
•	Numere Euler Jacobi pseudoprime
•	Testul Solovay-Strassen

7.	Teste de primalitate (1 curs + 1 seminar)
•	Testul Miller-Rabin
•	Pseudoprime tari
•	Testul Lucas-Lehmer
•	Testul Agraval-Kayal-Saxena-Lenstra

8.	Descompunerea în factori (1 curs + 1 seminar)
•	Atacuri împotriva cifrului RSA
•	Evoluţia tehnicilor de factorizare
•	Metoda Pollard rho
•	Metoda Pollard p-1
•	Metoda p+1 a lui Williams
•	Metoda lui Fermat

9.	Metode de factorizare (1 curs + 1 seminar)
•	Metoda bazei
•	Metoda fracţiilor continue
•	Metoda filtrului pătratic

10.	Determinarea logaritmilor discreţi (1 curs + 1 seminar)
•	Schimbul de chei Diffie-Hellman
•	Algoritmul ElGamal
•	Problema logaritmilor discreţi
•	Baby step-giant step algorithm

11.	Teoria codurilor (2 cursuri + 2 seminarii)
•	Exemple
•	Coduri liniare
•	Coduri ciclice
•	Cod dual
•	Coduri Reed-Muller
•	Factorizarea polinoamelor 

12.	Procesarea conceptuală a informaţiei (2 cursuri + 2 seminarii)
•	Ierarhii de concepte
•	Reprezentări cognitive
•	Reprezentare grafică a ierarhiilor conceptuale
•	Analiza Conceptuală Formală
•	Algoritmi de determinare a conceptelor, baze implicaţionale
•	Explorare atribuţională

VII. Metode didactice folosite
Expunere, prezentare, proiecte, exerciţii, studiu individual 	

VIII. Evaluare
Către finalul semestrului, studenţii vor primi câte un proiect care constă din implementarea practică a unor algoritmi prezentaţi la curs, precum şi din rezolvarea unei probleme concrete din domeniul Algebrei Computaţionale. Nota finală la această disciplină este nota pe proiectul de semestru.	

IX. Bibliografie suplimentară
1.	A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.
2.	B. Schneier, Applied Cryptography, John Wiley & Sons, New York, 1996.	

	Data,							Titular curs,
26 aprilie 2007					Lect. Dr. SACAREA Christian