Obvestila
Sestajamo se vsak četrtek od 16:15 do 18:00
Vodja seminarja: Aleksandar Jurišić
|
Šolsko leto 2005/2006 (2. semester)
|
Teorija kodiranja je matematična veja, ki se ukvarja s prenosom
(ali hranjenjem) podatkov preko nezanesljivega kanala, ki na koncu
povrne originalno sporočilo. Bistvo je torej v tem, da si olajšamo
branje: ne mešajte te teorije s kriptografijo, ki želi
otežiti branje sporočil.
Različna področja sodelujejo pri premagovanju teh težav: tehnične
vede kot so elektrotehnika in elektronika, računalništvo in matematika.
____ Namen tega seminarja je splošen uvod
v kriptografijo in teorijo kodiranja ter osvetlitev njenih pomembnejših
raziskovalnih dosežkov v zadnjih dvajsetih letih.
Mnogi, ki Vas zanima kriptografija, prihajate
z drugih področij, bodisi z elektrotehnike, računalništva ali matematike.
Celo tistim, ki imajo za seboj formalno šolo kriptografije, primankuje
trdnih osnov.
Aleksandar Jurisic, ajurisic@valjhun.fmf.uni-lj.si, mar. 2006.
Sprva so se ljudje trudili narediti računalnike in pomnilnike,
kateri bodo naredili oziroma vsebovali kar se da manj napak. Seveda so
bile zato cene takih izdelkov vedno višje. Potem pa so se nekega dne
domislil, da bi raje naučili računalnike iskati in odpravljati napake.
Tako je postala proizvodnja veliko bolj učinkovita in cenejša.
Pravzaprav smo dolgo časa uporabljali ``parity-check'' bite
(kot npr. pri številki čeka), ki so služili za kontrolo ali je morda
prišlo do napake, šele nato je Hamming nekega dne pomislil:
``če zna računalnik sam odkriti napako, potem jo bo moral znati sam
tudi odpraviti.''
Od kar so računalniki začeli prevzemati večino dela na
področju obdelovanja informaciji in telekomunikacij in
od kar jih ljudje uporabljajo, jih zanima, kaj se da narediti v
primeru, če mašina naredi napako?
V pričetku so računalniki in programi, ki jih izvajajo, bili dovolj
enostavni, da so tehnične napake (ponavadi je odpovedala vakumska
žarnica) postale hitro očitne. Toda z razvojem hardwara
(strojne opreme) so postali programi vse bolj zapleteni, s tem pa je
postalo upanje, da odkrijemo mikroskopske napake, ki spremenijo
delovanje naprave, zanemarljivo in s tem resna skrb.
Elektronska vezja postajajo iz dneva v dan bolj minjaturna,
računalniki pa vse hitrejši in tako je možnost, da se nam
izmuzne kakšna napaka vse večja.
Tudi če je ta možnost ena sama milijardinka, se bo računalnik s
2 GigaHetzi (tj. hitrost PC-ja), ki je
prav dolgočasno počasen glede na standarde super-računalnikov
(kot so Cray), zmotil 2-krat na sekundo.
Kaj lahko naredimo?
Odgovor, ki so ga raziskovalci našli, se nahaja v kodah za
odpravljanje napak.
Matematična teorija teh kod, ki se je razvila v
zadnjih 50-ih letih, je omogočila računalnikarjem in inžinjerjem,
da sestavijo sisteme, ki so maksimalno zanesljivi (at the very edge of
their physical capabilities).
Tehnologija kod za popravljanje napak je danes tako razširjena kot
zgoščenke; le-ta nam omogoča, da poslušamo priljubljen Mozartov ali
Madonnin CD brez kakršnih koli motenj, četudi nam je mačka spraskala
CD.
Isto tehnologijo uporabljajo tudi (deep-space probes) vesoljske ladje,
in tako omogočijo, da na zemljo pridejo kristalno jasni posnetki
oddaljenih planetov, pri tem pa porabijo manj energije kot hladilnikova
žarnica.
Matematično ozadje teorije kodiranja in kriptografije predstavlja
predvsem algebraična kombinatorika (vključno s teorijo števil),
ki se uporablja še na enem pomembne področju:
v teoriji statističnega designa.
Le-ta išče optimalne množice vzorcev in se uporablja na primer
za design digitalnih komunikacij.
Naš cilj je razširiti osnovni nivo znanja kriptografije in
teorije kodiranja ter se poglobiti v algebraično kombinatoriko.
Prepričan sem, da se znanje pridobi z intenzivnim skupinskim
študijem (kjer ima vsak posameznik priložnost
testirati svoje predloge in vprašanja) ter najbolje utrdi z reševanjem
večjega števila nalog. Zato na seminarju ne boste samo izmenično predavali,
temveč boste tudi predstavljali izbrane rešitve domačih nalog.
Število obiskovalcev: (z uporabo K2
števca.)