Boole-függvények (MSc 2008-2016)

Tanszék: Algebra és Számelmélet Tanszék

Tematika:
Hálók, disztributív és moduláris hálók, Boole-algebrák, Boole-gyűrűk. Zsegalkin-polinomok. Diszjunktív normálformák, prímimplikánsok. Boole-függvények minimalizálása (Quine--McCluskey-algoritmus, prímimplikáns-táblázat). Klónok és relációk kapcsolata. Post és Rosenberg teljességi tételei, s ezek egyszerű következményei. Kapcsoló-áramkörök és Boole-függvények klónjai. A generált klón meghatározása adott Boole-függvények esetén, s egy további Boole-függvény kifejezhetőségének kérdése. Szabad monoidok. Szilárd--Kraft--McMillan-féle egyenlőtlenség és "megfordítása". (Tömörítő) kódolás fogalma, blokkhalmazának jellemzése. Optimális kódolás, Huffman-tétel. Huffman-módszer optimális kódolás keresésére. Egyéb közkedvelt tömörítő algoritmusok (LZW).

Előfeltétel: