Algoritmuselmélet

előadás

 

2014 őszi félév

 

Időpont: csütörtök 12:00-13:30

Hely:  Vályi  terem

Előadó: Zádori László

Vizsga: írásbeli az előadás anyagából

Érdemjegy: 50% gyakorlat+50% vizsga alapon

 

Tematika:

Titkosírások:

nyilvános kulcsú titkosírások, RSA, a diszkrét logaritmus és alkalmazásai, Silver-Pohlig-Hellmann algoritmus, prímtesztek, Miller-Rabin tétel, AKS-tétel

 

Gröbner-bázisok:

Hilbert bázistétele, Galois-kapcsolat, radikálideálok, varietások, Hilbert Nullstellensatz, redukciós eljárás, ideálok Gröbner-bázisai, Buchberger-algoritmus, minimális és redukált Gröbner-bázisok

 

Gröbner-bázisok alkalmazásai:

algebrailag zárt test feletti egyenletrendszerek megoldhatósága, véges varietások meghatározása, minimálpolinom keresés, gráfszínezési problémák

 

 

Irodalom:

W. W. Adams: An introduction to Gröbner bases

Cormen, Leiserson, Rivest: Algoritmusok, Műszaki Könyvkiadó, Budapest, 1997.

Czédli Gábor: Boole-függvények, Polygon, Szeged, 1995.

N. Koblitz: A course in number theory and cryptography

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok,Typotex, Budapest, 2002.